Notes - Set Theory HT25, Natural numbers

\[x^+ := x \cup \\{x\\}\]

• Contains the empty set: $\emptyset \in x$
• Closed under successor operation: $\forall y (y \in x \to y^+ \in x)$.

An inductive set exists:

\[\exists x (\emptyset \in x \land \forall y (y \in x \to y \cup \\{y\\} \in x))\]

Recall that a set $x$ is inductive if $\emptyset \in x \land \forall y (y \in x \to y \cup \{y\} \in x)$.

---

Uniqueness: If $\mathbb N$ and $\mathbb N’$ are both the smallest such set, $\mathbb N \subseteq \mathbb N’$ and $\mathbb N’ \subseteq \mathbb N$ implies $\mathbb N = \mathbb N’$.

Existence: By the axiom of infinity, an inductive set $I$ exists. Let

\[\mathbb N := \bigcap \\{I' \subseteq I : I' \text{ is inductive}\\}\]

which is a set by comprehension.

Since the intersection of inductive sets is inductive, $\mathbb N$ is inductive. If $J$ is an inductive set, then $J \cap I \subseteq I$ and so appears in the intersection above. Hence $\mathbb N \subseteq J \cap I \subseteq J$.

Suppose:

• $\phi(x)$ is an $\mathcal L$-formula
• $\phi(0)$ is true
• If $n \in \mathbb N$ and $\phi(n)$ holds, then $\phi(n^+)$ holds

Then:

• $\phi(n)$ holds for all $n \in \mathbb N$

In other words, we have that

\[\left( (\phi(\emptyset) \land \forall n \in \mathbb N (\phi(n) \to \phi(n^+))) \to \forall n \in \mathbb N . \phi(n) \right)\]

This means that the set

\[X := \\{n \in \mathbb N : \phi(n)\\} \subseteq \mathbb N\]

is inductive, and hence $X = \mathbb N$ by the definition of $\mathbb N$.

Every element of $x$ is a subset of $x$, i.e. $\forall y \in x . y \subseteq x$.

There exists a bijection $f : X \to n$ for some $n \in \mathbb N$.

If $X$ is finite, then any injective function $f : X \to X$ is surjective.

Note that the successor function $n \mapsto n^+$ on $\mathbb N$ is injective but not surjective.

\[x < y \iff x \in y\]

(1): Note that $n \in n^+$, so if $n^+ = 0$, $0$ would be nonempty. But $0 = \emptyset$.

(2): Induct on $m$. If $m = 0$, then it is vacuous and thus immediate.

Now suppose that it holds for $m$. Let $n \in m^+$, and we want to show that $n^+ \in m^{++}$.

If $n = m$, then $n^+ = m^+ \in m^{++}$ as required.

Otherwise, $n \in m$, so $n^+ \in m^+$ by the inductive hypothesis, and therefore $n^+ \in m^{++}$ as required.

(3): Existence follows from induction.

For uniqueness, suppose $k, l \in \mathbb N$ and $k^+ = l^+$ but $k \ne l$. Then $k \in k^+ = l^+ = l \cup \{l\}$ but $k \ne l$, so $k \in l$.

But then $k^+ \in l^+ = k^+$ by (2), which contradicts irreflexivity.

In other words, we wish to show that

\[\forall n \in \mathbb N .\forall m \in \mathbb N. (n \in m \lor n = m \lor m \in n)\]

First we show that $\forall n \in \mathbb N . (0 \in n \lor 0 = n)$. If $n = 0$, then this immediate. If it holds for $n$, then $0 \in n^+$ since either $0 = n \in n^+$ or $0 \in n \subseteq n^+$.

Now we fix $n$ and induct on $m$ to show $\phi(n, m)$.

Base case: $\phi(n, 0)$ is true by the above.

Inductive step: If $\phi(n, m)$, we aim to show $\phi(n, m^+)$.

If $m = n$, then $n \in m^+$.

If $n \in m$, $n \in m \in m^+$ implies $n \in m^+$ by transitivity of $<$.

If $m \in n$, note that in particular $n \ne 0$. Hence $n = k^+ = k \cup \{k\}$ for some $k$. Then either $m = k$, in which case $m^+ = k^+ = n$, or $m \in k$, in which case $m^+ \in k^+ = n$ by the result that says:

If $n \in m$ then $n^+ \in m^+$.

\[n \subseteq m\]

Uniqueness: This is immediate, since if $n, n’$ are both least elements, $n \le n’ \le n$, so $n = n’$.

Existence: Suppose that $X \subseteq \mathbb N$ has no least element. Then we can show that $X = \emptyset$ by proving $\forall n \in \mathbb N . \forall m \in n . m \notin X$ by induction.

For $n = 0$, this is trivial. If it holds for $n$, then it holds for $n^+$, otherwise $n$ would be a least element of $X$.

