Class 17: Infinite Sets

### Schedule

Before Thursday, everyone should have finished reading MCS Chapter 8.

**Problem Set 7** is due **Friday (27 Oct) at 6:29pm**.

# Infinite Sets

**Finite Cardinality.** The *cardinality* of the set
$$
\mathbb{N}_k = { n | n \in \mathbb{N} \wedge n < k }
$$
is $k$. If there is a *bijection* between two sets, they have the same
cardinality. (Class 9)

Does this definition tell us the cardinality of $\mathbb{N}$?

###

**Definition.** A set $S$ is *infinite* if there is no bijection between
$S$ and any set $\mathbb{N}_k$ (as defined above).

Show that $\mathbb{Z}$ is infinite.

### Cardinality of Infinite Sets

**Equal Carinalities.** We say $|A|\; = |B|$ for arbitrary sets $A,B$ (and say that they have the same cardinality), if there is a bijection between $A$ and $B$.

**Comparing Cardinalities.** We say $|B|\; \leq |A|$ for arbitrary sets $A,B$ (and say that $B$’s cardinality is less than or equal to the cardinality of $A$), if there is a *surjective function* from $A$ to $B$.

Show that $|A|\; = |B|$ implies $|B|\; \leq |A|$ and $|A|\; \leq |B|$. Be careful as these sets might not be finite, in which case we cannot simply use natural numbers to denote their cardinalities.

##

**Schr\wrap{\“{o}}der-Bernstein Theorem:** If $|A|\; \leq |B|$ and $|B|\; \leq |A|$, then there is a bijection between $A$ and $B$, namely $|A|\; = |B|$. (Not proven in cs2102; this is somewhat tricky to prove! For a full proof, see the linked lecture notes.)

### Other Definitions for Infinite Sets

**Dedekind-Infinite.** A set $A$ is *Dedekind-infinite* if and only if there exists a *strict subset* of $A$ with the same cardinality as $A$. That is,
$$\exists B \subset A \ldotp \exists R \ldotp R\ \text{is a bijection between}\ A\ \text{and}\ B.$$

Recall the definition of strict subset: $$B \subset A \iff B \subseteq A \wedge \exists x \in A\; .\; x \notin B.$$

**Third Definition.** A set $S$ is *third-definition infinite* if $|S|\; \geq |\mathbb{N}|$ (as defined on the previous page). Namely, there is a *surjective function* from $S$ to $\mathbb{N}$.

Are the above three definitions of (standard) *infinite* and *Dedekind-infinite* and *third-definition infinite*
equivalent definitions?

##

**Definition.** A set $S$ is *countable* if and only if there exists a
surjective function from $\mathbb{N}$ to $S$. (That is, $\le 1$ arrow
out from $\mathbb{N}$, $\ge 1$ arrow in to $S$.) Using our notation defined above, this means $|S|\; \leq |\mathbb{N}|$.

Prove that these sets are countable: $\mathbb{Z}$, $\mathbb{N} \times \mathbb{N}$, $\mathbb{Q}$ (rationals), $\emptyset$, $\mathbb{N} \cup (\mathbb{N} \times \mathbb{N}) \cup (\mathbb{N} \times \mathbb{N} \times \mathbb{N})$, all finite sequences of elements of $\mathbb{N}$.

#

**Definition.** A set $S$ is *countably infinite* if and only if it is *countable* and it is *infinite* (according to standard definition).

Must a *countable* set that is *Dedekind-infinite* be *countably infinite*?

#

Using the definition of countable, and third definition of infinite, show that $S$ is countably infinite if and only if there is a bijection between $S$ and $\mathbb{N}$. (We might as well use this definition in the future.)