We’ve discussed previously about the equivalence relation determined by Cantor’s definition of set equivalence.
We have encountered things like
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.
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
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.
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.
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
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 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.
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
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,
How the sequence we’ve just defined can play out:
Finally, we have this definition:
Learn further:
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.
Thank you for reading ...
