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.)