cardinality of sets

Define N_n.

For n\in\mathbb{N}, N_n=\{1,2,3,\ldots,n\}=\{k\in\mathbb{N}\mid 1\le k\le n\}.

Rigorous definition: what does it mean that a finite set A has cardinality n?

There exists a bijection f:N_n\to A. We write |A|=n and define |\varnothing|=0.

How can you certify |A|=n without 'counting'?

Exhibit a bijection f:Nn\to A (i.e. label elements a1,\dots,an with f(i)=ai).

State Lemma: If there is an injection f:Nm\to Nn, what inequality holds?

m\le n.

Why is the lemma f:Nm\to Nn means M\le N useful for finite cardinality?

It shows cardinality is well-defined: if A is in bijection with both Nm and Nn, then m=n.

State precisely: when is finite cardinality well-defined?

If there are bijections f:Nm\to A and g:Nn\to A, then m=n.

What does an injection f:A\to B imply for finite sets?

|A|\le |B|; and if f is a bijection then |A|=|B|.

State the Pigeonhole Principle in cardinality language.

For finite sets, if |A|>|B| then no function f:A\to B is injective (some two elements of A map to the same element of B).

Cardinality of the union of disjoint finite sets?

If A\cap B=\varnothing, then |A\cup B|=|A|+|B|.

Generalise the previous result to finitely many pairwise-disjoint finite sets.

If A1,\dots,An are pairwise disjoint and finite, then \bigl|\bigcup{i=1}^n Ai\bigr|=\sum{i=1}^n |Ai|.

State the Inclusion–Exclusion principle for two finite sets.

|A\cup B|=|A|+|B|-|A\cap B|.

Define: sets A,B are equipotent.

There exists a bijection between A and B (they have the same cardinality).

Example of equipotent infinite sets on \mathbb{R}.

The intervals (0,1) and (0,2) are equipotent via f(x)=2x.

Define: denumerable set and the symbol for its size.

A is denumerable if there is a bijection f:\mathbb{N}\to A. We write |A|=\aleph_0.

Define: countable set.

A is countable if it is finite or denumerable.

Equivalent characterisation: how do we \list\ a denumerable set?

A is denumerable iff we can write A=\{a1,a2,\dots\} (a bijection with \mathbb{N} given by f(i)=a_i).

Example: show the even positive integers \{2k\mid k\in\mathbb{N}\} are denumerable.

Bijection f:\mathbb{N}\to A with f(k)=2k.

Example: show the squares \{k^2\mid k\in\mathbb{N}\} are denumerable.

Bijection f:\mathbb{N}\to B with f(k)=k^2.

Give an explicit bijection \mathbb{N}\to\mathbb{Z} to prove \mathbb{Z} is denumerable.

f(n)=\begin{cases}n/2,&n\text{ even}\\-(n-1)/2,&n\text{ odd}\end{cases}.

State Dedekind's characterisation of infinite sets.

A set A is infinite iff it is equipotent to a proper subset of itself.

Show: the union of two countable sets is countable.

If A and B are countable, list them as a1,a2,\dots and b1,b2,\dots; interleave to list A\cup B, hence it is countable.

Show: the product of two countable sets is countable (diagonal argument).

Arrange (ai,bj) in a grid and traverse along diagonals to list A\times B; thus countable.

Generalise: finite unions and finite products of countable sets are countable.

If A1,\dots,An are countable then both \bigcup{i=1}^n Ai and \prod{i=1}^n Ai are countable.

State: \mathbb{Q} is denumerable (idea of proof).

Since \mathbb{Z}\times\mathbb{Z} is countable and \mathbb{Q}=\{a/b\mid a,b\in\mathbb{Z},\,b>0,\,\gcd(a,b)=1\} injects into it, \mathbb{Q} is denumerable.

State Cantor's theorem: \mathbb{R} is uncountable (core diagonal step).

Assume $[0,1] is listed as an=0.a{n1}a{n2}\ldots and define b=0.b1b2\ldots with bn\ne a{nn} (e.g. bn=1 if a{nn}\ne 1, else bn=2). Then b$$ is missing from the list, contradiction.

Compare sizes: |\mathbb{N}|,|\mathbb{Z}|,|\mathbb{Q}|,|\mathbb{R}|.

|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|=\aleph_0<|\mathbb{R}|=:\mathfrak{c}.

What is |\mathbb{R}\times\mathbb{R}|?

|\mathbb{R}\times\mathbb{R}|=\mathfrak{c} (same cardinality as \mathbb{R}).

Define the power set \mathcal{P}(A).

\mathcal{P}(A)=\{B\mid B\subseteq A\}.

State Cantor's power-set theorem.

For every set A, |\mathcal{P}(A)|>|A|.

Consequence of the power-set theorem for \mathbb{R}.

|\mathcal{P}(\mathbb{R})|>|\mathbb{R}|=\mathfrak{c}, so there are infinitely many strictly larger infinities.

Technique tip: how to prove a set is countable in practice?

Either exhibit a bijection \mathbb{N}\to A (list it), or inject A into a known countable set, or surject \mathbb{N} onto A.

If |A|>|B| for finite sets and f:A\to B, what must happen? Why?

By the Pigeonhole Principle, f is not injective; some two elements of A share an image.

Compute |A\cup B| when |A|=7,|B|=10,|A\cap B|=4 (finite sets).

|A\cup B|=7+10-4=13.

Give a quick test to recognise an infinite set using Dedekind's idea.

Find an injection A\to A that misses at least one element (e.g. n\mapsto n+1 on \mathbb{N}).

Is a subset of a denumerable set always countable?

Yes: any subset is either finite or denumerable, hence countable.

Why doesn't the diagonal proof contradict that (0,1) and (0,2) are equipotent?

Both sets are uncountable of size \mathfrak{c}; a bijection like x\mapsto 2x exists between them. Diagonalisation only rules out listing them by \mathbb{N}.

TEST—rendering check: show this matrix as a square not a line.

\begin{pmatrix}1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1\end{pmatrix}