# Classification and construction of sets

This is my note of the video https://youtu.be/6EIWRg-6ftQ. It’s not a full guide how to construct “numbers” from the empty set.

## Classification of sets

In Mathematics, we usuallly investigate the “structure” of “spaces” in terms of “maps”.

### Space and map

The terminology **space** is usually meant to be some set equipped with some “structure”.

A **map** $\phi: A\rightarrow B$ is a relation such that for every $a\in A$ there exists exactly one $b\in B$ such that $\phi(a,b)$.

As a notation, we write this fact as follows:

$$ \begin{align} \phi: &A\rightarrow B \\\ &a \mapsto \phi(a) := b \end{align} $$

Terminology:

- $A$: domain of $\phi$
- $B$: target of $\phi$
- $\phi(A)$: image of $A$ under $\phi$

A map $\phi: A\rightarrow B$ is called:

- surjective if $\phi(A)=B$.
- injective if $\phi(a_1)=\phi(a_2) \Rightarrow a_1 = a_2$.
- bijective if $\phi$ is surjective and injective.

Two sets $A$ and $B$ are called (set-theoretically) isomorphic if there exists a bijection $\phi:A\rightarrow B$, and we denote it as $A\cong B$. As a remark, if there is any bijection $A\rightarrow B$, there are many bijection in general.

### Infinite sets

A set $A$ is called an **infinite set** if there exists a proper subset $B$ such that $B\subseteq A$ and $B $

#### Coutably infinite

- A set $A$ is called an countably infinite if $A\cong \mathbb{N}$.
- A set $B$ is called an non-countably infinite if $A$ is an infinite set and $A$ is not a countable.
- Otherwise, a set is called a finite set. When the finite set is isomorphic like $A\cong \{1, 2,\cdots, N\}$ for $N\in\mathbb{N}$, we define
**cardinality**of $A$ as $N$, denoted by $|A|=N$.

### Composition of maps

Given two maps $\phi:A\mapsto B$ and $\psi:B\mapsto C$.
One can construct a **composition of the two maps** $\psi\cdot\phi$ as follows:

$$ \begin{align} \psi\cdot\phi: &A\rightarrow C \\\ &a \mapsto \psi(\phi(a)) \end{align} $$

Diagramatically, this composition is denoted as follows:

Note that the composition is associative by definition:

$$ \xi \cdot (\psi\cdot\phi) = (\xi \cdot\psi)\cdot\phi $$

### Inverse map

Let $\phi:A \to B$ be a bijection. Then the **inverse** of $\phi$, denoted $\phi^{-1}$, is defined uniquely by:

$$ \begin{aligned} \phi^{-1}\cdot\phi &= \mathrm{id}_A \\\ \phi\cdot\phi^{-1} &= \mathrm{id}_B \end{aligned} $$

### Preimage

Let $\phi:A\to B$ be any map. Then we define a preimage of $B$ under $\phi$ as follows:

$$ \phi^{-1}[B] := \{a \in A \mid \exists b\in B: \phi(a) = b\} $$

In the lecture, Prof. Frederic uses the notation $\mathrm{preim}_{\phi}(B)$ so that “$^{-1}$” denotes always an inverse (defined on bijection) map. Insted, I use square brackets “[]” with “$^{-1}$”.

A preimage is also called “counter image” or “inverse image”, and denoted like $\phi^{\leftarrow}(B)$.

### Equivalence relation

Equivalence relation provides grouping methods inside a set. The word “grouping” implicitly implies that there is no intersection between the groups.

Let $M$ be a set.
**An equivalence relation $\sim$ on $M$** is defined as a relation which satisfies the following three conditions:

- reflexivity: $\forall m\in M: m\sim m$
- symmetry: $\forall m,n\in M: m\sim n \Leftrightarrow n\sim m$
- transitivity: $\forall m,n,p\in M: (m\sim n \land n\sim p)\Rightarrow m\sim p$

Let $M$ be a set and $\sim$ be an equivalence relation on $M$ An equivalence class of $m\in M$ is defined as follows:

$$ [m] := \{ n\in M \mid m\sim n \} $$

Properties:

- $a\in[m] \Rightarrow [a] \sim [m]$ (any element of equivalence class can act as its representative.)
- either $[m]=[n]$ or $[m]\cap[n] = \varnothing$.

We can define quotient set as follows:

$$ M/\sim \ := \{[m]\in \mathcal{P}(M)\mid m\in M\} $$

Due to the axiom of choice, there exists a “complete system of representatives” $R$ for $\sim$, i.e., $\exists R \cong M/\sim$.

When you define a map whose domain is a quotion set, we should check that function should be independent of the representative element.

## Construction of $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, and $\mathbb{R}$

By the axiom of infinity, we can define/construct a set of natural numbers $\mathbb{N}$.

Note that set of natural numbers is defined by Zermelo ordinals.

$$ \begin{aligned} 0 &:= \varnothing \\\ 1 &:= {0} = \{\varnothing\} \\\ 2 &:= {1} = \{\{\varnothing\}\} \\\ &\cdots \end{aligned} $$

### Define addition on $\mathbb{N}$

