The Axiom of Infinity

Once we have formulated the axioms, the natural next thing is to define the natural numbers. The way we do it is to define 0 to be the empty set, and for each number we define its successor. The axiom of infinity gurantees that a super set of the natural numbers exists, and we need to use the axiom schema of separation in order to extract the natural numbers.

Definition: Let $n$ be a set, then the set $n \cup \{n\}$ is called the successor of $n$, and is denoted by $S(n)$.

Claim: Exists $N$ a set such that $n \in N$ if and only if $n=\emptyset$ or exists $m \in N$ such that $n=S(m)$.

Proof: From the axiom of infinity there exists a set $I$ such that $\emptyset \in I$ and for each $x \in I$ holds that $S(x) \in I$, we denote the propery of being such a set by $\varphi$, then by the axiom of separation the class $\{n \in I: \text{for all }A\text{ h.t. } \varphi(A) \text{ implies } n \in A\}$ is a set.

Definition: The set which its existance we just proved is called the natural numbers or the naturals for short, and is denoted by $\mathbb{N}$.

Definition: Let $n \in \mathbb {N}$, then $n$ is called a natural number or natural for short.

Definitions:

1. $0 := \emptyset$
2. $1 := S(0)$
3. $2 := S(1)$
4. $3 := S(2)$

Claim (the principle of induction): Let $\varphi$ be a property such that $\varphi(0)$ holds true, and such that for each $n_{0} \in \mathbb{N}$ holds that if $\varphi(n_{0})$ holds true then $\varphi(S(n_{0}))$ holds true as well, then $\varphi(n)$ holds true for all $n \in \mathbb{N}$.

Proof: Denote $A := \{n \in \mathbb{N}: \varphi(n)\}$, from the definition $0 \in A$ and for each $n_{0} \in A$ holds that $S(n_{0}) \in A$, therefore $\mathbb{N} \subseteq A$, but since $A \subseteq \mathbb{N}$ we get that $A = \mathbb{N}$.

Definition: Let $A$ be a set, then $A$ is called transitive if for each $a \in A$ holds that
$a \subset A$.

Claim: Let $n \in \mathbb{N}$ be a natural number, then $n$ is transitive.

Proof: If $n=0$ then the claim is vacuously true. Let $n_{0} \in \mathbb{N}$ be transitive, and let $m \in S(n_{0}) = n_{0} \cup \{n_{0}\}$, then either $m \in n_{0}$ or $m = n_{0}$. If $m \in n_{0}$ then $m \subset n_{0}$ and in particular $m \subset n_{0} \cup \{n_{0}\} = S(n_{0})$, and if $m = n_{0}$ then $m = n_{0} \subset n_{0} \cup \{n_{0}\}$. Therefore $S(n_{0})$ is transitive and from the principle of induction all natural numbers are transitive.

Claim: $\mathbb{N}$ is transitive.

Proof: Denote $N := \{n \in \mathbb{N} : n \subset \mathbb{N}\}$, from the definition $0 \in \mathbb{N}$ and trivially $\emptyset \subset \mathbb{N}$ and therfore $0 \in N$. Let $n \in N$, then $n \subset \mathbb{N}$, and also $\{n\} \subset N \subseteq \mathbb{N}$, and therefore $n \cup \{n\} \subset \mathbb{N}$, and so $S(n) \subset N$ and from the principle of induction we get $N = \mathbb{N}$.

Ordering

We will now move on to talk about ordering, so we will be able to say that one number comes before another, but first we must define ordered pairs and relations.

Definition: Let $a,b$ be sets, then the set $\{\{a\},\{a, b\}\}$ is called an ordered pair and is denoted by $(a, b)$. Additionally for every property $\varphi$ we shall denote $\{(a, b): \varphi(a, b)\} := \{x : \text{exists } a \text{ and exists } b \text{ s.t. } x = (a,b) \text{ and } \varphi(a, b)\}$.

Definition: Let $A, B$ be sets, then the class $\{(a, b) : a \in A, b \in B\}$ is called the cartesian product of $A$ and $B$, and is denoted by $A \times B$.

Claim: Let $A, B$ be sets, then $A \times B$ is a set.

