MATH 557 Midterm 3 Preparation

The third midterm will again have two parts:

Reproduce a proof (in sufficient detail) of one the theorems below we covered in class.
Present a proof to one of the exercises (or a closely related problem) listed on this page.

Notations, Axioms

In the following, $\mathcal{L}_A = \{0,1,+,\cdot, <\}$ denotes the language of $\mathsf{PA}^-$.

The axioms of $\mathsf{PA}^-$ are:

A1: $\quad (x +y)+z= x + (y+z)$
A2: $\quad (x \cdot y) \cdot z= x \cdot (y \cdot z)$
A3: $\quad x + y= y + x$
A4: $\quad x \cdot y = y \cdot x$
A5: $\quad x \cdot (y+z) = x \cdot y + x \cdot z$
A6: $\quad x+0=x \wedge x \cdot 0 = 0$
A7: $\quad x \cdot 1 = x$
A8: $\quad \neg \; x < x$
A9: $\quad x < y \wedge y < z \to x < z$
A10: $\quad x < y \vee x = y \vee y < x$
A11: $\quad x < y \to x+z < y+z$
A12: $\quad 0 < z \wedge x < y \to x \cdot z < y \cdot z$
A13: $\quad x < y \to \exists z \; (x+z = y)$
A14: $\quad 0<1 \wedge \forall x \; (0 < x \to 1 \le x)$
A15: $\quad \forall x \; (0 \le x)$

If we add the induction scheme

Ind: $\quad ( \varphi(0,\vec{y}) \, \wedge \, \forall x (\varphi(x,\vec{y}) \to \varphi(x+1,\vec{y})) \to \forall x \; \varphi(x,\vec{y})$

we obtain (a theory equivalent to) full $\mathsf{PA}$.

Theorems

Theorem 1

For every $\Delta_0$-formula $\theta(\vec{v})$, the relation \[ R(\vec{a}) :\iff \mathbb{N} \models \theta(\vec{a}) \] is primitive recursive.

Theorem 2

Let $\mathcal{N}, \mathcal{M}$ be $\mathcal{L}_A$-structures with $\mathcal{N} \subseteq_{end} \mathcal{M}$, and let $\vec{a} \in N$. Then for every $\Delta_0$-formula $\varphi(\vec{v})$,

\[ \mathcal{N}\models \varphi[\vec{a}] \iff \mathcal{M}\models \varphi[\vec{a}], \]

Theorem 3

If $f:\mathbb{N} \to \mathbb{N}$ is recursive, then there exists a $\Sigma_1$-formula $\theta(x,y)$ such that for all $m,n \in \mathbb{N}$,

\[ f(n) = m \quad \Rightarrow \quad \mathsf{PA}^- \vdash \theta(\underline{n}, \underline{m}) \]

(This is one part of the Representability Theorem.)

Theorem 4

Let $T$ be a recursive set of (Gödel numbers of) $\mathcal{L}_A$-sentences such that:

$T$ is consistent, i.e., there is no $L$-sentence $\sigma$ with $\ulcorner \sigma \urcorner \in T$ and at the same time $\ulcorner \neg \sigma \urcorner \in T$,
$T$ contains the deductive closure of $\mathsf{PA}^-$, $\ulcorner (\mathsf{PA}^-)^\vdash \urcorner \subseteq T$.

Then $T$ is incomplete, i.e., there exists a sentence $\tau$ with

\[ \ulcorner \tau \urcorner \not \in T \text{ and } \ulcorner \neg \tau \urcorner \not \in T. \]

(You can use the Representability Theorem as well as the Diagonal Lemma.)

Theorem 5

If $T$ is a consistent theory in the language $\mathcal{L}_A$, then not both the diagonal function $d$ and the set $\ulcorner T^\vdash \urcorner$ are representable in $T$.

Problems

Problem 1

Show that the functions \[ \operatorname{rem}(x,y) = \text{remainder when $y$ is divided by $x$} \] (put $\operatorname{rem}(0,y) = y$ to make it total) and \[ \operatorname{qt}(x,y) = \text{quotient when $y$ is divided by $x$} \] (put $\operatorname{qt}(0,y) = 0$) are primitive recursive.

In other words, show that the uniquely determined functions (for $x \geq 1$) satisfying \[ y = \operatorname{qt}(x,y) \cdot x + \operatorname{rem}(x,y) \qquad 0 \leq \operatorname{rem}(x,y) < x \] are primitive recursive.

You can use that the functions $x+y$, $x\cdot y$, $\max(x,y)$, $\min(x,y)$, $|x-y|$, $x \dot{-} y$, $\operatorname{sg}(x)$, $\overline{\operatorname{sg}}(x)$ are primitive recursive.

Problem 2

Show that for all $k \in \mathbb{N}$,

\[ \mathsf{PA}^- \vdash \forall x \:(x \le \underline{k} \to (x = \underline{0} \; \vee \ldots \vee \; x = \underline{k}) \]

(Hint: use (meta-)induction on $k$. For the inductive step, show first that

\[ \mathsf{PA}^- \vdash \forall x,y \: (y > x \to y \geq x+1) \]

Problem 3

Let $\mathcal{M} \models \mathsf{PA}$ be non-standard. A proper cut in $\mathcal{M}$ is a set $I \subsetneq M$ that is closed downward under $<$ (the order of $\mathcal{M}$) and closed under successor. For example, the (copy of the) standard model $\mathbb{N}$ in $\mathcal{M}$ is a proper cut.

Show that if $\vec{a} \in M$ and $\mathcal{M} \models \varphi(b,\vec{a})$ for all $b \in I$, then there is $c > I$ in $M$ such that $\mathcal{M} \models \forall x \leq c \: \varphi(x,\vec{a})$.
Suppose $\mathcal{M} \models \mathsf{PA}^{-}$ is non-standard and has the property that for any proper cut $I$, if $\varphi(x,y)$ is a formula and $\vec{a} \in M$ such that \[ \mathcal{M} \models \varphi(b, \vec{a}) \quad \text{for all } b \in I, \] then there is $c > I$ in $M$ such that $\mathcal{M} \models \forall x \leq c \: \varphi(x,\vec{a})$ (in other words, $\mathcal{M}$ satisfies the conclusion of 1.). Show that then $\mathcal{M} \models \mathsf{PA}$.

(Note: For (2.), it suffices to show $\mathcal{M}$ satisfies the induction scheme.)

Problem 4

Show that, for all functions $f : \mathbb{N}^k \to \mathbb{N}$ (where $k\geq 1$), if $f$ is representable in $\mathsf{PA}^-$ then $f$ is computable.

(You can argue by Church-Turing Thesis.)

Problem 5

(a) We say an $\mathcal{L}_A$-theory $T'$ is a finite extension of an $\mathcal{L}_A$-theory $T$ if $T' \supseteq T$ and $T' \setminus T$ is finite. Show that if $T$ is decidable and $T'$ is a finite extension of $T$, then $T'$ is decidable.

(b) An $\mathcal{L}_A$-structure $\mathcal{A}$ is strongly undecidable if every $\mathcal{L}_A$-theory $T$ with $\mathcal{A} \models T$ is undecidable. Show that the standard model $\mathbb{N}$ is strongly undecidable.