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:
Problem 1. A function has the following property: every straight line on the plane
intersects the graph of
and the parabola
at the same number of points. Prove that
for every
.
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:
Problem 2. Two functions have graphs
and
such that for every straight line
:
. Does it follow that
and
are the same function?
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
.
Exercise 2. If is a well-ordered set and
, then
is itself well-ordered by relation
.
Exercise 3. Every set can be well-ordered in such a way that for every
we have
. (Assume that we already have the well-ordering theorem).
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
.
Exercise 5. If and
are well-ordered sets then
can be embeddable into
in at most one way. More precisely, there cannot exist more than one map
such that
and
is an isomorphism between
and
.
Lemma 6. Suppose and
are well-ordered, and
is a collection of initial segments in
. If each
is embeddable into
then
is also embeddable into
.
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
.
Lemma 7. If and
are well-ordered sets, then
is embeddable into
or
is embeddable into
.
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.
Lemma 8. Suppose and
are sets, and
is well-ordered. Suppose also that for every
we have
. Then
.
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:
Lemma 9. If is an infinite set then
.
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
.
Lemma 15. Suppose is a well-ordered set without a maximal element, and
. Then there exists a proper initial segment
such that
.
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.
Proof of lemma 9. Let be an infinite set. Let us well-order
in an arbitrary way and suppose that
. By exercise 2 there exists a minimal initial segment
such that
is infinite and
.
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
.
Corollary 16. If a set is infinite and
, then
.
3. Doing transfinite constructions on the plane
Lemma 17. There exists a set such that every line
has exactly two points in common with
.
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
.
Exercise 19. . (Hint: use exercise 11 or lemma 9).
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
.
Exercise 20. Check that is indeed a partial order on
.
Exercise 21. If is a nonempty chain of partial solutions (i.e. a totally ordered subset of
), then pair
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
As I mentioned earlier, exercise 18 almost solves problem 2, but not quite, because sets and
in that exercise are not graphs of functions. There are several ways to fix this.
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:
Exercise 23. Make sure that the proof of lemma 17 also works for lemma 22.
For convenience let us call lines in of the form
vertical, and
— horizontal.
Lemma 24. There exists a set such that for every line
we have
if
is vertical or horizontal, and
otherwise.
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!
I’ve study several great stuff right here. Certainly worth bookmarking for revisiting. I surprise how much effort you put to make such a magnificent informative site.