Classification and construction of sets

Page content

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:

  1. reflexivity: $\forall m\in M: m\sim m$
  2. symmetry: $\forall m,n\in M: m\sim n \Leftrightarrow n\sim m$
  3. 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