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


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.

  • $\begingroup$ 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. $\endgroup$ – Francesco Turco Sep 25 '10 at 17:53
  • $\begingroup$ @Muad: I don't see how your successor set works. In your definition does $0\in x+1$? $\endgroup$ – alext87 Sep 25 '10 at 21:31
  • $\begingroup$ @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. $\endgroup$ – Andy Sep 27 '10 at 13:31
  • $\begingroup$ @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. $\endgroup$ – Francesco Turco Sep 27 '10 at 16:13
  • $\begingroup$ @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. $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – Francesco Turco Sep 26 '10 at 9:23
  • $\begingroup$ 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. $\endgroup$ – mweerden Sep 26 '10 at 9:44

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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