Kaye-Wong paper Theorem 6.5

211 Views Asked by At

In the paper On Interpretations of Arithmetic and Set Theory of Kaye and Wong they say that Theorem 6.5 (that PA can be interpreted in ZF-Inf*, that is, ZF plus every set is contained in a transitive closure and the negation of Inf) follows from Theorem 4.5 and Propositions 5.6 and 6.3. Why is that?

I think I can verify it for the semi-ring axioms ($\text{PA}^-$) without much trouble, but the induction axiom scheme becomes (right?): $$ [ \, \forall y \,(\forall x \, ( \; ( p(x) < p(y) \to \varphi^{\mathfrak{b}}(x)) \to \varphi^{\mathfrak{b}}(y)) \, ] \to \forall y \, \varphi^{\mathfrak{b}}(y) $$ where $p(x) = \sum_{y\in x} \, 2^{p(y)}$. I'm not sure how to tackle that. Epsilon induction?

And what do Theorem 4.5 and Propositions 5.6 and 6.3 have to do with it?

1

There are 1 best solutions below

7
On BEST ANSWER

I will try to sketch the detail of their article.

First, Theorem 4.5 establishes that the ordinal interpretation $\mathfrak{o}$ ensures $\mathsf{ZF-Inf}$ interprets $\mathsf{PA}$. However, the ordinal interpretation is not bijective, in the sense that $\mathsf{ZF-Inf}$ does not prove $\forall x \operatorname{Dom}^\mathfrak{o}(x)$. In the case of ordinal interpretation, $\operatorname{Dom}^\mathfrak{o}(x)$ is equivalent to that $x$ is an ordinal, but not all sets are ordinals.

On the other hand, if $\mathfrak{o}$ has an inverse interpretation $\mathfrak{t}$, then $(\operatorname{Dom}^\mathfrak{o})^\mathfrak{t}(x)$ is equivalent to $x=x$. Hence $\operatorname{Dom}^\mathfrak{o}(x)$ is equivalent to $(x=x)^\mathfrak{o}$, and in the case of ordinal interpretation, this is just $x=x$. Therefore there is no interpretation $\mathfrak{t}:\mathsf{ZF-Inf\to PA}$ such that $\mathfrak{o\circ t}$ is the identity interpretation $\mathsf{Id}_\mathsf{ZF-Inf}$.

This is the reason why Kaye and Wong introduce $\mathfrak{p}$: by composing $\mathfrak{o}$ with $\mathfrak{p}$, we can make the interpretation closer to 'bijective'. To achieve this, we have to ensure $\mathfrak{p}$ a bijective class function, and this is the role of Proposition 6.3.

Proposition 5.6 is about $\mathfrak{a}$, not $\mathfrak{b}$. However, it explains why we need to consider the existence of transitive closure as an axiom of a set-theoretic counterpart of $\mathsf{PA}$. I do not find any specific role of this proposition in the proof, but it at least gives how to motivate the statement of Theorem 6.5.

Lastly, your interpretation of the induction scheme is not correct. The correct interpretation should be $$[\forall y (\forall x (\mathfrak{p}(x)<\mathfrak{p}(y))\to \phi(\mathfrak{p}(x))\to \phi(\mathfrak{p}(y))]\to \forall y \phi(\mathfrak{p}(y)).$$

(Interpretations might be confusing. This article suppresses some details.)

Then everything is clear: since $\mathfrak{p}(x)$ is an arbitrary natural number (or finite ordinals, if you prefer), we can see that the previous statement is another way to describe the induction scheme.