Strict ordering on natural numbers

Question

I already asked this question here, but unfortunately no acceptable answers were provided. Also, I hope this is not too basic for MathOverflow.

I'm studying on K. Hrbacek and T. Jech, Introduction to Set Theory. In the third chapter, they prove the usual properties of the strict ordering on natural numbers in the following way:

1. They prove transitivity using induction.
2. They prove irreflexivity using induction and transitivity.
3. They prove asymmetry by contradiction and using transitivity and irreflexivity.

There is nothing wrong with this, but I'd like, if possible, to prove the previous properties (in particular irreflexivity and asymmetry) independently and using induction only.

For example, let $\phi(x)$ be $x\not\in x$. Of course $\phi(0)$ is true ($0\not\in 0$ since $0$ is the empty set). Now I should suppose that $\phi(x)$ is true and show that $\phi(x+1)$ is true, too. $\phi(x+1)$ stands for $x+1\not\in x+1$, that is $x+1\not\in x$ and $x+1\not=x$. But here I cannot go on, mainly because $x+1$ is at the left of the relations symbols.

$x+1$ is defined as $x\cup\{x\}$.

Any hint? Thank you.

Answer 1

With the common set-theoretic approach of defining the order in terms of $\subseteq$ or $\in$, appealing to eg transitivity/ordinality is unavoidable. But if you take a slightly different approach to the definitions, these can certainly be done with just induction and a couple of basic facts about the surrounding set theory; and the end result is in a sense more natural, not depending on the specific implementation of the numbers.

Suppose $N$ is any set, $0 \in N$, and $s: N \to N$, and $(N,0,s)$ satisfy the usual induction principle.

Then firstly, you can bump this up to the recursion principle: that you can define functions on $N$ (in particular, $\{0,1\}$-valued functions, i.e. predicates) by recursion. This is where you need to use a few things in how the surrounding theory treats functions and so on. (You could also start by saying that recursion, rather than induction, should be the basic defining principle of the natural numbers.)

Now you can define the strict ordering by recursion:

• $0 \not < 0$;
• $0 < s(n)$;
• $s(n) \not < 0$;
• $s(n) < s(m)$ iff $n < m$.

Now irreflexivity, transitivity and antisymmetry are all immediate by induction… just divide up into the appropriate cases, and the induction steps fall straight out :-)

Answer 2

$x+1\neq x$ just follows from $\phi (x)$. Now you need $x+1\not\in x$. Suppose the opposite. Then $x+1\in x$ and by ordinality $x+1\subseteq x$. But this will imply that $x\in x$, contradiction with the induction assumption.