: Natural numbers in ZF<a class="btn btn-sm" href="/UUID/EDB/246/?lang=eng"><span class="ttfamily"><small class="scriptsize">[246]</small></span></a>

3.8 Natural numbers in ZF[246]

In this section we will build a model of the natural numbers inside the ZF set theory; this model satisfies Peano’s axioms 132 and has an order relation that satisfies 143, so this model enjoys all properties described in Sec. 4; for this reason in this section we will mostly discuss properties that are specific of this model.

Successor

Definition 83

[24X]Given \(x\) the successor is defined as

\begin{equation} S(x) {\stackrel{.}{=}}x ∪ \{ x\} \quad . \label{eq:successore} \end{equation}

We will often write \(Sx\) instead \(S(x)\) to ease notations.

We say that a set \(A\) is S-saturated if \(∅∈ A\) and if for every \(x∈ A\) you have \(S(x)∈ A\). ¹

E84

[24V]Note that \(z∈ S(x)\) if and only if \(z∈ x∨ z=x\);

E84

[24M]Prerequisites:13,1.Prove that \(x∈ S(x)\) and \(x\varsubsetneq S(x)\). Hidden solution: [UNACCESSIBLE UUID ’24N’]

E84

[239]Prerequisites:13,84,1.Let \(x,y\) be elements (generic, not necessarily natural numbers), such that

\begin{equation} x⊆ y⊆ S(x) \label{eq:x_ y_ Sx} \end{equation}

prove that

\[ x=y∨ y = S(x)\quad ; \]

where the above two are mutually exclusive, and (in the hypothesis ?? above) the second one holds if and only if \(x\in y\); summarizing

\[ \ref{eq:x_ y_ Sx} ⇒ (x=y\iff y ≠ S(x)\iff x∉ y )\quad . \]

Note the analogy with 2.

E84

[245]Prove that the intersection of S-saturated sets provides an S-saturated set.

E84

[1YM]Prerequisites:13,84,1. ² Prove that

\[ x=y \iff S(x) = S(y) \quad . \]

In particular this shows that, if \(A\) is an S-saturated set, then the function \(S:A→ A\) is well defined, and its graph is the relation

\[ \{ (x,y)∈ A^ 2 : y=S(x) \} \quad ; \]

moreover \(S\) is injective.

Hidden solution: [UNACCESSIBLE UUID ’1YN’]

E84

[24Q]Find an example of \(x,y\) such that \(x∈ y∧ x⊆ y\) but \(S(x)∉ S(y)\)

Hidden solution: [UNACCESSIBLE UUID ’24R’]

E84

[24S]Show that when \(x∈ y∧ x⊆ y\) then \(S(x)⊆ y\). Hidden solution: [UNACCESSIBLE UUID ’24T’]

Natural numbers in ZF

Definition 86

[243] The axiom of infinity guarantees that there is a set \(A\) that is S-saturated.

Using the axiom of infinity 86 we can prove the existence of the set of natural numbers.

Theorem 87

[244]\(ℕ\) is the smallest S-saturated set.

Proof ▼

Given a set \(A\) that is S-saturated, \(ℕ_ A\) is defined as the intersection of all S-saturated subsets of \(A\). By 4, \(ℕ_ A\) is S-saturated. Given two sets \(A,B\) that are S-saturated, it is proven that \(ℕ_ A=ℕ_ B\): we denote then by \(ℕ\) this set. In particular, given a set \(A\) that is S-saturated, we have \(ℕ\subseteq A\).

Example 88

[291]In this model, the first natural number \(0\) is identified with \(∅\). Then

\begin{align*} 1& = 0 ∪ \{ 0\} = \{ 0\} = \big\{ \{ \} \big\} ,\\ 2& = 1 ∪ \{ 1\} = \{ 0, 1\} = \Big\{ \{ \} , \big\{ \{ \} \big\} \Big\} ,\\ 3& = 2 ∪ \{ 2\} = \{ 0, 1, 2\} = \bigg\{ \{ \} , \big\{ \{ \} \big\} , \Big\{ \{ \} , \big\{ \{ \} \big\} \Big\} \bigg\} ,\\ .... \end{align*}

Remark 89

[25C]This fact holds true:

\[ ∀ y∈ℕ, y≠ ∅⇒ ∃ x∈ℕ , S(x)=y \]

this can be proven by induction, as in 131, or by proving that, if

\[ ∃ y∈ℕ, y≠ ∅∧ ∀ x∈ℕ , S(x)≠ y \]

then \(ℕ ⧵ \{ y\} \) would be an S-saturated set smaller than \(ℕ\), a contradiction. In particular by 5 we get that the successor function

\[ S:ℕ → ℕ⧵\{ 0\} \]

is bijective.

If \(n\neq 0\), we will call \(S^{-1}(n)\) the predecessor of \(n\).

We can also prove directly the induction principle.

Theorem 90 Induction Principle

