I'm studying the axioms of Zermelo-Frankel Set Theory at the moment. I already know the following six axioms:

  • The axiom of empty set
  • The axiom of extensionality
  • The axiom of pairing
  • The axiom of infinity
  • The axiom schema of separation
  • The axiom of power set

In the lecture we wanted to construct a model of peano arithmetic on $\omega$ just using the above axioms. We started as follows (the language of Peano Arithmetic is $\mathcal{L}_{PA}=\{0,s,+,\cdot\}$):

$$0^\mathbb{N}:=\emptyset$$ $$s^\mathbb{N}:=\{\langle n,m \rangle\in \omega\times \omega\mid m=n \cup \{n\}\} $$ $$+^\mathbb{N}:=\bigcup\{a\in\mathcal{P}((\omega\times\omega)\times\omega)\mid\varphi(a)\}, $$ where $$\varphi(a)\equiv \forall x\in \omega (\langle \langle x,\emptyset\rangle,x\rangle\in a) \land \forall x\forall y\forall z\forall z'(\langle \langle x,y\rangle,z\rangle\in a\land \langle \langle x,y\rangle,z'\rangle\in a \rightarrow z=z')$$

Why does the following hold? $$\forall x\forall y(x+^\mathbb{N}s^\mathbb{N}(y)=s^\mathbb{N}(x+^\mathbb{N}y))$$

Is the definition of $+^\mathbb{N}$ correct? Because even in "simple" cases like $y=\emptyset$ and $x\in\omega$ I don't know what $x+^\mathbb{N}y$ is.

Edit: I thought about my question again and I agree that there's something wrong with the definition of $+^\mathbb{N}$. Here are my thoughts:

Lets define $$+^\mathbb{N}:=\bigcap\{a\in\mathcal{P}((\omega\times\omega)\times\omega)\mid\varphi(a)\}, $$ where $$\varphi(a)\equiv \forall x\in \omega (\langle \langle x,\emptyset\rangle,x\rangle\in a) \land \forall x\forall y\forall z\forall z'(\langle \langle x,y\rangle,z\rangle\in a\land \langle \langle x,y\rangle,z'\rangle\in a \rightarrow z=z')\land \forall x\forall y\forall z (\langle\langle x,y\rangle,z\rangle \in a \rightarrow \langle\langle x, s^\mathbb{N}(y)\rangle, z\cup \{z\}\rangle \in a)$$

Now I want to prove that $+^\mathbb{N}$ is functional. Therefore let $x,y\in \omega$. If $y=\emptyset$ then $\langle\langle x,y\rangle,x\rangle\in +^\mathbb{N}.$ So assume now that $y\neq \emptyset.$ But then by definition of $\omega$, $y$ is a successor ordinal. So $y=k\cup \{k\}$. If there is a $z_1\in \omega$ such that $\langle\langle x,k\rangle,z_1\rangle\in a$, then $\langle\langle x,y\rangle,z_1\cup \{z_1\}\rangle\in a.$ But if $k\neq \emptyset$, $k$ is again a successor ordinal, etc... We can do that until we get to the empty set. (I'm really not sure about that. I'm still a little bit confused by the definition of the natural numbers.) Uniqueness of the sum of two numbers $x,y\in \omega$ is clear by the condition

$$ \forall x\forall y\forall z\forall z'(\langle \langle x,y\rangle,z\rangle\in a\land \langle \langle x,y\rangle,z'\rangle\in a \rightarrow z=z').$$

  • $\begingroup$ Something is definitely wrong: $\varphi(a)$ just says that $a$ is a binary operation on $\omega$ with $0$ as a right identity, so $+^{\Bbb N}$ as defined here isn’t even a function. Are you sure that you’ve given the full definition of $\varphi$? $\endgroup$ – Brian M. Scott Mar 7 '15 at 22:59
  • $\begingroup$ I would really like to know why there are two votes to close this perfectly good question. $\endgroup$ – Brian M. Scott Mar 7 '15 at 22:59
  • $\begingroup$ Thank you for your answer. I gave the definition of $+^\mathbb{N}$ as we wrote it down in the lecture. But I agree that there is something wrong. I thought about my question again. Please see my edited question. $\endgroup$ – Rungo Mar 8 '15 at 9:12

