Okay, so I have been working through problems in Munkres and I came across an interesting problem tonight. First, a quick refresher on bijective functions.

Recall that a bijective function is one that perfectly matches up elements of two sets. See ::this other paper of mine:: for a more in depth discussion. A quick refresher: Suppose that we have two sets M = {Miles, Coltrane, Mingus} and I = {Bass, Sax, Trumpet}. A function, f, from the set M to the set I is an assignment that intakes one element of M (one musician) and outputs one element of I (one instrument). For example, maybe f(Miles) = Sax. A bijective function is one that is injective (which means that no two musicians get sent to the same instrument, so it is not true that f(Miles) = Sax AND f(Coltrane) = Sax) and surjective (which means that every instrument has a musician assigned to it). In this case, one such bijective function would be f(Miles) = Trumpet, f(Coltrane) = Sax, and f(Mingus) = Bass.

Now, onto the problem:

Let X be the set of two elements {0, 1}. Consider the set . That is, the cartesian product of countably many copies of X. So, members of X look like tuples with infinitely many entries. That is, members of X look like (0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, …). You could also think of members of X as infinite binary strings. Anyway, the problem asks you to find a function that maps bijectively into a proper subset of itself. Wait, what? That doesn’t make any sense! Consider our example above. What if M is bigger than I. Say, M = {Miles, Coltrane, Mingus, Monk} and I={Bass, Sax, Trumpet}. There is no possible way we can make an injective function from M to I, because we will have to send two of the musicians to the same instrument. Similarly, if the set I was bigger than M, there is no way our function could be surjective, because there would be an instrument without a musician. So our problem is crazy! We are trying to find a bijective map between a set S and a proper subset of itself, T. That is, T is smaller than S! Sounds like it’s not possible, right? Well, the whole thing essentially boils down to how crazy infinity is. This example might make it easier to believe that we can (and we will) actually do this.

Example: Consider the natural numbers N={0, 1, 2, 3, 4, …} and consider the even numbers E={0, 2, 4, 6, …}. Here, E is a subset of N, and (in some sense) E is smaller than N, but we can still define the function d: N -> E with d(n) = 2n that is a bijection between these two sets. That is, take a natural number and double it. Every even number is hit and no two natural numbers are mapped to the same even number. Okay, so hopefully now this madness seems plausible.

So, the trick finding the bijection for the problem is to first find a worthy proper subset. Lets turn our attention to the set of all of the binary strings that start with 0. This is certainly a proper subset of since any string that starts with 1 is in X^{\omega} but not in the set that we’re investigating. Now, what happens if we take a binary string from and simply tack a 0 onto the beginning. This makes any string automatically belong to our new set. At this point we might as well give it a name, lets call it Z, for zero. So, the idea is that we take a member of that could look like any infinite binary string like 000111111001011101010111010………, or 11111111111111111111111111………, or 1011011010101010101010101…………., or (you get the idea) and we tack a 0 onto the beginning to get things that look like 0000111111001011101010111010………, or 011111111111111111111111111………, or 01011011010101010101010101…………., or (again, you get the idea). But this is exactly the function we want!!! This is a function . It turns out that its not too hard to check that this is actually a bijective function. I thought that this was cool because in finding this proper subset, we were actually making our set ‘bigger’. What I mean by that is our set Z is really the same as our set , but with another element added on to the front. By ADDING this element, we are getting a set that is SMALLER. This is just another example of how nuts infinity is. For those who know a bit about math, what I’m saying is that .

Now, the fun doesn’t quite end there. If you are an avid reader of my musings, you may be sensing some familiarity here. While its not necessary to go looking, you may find something very similar happening on ::this post::. If reading back doesn’t strike your fancy, I’ll give a quick run down here. Recall that you can build something awesome called a Cantor Set by taking a line segment, removing the middle third, then removing the middle third of each of the remaining line segments, then doing this until, well, forever. The members of the Cantor Set are the ones that survive the cuts at all stages.

One nice way to describe the Cantor Set is to give each member an address as follows. At stage , if the point is in the left segment, write 0. If the point is in the right segment, write 1. At stage , if the point is in the left subsegment of the previous stage, write 0. If the point is in the right subsegment, write 1. Keep doing this forever and what do you get? A BINARY STRING!!! That is, every member of the Cantor Set can be represented by a binary string and every binary string represents a member of the Cantor Set. So what is this problem really asking? It is asking us to map the Cantor Set onto a proper subset of itself! Now that we have a picture to describe it, this seems totally reasonable. The Cantor Set is one of the very first examples of a ::fractal::, and thus exhibits incredible self-similarity. Now, what are we really doing when we put a zero in front of the binary string? Well, the red portion of the diagram represents the branch of members of the Cantor Set whose binary string starts with a zero. What we are doing is taking the entire diagram and shrinking it down by a factor of three and placing it on top of the left branch. It should be easy to imagine that a shrunken version of the entire diagram will fit exactly on top of the left branch.

Anyway, the take away from this problem is that sometimes you have to add stuff on to an infinite set to make it smaller.