[23B] Let \(A⊇ ℕ\) and \(P(n)\) be a logical proposition that can be evaluated for \(n∈ A\). Suppose the following two assumptions are satisfied:

\(P(n)\) is true for \(n=0\) and
\(∀ n∈ ℕ, P(n)⇒ P(S(n))\) ;

then \(P\) is true for every \(n∈ ℕ\).
The first hypothesis is known as ”the basis of induction” and the second as ”inductive step”

Proof ▼

Let \(U=\{ n∈ ℕ:P(n)\} \), we know that \(0∈ U\) and that \(∀ x, x ∈ U⇒ S(x)∈ U\), so \(U\) is S-saturated and \(U\subseteq N\) we conclude that \(U=\mathbb {N}\).

Theorem 91

[24D] Consider the order relation \(⊆ \) on \(ℕ\); then

\begin{equation} ∀ x,y ∈ ℕ , (x ⊆ Sy∧ x≠ Sy) \iff (x ⊆ y ) \quad . \label{eq:subseteq_ caratt_ le_ N} \end{equation}

This will be proven in Exercise 4.

To prove the above theorem, the exercises in the following section can be used.

Remark 93

[26K]Peano’s Axioms are provable in this model; moreover the order relation satisfies the requirements of Hypothesis 143; therefore this model of \(ℕ\) enjoys all properties discussed in Sec. 4: all different versions of the induction principle; \((ℕ,⊆)\) is well-ordered; definitions by recursion; arithmetic, etc.

When we will want to compare this model with other models, we will denote it by \(ℕ_\text {ZF}\).

The ordered set \(ℕ,⊆\) then enjoys these properties.

Proposition 94

[26J]This model of \(ℕ\) is a well-ordered set with the ordering

\[ n≤ m \iff n⊆ m\quad . \]

Moreover in this model we have

\begin{equation} ∀ n,m∈ ℕ, n ∈ m \iff (n ⊆ m ∧ n≠ m)\quad . \label{eq:n_ in_ m_ iff} \end{equation}

so, defining (as usual)

\[ n{\lt}m ≐ (n≤ m ∧ n≠ m) \]

we can write

\[ n∈ m \iff n{\lt}m\quad . \]

This is proven in the following exercises, see in particular 1.

More details are in the course notes (Chap. 1 Sec. 7 in [ 2 ] ); or [ 13 ] , [ 12 ] .

Transitive sets

Definition 96

[24Z] A set \(A\) is said to be transitive if these equivalent conditions hold:

\[ ∀ x, x ∈ A ⇒ x⊆ A\quad , \]

i.e. every element of \(A\) is also a subset of \(A\);
\[ ∀ x,y, x ∈y ∧ y∈ A ⇒ x∈ A\quad . \]

Example 97

[290]Examples of transitive sets are:

\begin{align*} \{ \} = 0 \\ \big\{ \{ \} \big\} = 1, \\ \Big\{ \{ \} ,\big\{ \{ \} \big\} \Big\} = 2,\\ \bigg\{ \{ \} ,\big\{ \{ \} \big\} ,\Big\{ \big\{ \{ \} \big\} \Big\} \bigg\} , \\ \Bigg\{ \{ \} ,\big\{ \{ \} \big\} ,\Big\{ \big\{ \{ \} \big\} \Big\} , \bigg\{ \Big\{ \big\{ \{ \} \big\} \Big\} \bigg\} \Bigg\} ,\\ ...\\ \bigg\{ \{ \} , \big\{ \{ \} \big\} , \Big\{ \{ \} , \big\{ \{ \} \big\} \Big\} \bigg\} =3\\ \bigg\{ \{ \} , \big\{ \{ \} \big\} , \Big\{ \big\{ \{ \} \big\} \Big\} ,\Big\{ \{ \} ,\big\{ \{ \} \big\} \Big\} \bigg\} ,\\ .... \end{align*}

Comparing with 88 note that there are transitive sets that are not natural numbers.

E97

[25J]If every element of \(A\) is a transitive set then the relation \(x ∈y\) is a transitive relation in \(A\) . (Note that this holds also if \(A\) is not a transitive set.) Hidden solution: [UNACCESSIBLE UUID ’25K’]

E97

[257]Prove that for each \(m ∈ ℕ\), \(m\) is a transitive set.

Hidden solution: [UNACCESSIBLE UUID ’258’]

E97

[26N]Prerequisites:96,7,2.

\(∀ n,k∈ℕ\) if \(n∈ k\) then \(Sn⊆ k\).

(Hint: you do not need induction, use that each \(n∈ℕ\) is a transitive set).

E97

[26P]Prerequisites:3,13.To assert the Theorem 91 we have to prove

\begin{equation} ∀ x,y ∈ ℕ , (x ⊆ Sy∧ x≠ Sy) \iff (x ⊆ y )\quad . \tag {\ref{eq:subseteq_ caratt_ le_ N}}\end{equation}

Prove that if \(X\) is a set where each element is transitive