Proof: From the axiom of union $A \cup B$ is a set, and from the axiom of the power set $P(P(A \cup B))$ is also a set, therefore from the axiom schema of separation the class $\{x \in P(P(A \cup b)) : \text{exists } a \in A, b \in B \text{ s.t. } x = (a, b)\}$ is a set.

Corollary: Let $A, \mathcal{B}$ be sets, then:

1. $A \times \bigcup \mathcal{B} = \bigcup \limits _{B \in \mathcal{B}} (A \times B)$
2. $\bigcup \mathcal{B} \times A = \bigcup \limits _{B \in \mathcal{B}} (B \times A)$

Corollary: Let $A, B, C$ be sets, then:

1. $A \times (B \cup C) = (A \times B) \cup (A \times C)$
2. $(A \cup B) \times C = (A \times C) \cup (B \times C)$

Definition: Let $A, B$ be sets, then $R \subseteq A \times B$ is called a binary relation between $A$ and $B$, if $(a, b) \in R$ denote $aRb$ for short.

Definitions: Let $A$ be a set, and let $R \subseteq A \times A$ be a binary relation, then:

1. $R$ is called reflexive if for each $a \in A$ holds that $aRa$.
2. $R$ is called symmetric if for each $aRb$ holds that $bRa$.
3. $R$ is called antisymmetric if for each $aRb$ such that $bRa$ holds that $a = b$.
4. $R$ is called transitive if for each ${a, b, c} \subseteq A$ such that $aRb$ and $bRc$ holds that $aRc$.

Definition: Let $A$ be a set and let $\preccurlyeq \subseteq A \times A$ be a reflexive antisymmetric and transitive binary relation, then it is called an ordering on $A$, and $A$ is called ordered relative to $\preccurlyeq$.

Corollary: Let $A$ be any set, then $A$ is ordered relative to $\{(a,b) \in A \times A: a \subseteq b\}$.

Definitons:

1. $\le := \{(n, m) \in \mathbb{N} \times \mathbb{N} :n \in m \text{ or } n = m\}$.
2. $< := \{(n, m) \in \mathbb{N} \times \mathbb{N} :n \in m\}$.

Claim: $\mathbb{N}$ is ordered relative to $\le$.

Proof: Reflexivity is trivial, and antisymmetry is implied by the axiom of regularity. Let $k \le m$ be natural. If $m \le 0$ then $m = 0$ and therefore $k = 0$, and in particular $k \le 0$. Let $n_{0} \in \mathbb{N}$ such that $m \le n_{0}$ implies $k \le n_{0}$. Assume $m \le S(n_{0})$, then either $m = S(n_{0})$ or $m \le n_{0}$. if $m = S(n_{0})$ then $k \le m = S(n_{0})$, otherwise $m \le n_{0}$ and therefore $k \le n_{0}$ and in praticular $k \le S(n_{0})$, and from the principle of induction we get that for each $n \in \mathbb{N}$ holds that $m \le n$ implies $k \le n$.

Claim: Let $n \in \mathbb{N}$ be natural, then $0 \le n$.

Proof: For $n = 0$ the claim is trivial. Let $n \in \mathbb{N}$ such that $0 \le n$ then either $0 = n$ or $0 \in n$. If $0 = n$ then $0 \in \{0\} = S(0) = S(n)$, otherwise $0 \in n$ and in particular $0 \in n \cup \{n\} = S(n)$, then from the principle of induction we get that $0 \le n$.

Claim: Let $n \in \mathbb{N}$ natural, then for each $m \in n$ holds that $S(m) \le n$.

Proof: For $n = 0$ the claim is vaccusly true. Let $n_{0}$ such that for each $m \in n_{0}$ holds that $S(m) \le n_{0}$. Assume $m \in S(n_{0})$, then $m \le n_{0}$. If $m = n_{0}$, then $S(m) = S(n_{0})$ and in praticular $S(m) \le S(n_{0})$, otherwise $m \in n_{0}$ and from the choice of $n_{0}$ we get $S(m) \le n_{0}$ and in particular $S(m) \le S(n_{0})$. Therefore from the principle of induction the claim is true for all $n \in \mathbb{N}$.