Suppose:

• $X$ is a set
• $g : X \to X$
• $x _ 0 \in X$

Then there exists a unique function $f : \mathbb N \to X$ such that

• $f(0) = x _ 0$
• $f(n^+) = g(f(n))$

For each $n \in \mathbb N$, say $h : n^+ \to X$ is an $n$-approximation if $h(0) = x _ 0$ and $h(m^+) = g(h(m))$ for all $m \in n$.

First, we prove that for each $n \in \mathbb N$, there exists a unique $n$-approximation.

Existence: Induct on $n$. $\{\langle 0, x _ 0\rangle\}$ is a $0$-approximation. If $h$ is an $n$-approximation, set $h’ := h \cup \{\langle n^+, g(h(n))\}$. Then $h’$ is an $n^+$-approximation.

Uniqueness: Induct on $n$. For $n = 0$, $\{\langle 0, x _ 0 \rangle\}$ is a unique $0$-approximation. Suppose uniqueness holds for $n$, and consider $h _ 1$ and $h _ 2$ as $n^+$-approximations. Then $h _ 1 \vert _ {n^+} = h _ 2 \vert _ {n^+}$ since these are both $n$-approximations. But then

\[h_1(n^+) = g(h_1(n)) = g(h_2(n)) = h_2(n^+)\]

and so $h _ 1 = h _ 2$.

Now, we prove that $f$ exists as stated in the theorem.:

Existence: Each $n$-approximation $h : n^+ \to X$ is a subset of $\mathbb N \times X$. The property of being an $n$-approximation is expressible in $\mathcal L$ as $\phi(h, n)$ by translating the definition. Hence by comprehension, there is a set

\[H := \\{h \in \mathcal P(\mathbb N \times X) : \exists n \in \mathbb N . \phi(h, n)\\}\]

Let

\[f := \bigcup H\]

Then:

• $f : \mathbb N \to X$: Let $n \in \mathbb N$. Then there exists an $n$-approximation $h$, so $\langle n, h(n)\rangle \in f$. If $\langle n, x \rangle \in f$, then $\langle n, x \rangle \in h’$ for some $h’ \in H$. Then $h’$ is an $m$-approximation for some $m$ with $n \le m$, so $h’ \vert _ {n+}$ is an $n$-approximation, so $h’ \vert _ {n^+} = h \vert _ {n^+}$, and so $x = h(n)$.
• $f(0) = x _ 0$. If $h \in H$ is the $0$-approximation, we have $\langle 0, x _ 0 \rangle \in h \subseteq f$.
• $f(n^+) = g(f(n))$ for $n \in \mathbb N$: Let $H \in H$ be the $n^+$-approximation. Then $f(n^+) = h(n^+) = g(h(n)) = g(f(n))$.

Uniqueness: Suppose $f, f’ : \mathbb N \to X$ are as in the statement. Let $n \in \mathbb N$. Then $f \vert _ {n+}$ and $f’ _ {n^+}$ are $n$-approximations, so $f \vert _ {n^+} = f’ \vert _ {n^+}$ by the uniqueness in the previous claim, and in particular $f(n) = f’(n)$. Hence $f = f’$.

Suppose:

• $A$ and $X$ are sets
• $g _ 0 : A \to X$
• $g _ + : A \times X \to X$

Then there exists a unique $f : A \times \mathbb N \to X$ such that

• $f(a, 0) = g _ 0(a)$
• $f(a, n^+)) = g _ +(a, f(a, n))$ for all $n \in \mathbb N$.

For each $a$, the theorem implies that there is a unique $f _ a : \mathbb N \to X$ such that $f _ a(0) = g _ 0(a)$ and $f _ a(n^+) = g _ +(a, f _ a(n))$ for all $n \in \mathbb N$. So if it is possible to define $f(a, n) := f _ a(n)$.

To see that this is possible, observe that it is possible to express in a formula that $f _ a$ is defined by recursion using $g _ 0(a)$ and $g _ +(a, x)$ so that there is a formula $\phi(x, y)$ such that for all $a \in A$, $f _ a$ is unique such that $\phi(a, f _ a)$ holds.

Then $\phi$ defines by comprehension the function $f : A \to X^\mathbb N$ where $a \mapsto f _ a$. Then the function $f$ can be defined by $f(a, n) := F(a)(n)$, i.e.

\[f = \\{ \langle \langle a, n \rangle, x \rangle \in (A \times \mathbb N) \times X) : \langle a, \langle n, x \rangle \rangle \in F \\}\]

as required.

• Addition:
  • $g _ 0(n) = n$
  • $g _ +(n, k) = k^+$
• Multiplication:
  • $g _ 0(n) = 0$
  • $g _ +(n, k) = k + n$
• Exponentiation:
  • $g _ 0(n) = 1$
  • $g _ +(n, k) = k \cdot n$

@example~