Cardinality

Functions

If $A,B$ are non empty sets, then a function is an association of $A$ to $B$ denoted as $f:A\to B$

• $f$ is injective if $f(a_1)=f(a_2)⟹a_1=a_2$
• $f$ is surjective if $\forall b\in B,\exists a\in A,f(a)=b$
• $f$ is bijective if both of these properties are held.

Notation

If $\exists$ bijection $f:A\to B$, then we write $A\sim B$ (or $|A|=|B|$) and we say $A,B$ have the same cardinality.

Finite Sets

A finite set is a set $A$ such that $A\sim \{1,2,\cdots ,n\}$ for some $n\in \mathbb{N}$.

• If a set $A$ is not finite, then it is called infinite.
• If $A\sim \mathbb{N}$ then $A$ is called countable.
• $A$ is uncountable if it is neither finite nor countable.
• $A$ is at most countable if $A$ is finite or countable.

Sequence

A sequence in set $X$ is a function $f:\mathbb{N}\to X$. Typically, we write $a_n$ or $x_n$ or $f_n$ for the $a(n),x(n),f(n)$ item in the sequence.

Lemma (Countability)

Let $A$ be an infinite set. The following are equivalent:

1. $A\sim \mathbb{N}$
2. $\exists f:A\to \mathbb{N}$ where $f$ is injective
3. $\exists g:\mathbb{N}\to A$ where $g$ is surjective

Corollary (Structure in Subsets)

Any subset of a countable set is countable (Rudin 2.8).

• We have that $\mathbb{N}$ is countable. $f:\mathbb{N}\to \mathbb{N}$ is bijective, the identity map.
• $\mathbb{Z}$ is countable. $$f(n)=\{\begin{array}{ll}n/2& n\text{ even}\\ -(n-1)/2& n\text{ is odd}\end{array}$$
• $\mathbb{Q}=\{m/n\mid m,n\in \mathbb{Z},n>0,\gcd (n,m)=1\}$ is countable.
  • We find an injection from $\mathbb{Q}\to \mathbb{Z}$. Let $h:\mathbb{Q}\to \mathbb{Z}$ where $$h(m/n)=\{\begin{array}{ll}{2}^m{3}^m& m>0\\ 0& m=0\\ -2^{-m}{3}^n& m<0\end{array}$$
  • Check $h$ is injective. Then, by the previous example, $\exists g:\mathbb{Z}\to \mathbb{N}$ is injective. We then have our function, $g\circ h$ which is an injection, so $\mathbb{Q}$ is countable, by the Lemma.

Operations on Sets

Recall, $n\in \mathbb{N}$ and $A_{1\le i\le n}$ then

$$\bigcup _{i=1}^n{A}_i:=A_1\cup A_2\cup \cdots \cup A_n$$ $$\bigcap _{i=1}^n{A}_i:=A_1\cap A_2\cap \cdots \cap A_n$$

We can extend this to countably infinite sets:

$$\bigcup _{i=1}^{\infty }{A}_i:=\{x\in X\mid \exists i\in \mathbb{N},x\in A_i\}$$ $$\bigcap _{i=1}^{\infty }{A}_i:=\{x\in X\mid \forall i\in \mathbb{N},x\in A_i\}$$

More generally, if $I$ is a set and $\alpha \in I$, then

$$\bigcap _{\alpha \in I}{A}_{\alpha }:=\{x\in X\mid \exists \alpha \in I,x\in A_{\alpha }\}$$ $$\bigcap _{\alpha \in I}{A}_{\alpha }:=\{x\in X\mid \forall \alpha \in I,x\in A_{\alpha }\}$$

Example

Let $I=(0,1)$ be the indexing set. For each $\alpha \in (0,1)$ consider:

$$A_{\alpha }=\{x\in \mathbb{R}\mid 0<x<\alpha \}$$

Then, ${\bigcap }_{\alpha \in I}{A}_{\alpha }={\bigcap }_{\alpha \in (0,1)}{A}_{\alpha }=\{x\in \mathbb{R}\mid x\in A_{\alpha },\alpha \in (0,1)\}$, which is really just

$$\{x\in \mathbb{R}\mid 0<x<1\}=(0,1)$$

Theorem (Countable Union)

• A countable (or finite) union of countable sets is countable.
• The union of countable (infinite or finite) countable sets is countable.

Theorem (Countable Products)

Let $A_1,A_2,\cdots A_n$ be countable. Then $A_1\times A_2\times \cdots \times A_n$ is countable. In particular, if $A$ is countable, then

$$A^n:=\{(a_1,\cdots a_n\mid a_i\in A,\forall i=1,\cdots ,n\}$$

is countable.

Indeed by this theorem and Corollary (Structure in Subsets), ${\mathbb{Q}}^n$ is countable.

Theorem ($\mathbb{R}$ is uncountable)

$$\{0,1{\}}^{\mathbb{N}}:=\{(a_1,a_2,\cdots \mid a\in \{0,1\}\}$$

is uncountable. Hence $\mathbb{R}$ is uncountable.

Remark

Recall, $\mathcal{P}(\mathbb{N})$ is the power set of $\mathbb{N}$ given by the subsets of $\mathbb{N}$. Generally, this is uncountable. More generally, $\forall X$ where $X$ is a set,

$$X\nsim \mathcal{P}(X)$$

i.e. there is no bijection $f:X\to \mathcal{P}(X)$ for any set $X$.