Or maybe I'm just confused about the definition of cardinality. Please enlighten me.
It's been a while also for me, but if IIRC, it goes like this (let #N be the cardinality of the set N):
When you're reasoning about infinite sets, you say that #A <= #B whenever there is an injective function from A to B. (intuitively, you can "fit" all of A inside B)
Let C be the set of the complex numbers and R be the set of the real numbers. What we'll do is show that #R <= #C and #C <= #R, and, so, #C = #R.
The first part is easy:
f : R -> C
f(x) = x + 0*i
this is clearly injective, and so we have that #R <= #C.
The second part is somewhat tricky, and it resembles the original "infinite hotel room" arguments about infinite sets. We'll first define some auxiliary functions. Let frac be the fractional part of a number and int the integer part. We'll also use two functions that are similar, one which will work on the integer part, and one which will work on the fractional part.
These functions will intersperse the actual digits of the numbers with zeroes, so that we can zip two of them together (and extract them later). The first function, intersperse_int, works like this:
intersperse_int(1234) = 10203040
intersperse_int(100) = 10000
The second function, works in a similar manner, but for the fractional part.
intersperse_frac(0.123) = 0.010203
intersperse_frac(1/3) = 0.03030303...
You might have and idea of what we'll do with these auxiliary functions now. The mapping from C to R is defined as:
g : C -> R
g(a + bi) = intersperse_frac(frac(a)) * 10 + intersperse_int(int(a))) +
intersperse_frac(frac(b)) + intersperse_int(int(b))) / 10
g(3.45 + 13/3i) = 0.4050 + 30 * 10 + 0.0303030303... + 4 = 34.43453030303...
We zipped the numbers together in a way that ensures g is injective. So, #C <= #R, and #C = #R. A similiar trick can be used to prove that every non-degenerate finite interval of the reals has the same cardinality as the whole set. Also weird is the fact that every vector space over the reals has the same cardinality, or, more generally, the cartesian product of two infinite sets does not increase its cardinality (the power set operation does, however)
He took a duck in the face at two hundred and fifty knots.
[ Parent ]