Lesson 2

Several examples of statements with quantifiers:

• There are infinitely many prime numbers: \[\forall q \in \mathbb{Z}_{>0}\ \exists p \in \mathbb{Z}_{>0}\colon (p>q \land (\forall x, y \in \mathbb{Z}_{\ge 2}\colon xy \neq p)) \ .\]


• Fermat's Last Theorem: \[\forall a,b,c,n \in \mathbb{Z}_{>0}\colon (n>2 \Rightarrow a^{n}+b^{n} \neq c^{n}) \ .\]


• The twin prime conjecture: \[\forall q \in \mathbb{Z}_{>0}\ \exists p \in \mathbb{Z}_{>0}\colon (p>q \land (\forall x, y \in \mathbb{Z}_{\ge 2}\colon (xy \neq p \land xy \neq p+2))) \ .\]


• The outgoing degree of each vertex in a (directed) graph is exactly one: \[(\forall x \in V\ \exists y \in V \colon G(x,y)) \land (\forall x,y,z\in V \colon ((G(x,y) \land G(x,z)) \Rightarrow y=z)) \ .\]