An exercise in transfinite magic
by Dan Shved
In my hometown there is a university called SUSU. And in this university regular math contests (link in Russian) are held, organized by A. Yu. Evnin. The following problem appeared in one of these contests:
The solution is quite straightforward, I am not going to write it down. It is probably enough to say that it heavily exploits the convexity of .
This post is not about problem 1. It is about the next thing that comes to mind:
If you think about this one for a minute, I’m sure you’ll find it much more challenging than problem 1. This whole post is about solving problem 2. If you want to give it a try yourself, this is the last point in the text where you can still do this without knowing the answer.
1. Preliminary stuff
The answer to problem 2: no, it doesn’t. That is, there do exist two distinct functions and such that it is impossible to distinguish between their graphs by measuring the size of intersections with straight lines. I can’t write down formulas for these functions, and I strongly suspect that it is impossible. But it is possible to prove their existence using tools from set theory.
This post is not the right place to develop everything from scratch, so I will use certain well known things without proof. For one, I will compare cardinalities and use intuitive statements about them, for instance “ iff not ”. I will also use Zorn’s lemma and the well-ordering theorem.
Definition. Let be a well-ordered set and . Then is called an initial segment of if for every such that , implies . If in addition then is called a proper initial segment.
Some notation (AFAIK not standard): will mean that is an initial segment in , — that is a proper initial segment. I am not very fond of this particular choice, but WordPress doesn’t have the symbols that I’d prefer. To make things uniform, I will use the following notation for general sets (only in this post): means “is a subset of”, means “is a proper subset of”.
If and , then saying is the same as . In situations like this I will always use , just to remind myself and the reader that these are initial segments and not arbitrary subsets that we’re dealing with.
Some more notation: if , then and .
Exercise 1. If is a well-ordered set then unions and intersections of arbitrary sets of initial segments in are themselves initial segments in .
Definition. Let and be well-ordered sets. is embeddable into if is isomorphic to an initial segment of .
Exercise 4. is embeddable into iff there exists an order-preserving injection .
Proof. Let be the corresponding map for every index . If , then by exercise 5 and agree on . It follows that we can glue all of together into a map . A routine check shows that and is an isomorphism between and .
Proof. Suppose is not embeddable into . By exercise 2 there is a minimal such that is not embeddable into .
By choice of every is embeddable into . Then by lemma 6 is also embeddable into . Clearly, is the maximal initial segment of that is embeddable into . Let be the embedding.
Now take . If then we can extend to an embedding of by sending to . This contradicts to the maximality of . So, . But then is isomorphic to and embeddable into , qed.
Proof. Let’s well-order in an arbitrary way (we can do this by the well-ordering theorem). If is isomorphic to an initial segment of , then clearly and there’s nothing to prove. Therefore, by lemma 7, we can assume that is isomorphic to an initial segment of .
Clearly, . By the premises of the lemma, cannot be a proper initial segment, therefore and , qed.
2. Some cardinal arithmetic
The goal of this section is to prove the following:
For some reason this fact is not as widely known as two special cases:
Both of these can be proved in numerous ways. Here is a way to solve exercise 10 that we will use as a model:
Solution to exercise 10. We can build a bijection by enumerating, or “visiting”, pairs in the following order:
- First, visit .
- Next, visit , then and then .
- Visit , then and in that order.
- Continue indefinitely, visiting at step pairs through and then through .
This way we cover all of in steps, which is exactly what we wanted.
Here is a graphical depiction of this solution:
Let’s generalize this idea to arbitrary well-ordered sets.
Definition. Let be a well-ordered set. Define the corner order on the Cartesian product like this: if any of these conditions hold:
- and ,
- , and .
We will call the set equipped with the corner order the cornered square of .
Remark. You may have noticed that the corner ordering is similar to the lexicographic ordering. In fact, if we define a map by , then the corner order on is induced by from the lexicographic order on .
Exercise 12. If is well-ordered then is also well-ordered.
Exercise 13. Suppose is well-ordered and . Then the order on induced from coincides with the corner order on .
Because of the last exercise we can write whenever without the risk of confusion.
Exercise 14. If is well-ordered and , then .
Proof. Choose an arbitrary . Since has no maximum, there exists a such that . Then clearly . It remains to show that .
Since is an initial segment in and , . We see from the definition of corner ordering that . Since , it follows that and we are done.
Now we are ready to prove lemma 9.
Now, let . Let us show that and . This is trivial if is finite. If is infinite, then by choice of we have . Then , which implies , which in turn implies .
Finally, let be a proper initial segment in . It follows from the previous passage that doesn’t have a maximal element. By lemma 15 there exists a such that . Then we have . By lemma 8 , a contradiction.
This means that our assumption is false and . Clearly, , and by Cantor-Bernstein-Schroeder theorem we have .
3. Doing transfinite constructions on the plane
Proving this lemma is our next step towards solving problem 2. Here is an exercise that demonstrates the connection:
Exercise 18. Assuming lemma 17, show that there exist two distinct subsets in such that for every line we have .
This almost solves the problem! The only obstacle is that sets and in this exercise are not graphs of functions. But this is in fact only a minor technicality, and we will deal with it in the next section. For now, let’s prove lemma 17.
Here’s an informal sketch of what we’ll do. Let’s think of set as a coloring of . Elements of are black, all the other points are white. We will start with an all-white plane and then paint some points black in a series of steps. When we are done, we want there to be exactly two black points on every line.
How would this painting process go? Let’s do what seems natural. Take an arbitrary line , pick two points on and paint them black. Now has two black points on it and every other line on the plane has at most one. So, we pick some other line . has at most one black point on it, so we need to paint some more to make it two. But we must be careful not to paint anything extra on . Therefore, when we choose new points to paint on , we must actually choose them from .
It’s not hard to imagine how this can go further. After steps we have lines , each of them with two black points on it. Every other line on the plane has two black points or less, and the total number of black points is finite. Now we pick the next line and, if necessary, choose several points on it and paint them black. We don’t want to break our “loop invariant”, which is why these new points must be chosen from , where iterates over all lines on the plane that already have two black points on them. There’s only a finite amount of such lines, so is infinite and we have plenty of painting candidates to choose from.
We can go on like this indefinitely. Let’s see where it will lead us. We will end up with a countable collection of lines , each of them having two black points on it, but we won’t have solved the problem, because there will still be lots of “underpainted” lines in that are not in our collection.
We could persist and pick a new line again. Call it (say) . Suppose it has less than two black points on it. Can we still paint some points on black without breaking anything? We can, but now we must be extra careful, because a countable number of lines already have two black points on them, and we cannot touch these lines ever again. This is not critical, because is uncountable, and there’s only a countable number of “forbidden” points on . But still, this starts to look dangerous. Ok, we build , and then probably the next line , and then the next… When will it ever end?
At this point it’s probably best to get off this train heading towards infinity (or maybe “transfinity”) and start doing rigorous math. So, we are now going to turn this sketch into a real proof using Zorn’s lemma. Oh, by the way: here is an absolutely wonderful post about Zorn’s lemma on Tim Gowers’s blog. Anyway, here we go.
Let be the set of all lines in . By exercise 3 we can assume that is well-ordered in such a way that every proper initial segment in has cardinality strictly less than .
Definition. A partial solution is a pair where , , and the following conditions hold:
- For every line we have , and if .
Let be the set of all partial solutions. Let us impose a partial order on like this: if and .
is also a partial solution.
Proof of lemma 17. By exercise 20 is a partially ordered set. It is non-empty because . It satisfies the chain condition by exercise 21. Therefore, by Zorn’s lemma, there exists a maximal partial solution .
Assume that , i.e. is a proper initial segment. By our choice of ordering on , and, by exercise 19, . Now, by definition of partial solutions, is contained in the union of all the lines in , and each of these lines contains exactly two points from . Therefore . By corollary 16 we have .
Let be the set of all the lines that have exactly two points in common with :
Each line in is determined by a pair of points in , therefore . From lemma 9 we deduce that , and .
Finally, let be the minimal line in . Either or . If , then is a partial solution, which contradicts the maximality of . We conclude that , which means that . Now, each line in intersects in at most one point, therefore
Since , it follows that set is infinite. Pick a subset consisting of (that is, one or two) points. A routine check shows that is a partial solution, again contradicting the maximality of .
This contradiction shows that . But then it follows from the definition of partial solutions that has exactly two points in common with each line, and the proof is complete.
4. The solution
For instance, we could go like this: we could make a construction similar to that in lemma 17 and build a set that has only one point in common with each vertical line (i.e. line parallel to ) and two points in common with every other line. Then would be a graph of a function, and so would be any parallel shift of .
This would of course solve problem 2, but there’s a drawback: it is not immediately obvious that such a construction can be carried through. We would have to change the notion of a partial solution, and again check that Zorn’s lemma is applicable, and that it yields the desired result. That’s why I prefer to use a slightly different approach.
Lemma 22. There exists a set on the real projective plane such that for any projective line .
The proof of this lemma goes exactly, word by word, the same as the proof of lemma 17. I could have written this post without lemma 17 at all, talking about lemma 22 from the very beginning. The only reason I didn’t do that is because the introduction of a projective space from the start would seem a bit “out of the blue”. Of course, I’m not asking you to take anything on faith, so here it goes:
For convenience let us call lines in of the form vertical, and — horizontal.
Proof. We can treat as a subset of the projective plane by means of the injection
Lemma 22 guarantees the existence of a set having exactly two points in common with every projective line in . In particular, has two points in common with the line at infinity . By applying an appropriate projective transformation, we can guarantee that these two points are and .
Now, let be an arbitrary projective line distinct from . It is clear that is then an affine line, and each affine line in can be obtained this way. Furthermore, is horizontal iff , and is vertical iff .
From the previous passage it follows that subset has exactly the property that we desire: it has one point in common with every horizontal or vertical (affine) line, and two points in common with every other line.
We can reformulate lemma 24 like this:
Corollary 25. There exists a bijective function such that its graph has exactly two points in common with each line , where .
Now, if we take such a function and (say) , then and are the solution that we’ve been looking for. Done!