I accept. I ought to because I've delivered a few and felt justified doing so, so I ought to take if I've earned. — tim wood
Rock and roll Brother Tim. Thanks for the kind words. It's all good.
I haven't read the intervening posts so perhaps some of these points have been covered. I did want to toss in my two cents about uncountable bijections, and how the subject of bijections relates to the subject of well-ordering. In short, it doesn't at this level. It's not an unreasonable thing to think, as I came to learn. But bijections are defined between sets; and sets have no inherent order. The sets {a,b,c} and {c,b,a} are the exact same set. Any maps between them, including bijections, pertain only to the elements and not to any order properties the sets might have.
Of course there are ordered sets, along with the
order preserving bijections between them. Among these are the well-ordered sets, which lead to the beautiful topic of the ordinal numbers. I could talk about the ordinals all day. But not right now, because they're peripheral to the subject of basic bijections. I hope you'll take this on faith now, and the following examples will bring out this point. In this post I'll limit myself to discussing bijections.
Now I'm going to walk through six bijections between uncountable sets.
(1) The question arises: Can there be a bijection between uncountable sets?
Suppose there were such a thing. What's the most obvious example we could think of? How about the
identity map on the reals; that is, the function
given by
.
This function should look familiar to everyone who took analytic geometry in high school. Its graph is a straight line through the origin making an angle of 45 degrees or
radians with the positive
-axis. This is such a familiar mathematical object that we never stop to think that it's a bijection between two uncountable sets.
We now have at least one example of a bijection between uncountable sets. And in passing we've proven a theorem.
Theorem: Every set is cardinally equivalent to itself.
Proof: The set's identity function provides the required bijection.
In other words, cardinal equivalence is a
reflexive relation.
(2) Even though the real numbers aren't well ordered, the identity map preserves the usual order on the reals. (The usual order is the one we learned in grade school). So maybe bijections are related to order properties after all??? But no. Consider the bijection
from the reals to itself given by
everywhere
except that
,
, and
.
This bijection does not preserve order, because
but
. And you can see that we could easily cook up far more complicated nested cycles and loops and tricks that would make bijections as complicated as we want. So we can see that order properties are a separate consideration from whether or not a function is a bijection.
By the way we have a familiar name for a bijection from a set to itself: a
permutation. Permutations of finite sets are more familiar to us, but you can permute infinite sets as well. Every permutation of a set is a bijection from that set to itself; and most of them are completely random, they don't preserve order or any other property.
(3) The function between
and
given by
, with inverse function
.
This has already been mentioned earlier in the thread. There are two points of interest.
* This bijection shows that
bijections do not necessarily preserve length. And in general, bijections don't necessarily preserve measure, the abstract generalization of length, area, volume, etc. A circle of radius 1 is bijectively equivalent to a circle of radius 2. Bijections don't preserve measure. Good to know.
* Both
and its inverse
are
continuous in the sense of freshman calculus. Very informally, their graphs can be drawn without lifting your pencil from the paper.
In the mathematical discipline of
topology, two topological spaces are regarded as equivalent if there is such a bi-continuous bijection between them (meaning the bijection and its inverse are both continuous). The intuitive meaning is that we can stretch or shrink or twist one space into the other without ripping or tearing or poking holes. If you've ever seen one of those illustrations of a donut being turned into a coffee cup, that mathematical trick is done using a continuous bijection.
https://en.wikipedia.org/wiki/File:Mug_and_Torus_morph.gif
(4) The continuous bijection between
and
given by
, with inverse
.
The tangent function is usually defined as sine over cosine, but it's more helpful to think of it as the function that inputs an angle, and outputs the slope of the line through the origin making that angle with the positive
-axis. If you think of a clock with a single hand that goes from 6 counterclockwise to 12, as the angle goes from
to
, the slope goes from
to
. That is, the tangent function is a bijection from the open interval
to the entire real line
. Its inverse, the arctangent, maps the entire real line to the the open interval
.
Since both the tangent and the arctangent are continuous, we see that a bounded open interval is topologically equivalent to the entire real line. Not only do bijections fail to preserve finite lengths; they can't even distinguish between finite and infinite lengths. And topology can't tell the difference either. You can take the tiniest imaginable open interval of the real numbers, and stretch it like taffy till it becomes the entire real line.
(5) "Cantor's surprise." For any positive integer
, the
-dimensional Euclidean space
has the same cardinality as the real numbers.
Cantor originally thought that the real numbers had cardinality
; and the plane
had cardinality
, and Euclidean 3-space
had cardinality
, and so forth. [In math,
dimensional space just means the set of all
-tuples of real numbers, with pointwise addition and scalar multiplication by reals, just as with the usual x-y plane and x-y-z space. Nothing to do with "time as the fourth dimension" or rolled-up dimensions in string theory or any other physical interpreation. That's sometimes a point of confusion.]
He was surprised to realize that in fact all finite-dimensional Euclidean spaces have the same cardinality. Here's the proof. We'll show that the open unit interval and the open unit square have the same cardinality. That is, we'll show a bijection between the real numbers strictly between 0 and 1, and the set of ordered pairs in the x-y plane each of whose coordinates are strictly between 0 and 1.
Suppose
is a point in the open unit square with decimal representations
and
respectively. We map the pair
to a single real number by
interleaving the digits to get
.
It's clear that you can reverse this process. Given any real number you can de-interleave its digits to get a pair of real numbers. We can extend the result from the unit interval to the entire real line via the tangent/arctangent. Of course this bijection is highly discontinuous, it has no nice properties at all.
You can clearly interleave
-digits this way, and that's the proof. When Cantor discovered this result he wrote to his friend Dedekind: "I see it but I don't believe it!"
We saw earlier that bijections don't necessarily preserve length or volume. Now we see that bijections don't necessarily preserve dimension. It's good to keep in mind the limitations as well as the utility of bijections.
Quibble: One could note that some real numbers have two distinct decimal representation, such as
, possibly messing up the bijection. But there are only countably many such problematic reals, and we can formalize the principle that "countable sets never make a difference in uncountability arguments." The problem can be fixed.
(6) Can we find a bijection between
and
? There must be one but it's tricky.
First, why must there be a bijection? We've seen earlier that there's a bijection between
and the entire real line. And
and
are both proper subsets of the real line and proper supersets of
. So both of those cardinalities are squeezed between two equal cardinalities. In other words if
is the cardinality of the set
, then:
, but the first and last cardinalities are equal via the tangent/arctangent. So
and
must have the same cardinality; after all they only differ by a point.
If you've seen the story of the Hilbert hotel, you know that you can always shift each guest to the next higher room, in effect "losing a guest." And if you were to move each guest to the next lower-numbered room, the hotel would still be full and you'd have an extra guest with no room! This is the basic idea behind adding or getting rid of endpoints in all these kinds of problems.
In this case we pick out a countable subset of
, and "Hilbert shift" away that pesky 1 at the right end. Here's the function
:
[Something funny about the markup, ignore those brl things, the forum software put them in].
Everything gets mapped to itself; except that 1 goes to 1/2, 1/2 goes to 1/4, 1/4 goes to 1/8, and so on. We've "made the 1 disappear" by Hilbert-shifting it to the "next room" as it were, and we have our bijection.
Here's a picture of what happens. 1 goes to 1/2, 1/2 goes to 1/4, and so forth. Every point has somewhere to go, and nothing replaces the point at 1. It disappears like the guest in the first room of the Hilbert hotel.
