Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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\}$.

share|cite|improve this question

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.

share|cite|improve this answer
Thank you for your answer. I edited my question and pointed out how the authors of my book define the successor of a set. It's a different definition than yours and I can't apply your proof in my case. I can't judge which definition is better because I'm not very knowledgeable yet. – Francesco Turco Sep 25 '10 at 17:53
@Muad: I don't see how your successor set works. In your definition does $0\in x+1$? – alext87 Sep 25 '10 at 21:31
@Francesco: in your edited question you say that $x+1$ is $x \cup \{ x \}$, which is exactly what muad said and is the usual definition of natural number. – Andy Sep 27 '10 at 13:31
@Andy: I don't think they are the same. For example, consider $x=\emptyset$. According to my definition $x+1=\{\emptyset\}$; it just contains one element. According to his definition $x+1=\{\emptyset,\{\emptyset\}\}$; it contains two elements. – Francesco Turco Sep 27 '10 at 16:13
@Francesco: (I can't see through your LaTeX, but I'll interpret) it's just a question of notation, the empty set is contained in every set, we just don't always show that. So, if $0 = \{ \emptyset \}$ then $1 = \{ \emptyset, \{ \emptyset \} \}$, which you can show as only $1 = \{ \{\emptyset\} \}$ in virtue of the observation above. – Andy Sep 27 '10 at 16:49

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$.

share|cite|improve this answer
Sorry, but I can't understand your suggestion. I noticed you introduced another variable besides x. Are you considering double induction perhaps? Can you elaborate a bit further, please? Thank you. – Francesco Turco Sep 26 '10 at 9:23
What I'm saying is that proving $\forall_y(x\le y\Rightarrow y\not\in x)$ instead of $x\not\in x$ might work. So it's still one induction, but you are proving more than just $x\not\in x$ such that the induction hypothesis also gives you more that you can use. – mweerden Sep 26 '10 at 9:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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