# Proving some properties of $\Bbb N$ without using recursion

I will try to prove that if $a, b, c \in \Bbb N$ and $a \in b \in c$, then $a \in c$ (the transitivity property). I will not use recursion or the replacement axiom.

Actually we can proove in the same fashion that $\in$ lineary orders $\Bbb N$, and that any subset of $\Bbb N$ has a minilal element. (Assuming, of course, you don't find a mistake in this proof.)

By ZF7 (the 7th axiom) there is an inductive set $X$ such that $\emptyset \in X$ and if $x \in X$ than $x \cup \{x\} \in X$. ZF4 and ZF5 say that for $X$ there is its power set $\mathscr P (X)$ and we can separate from the power set only those sets that are inductive: $I = \{x \in \mathscr P(X)$: $x$ is inductive: $\}$. We define $\Bbb N = \bigcap I$.

There is no "smaller" inductive set than $\Bbb N$. If we remove some element from $\Bbb N$, the resulting set is not inductive. Suppose there is $a \in \Bbb N$ and $\Bbb N / \{a\}$ is inductive. Than $\Bbb N / \{a\} \in I$, hence $a \notin \bigcap I = \Bbb N$, which is a contradiction because $a \in \Bbb N$.

(I will use the division of $\Bbb N$ discussed in the following lemma as the main instrument.)

Lemma. If $A \subset N$ and $\emptyset \in A$, than for some $a \in A$, $a\cup\{a\} \notin A$. In other words we can properly divide set $A$ into sets $X$ and $Y$, $\emptyset \in X$, $X \cap Y = \emptyset$, such that for some $x \in X$, $x \cup \{x\} \in Y$.

For if not than $A$ would be an inductive set "smaller" than $\Bbb N$ which is impossible. $\square$

Let's divide $\Bbb N$ into two sets $A$ and $B$ so that for any element $c \in B$, there are $a, b \in \Bbb N$ such that $a \in b \in c$ and $a \notin c$. $A$ contains those elements of $\Bbb N$ that are not in $B$. Let assume that $B$ is not empty.

$\emptyset$ is vacuously in $A$. Hence by Lemma there is $c \in A$ and $c \cup \{c\} \in B$. Then there are $a, b \in \Bbb N$ such that $a \in b \in c \cup \{c\}$ and $a \notin c \cup \{c\}$. There are two possibilities: $b = c$ or $b \in c$. If $b = c$ then $a \in c = b$, $a \in c \cup \{c\}$. Suppose $b \in c$, since $c \in A$ and $a \in b \in c$ than $a \in c$, hence $a \in c \cup \{c\}$. Both cases contradict the fact that $a \notin c \cup \{c\}$.

Hence the set $B$ must be empty, leading to the fact that transitivity holds for all elements of $\Bbb N$.

• What does it mean $a\in b \in c$? – Elimination Jul 22 '14 at 8:59
• @Elimination $a \in b$ and $b \in c$. – William Jul 22 '14 at 8:59
• @Elimination In the ordinal formalization of the natural numbers, $n < m$ if and only if $n \in m$. The question is more or less to connect the smallest inductive set definition with this ordinal definition. – William Jul 22 '14 at 9:02
• @Elimination, this is a set theoretic definition of numbers. $\emptyset$ is $0$ and $\{n, \{n\}\}$ is $n+1$. – Karolis Juodelė Jul 22 '14 at 9:02
• @Graduate I don't think that William wanted to object against referencing the axioms, but against referencing them by a local obscure notation. Saying Axiom of Infinity or simply INF instead of ZF7, Axiom of Power Set or simply POW instead of ZF4, Axiom Schema of Separation or simply SEP instead of ZF5 would have made a reference to the axioms as intended - and the reader would know which are meant. – Hagen von Eitzen Jul 22 '14 at 9:18

I think it's fine, but may be straightened a bit (but that's a matter of taste maybe): You let (using the Axiom Schema of Separation) $$A=\{\,c\in\mathbb N\mid \forall a,b\in\mathbb N\colon a\in b\in c\to a\in c\,\}.$$ Vacuously, $\emptyset \in A$. Assume $n\in A$. We show that $c:=n\cup \{n\}\in A$. Indeed, assume we have $a,b\in\mathbb N$ with $a\in b\in c$. Then either $b=n$ or $b\in n$. In the first case, we have $a\in b\subseteq c$. In the second case, we have $a\in b\in n$ and from $n\in A$ conclude $a\in n\subseteq c$. At any rate $a\in c$ and we conclude that $A$ is inductive and hence $\mathbb N\subseteq A$.