We will construct $\mathbb{Z}$ and $\mathbb{Q}$ from $\mathbb{N}$, but we will also inherit the addition on $\mathbb{N}$ later.

Define a successor map as follows:

$$ \begin{aligned} S:&\mathbb{N}\rightarrow \mathbb{N} \\\ &n \mapsto \{n\} \end{aligned} $$

Define $\mathbb{N}^* := \mathbb{N}\backslash \{0\}$.

Define a predesessor map as follows (this definition is required to ):

$$ \begin{aligned} P:&\mathbb{N}^* \rightarrow \mathbb{N} \\\ &n \mapsto m \text{ s.t. } m\in n \end{aligned} $$

Define $n$-th power of $S$ as follows:

$$ \begin{aligned} S^n &:= S\cdot S^{P(n)} & \text{ if } n\in\mathbb{N}^* \\\ S^0 &:= \mathrm{id}_{\mathbb{N}} \end{aligned} $$

Finally, define addition + on $\mathbb{N}$ as follows:

$$ \begin{aligned} + :& \mathbb{N}\times\mathbb{N}\to\mathbb{N} \\\ & (m,n)\mapsto m+n := S^n(m) \end{aligned} $$

We can check,

- the addition is associative.
- the “neutral element” is 0.

### The set of integer numbers $\mathbb{Z}$

Let the equivalence relation on $\mathbb{N}\times\mathbb{N}$ as follows:

$$ (m,n) \sim (p,q) :\Leftrightarrow m+q = p+n $$

The idea is, $[(m, n)]$ corresponds/states for $m-n$

Under this equivalence relation, we can define a set of integer numbers $\mathbb{Z}$ as follows:

$$ \mathbb{Z} := (\mathbb{N}\times\mathbb{N})/\sim $$

From the definition it’s obvious $\mathbb{N}\not\subseteq\mathbb{Z}$
Instead, we can **embed** $\mathbb{N}$ into $\mathbb{Z}$ by introducing **inclusion map**:

$$ \begin{aligned} \iota: \mathbb{N} &\hookrightarrow \mathbb{Z} \\\ n &\mapsto [(n,0)] \end{aligned} $$

As a conclusion of embedding, we defined $n:=[(n,0)]$ where $n\in\mathbb{N}$. And using this new $n$, we can define the inverse of $n$ as $-n:=[(0,n)]$.

Finally, the addition of integers $+_{\mathbb{Z}}$ can be defined as follows:

$$ \begin{aligned} +_{\mathbb{Z}}: &\mathbb{Z}\times\mathbb{Z} \to \mathbb{Z} \\\ &[(m,n)] +_{\mathbb{Z}} [(p,q)] \mapsto [(m+p,n+q)] \end{aligned} $$

Roughly speaking, multiplication on $\mathbb{Z}$ can be defined as follows (Peano arithmetic):

$$ \begin{aligned} x\times 0 &:= 0 \\\ x\times S(y) &:= (x\times y) +x \end{aligned} $$

### The set of rational numbers $\mathbb{Q}$

The construction is similar to previous one.

Let the equivalence relation on $\mathbb{Z}\times\mathbb{Z}^*$ as follows:

$$ (x,y) \sim (u,v) :\Leftrightarrow x\times v = y\times u $$

The idea is, $[(m, n)]$ corresponds/states for $\displaystyle\frac{m}{n}$.

Under this equivalence relation, we can define the set of rational numbers $\mathbb{Q}$ as follows:

$$ \mathbb{Q} := (\mathbb{Z}\times\mathbb{Z*})/\sim $$

We can **embed** $\mathbb{Z}$ into $\mathbb{Q}$ by the introducing inclusion map as follows:

$$ \begin{aligned} \iota: \mathbb{Z} &\hookrightarrow \mathbb{Q} \\\ x &\mapsto [(x,1)] \end{aligned} $$

The addition of rational numbers $+_{\mathbb{Q}}$ can be defined as follows:

$$ \begin{aligned} +_{\mathbb{Q}}: &\mathbb{Q}\times\mathbb{Q} \to \mathbb{Q} \\\ &[(x,y)] +_{\mathbb{Q}} [(u,v)] \mapsto [(xv+yu,yv)] \end{aligned} $$

The multiplication of rational numbers $\cdot_{\mathbb{Q}}$ can be defined as follows:

$$ \begin{aligned} \cdot_{\mathbb{Q}}: &\mathbb{Q}\times\mathbb{Q} \to \mathbb{Q} \\\ &[(x,y)] \cdot_{\mathbb{Q}} [(u,v)] \mapsto [(xu,yv)] \end{aligned} $$

Note that the following wrong definition of addition is ill-defined because the RHS depends on the representatives of quotion sets:

$$ \begin{aligned} +_{ill}: &\mathbb{Q}\times\mathbb{Q} \to \mathbb{Q} \\\ &[(x,y)] +_{ill} [(u,v)] \mapsto [(x+u,y+v)] \end{aligned} $$

### The set of rational numbers $\mathbb{R}$

https://en.wikipedia.org/wiki/Construction_of_the_real_numbers