: 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>

2.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 133 and has an order relation that satisfies 144, so this model enjoys all properties described in Sec. 3; for this reason in this section we will mostly discuss properties that are specific of this model.

Successor

Definition 85

[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\). ¹

E86

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

E86

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

E86

[239]Prerequisites:13,86,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.

E86

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

E86

[1YM]Prerequisites:13,86,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’]

E86

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

Hidden solution: [UNACCESSIBLE UUID ’24R’]

E86

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

Natural numbers in ZF

Definition 88

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

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

Theorem 89

[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 90

[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 91

[25C]This fact holds true:

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

this can be proven by induction, as in 132, 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 92 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 93

[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 95

[26K]Peano’s Axioms are provable in this model; moreover the order relation satisfies the requirements of Hypothesis 144; therefore this model of \(ℕ\) enjoys all properties discussed in Sec. 3: 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 96

[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 98

[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 99

[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 90 note that there are transitive sets that are not natural numbers.

E99

[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’]

E99

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

Hidden solution: [UNACCESSIBLE UUID ’258’]

E99

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

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

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

E99

[26P]Prerequisites:3,13.To assert the Theorem 93 we have to prove ??, that is

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

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}

100

Hidden solution: [UNACCESSIBLE UUID ’26Q’]

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

Here following are other interesting exercises.

E100

[269]We know from 95 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}

101

By 4 this implies

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

Hidden solution: [UNACCESSIBLE UUID ’26B’]

E100

[265]Prove this assertion

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

Hidden solution: [UNACCESSIBLE UUID ’266’]

E100

[25D]Prerequisites:93,96.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 96 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 102

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

E102

[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’]

E102

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

E102

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

E102

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

Hidden solution: [UNACCESSIBLE UUID ’25P’]

E102

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

Hidden solution: [UNACCESSIBLE UUID ’25H’]

E102

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

Hidden solution: [UNACCESSIBLE UUID ’256’]

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

E102

[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).

E102

[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 103

[275]Consider again Proposition 96 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 96 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 135
the proof of Theorem 135 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. 3, and then eventually we can prove the result 8, that states that any ordinal is well ordered by the relation \(⊆\).

(da sistemare)