Problem 2

As we saw in class, you can define the ${\leq}$ relation using the formula ${\varphi(x,y) \equiv \exists z ( x+z =y)}$. Furthermore, given any number ${n \in {\mathbb N}}$, we can represent it as ${\underline{n} = S(S \dots S(\underline{0}))}$, where we apply ${S}$ ${n}$-times.

Now show that ${\mathsf{PA} \models \forall x ( \underline{0} < x \; \Rightarrow \underline{1} \leq x)}$.

Problem 3

For any specific finite number ${n}$, you can find a formula that says: “There exist exactly ${n}$ distinct elements”.

Problem 4

One direction is trivial. For the other direction, use the completeness theorem. Argue that a theory ${T}$ is consistent if and only if it has a model. Then use the fact that proofs are finite, in particular can use at most finitely many formulas.

Problem 5

Extend the language of arithmetic by a new constant symbol ${\underline{c}}$. Add sentences of the form ${\underline{0} < \underline{c}}$, ${\underline{1} < \underline{c}}$, ${\underline{2} < \underline{c}}$, … to ${T_{\mathbb N}}$. Apply the compactness theorem.