Equivalent Sets and Cantor Bernstein Theorem

Given sets we can define an equivalence relation by saying two sets $A,B$ are equivalent $A \sim B$ if there is a set isomorphism $\psi:A \rightarrow B$ between them. This generalizes the notion of cardinality of sets.

definition: [finite, countable, uncountable sets]

$A$ is finite is it is empty or there is $n \in \mathbb{N}$ such that $A \sim 1..n$
$A$ is countable if $A \sim \mathbb{N}$ .
$A$ is at most countable if $A$ is finite or $A$ is countable.
$A$ is not countable if it is not finite or countable.
$A$ is infinite if it is not finite.
an (finite) enumeration of a set $A$ is an isomorphism ( $\phi: 1..n \rightarrow A$ ) $\phi: \mathbb{N} \rightarrow A$ .

sets can be ostensibly larger than sets they are equivalent to in the sense of containment, but this is in some sense a mirage since if this is the case the symbols in the larger may be encoded using symbols in the smaller set.

lemma: $\mathbb{Z} \sim \mathbb{N}$

Define $\phi(1) = 0, \phi(2k) = k, \phi(2k+1) = -k$ . Then $\phi$ is an enumeration of $\mathbb{Z}$ .

the same can be true in the other sense.

lemma: for any $c \in \mathbb{N}$ , $c \mathbb{cN} \sim \mathbb{N}$ .

Define $\phi(k) = ck$ is clearly surjective and injective.

lemma: $\mathbb{N} \times \mathbb{N} \sim \mathbb{N}$

Consider the ordering $(a,b) < (c,d)$ iff $\max(a,b) < \max(c,d)$ or $\max(a,b) = \max(c,d)$ and $a < c$ or $a = c$ and $d < b$ . Let $\text{next}(a,b)$ be the next element in the ordering. Define $\phi(1) = (1,1)$ and $\phi(k) = \text{next}(\phi(k-1))$ . This assignment is injective and covers all the pairs, therefore it is an isomorphism.

lemma: for any $k \in \mathbb{N}$ , $\mathbb{N}^k \sim \mathbb{N}$ .

The claim is true when $k = 1$ . Assume it is true for a given $k$ . Then $\mathbb{N}^{k+1} \sim \mathbb{N}^k \times \mathbb{N} \sim \mathbb{N} \times \mathbb{N} \sim \mathbb{N}$

the first equivalence is true since $\phi((i,j,k)) = ((i,j),k)$ defines an isomorphism, the second equivalence follows from the induction hypothesis, and the final equivalence follows from the prior lemma.

lemma: every subset of a countable set is at most countable.

Let $\phi$ be an enumeration of the countable set $A$ and let $B$ be a subset of $A$ . If $B$ is empty it is finite. Otherwise, define $n_1 = \min \{ i : \phi(i) \in B \}$ and inductively, $n_k = \min \{ i > n_{k-1} : \phi(i) \in B \}$ terminating when the minimum does not exist (set is empty). Then $\phi \circ n$ is an (finite or infinite) enumeration of $B$ and so $B$ is at most countable.

corollary: every infinite subset of a countable set is countable.

by the prior lemma, subsets of countable set are either finite or countable. But if infinite, then the set is not finite and so must be countable.

lemma: $\mathbb{Q} \sim \mathbb{N}$

Every rational $q$ has a unique coprime factorization $q = n/m$ with $m > 0$ . The set of rationals is infinite but it is a subset of $\mathbb{N}^2$ by defining $\phi(q) = (n,m)$ where $n,m$ is the coprime factorization, and so is countable.

lemma: every countable set is equivalent to a strict subset.

proof: Let $a \in A$ . Then $A - \{a\}$ is an countable set and so $A - \{a\} \sim \mathbb{N}$ . But $\mathbb{N} \sim A$ and so $A - \{a\} \sim A$ .

lemma: the set of real numbers in the closed unit interval $[0,1]$ is uncountable.

