# 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 using1 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 only2.

### 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 &gt; 0$$ there is a $$\delta &gt; 0$$ such that $$|f(x)-f(a)| &lt; \epsilon$$ for all $$x\in D$$ with $$|x-a| &lt; \delta.$$

This proposition can be codified using a formula like this:

$\forall\epsilon\,(\epsilon &gt; 0)\,\exists\delta\,(\delta &gt; 0)\,\forall x\,(x\in D)\,(|x-a|&lt;\delta\Longrightarrow|f(x)-f(a)|&lt;\epsilon).$

In this formula, e.g. the strings $$"\epsilon &gt; 0"$$, $$"\epsilon &gt; 0"$$, or $$"|x-a|&lt;\delta\Longrightarrow|f(x)-f(a)|&lt;\epsilon"$$ are less complex formulae.

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

Github: ### References

#### Bibliography

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

#### Footnotes

1. Just like we can do with Boolean variables in propositional logic. Therefore, the first order predicate logic $$\operatorname{PL1}$$ is an extension of a propositional logic, because Boolean variables are a simple special case of more complex formulae in $$\operatorname{PL1}$$.

2. While $$\operatorname{PL1}$$ only allows to apply quantifiers to variables, it is possible to apply them also to predicates and formulae in higher order logics