I am learning the ZF (C) set theory considering all the 6 standard axioms, here is how I defined the set of natural integers $\mathbb{N}$. Is it correct and how do I prove the Lemma 2 ?

Axiom of Infinity : There exist a set ($A$) s.t

($\emptyset \in A ) \wedge (\forall X \in A, X\cup \left\lbrace X\right\rbrace \in A)$

Lemma there exist a (unique) set $\mathbb{N}$ that satisfies the axiom and such that $\mathbb{N} \subset A$

Proof :

Let $\mathcal{B}$ the power set of all subsets B of $A$ which have the above property (exists, power set axiom), $\mathbb{N}=\bigcap_{B \in \mathcal B} B,$ then $\forall P \in B, P \, \cap A $ also has this property (ie. $P \, \cap A \in \mathcal{B}$). Thus, by definition $\mathbb{N} \subset P \, \cap A$. Whence $ \mathbb{N} \subset P$. (this also proves the uniqueness)

Lemma 2 : $\forall n \in \mathbb{N}^* \exists m \in \mathbb{N}^*, n=m\cup \left\lbrace m\right\rbrace$

This one I can't find a proof by myself

Can you help me ?



You're definitely thinking along the right lines, but I'm a bit puzzled by your 'definition' of $\mathbb{N}$, since $\mathbb{N}$ appears in the condition defining itself. (In fact, all sets $A$ satisfying the axiom of infinity should satisfy $\mathbb{N} \subseteq A$.) It's also not clear what kind of uniqueness you're trying to prove—$\mathbb{N}$ is the unique set such that... what?

Here's what I'd do.

  • We start off doing what you did: fix a set $A$ satisfying the axiom of infinity, let $\mathcal{B}$ be the set of subsets of $A$ which satisfy the axiom of infinity, and define $\mathbb{N} = \bigcap \mathcal{B}$.
  • Next, prove that $\mathbb{N}$ satisfies the axiom of infinity. To see that $\varnothing \in \mathbb{N}$, note that $\varnothing \in B$ for each $B \in \mathcal{B}$; and given $X \in \mathbb{N}$, you have for each $B \in \mathcal{B}$ that $X \in B$, and hence $X \cup \{ X \} \in B$. Piecing this together tells you that $\mathbb{N}$ satisfies the axiom of infinity.
  • You might now want to prove that $\mathbb{N}$ is the unique set such that $\mathbb{N} \subseteq C$ for all sets $C$ satisfying the axiom of infinity. (You know this when $C \subseteq A$.) Proving that $\mathbb{N} \subseteq C$ for each $C$ satisfying the axiom of infinity goes just like the previous step; proving that $\mathbb{N}$ is the unique such is easy (let $\mathbb{N}'$ be another such set, and note that $\mathbb{N} \subseteq \mathbb{N}'$ and $\mathbb{N}' \subseteq \mathbb{N}$ by the condition we just proved).

Something is also awry with your 'Lemma 2'. I don't know what $\mathbb{N}^*$ means, and in any case the expression $\exists m \in \mathbb{N},~ n = m \cup \{ m \}$ is only true when $n \ne \varnothing$. So instead let's prove $$\forall n \in \mathbb{N} \setminus \{ \varnothing \},~ \exists m \in \mathbb{N}, ~ n = m \cup \{ m \}$$ Proceed by contradiction, and suppose there is some $\varnothing \ne n \in \mathbb{N}$ which is not of the form $m \cup \{ m \}$. Now define $\mathbb{N}' = \mathbb{N} \setminus \{ n \}$. You will see that $\mathbb{N}'$ satisfies the axiom of infinity. You can deduce a contradiction from this, using the facts we already proved earlier.

  • $\begingroup$ N* means N without the empty set $\endgroup$ Sep 7 '18 at 19:13
  • $\begingroup$ @T.D. In that case the '$\exists m \in \mathbb{N}^*$' part of the formula in your Lemma 2 should be replaced by '$\exists m \in \mathbb{N}$'. $\endgroup$ Sep 7 '18 at 19:15
  • $\begingroup$ This theory considers that 0 is an integer (the empty set is noted 0) $\endgroup$ Sep 8 '18 at 9:12
  • $\begingroup$ Yes, but $\forall n \in \mathbb{N}^*,~\exists m \in \mathbb{N}^*,~n = m \cup \{ m \}$ is false since $1 = \{ \varnothing \} \ne m \cup \{ m \}$ for any $m \in \mathbb{N}^*$. But $1 = \varnothing \cup \{ \varnothing \}$, so you have to include $0=\varnothing$ in the second set. This corresponds with the Peano axiom saying 'every nonzero natural number is the successor of some natural number' (not 'successor of some nonzero natural number'). $\endgroup$ Sep 8 '18 at 13:39

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.