Prove that if $n \in \omega$ then $n \notin n$

Question

Prove that if $n \in \omega$ then $n \notin n$.

I'm trying to do it by induction. Consider $S=\{n \in \omega : n \notin n\}$

• $0 \in S$: $\emptyset \notin\emptyset $

• $i\in S \Rightarrow s(i) \in S$: $i \notin i \Rightarrow \{i\} \notin \{i\}$ (if $\{i\} \in \{i\} \text{ then } i=\{i\}, \text{ therefore } i \in i$). I want show now that $\{i\} \notin\{i\} \Rightarrow s(i)=\{i\} \cup i \notin s(i)=\{i\} \cup i$. Suppose by absurdity that $\{i\} \cup i \in\{i\} \cup i$ then:

  • or $\{i\} \cup i \in \{i\} \Rightarrow \{i\}\cup i = i \text{ then } i \in i$, contradition.

  • or $\{i\} \cup i \in i$. I do not know to get in a contradition. I do not have the axim of regularity.

Answer 1

It might help to make your induction hypothesis slightly stronger. Recall that a set $z$ is called transitive if $x \in y \in z$ implies $x \in z$. Now let the induction hypothesis be "$n \not \in n$ and $n$ is transitive", or in your setting: $$ S = \{n \in \omega : n \not \in n \text{ and } n \text{ is transitive}\}. $$ You may want to try this for yourself, but if you are stuck, here is how to do it (hover your mouse to show the text):

The base case is again easy, as clearly $\emptyset \not \in \emptyset$ and $\emptyset$ is vacuously transitive. For the successor step, assume that $n \in \omega$ is transitive and $n \not \in n$. Now suppose that $n \cup \{n\} \in n \cup \{n\}$. Then there are two cases: 1. $n \cup \{n\} \in n$, this cannot happen because then $n \in n \cup \{n\} \in n$, so by transitivity $n \in n$, 2. $n \cup \{n\} \in \{n\}$, this cannot happen as your reasoned before: this would mean $n = n \cup \{n\}$, so again $n \in n$.

So clearly $n \cup \{n\} \not \in n \cup \{n\}$. Now we are left to check that $n \cup \{n\}$ is transitive. For that we let $x \in y \in n \cup \{n\}$. Then either $y \in n$, so $x \in n$ by transitivity from the induction hypothesis, or we have $y \in \{n\}$ which means $y = n$ and thus $x \in n$. In both cases we have $x \in n$, so definitely $x \in n \cup \{n\}$, and $n \cup \{n\}$ is transitive, which concludes our induction step.

Answer 2

For any ordinal number $\alpha$, we cannot have $\alpha \in \alpha$. If so, $\in_\alpha=\{\langle a,b\rangle|\, a,b\in\alpha \,\wedge \, a\in b\}$ would not be a (strict) linear order of $\alpha$, just because we would have $\langle\alpha,\alpha\rangle\in\,\in_\alpha$, contrary to the fact that $\in_\alpha$ is irreflexive.

P.S. Note that by definition, for any ordinal $\alpha$, the natual membership order relation, $\in_\alpha$, must be a well-ordering of the set $\alpha$.

Answer 3

An attenpt using the idea that if n greater that 0 belongs to itself, if must also be a member of its predecessor, and of the predecessor of its predecessor, etc., until we arrive at : n belongs to 1 = 0 u {0} , which would be contradictory as implying either that n greater than 0 is equal to 0 or that n belongs to 0 = { }.

---

Let us admit that : the list of natural numbers does not have any repetition, that is, no natural number is identical to its predecessor, nor to the predecessor of it's predecessor, and so on,

and that : if n is greater that 0

{ n, Pred(n) , Pred(Pred(n)),....1} is a finite set.

with Pred(n) denoting the predecessor of n ( in case n is greater than 0).

For example: Pred(10)= Pred ( 9 u {9} ) = 9

---

We want to prove that :

if n is a natural number, then n is not a member of itself.

that is, by contraposition

       **if n is a member of itself, then n is not a natural number.** 

---

Suppose n is a member of itself.

(1) First, n cannot be the natural number 0, since 0 = { }. Having no element, 0 cannot be a member of itself.

(2) Now suppose that n is greater than 0.

The number n has therefore a predecessor, Pred(n).

By definition, n = Pred(n) u { Pred(n) }.

Since by hypothesis, n is an element of n , it means that

                **n belongs to Pred(n) u {  Pred(n)  }**

and, consequently, that either n=Pred(n) or that n is a member of Pred(n) ( otherwiise n would not belong to the union of the 2 sets). But n cannot be Pred(n) since no natural number is identical to any of its predecessor. So n must belong to P(n).

But, by definition, Pred(n) = Pred ( Pred(n) ) u { Pred (Pred(n) ) ).

So, if n belongs to Pred(n), then either n= Pred ( Pred(n)) or n belongs to Pred (Pred (n)). But n is not equal to Pred ( Pred(n)) ( since as we said, no natural number is identical to its predecessor, nor to the predecessor of its predecessor, and so on). So n must belong to Pred (Pred (n)).

At the next stage, we would find that, by definition,

Pred ( Pred(n) = Pred( Pred( Pred (n))) u { Pred( Pred( Pred (n)))} , and that n, not being possibly equal to Pred( Pred( Pred (n), must be a member of Pred( Pred( Pred (n).

This process leads us from predecessor to predecessor. But since { n, n-1, n-2, ....1 } is a finite set, the process must find an end. In other words, necessarily, we arrive at some stage where we have to say :

     **n must belong to  1 = Pred(1) u {Pred(1)} = 0 u {0}**

that is :

      either n=0 or n belongs to 0. 

But either alternative is impossbile. Indeed, in this part of the proof, we have admitted as hypothesis that n is not equal to 0. And the alternative " n belongs to 0" is impossible by definition.

Conslusion : if n belongs to n, then n is neither the number 0 nor a natural number greater that 0, in other words, n is not a natural number.