We’ve discussed previously about the equivalence relation determined by Cantor’s definition of set equivalence.

We have encountered things like without actually fully understanding what it means aside from the fact that it tells us that A has a larger size than B. There is actually a more fundamental notion used for comparing set sizes than equivalence – dominance.

Dominance is an ordering relation on the class of all sets.

Actually, it was more proper to discuss dominance first, then define set relations in terms of it. The primary reason this was prolong was that it depend on the difficult Cantor-Bernstein-Schroder theorem.

Also, dominance is actually an ordering relation on the set of all cardinal numbers not on the collection of all sets. Thus, it was needed to define set equivalence before dominance.

Dominance

---

A set is said to dominate another set if there exist a function from the latter into the former. Formally,

This relation is easy to see as reflexive and transitive. To prove that it is anti-symmetric, Cantor-Bernstein-Schroder theorem is need which will then led us to a conclusion that dominance is an ordering relation.

What are the domain and range of the “dominance” relation?
From the relation that , it is actually the cardinal numbers of the sets instead of the sets itself that go on either side of the relation. Basically, we are comparing cardinal numbers instead of the set.

Thus, anti-symmetry for this relation is,

In simple words, if A dominates B and B dominates A, it implies that A and B are equivalent sets.

Cantor-Bernstein-Schroder (CBS) theorem

---

First it’ll be instructive to look at some of its consequences. Knowing CBS theorem provides a useful shortcut in proving set equivalences. For example, we can use CBS to prove that the set of all infinite binary strings and the set of reals in (0,1) really are equinumerous.

Hilbert’s Hotel

This cute thought-experiment will lead us to a technique for developing an injective function in the other direction.
Hilbert’s Hotel has hotel. For a countable collection of guests, we can have enough rooms for them.

Suppose you arrive at Hilbert’s hotel one dark and stormy evening and the “No Vacancy” light is on – there are already a denumerable number of guests there – every room is full. But a clerk approached you and said that to accommodate you others will vacate their room and move to the room numbered one higher. So you find yourself occupying room number 1. So you don’t have to worry.

We are going to develop an injection from infinitely-long binary sequences to (0,1). To do this we are going to use “room number 1” to separate the binary expansions that represent the same real number. Move all the digits of a binary expansion down by one, and make the first digit 0 for the terminating expansions and 1 for the non-terminating ones.

For instance,

0.0101010101 => 0.0010101010
0.0101010101… => 0.10101010101…

And then consider these expansions as real numbers, we now have an expansion separated in the intervals

This is a funny mapping, we now have infinitely-many real numbers with no preimages. Nevertheless, the map is injective, so CBS tells us that to (0,1) are equivalent. There are quite a few different proofs of the CBS theorem.

Learn Further:
The Infinite Hotel Paradox - Jeff Dekofsky

Axiom of Choice

---

The one that Cantor relies in to prove CBS is the axiom of choice. When it was introduced, axiom of choice was controversial, but these days mathematicians use it without qualms. What is says basically is,

it is possible to make an infinite number of choices, more precisely, is that if we have an infinite set consisting of non-empty sets, it is possible to select an element out of each set.

The usual axioms for set theory were developed by Zermelo and Frankel, known as ZF axioms collectively. If we allow that axiom of choice, we are in the ZFC axiom system. A proof of the CBS theorem which necessarily must be able to deal with uncountably infinite sets, will have to depend on some sort of notion that will allow us to deal with huge infinities.

Julius König and his CBS Proof

---

Julius König was a contemporary of Cantor, well respected but was an asshole in Cantor’s perspective. König presented a well-publicized lecture claiming that continuum hypothesis was absurd. (he was wrong). Continuum hypothesis was one of Cantor’s favourite ideas.

We will leave that past behind and move to the contribution of Konig in proving the CBS without using the axiom of choice.

..it has its own strangeness: a function that is not necessarily computable – that is, a function for which (for certain inputs) it may not be possible to compute an output in a finite amount of time!

Konig ‘s proof is probably the easiest to understand of all the proofs of CBS. First, let’s understand the basic setup.

In set theory, the CBS theorem is stated as follow:

The CBS theorem states that whenever A and B are sets and there are injective functions

Then it follows that A and B are equivalent, which equally mean that we can find a bijective function between them. So, to prove CBS we hypothesize the two injections and somehow we must construct the bijection.

a one-to-one correspondence

The figure above shows a good picture of our basic hypotheses that A and B are sets and we have two functions, one from A into B, and another from B into A. We will have to build our bijective function in a piecewise manner. This is similar to the Hilbert Hotel that we have previously, but instead of individually moving elements of a set, we move a subset of a set.

If there is a non-empty intersection between A and B, we can use the identity function for that part of the domain of our bijection.

Suppose is an arbitrary element. Since f is defined on all of A, we can compute f(a). Now since f(a) is an element of B, and g is defined on all of B, we can compute g(f(a)) and so on.

We can create an infinite sequence, which alternate back and forth between A and B using the function f and g. This gives us the following sequence,

Note that we can actually extend this sequence further to the left, and this process may stop only when one of the images of f and g fails to be defined,

Now, we’ve seen that every element of the set A and B is contained in one of these sequences. It is easy to see also that these sequences are either disjoint or identical. These two facts together implies that these sequences form a partition of .

We define a bijection, by deciding what it must do on these sequences.

How the sequence we’ve just defined can play out:

1. Upon extending to the left, we may run into a place where one of the inverse functions needed is not defined: we say a sequence is an A-stopper if upon extending to the left we end up on an element of A that has no preimage under g
2. If the inverse functions are always defined within a given sequence there are also two possibilities, (1) the sequence may be finite, or (2) the sequence may be truly infinite. This is a B-stopper.

Finally, we have this definition:

Learn further:

1. Cantor Schroeder Berenstein pt.1
2. Cantor Schroeder Berenstein pt.2
3. The Cantor-Schroeder-Bernstein Theorem

^{Disclaimer: this is a summary of section 8.4 from the book A Gentle Introduction to the Art of Mathematics: by Joe Fields, the content apart from rephrasing is identical, most of the equations are screenshots of the book and the same examples are treated.}

1. A Gentle Introduction to the Art of Mathematics by Joe Field

---

Thank you for reading ...