Cardinality

Definitions

• $A\preccurlyeq B$, if injective function $f:A\to B$ exists
  • reflexive, transitive, not antisymmetric (so not a partial order relation)
  • $A\subseteq B⟹A\preccurlyeq B$
• $A\sim B$, if bijective function $f:A\to B$ exists
  • equivalence relation
  • $A\preccurlyeq B\wedge B\preccurlyeq A⟹A\sim B$
• $|A|=n$ if $A\sim n$ (n is a natural number defined using a set)
• $A$ countable, if $A\preccurlyeq \mathbb{N}$
  • or if $A\sim \mathbb{N}$ or $A\sim n$ for a $n\in \mathbb{N}$ (See Theorem 3.17 Countability)

Example

$|\{1,2,5\}|=3$

• The number of elements $\mathbb{Z}\sim \mathbb{N}$
• $f:\mathbb{N}\to \mathbb{Z}$ with $f(n)=(-1{)}^n\lceil \frac{n}{2}\rceil$ a bijective function Interval $(0,1)\sim \mathbb{R}$
• $f:\mathbb{R}\to (0,1)$ with $f(x)=\frac{1}{e^x+1}$

Theorem 3.17 Countability

NOTE

A set $A$ is countable ($A\preccurlyeq B$) if and only if it is finite or if $A\sim N$

Proof: The important step is to show if $A$ is infinite $A\preccurlyeq B$ then $A\sim N$:

If $A\preccurlyeq \mathbb{N}$, then according to the definitions, a injective function $f:A\to \mathbb{N}$ exists. Let $C\subseteq \mathbb{N}$ be the image of $f$ (also infinite), meaning $f:A\to C$ is bijective. According to the well-ordering principle of $\mathbb{N}$, every subset of $\mathbb{N}$ has a least element. So we define a function $g:C\to \mathbb{N}$ with $g(c_0)=0$ $g(c_1)=1$ $⋮$

definitions of $c_0,c_1,\dots$

$c_0$ is the least element in $C$ $c_1$ is the least element in $C_1$ with $C_1=C\setminus \{c_0\}$ $⋮$

And this process can be continued, and shows $g:C\to \mathbb{N}$ is bijective. Using Transitivity of injectivity and surjectivity we know $g\circ f$ is a bijection $A\to \mathbb{N}$, which proves $A\sim \mathbb{N}$

A shorter proof (Overkill)

using Axiom of Choice (well-ordering principle), which assumes $A$ has a least element. Therefore, we can skip the construction of $C$ an show directly $A\sim \mathbb{N}$

Important Examples

Example 1

Alphabet

NOTE

set of all finite binary strings $\{0,1{\}}^{\ast }\stackrel{def}{=}\{\epsilon ,0,1,00,01,10,11,000,\dots \}$ $|x|\stackrel{def}{=}$ length of $x$

Link to original

$\{0,1{\}}^{\ast }\sim \mathbb{N}$ Proof: Define $f:\{0,1{\}}^{\ast }\to \mathbb{N}$ with $f(x)=\text{toRationalNumber}(\text{"1"}+x)-1$

Example 2

$\mathbb{N}\times \mathbb{N}\sim \mathbb{N}$

Example 3

$A$ countable $⟹$ $A^{\ast }$ countable Encode the finite sequence $(a_1,\dots ,a_n)$ with an unique bit string and let it be $f:A\to \{0,1{\}}^{\ast }$ showing $A\sim \{0,1{\}}^{\ast }$ …

Example 4

$\{0,1{\}}^{\infty }$ (the set of semi-infinite binary sequences) is uncountable $\{0,1{\}}^{\infty }\sim \mathbb{R}$ or denoted as $\{0,1{\}}^{\mathbb{N}}$ (see Notation of the set of all functions) The set of all functions from $\mathbb{N}$ to $\{0,1\}$ is uncountable

Bemerkung 1

The set of all programs $\sim \mathbb{N}$, jedes Program

Es existiert Funktionen, die von keinem Programm berechnet werden.

Bemerkung 2

$\mathbb{N}\prec \mathcal{P}(\mathbb{N})\prec \mathcal{P}(\mathcal{P}(\mathbb{N}))$

Continuum hypothesis

NOTE

There is no set whose cardinality is strictly between that of the integers and the real numbers.

Cannot be proven under ZFC.