04. Cardinality

$\gdef \N{\mathbb{N}} \gdef \Z{\mathbb{Z}} \gdef \Q{\mathbb{Q}} \gdef \R{\mathbb{R}} \gdef \C{\mathbb{C}} \gdef \setcomp#1{\overline{#1}} \gdef \sseq{\subseteq} \gdef \pset#1{\mathcal{P}(#1)} \gdef \covariant{\operatorname{Cov}} \gdef \of{\circ} \gdef \p{^{\prime}} \gdef \pp{^{\prime\prime}} \gdef \ppp{^{\prime\prime\prime}} \gdef \pn#1{^{\prime\times{#1}}} $

Jan. 28

Cardinal Numbers¶

Definition:
Define a relation between sets as follows:
\(A\) is “(cardinal-)equivalent” to \(B\) (denoted \(|A|=|B|\)) whenever there exists a bijection \(f:A\to B\).

It’s easy to see that two finite sets are equivalent iff they have the same number of elements.

A cardinal number is an equivalence class of this relation.
Finite cardinal numbers: 0,1,2,3,4,5,6…

For infinite sets, things are a bit different.

Cardinality of Infinite Sets¶

Bounded Intervals¶

What other sets are in the equivalence class of \([0,1]=\set{x\in\R:0≤x≤1}\)?

Is there a bijection \(f:[0,1]\to[0,2]\)? Yes there is: \(f(x)=2x\).
Therefore, \(|[0,1]|=|[0,2]|\), meaning that they are in the same equivalence class, and therefore have the same cardinality.

Graphically, we connect the left endpoints and the right endpoints with segments that meet at point \(A\). Drawing any segment from \(A\) to some point on \([0,2]\), associate \(x\in[0,1]\) with \(f(x)\in[0,2] \Rightarrow\) bijection.

Expanding on this, we can see that all bounded intervals are equivalent.
(We’ll see later about intervals in the form \((0,1]\to[0,1]\))

Unbounded intervals¶

\(f:(0,1]\to[1,\infty)\)
\(f(x)=\frac 1x\). Easy to see that \(f\) is a bijection.

\(f:(0,1]\to(-\infty, 1]\)
\(f(x)=\ln x\). \(f\) is a bijection.

What about the infinite sets \(\N\) and \(\Z\)? Does there exist a bijection \(f:\N\to\Z\)?
Yes: \(f(n)=\cases{2n&n>0\\-2n+1&n≤0}\)

Is there a bijection \(f:\N\times\N\to\N\)?

Think of \(\N\times\N\) as the set of all passengers in “infinitely many busses carrying infinite passengers each.”
E.g., passenger 83 on bus 24 is pair (83,24)

Yes: We can see it by writing out \(\N\times\N\) in an infinite 2D array.
$$\begin{array}{cccccc} (1,1) & (1,2) & (1,3) & (1,4) & (1,5) & \cdots \\ (2,1) & (2,2) & (2,3) & (2,4) & (2,5) & \cdots \\ (3,1) & (3,2) & (3,3) & (3,4) & (3,5) & \cdots \\ (4,1) & (4,2) & (4,3) & (4,4) & (4,5) & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{array}$$

Then we can define a bijection \(f:\)\(\N\times\N\to\N\) by following a diagonal traversal of the array.

Feb. 4
However…