Strict ordering on natural numbers

Question

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.

Any hint? Thank you.

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

Answer 1

Assuming that $0 = \{\}$ and $x + 1 = \{x,\{x\}\}$ are the definitions you use, the recursive induction step would be to prove:

$$x \notin x \Rightarrow \{x,\{x\}\} \notin \{x,\{x\}\}$$

By extensionality what we really need to show is the two cases

• $\{x,\{x\}\} \neq \{x\}$
• $\{x,\{x\}\} \neq x$

The first is immediate since one is a singleton and the other is not.

For the second part we notice that if it were true, we would have $x \in x$ but that contradicts the induction hypothesis.

Answer 2

As the induction hypothesis is clearly not strong enough, how about strengthening your proof obligation? Just adding $x+1\not\in x$ will mean you'll also need $x+2\not\in x$, so I'd suggest $y\not\in x$ for all $y$ such that $x\le y$.