Cardinality

Pigeonhole Principle

Let $A$ and $B$ be finite sets. If there is an injection $f:A\to B$ , then $|A|\le |B|$ Contrapositive: Let $m,n\in {\mathbb{Z}}^{+}$ with $m>n$ . If $m$ pigeons are put into $n$ pigeonholes, then there must be (at least) one pigeonhole with (at least) two pigeons.

Dual Pigeonhole Principle

Let $A$ and $B$ be finite sets. If there is an surjection $f:A\to B$ , then $|A|\ge |B|$ Contrapositive: Let $m,n\in {\mathbb{Z}}^{+}$ with $m<n$ . If $m$ pigeons are put into $n$ pigeonholes, then there must be (at least) one pigeonhole with no pigeons.

Finite vs Infinite set

A set $S$ is said to be finite if it is empty, or there exists a bijection from $S$ to the set of positive integers from 1 to $n$ $\{1,2,3,...,n\}$
A set $S$ is said to be infinite if it is not finite

Cardinality

Finite Set

The cardinality of a finite set $S$, denoted $|S|$, is

1. 0 if $S=\varnothing$ or
2. $n$ if $f:S\to \{1,2,\dots ,n\}$ is a bijection
   Equality of cardinality of finite sets theorem For finite sets $A$ and $B$ : $|A|=|B|$ iff there is a bijection $f:A\to B$
   Any subset of a finite set is finite (contrapositive: any subset of a infinite set is infinite)

Infinite Sets

Given two sets $|A|$ and $|B|$ , $A$ is said to have the same cardinality as $B$ , written as $|A|=|B|$ , iff there is a bijection $f:A\to B$
note: we define what $|A|=|B|$ is without defining what $|A|$ or $|B|$ is
Another definition: Set $A$ is infinite iff there exists a set $B$ such that $(B\subseteq A)\wedge (B\ne A)\wedge (|B|=|A|)$ (A proper subset of $B$ has the same cardinality as $B$)

Properties of cardinality

The same-cardinality relation is an equivalence relation. For all sets $A$, $B$ and $C$

• Reflexive: $|A|=|A|$
• Symmetric: $|A|=|B|\to |B|=|A|$
• Transitive: $(|A|=|B|)\wedge (|B|=|C|)\to |A|=|C|$

Countability

A set is countable iff it is finite our countable infinite. Otherwise, it is uncountable.

Countably Infinite

Theorem 7.4.3: Any subset of any countable set is countable. (Contrapositive: Any set with an uncountable subset is uncountable.)
Lemma 9.4: Let $A$ and $B$ be countable infinite sets. Then $A\cup B$ is countable

Definition through bijection with ${\mathbb{Z}}^{+}$

“aleph zero” $={\aleph }_0=|{\mathbb{Z}}^{+}|$
A set $A$ having the same cardinality as ${\mathbb{Z}}^{+}$ is called a countably infinite set i.e. $|A|={\aleph }_0$
If sets $A_1,A_2,...,A_n$ are countably infinite, so is the cartesian product $A_1\times A_2\times \dots \times A_n$

Definition through sequence

An infinite set $B$ is countable iff there is a sequence $b_0,b_1,b_2,\dots \in B$ in which every element f $B$ appears (exactly once — whether this is included doesn’t matter) (this is equivalent to the above definition)

Example

${\mathbb{Z}}^{+}\times {\mathbb{Z}}^{+}$ is countable
Arrange the elements in a grid as shown:

(1,1)	(1,2)	(1,3)
(2,1)	(2,2)	(2,3)
(3,1)	(3,2)	(3,3)
We can count the ordered pairs following the diagonals: (1,1) → (1,2) → (2,1) → (1,3) → (2,2) → (3,1) etc. (sequence argument)
The function that represents this is $f(x,y)=\frac{(x+y-2)(x+y-1)}{2}+x$ (bijective function argument)
Therefore, ${\mathbb{Z}}^{+}\times {\mathbb{Z}}^{+}$ is countable.

Uncountable Infinite

A set is uncountable if it is impossible to find a bijection from that set to ${\mathbb{Z}}^{+}$ Theorem 7.4.2: The set of real numbers between 0 and 1, $(0,1)=\{x\in \mathbb{R}|0<x<1\}$ is uncountable
Proposition 9.3: Every infinite set has a countable infinite subset

Cantor’s diagonalization argument

(Prove the above by contradiction)

1. Suppose $(0,1)$ is countable
2. Since it is not finite, it is countable infinite
3. We list the elementns $x_{i}of(0,1)inasequenceasfollows:$x_1 = 0.a_{11}a_{12}a_{13}…a_{1n}…x_2 = 0.a_{21}a_{22}a_{23}…a_{2n}…x_3 = 0.a_{31}a_{32}a_{33}…a_{3n}……x_n = 0.a_{n1}a_{n2}a_{n3}…a_{nn}……$whereeach$a_{ij} \in {0,1,…,9}$ is a digit. (For numbers that have two representations 0.499… = 0.500…, we use only the latter representation)
4. Now, construct a number (from a diagonal of the above sequence) $d=0.d_1{d}_2{d}_3\dots d_n\dots$ such that

\begin{array}{ll} 1 & \text{if} a_{nn} \neq 1 \\ 2 & \text{if} a_{nn} = 1 \\ \end{array} \right.$$ 5. Note that $\forall n \in \mathbb Z^+, d_n \neq a_{nn}$ . Thus, $d \neq x_n, \forall n \in \mathbb Z^+$ 6. But clearly, $d \in (0, 1)$ . Hence, a contradiction. Therefore $(0,1)$ is uncountable # Well-ordering principle Every nonempty subset of $\mathbb{Z} _{\geq 0}$ has a smallest element