Definition: Let $A$ be an ordered set relative to $\preccurlyeq$, if for each $\{a, b\} \subseteq A$ holds that either $a \preccurlyeq b$ or $b \preccurlyeq a$, then $\preccurlyeq$ is called a linear ordering on $A$, and $A$ is called linearly ordered relative to $\preccurlyeq$.

Claim: $\mathbb{N}$ is linearly ordered relative to $\le$

Proof: Let $m \in \mathbb{N}$ be natural. $0$ holds that $0 \le m$, so let $n_{0} \in \mathbb{N}$ such that either $n_{0} \le m$ or $m \le n_{0}$. If $m = n_{0}$ then $m \in S(m) = S(n_{0})$. If $m \in n_{0}$ then in particular $m \in n_{0} \cup \{n_{0}\} = S(n_{0})$, and if $n_{0} \in m$ we get from the previous claim that either $S(n_{0}) = m$ or $S(n_{0}) \in m$, and therefore from the principle of induction we get the $\mathbb{N}$ is linearly ordered.

Definitions: Let $A$ be ordered set relative to $\preccurlyeq$, let $A_{0} \subseteq A$, and let $a \in A_{0}$, then:

1. If for each $b \in A_{0}$ holds that $a \preccurlyeq b$, then a is called a minimum element of $A_{0}$ relative to $\preccurlyeq$, and is denoted by $\min A_{0}$.
2. If for each $b \in A_{0}$ holds that $b \preccurlyeq a$, then a is called a maximum element of $A_{0}$ relative to $\preccurlyeq$, and is denoted by $\max A_{0}$.

Claim: Let $A$ be linearly ordered relative to $\preccurlyeq$, Let $A_{0} \subset A$, then $A_{0}$ has at most one minimal element.

Proof: Assume $a, b$ are minimal elemets of $A_{0}$, then $a \preccurlyeq b$ and $b \preccurlyeq a$ and from antisymmetry we get $a = b$.

Corollary: $\min \mathbb{N} = 0$.

Definition: Let $A$ be linearly ordered set relative to $\preccurlyeq$, then if for each $A_{0} \subseteq A$ non-empty subset exists a minimal element, then $\preccurlyeq$ is called a well ordering on $A$, and $A$ is called well ordered relative to $\preccurlyeq$.

Claim (the well ordering principle): $\mathbb{N}$ is well ordered relative to $\le$.

Proof: Let $N \subseteq \mathbb{N}$ such that for each $n \in N$ exists $m \in N$ such that $m < n$. If $0 \in N$ then exists $m \in N \setminus \{0\}$ such that $m \in 0$ in contradiction, and therefore $0 \in \mathbb{N} \setminus N$. Let $n \in \mathbb{N} \setminus N$ such that for each $m < n$ holds that $m \in \mathbb{N} \setminus N$. Assume $S(n) \in N$, then exists $m \in N \setminus \{S(n)\}$ such that $m < S(n)$, i.e. $m le n$, in cotradiction to the choice of $n$. Therefore $S(n) \in \mathbb{N} \setminus N$ and for each $m < S(n)$ holds that $m \in \mathbb{N} \setminus N$, and from the principle of induction we get that $\mathbb{N} \setminus N = \mathbb{N}$ and $N = \emptyset$.

Claim: Let $\{n, m\} \subset \mathbb{N}$ such that $n \subset m$, then $n \in m$.

Proof: Denote $N := m \setminus n$ a non empty subset of the naturals. Exists $n_{0} \in N$ such that for each $m \in N$ holds that $n_{0} \le m$. If exists $k \in n_{0} \setminus n$, then in particular $k \in m \setminus n$ and $k \in n_{0}$ in contradiction of the choice of $n_{0}$ and threfore $n_{0} \subseteq n$. If on the other hand exists $k \in n \setminus n_{0}$, then from linearity either $n_{0} = k$ or $n_0 \in k$. But then from trasitivity we get $n_{0} \subseteq k \subset n \setminus n_{0}$ in contradiction. Therefore $n = n_{0}$ and in particular $n \in m$.