Proving that for all natural number $n$, $n\notin n$

Question

I'm having some trouble proving that, for all $n\in \omega$ we have that $n\notin n$. I tried the following:

Let $S=\{n\in \omega:n \notin n \}$. Obviously $0\in S$, But now I'm having trouble with the induction step. is induction the right way to do this?

---

Just so we are all on the same page, these are the definitions that we are using in my Set theory class.

• Let $k$ be a set, then we define the successor of $k$ as: $k^+ = k\cup \{k\}$

• We define the number $0$ as the empty set

• Let $X$ be a set. We say that $X$ is inductive if $0\in X \wedge \forall x(x\in X\implies x^+\in X)$

• AXIOM: There exists an inductive set

• Let $I$ be any inductive set, then we define the set of natural numbers $\omega$ as the intersection of all inductive subsets of $I$. $\omega$ is the smallest inductive set

Answer 1

I would proceed as follows (modified from the original due to your comment).

Base Case: The proposition is true for $n = 0$.

Proof: By definition, $0 = \{\}$. Now $\{\} \notin \{\}$, since by definition, the set $\{\}$ is defined by the property that it has no elements. Therefore, $0 \notin \{\}$.

Additional base case: $n^{+} \notin n$ for $n = 0$.

Proof: Similarly, by definition, $0 = \{\}$ and $0^{+} = \{\} \cup \{\{\}\}$. Now $\{\} \cup \{\{\}\} \notin \{\}$, since by definition, the set $\{\}$ is defined by the property that it has no elements. Therefore, $0^{+} \notin \{\}$.

Inductive Step (using your notation): if $n \notin n$ and $n^{+} \notin n$, then $n^{+} \notin n^{+}$.

Proof: Suppose $n^{+} \in n^{+}$. Then, by definition, $n \cup \{n\} \in n \cup \{n\}$. This means either $n \cup \{n\} \in n$ or $n \cup \{n\} \in \{n\}$. If the first is true, it violates the second inductive assumption. If the second is true, it means $n \cup \{n\} = n$, since $n$ is the only element of $\{n\}$. But if $n \cup \{n\} = n$, any element of $n \cup \{n\}$ is also in $n$ by the definition of set equality. In particular, $n \in n \cup \{n\}$, so this implies $n \in n$, violating the first inductive assumption. This proves the result by contradiction.

I think this is what you were trying to ask.