MHB Why does the implication hold?

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    implication
AI Thread Summary
The discussion revolves around the proof that for each natural number n, it holds that n is not an element of itself (n ∉ n). The proof constructs a set X of natural numbers that do not contain themselves and shows that X is inductive, implying X equals the set of all natural numbers (ω). A key part of the proof involves demonstrating that if n' (the successor of n) were in n', it leads to contradictions regarding n being in itself. The conversation also seeks clarification on a specific logical implication related to set membership and subsets. Ultimately, the proof successfully establishes the foundational concept that no natural number can contain itself.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hi! (Smile)

I am looking at the proof of the following sentence:

For each natural number $n$ it holds that $n \notin n$.

Proof :

We define the set $X=\{ n \in \omega: n \notin n\}$.
It suffices to show that $X$ is an inductive set, because then $X=\omega$.
Obviously $\varnothing \in X$.
We suppose that $n \in X$ and we will show that $n'=n \cup \{n\} \in X$.

We suppose that $n' \in n'$. Then $n \cup \{ n \} \in n \cup \{ n \}$.
We have two cases:
  • $n \cup \{ n \} \in n$
  • $n \cup \{ n \} \in \{ n \} \rightarrow n \cup \{ n \}=n$

If $n \cup \{ n \} \in n$ then $n \cup \{ n \} \subset n \rightarrow \{ n \} \subset n \rightarrow n \in n$, contradiction since $n \in X$.

If $n \cup \{ n \}=n \rightarrow n \cup \{ n \} \subset n$ and from the proof of the previous sentence we conclude again to a contradiction.

So, $n' \notin n'$ and so $X$ is inductive, i.e. $X=\omega$.Could you explain me why $n \cup \{ n \} \subset n \rightarrow \{ n \} \subset n \rightarrow n \in n$ ? (Thinking)
 
Physics news on Phys.org
evinda said:
Could you explain me why $n \cup \{ n \} \subset n \rightarrow \{ n \} \subset n \rightarrow n \in n$ ?
For all sets $A$, $B$ and $C$ and for all $x$ it is the case that $A\cup B\subseteq C\implies B\subseteq C$ and $\{x\}\subseteq A\iff x\in A$.
 
Evgeny.Makarov said:
For all sets $A$, $B$ and $C$ and for all $x$ it is the case that $A\cup B\subseteq C\implies B\subseteq C$ and $\{x\}\subseteq A\iff x\in A$.

I understand... Thanks a lot! (Cool)
 

Similar threads

Back
Top