The revised $\varphi$ looks good: $\varphi(x)$ now specifies that $x$ satisfies the minimum requirements to be what we want, and intersecting all such sets ought to cut out all of the extraneous elements. However, your argument that $+^{\Bbb N}$ is functional definitely needs work.

Fix $x\in\omega$. Let

$$B_x=\left\{y\in\omega:\exists u,v\in\omega\left(u\ne v\land\big\langle\langle x,y\rangle,u\big\rangle,\big\langle\langle x,y\rangle,v\big\rangle\in+^{\Bbb N}\right)\right\}\;,$$

and suppose that $B_x\ne\varnothing$. Let $m=\min B_x$, and suppose first that $m=0$. Then there is an $n\in\omega$ such that $\big\langle\langle x,0\rangle,n\big\rangle\in+^{\Bbb N}$ and $n\ne x$. Let

$$a=\left(+^{\Bbb N}\right)\setminus\left\{\big\langle\langle x,0\rangle,n\big\rangle\right\}\;;$$

then $\varphi(a)$, so $+^{\Bbb N}\subseteq a\subsetneqq+^{\Bbb N}$, which is absurd. Thus, $m>0$, and therefore $m=s^{\Bbb N}(k)$ for some $k\in\omega$.

A similar argument works for this case. By the choice of $m$ there is a unique $\ell\in\omega$ such that $\big\langle\langle x,k\rangle,\ell\big\rangle\in+^{\Bbb N}$, but there is an $n\in\omega$ such that $\big\langle\langle x,m\rangle,n\big\rangle\in+^{\Bbb N}$ and $n\ne \ell\cup\{\ell\}$. We can again let

$$a=\left(+^{\Bbb N}\right)\setminus\left\{\big\langle\langle x,m\rangle,n\big\rangle\right\}\;,$$

and we get exactly the same contradiction as in the case $m=0$. It follows that $B_x=\varnothing$ and hence that for each $y\in\omega$ there is a unique $u\in\omega$ such that $\big\langle x,y\rangle,u\big\rangle\in+^{\Bbb N}$. Since $x\in\omega$ was arbitrary, we’ve shown that $+^{\Bbb N}$ is a function.

It remains to check that

$$\forall x\forall y\left(x+^\mathbb{N}s^\mathbb{N}(y)=s^\mathbb{N}\left(x+^\mathbb{N}y\right)\right)\;.$$

The idea is basically the same. Fix $x\in\omega$, and let

$$B_x=\left\{y\in\omega:x+^{\Bbb N}s^{\Bbb N}(y)\ne s^{\Bbb N}\left(x+^{\Bbb N}y\right)\right\}\;.$$

Assume that $B_x\ne\varnothing$, let $m=\min B_x$ and use the definition of $+^{\Bbb N}$ to derive a contradiction. This is very much like what I did above to show that $+^{\Bbb N}$ is a function, so I’ll give you a crack at it first; if you get stuck, leave a comment, and I’ll fill it in.

  • $\begingroup$ Thank you for your answer. It is very helpful. I think that there is a small mistake(?) It should be $a=\left(+^{\Bbb N}\right)\setminus\left\{\big\langle\langle x,m\rangle,n\big\rangle\right\}$ instead of $a=\left(+^{\Bbb N}\right)\setminus\left\{\big\langle\langle x,0\rangle,n\big\rangle\right\}$ (the second time you define a). $\endgroup$ – Rungo Mar 9 '15 at 18:39
  • $\begingroup$ @Rungo: You’re welcome. You’re right about the mistake: I did a mindless copy/paste of the earlier line and forgot to make the necessary change. Thanks for catching it. $\endgroup$ – Brian M. Scott Mar 9 '15 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.