Every real number $x \in [0,1]$ has one or two binary expansion of the form $x = \sum_{i = 1..} a_{i} 2^{-i}$ where $a_{i} \in \{0,1\}$ . Assume the set of real numbers $[0,1]$ is countable. Then the set of binary expansions $A$ is countable. Let $\{A_i\}$ be one such enumeration. Form the diagonal complement from the enumeration of binary expansions: $s_i = 1- A_i(i)$ for $i = 1\ldots$ . Then $s$ is equal to no binary expansion. But this means that $\sum_{i > 0} s_i 2^{-i}$ corresponds to no number in $[0,1]$ which is false.

Cantor-Bernstein:

theorem: If there is an injection $f : A \rightarrow B$ and an injection $g: A \rightarrow B$ then there is a bijection $\beta: A\rightarrow B$ .

Since the extension of an injection to sets is order-preserving with respect to set inclusion, and since finite composition of injections is an injection and since for any injection $\gamma$ , $X \sim \gamma X$ ,

$A \supseteq gB$ , and so $fA \supseteq fgB$

$gB \supseteq gfA$ since $B \supseteq fA$

it is true that

$A \supseteq gB \supseteq gfA$

$B \supseteq fA \supseteq fgB$

and by order-preserving properties, the sequence of sets $\left< A_i \right>$ is non-increasing:

$A_1 = A, A_2 = gB, A_{k+2} = gf A_k, k =1,\ldots$

and so $A = \cup_{i=1\ldots} \left(A_i - A_{i+1} \right) \cup \cap_i A_i$ is a disjoint union.

Since $gf(A_i - A_{i+1}) = A_{i+2} - A_{i+3}$ and $gf$ is an injection $A_i - A_{i+1} \sim A_{i+2} - A_{i+3}$ .

$A_1 = \cup_{i=1..} \left(A_{2i-1} - A_{2i}\right) \cup \cup_{i=1..} \left(A_{2i} - A_{2i+1}\right) \cup \cap_i A_i$

$A_2 = \cup_{i=1..} \left(A_{2i+1} - A_{2i+2}\right) \cup \cup_{i=1..} \left(A_{2i} - A_{2i+1}\right) \cup \cap_i A_i$

and so there are isomorphisms between the corresponding disjoint countable unions and therefore correspondence $A = A_1 \sim A_2 = gB \sim B$ .

Hence there is an isomorphism between $A$ and $B$ .

The Cantor Bernstein theorem enables ordering of the equivalence classes defined by $\sim$ .

Define $A \le B$ if there is an injection $\phi : A \rightarrow B$ . Then $\le$ is reflexive, transitive and antisymmetric (relative to $\sim$ ):

$A \le A$ since $id_A : A \rightarrow A$ is an injection
$A \le B \le C$ implies $A \le C$ since the composition of injections is an injection.
$A \le B \le A$ implies by Cantor-Bernstein that $A \sim B$ .

Hence there is a valid meaning to the concept of power. Let $\mathcal{S}$ be a suitably sized collection of sets and let $\text{power}$ be a labeling function whose kernel is the set of equivalence classes induced by the cardinality equivalance: $\text{ker} \text{power} = \mathcal{S} / \sim$ . Define the induced order $\text{power}(s) \le \text{power}(t)$ iff $s \le t$ . Then $\text{power}$ is an order-isomorphism.

The power mapping is not well-explored. It typical to assign $\text{power}(\mathbb{N}) = \aleph_0$ and $\text{power}(\mathbb{R}) = c$ , the power of the continuum. We have $\aleph_0 < c$ .

theorem: $\text{power}(M) < \text{power}(2^M)$

since $\phi: M \rightarrow 2^M$ defined by $m \mapsto \{m\}$ is an injection, it follows that $M \le 2^M$ . Suppose $M \sim 2^M$ . Then there is an isomorphism $\psi: M \rightarrow 2^M$ . consider the set $T = \{x \in M \; : \; x \not \in \psi(x)\} \in 2^M$ . there is an $x \in M$ such that $\psi(x) = T$ . If $x \in T$ then $x \not\in \psi(x) = T$ , and if $x \not \in T$ then $x \in \psi(x) = T$ . This is an impossibility, therefore an isomorphism cannot exist.