Strict ordering on natural numbers 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:


*

*They prove transitivity using induction.

*They prove irreflexivity using induction and transitivity.

*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\}$.
 A: 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.
A: 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$.
A: Hint:  The theorem you want to prove as related to the 'strict' ordering of natural numbers is the following one which says that the binary predicate $\in$ is an irreflexive relation on natural numbers.
Theorem 2: No natural number is an element of itself, i.e., If $n$ is a natural number, then $n$ is not an element of $n$.  
This theorem is proved using the Principle of Mathematical Induction as K. Hrbacek as presented it.  However, in order get yourself unstuck in going about your proof, you will need to prove the following theorem as a first step.
Theorem 1:  Every element of a natural number is also a subset of that natural number.
Its proof requires the use of the Principle of Induction as well.
