Integer induction without infinity

136 Views Asked by At

In ZFC minus infinity (let us call this T), one can still define ordinals, and then define integers as ordinals all of whose members are zero or successor ordinals.

I am looking for a formula $\psi$ such that

  • T proves $\psi(0)$

  • T proves $\psi(n)\Rightarrow \psi(n+1)$ for every "integer" (in the above sense ) $n$,

  • T does not prove the (obviously true) $\forall \ \text{integer}\ n, \psi(n)$.

This would be a typical situation of $\omega$-incompleteness. This is probably well-known, but I cannot remember where it is explained.

1

There are 1 best solutions below

6
On BEST ANSWER

Suppose that $\psi$ is such formula, and let $(M,E)$ be a model of $T$ in which $\forall n(n\text{ is an integer}\rightarrow\psi(n))$ is false.

Consider $A=\{k\mid M\models\lnot\psi(k)\land k\text{ is an integer}\}$, then this class cannot have an $E$-minimal element. If $M\models k=\min A$, then of course $k\neq 0$, since $T\vdash\varphi(0)$, so $k=n+1$, but $M\models\psi(n)\land(\psi(n)\rightarrow\psi(n+1))$, so $M\models\psi(k)$.

Therefore $A$ is a class without a least element. This is a contradiction, since if $M\models k\in A$, then $M\models k\cap A\text{ is a set linearly ordered by }E\text{ and without a least element}$, which is a contradiction to the fact that $M$ satisfies the axiom of foundation.


Note that the assumption that $T\vdash\psi(0)\land\forall k(k\text{ is an integer}\land\psi(k)\rightarrow\psi(k+1))$ was necessary here.

On the other hand, if you only require that $T$ proves this for meta-integers, then something like $n$ encodes a proof for contradiction from $T$ is an example for a statement like that.