\begin{equation} ∀ x,y ∈ X , (x ⊆ Sy∧ x≠ Sy) \iff (x ⊆ y ) \quad . \label{eq:caratt_ le_ ordinale} \end{equation}

Hidden solution: [UNACCESSIBLE UUID ’26Q’]

The previous exercises prove Theorem 91, then by results of Sec. 4 we obtain that \((ℕ,≤)\) is well ordered.

Here following are other interesting exercises.

E99

[269]We know from 93 that the relation \(n ⊆ m\) is total in \(ℕ\). Prove that

\begin{equation} ∀ n,m∈ ℕ, n ∈ m \iff (n ⊆ m ∧ n≠ m)\quad . \tag {\ref{eq:n_ in_ m_ iff}}\label{eq:n_ in_ m_ iff_ 2} \end{equation}

100

By 4 this implies

\[ ∀ n,m∈ ℕ, n ⊆ m \iff (n ∈ m \lor n= m)\quad . \]

Hidden solution: [UNACCESSIBLE UUID ’26B’]

E99

[265]Prove this assertion

\[ ∀ k∈ ℕ, k≠ ∅⇒ ∅∈ k\quad . \]

Hidden solution: [UNACCESSIBLE UUID ’266’]

E99

[25D]Prerequisites:91,94.Prove that

\[ ∀ x,y∈ ℕ~ ,~ x⊆ y~ ∧ ~ x≠ y ⇒ Sx⊆ y\quad . \]

Hidden solution: [UNACCESSIBLE UUID ’279’]

[UNACCESSIBLE UUID ’25F’]

[25W]Having fixed \(N\in ℕ\), consider the ordering \(n⊆ m\) for \(n,m\in N\). Since \(N\subseteq ℕ\) is well ordered, then Proposition 94 implies that \((N,\subseteq )\) is well ordered; nonetheless prove directly by induction that \(n⊆ m\) is a well ordering in \(N\).

Hidden solution: [UNACCESSIBLE UUID ’25X’] [25Z]Prove that

\[ \underline⋃ ℕ = ℕ\quad . \]

Hidden solution: [UNACCESSIBLE UUID ’260’]

Ordinals

Perusing the above results we can give some elements of the theory of ordinals.

Definition 101

An ordinal (according to Von Neumann) is a transitive set \(A\) such that any element in \(A\) is a transitive set.

E101

[25Q]Prerequisites:13,3.If \(A\) is a set where \(∈\) is transitive, we define

\[ x≤ y ≐ x∈ y∨ x=y \]

prove that \(x≤ y\) is a (possibly partial) order relation in \(A\).

Hidden solution: [UNACCESSIBLE UUID ’25S’]

E101

[25B]Prove that the intersection of transitive sets is a transitive set.

E101

[25N]Prove that the intersection of ordinals is an ordinal.

E101

[25M]Prove that if \(X\) is an ordinal and \(A\in X\) then \(A\) is an ordinal.

Hidden solution: [UNACCESSIBLE UUID ’25P’]

E101

[25G] Use the axiom of foundation 13 to prove that if \(A\) is transitive and \(A≠ ∅\) then \(∅∈ A\).

Hidden solution: [UNACCESSIBLE UUID ’25H’]

E101

[255]Prove that \(ℕ\) is a transitive set. (Hint: use induction.)

Hidden solution: [UNACCESSIBLE UUID ’256’]

This and 2 say that \(ℕ\) is an ordinal.

E101

[26S]Let \(X\) be an ordinal and

\[ P_ x =\{ z\in X, z\in x\} \]

show that

\[ ∀ x,y∈ X~ ,~ P_ x = P_ y ⇒ x=y\quad . \]

Hidden solution: [UNACCESSIBLE UUID ’26T’]

(Note the similarity with 2).

E101

[26V]Prerequisites:1,13,11,4,7.

Let \(X\) be an ordinal, we define

\[ x≤ y ≐ x∈ y∨ x=y \]

we know from 1 that \(x≤ y\) is a (possibly partial) order relation in \(X\). Prove that \(x≤ y\) is a well order.

Hidden solution: [UNACCESSIBLE UUID ’26W’]

Remark 102

[275]Consider again Proposition 94 that states that \(ℕ_\text {ZF}\) is well ordered by the relation \(⊆\).

We know by 6 and 2 that \(ℕ_\text {ZF}\) is an ordinal; we may be tempted to see Proposition 94 as a corollary of the previous result 8.

This is unfortunately not a well posed way of proving this result, because of this cascade of dependencies:

the proof of 8 relies on the result 11
the result 11 in turn needs a definition by recurrence of a function: this is Theorem 134
the proof of Theorem 134 uses the fact that the induction principle holds on \(ℕ\).

So we need to first prove the properties of \(ℕ_\text {ZF}\) independently of the theory of ordinals, and then prove the results in Sec. 4, and then eventually we can prove the result 8, that states that any ordinal is well ordered by the relation \(⊆\).

(da sistemare)