◀ ▲ ▶Branches / Logic / Part: PL1 - First Order Predicate Logic

Part: PL1 - First Order Predicate Logic

A predicate logic of first order \(\operatorname{PL1}\) consists of all formulae, which obey a syntax defined recursively by:

• Each atomic formula is a formula of \(\operatorname{PL1}\).
• Let \(\phi,~\psi\) be formulae. Then we can combine them using¹ Boolean connectors to produce more complex formulae:
  • negation of \(\phi\): \((\neg \phi)\)
  • conjunction of \(\phi\) and \(\psi\): \((\phi\wedge \psi)\),
  • disjunction of \(\phi\) and \(\psi\)): \((\phi\vee \psi)\),
  • conclusion \(\psi\) follows from \(\phi\): \((\phi\Rightarrow \psi)\), and
  • equivalence of \(\phi\) and \(\psi\)): \((\phi\Leftrightarrow \psi)\).
• If \(x\) is a variable and \(\phi\) is a formula using this variable, then, using the quantifiers "\(\exists\)" and "\(\forall\)", the following expressions are also formulae:
  • \(\exists x\,(\phi)\)
  • \(\forall x\,(\phi)\)

The notion first order" in the name of \(\operatorname{PL1}\) means that quantifiers can be applied to variables only².

Example

Take real numbers as the domain of discourse, and consider the \(\epsilon-\delta\) definition of continuous real functions:

A real function \(f:D\to\mathbb R\) is continuous at the point \(a\in D\), if for every \(\epsilon > 0\) there is a \(\delta > 0\) such that \(|f(x)-f(a)| < \epsilon\) for all \(x\in D\) with \(|x-a| < \delta.\)

This proposition can be codified using a formula like this:

\[\forall\epsilon\,(\epsilon > 0)\,\exists\delta\,(\delta > 0)\,\forall x\,(x\in D)\,(|x-a|<\delta\Longrightarrow|f(x)-f(a)|<\epsilon).\]

In this formula, e.g. the strings \("\epsilon > 0"\), \("\epsilon > 0"\), or \("|x-a|<\delta\Longrightarrow|f(x)-f(a)|<\epsilon"\) are less complex formulae.

Table of Contents

1. Definition: Terms in Predicate Logic
2. Definition: Atomic Formulae in Predicate Logic
3. Chapter: Peano Arithmetic

Mentioned in:

Chapters: 1
Definitions: 2
Lemmas: 3 4
Parts: 5 6
Proofs: 7

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Hoffmann, Dirk W.: "Grenzen der Mathematik - Eine Reise durch die Kerngebiete der mathematischen Logik", Spektrum Akademischer Verlag, 2011

Footnotes