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 $f: \mathbb {R} \to \mathbb {R}$ has the following property: every straight line on the plane $\mathbb {R}^2$ intersects the graph of $f$ and the parabola $y = x^2$ at the same number of points. Prove that $f(x) = x^2$ for every $x \in \mathbb {R}$ .

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 $y = x^2$ .

This post is not about problem 1. It is about the next thing that comes to mind:

Problem 2. Two functions $f, g: \mathbb {R} \to \mathbb {R}$ have graphs $F$ and $G$ such that for every straight line $l \subset \mathbb {R}^2$ : $|l \cap F| = |l \cap G| < \infty$ . Does it follow that $f$ and $g$ 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 $f$ and $g$ 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 “ $|A| < |B|$ iff not $|B| \leqslant |A|$ ”. I will also use Zorn’s lemma and the well-ordering theorem.

Definition. Let $X$ be a well-ordered set and $P \subset X$ . Then $P$ is called an initial segment of $X$ if for every $x,y \in X$ such that $x \leq y$ , $y \in P$ implies $x \in P$ . If in addition $P \neq X$ then $P$ is called a proper initial segment.

Some notation (AFAIK not standard): $P \sqsubseteq X$ will mean that $P$ is an initial segment in $X$ , $P \sqsubset X$ — that $P$ is a proper initial segment. I am not very fond of this particular choice, but WordPress $\LaTeX$ 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): $\subseteq$ means “is a subset of”, $\subset$ means “is a proper subset of”.

If $P\sqsubseteq X$ and $Q \sqsubseteq X$ , then saying $P \subseteq Q$ is the same as $P \sqsubseteq Q$ . In situations like this I will always use $\sqsubseteq$ , 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 $a,b \in X$ , then $[a,b] = \{ x \in X\, |\, a \leqslant x \leqslant b\}$ and $[a,b) = \{ x \in X\, |\, a \leqslant x < b\}$ .

Exercise 1. If $X$ is a well-ordered set then unions and intersections of arbitrary sets of initial segments in $X$ are themselves initial segments in $X$ .

Exercise 2. If $X$ is a well-ordered set and $\mathcal{X} = \{ P\, |\, P \sqsubseteq X\}$ , then $\mathcal{X}$ is itself well-ordered by relation $\sqsubseteq$ .

Exercise 3. Every set $X$ can be well-ordered in such a way that for every $P \sqsubset X$ we have $|P|<|X|$ . (Assume that we already have the well-ordering theorem).

Definition. Let $X$ and $Y$ be well-ordered sets. $X$ is embeddable into $Y$ if $X$ is isomorphic to an initial segment of $Y$ .

Exercise 4. $X$ is embeddable into $Y$ iff there exists an order-preserving injection $\psi : X \to Y$ .

Exercise 5. If $X$ and $Y$ are well-ordered sets then $X$ can be embeddable into $Y$ in at most one way. More precisely, there cannot exist more than one map $\varphi : X \to Y$ such that $\varphi (X) \sqsubseteq Y$ and $\varphi$ is an isomorphism between $X$ and $\varphi (X)$ .

Lemma 6. Suppose $X$ and $Y$ are well-ordered, and $(P_ i)_{i \in I}$ is a collection of initial segments in $X$ . If each $P_ i$ is embeddable into $Y$ then $Q=\bigcup _{i \in I} P_ i$ is also embeddable into $Y$ .

Proof. Let $\varphi _ i$ be the corresponding map $P_ i \to Y$ for every index $i$ . If $P_ i \sqsubseteq P_ j$ , then by exercise 5 $\varphi _ i$ and $\varphi _ j$ agree on $P_ i$ . It follows that we can glue all of $\varphi _ i$ together into a map $\varphi : Q \to Y$ . A routine check shows that $\varphi (Q) \sqsubseteq Y$ and $\varphi$ is an isomorphism between $Q$ and $\varphi (Q)$ .

Lemma 7. If $X$ and $Y$ are well-ordered sets, then $X$ is embeddable into $Y$ or $Y$ is embeddable into $X$ .

Proof. Suppose $X$ is not embeddable into $Y$ . By exercise 2 there is a minimal $P \sqsubseteq X$ such that $P$ is not embeddable into $Y$ .

By choice of $P$ every $R \sqsubset P$ is embeddable into $Y$ . Then by lemma 6 $Q = \bigcup _{R \sqsubset P} R$ is also embeddable into $Y$ . Clearly, $Q$ is the maximal initial segment of $X$ that is embeddable into $Y$ . Let $\varphi :Q \to Y$ be the embedding.

Now take $x = \min (X \setminus Q)$ . If $\varphi (Q) \sqsubset Y$ then we can extend $\varphi$ to an embedding of $Q \cup \{ x\}$ by sending $x$ to $\min (Y \setminus \varphi (Q))$ . This contradicts to the maximality of $Q$ . So, $\varphi (Q) = Y$ . But then $Y$ is isomorphic to $Q$ and embeddable into $X$ , qed.

Lemma 8. Suppose $X$ and $Y$ are sets, and $X$ is well-ordered. Suppose also that for every $P \sqsubset X$ we have $|P| < |Y|$ . Then $|X| \leqslant |Y|$ .

Proof. Let’s well-order $Y$ in an arbitrary way (we can do this by the well-ordering theorem). If $X$ is isomorphic to an initial segment of $Y$ , then clearly $|X| \leqslant |Y|$ and there’s nothing to prove. Therefore, by lemma 7, we can assume that $Y$ is isomorphic to an initial segment $P$ of $X$ .

Clearly, $|P|=|Y|$ . By the premises of the lemma, $P$ cannot be a proper initial segment, therefore $P=X$ and $|X|=|Y|$ , qed.

2. Some cardinal arithmetic

The goal of this section is to prove the following:

Lemma 9. If $X$ is an infinite set then $|X \times X| = |X|$ .

For some reason this fact is not as widely known as two special cases:

Exercise 10. Prove that $|\mathbb {N} \times \mathbb {N}| = |\mathbb {N}|$ .

Exercise 11. Prove that $|\mathbb {R} \times \mathbb {R}| = |\mathbb {R}|$ .

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 $\mathbb {N} \to \mathbb {N} \times \mathbb {N}$ by enumerating, or “visiting”, pairs $(m,n) \in \mathbb {N} \times \mathbb {N}$ in the following order:

First, visit $(1,1)$ .
Next, visit $(1,2)$ , then $(2,1)$ and then $(2,2)$ .
Visit $(1,3),\, (2,3)$ , then $(3,1),\, (3,2)$ and $(3,3)$ in that order.
Continue indefinitely, visiting at $i^{th}$ step pairs $(1,i)$ through $(i-1, i)$ and then $(i,1)$ through $(i,i)$ .

This way we cover all of $\mathbb {N} \times \mathbb {N}$ in $\mathbb {N}$ 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 $X$ be a well-ordered set. Define the corner order on the Cartesian product $X \times X$ like this: $(x,y) \leqslant (x',y')$ if any of these conditions hold:

$\max \{ x,y\} < \max \{ x',y'\}$ ,
$\max \{ x,y\} = \max \{ x',y'\}$ and $x < x'$ ,
$\max \{ x,y\} = \max \{ x',y'\}$ , $x = x'$ and $y \leqslant y'$ .

We will call the set $X\urcorner = X \times X$ equipped with the corner order the cornered square of $X$ .

Remark. You may have noticed that the corner ordering is similar to the lexicographic ordering. In fact, if we define a map $f: X \times X \to X \times X \times X$ by $f(x,y)=\left(\max \{ x,y\} , x, y\right)$ , then the corner order on $X \times X$ is induced by $f$ from the lexicographic order on $X \times X \times X$ .

Exercise 12. If $X$ is well-ordered then $X\urcorner$ is also well-ordered.

Exercise 13. Suppose $X$ is well-ordered and $Y \subseteq X$ . Then the order on $Y \times Y$ induced from $X\urcorner$ coincides with the corner order on $Y \times Y$ .

Because of the last exercise we can write $Y\urcorner \subseteq X\urcorner$ whenever $Y \subseteq X$ without the risk of confusion.

Exercise 14. If $X$ is well-ordered and $P \sqsubseteq X$ , then $P\urcorner \sqsubseteq X\urcorner$ .

Lemma 15. Suppose $X$ is a well-ordered set without a maximal element, and $D \sqsubset X\urcorner$ . Then there exists a proper initial segment $P \sqsubset X$ such that $D \sqsubseteq P\urcorner$ .

Proof. Choose an arbitrary $(x,y) \in X\urcorner \setminus D$ . Since $X$ has no maximum, there exists a $z \in X$ such that $\max \{ x,y\} <z$ . Then clearly $[\min X, z) \sqsubset X$ . It remains to show that $D \sqsubseteq [\min X, z)\urcorner$ .

Since $D$ is an initial segment in $X\urcorner$ and $(x,y) \not\in D$ , $D \sqsubseteq \left[\min X^\urcorner , (x,y)\right)$ . We see from the definition of corner ordering that $D \sqsubseteq [\min X, \max \{ x,y\} ]\urcorner$ . Since $\max \{ x,y\} < z$ , it follows that $D \sqsubseteq [\min X, z)\urcorner$ and we are done.

Now we are ready to prove lemma 9.

Proof of lemma 9. Let $X$ be an infinite set. Let us well-order $X$ in an arbitrary way and suppose that $|X\urcorner | > |X|$ . By exercise 2 there exists a minimal initial segment $P \sqsubseteq X$ such that $P$ is infinite and $|P\urcorner | > |P|$ .

Now, let $Q \sqsubset P$ . Let us show that $|Q| < |P|$ and $|Q\urcorner | < |P|$ . This is trivial if $Q$ is finite. If $Q$ is infinite, then by choice of $P$ we have $|Q\urcorner | \leqslant |Q|$ . Then $|Q\urcorner | \leqslant |Q| \leqslant |P| < |P\urcorner |$ , which implies $|Q| < |P|$ , which in turn implies $|Q\urcorner | < |P|$ .

Corollary 16. If a set $X$ is infinite and $|Y| \leqslant |X|$ , then $|X \times Y| = |X \sqcup Y| = |X|$ .

3. Doing transfinite constructions on the plane

Lemma 17. There exists a set $A \subset \mathbb {R}^2$ such that every line $l \subset \mathbb {R}^2$ has exactly two points in common with $A$ .

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 $A, B$ in $\mathbb {R}^2$ such that for every line $l \subset \mathbb {R}^2$ we have $|l \cap A| = |l \cap B| < \infty$ .

This almost solves the problem! The only obstacle is that sets $A$ and $B$ 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 $A$ as a coloring of $\mathbb {R}^2$ . Elements of $A$ are black, all the other points are white. We will start with an all-white plane $\mathbb {R}^2$ 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 $l_1 \subset \mathbb {R}^2$ , pick two points on $l_1$ and paint them black. Now $l_1$ has two black points on it and every other line on the plane has at most one. So, we pick some other line $l_2$ . $l_2$ 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 $l_1$ . Therefore, when we choose new points to paint on $l_2$ , we must actually choose them from $l_2 \setminus l_1$ .

It’s not hard to imagine how this can go further. After $i$ steps we have lines $l_1,\, l_2,\ldots ,l_ i$ , 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 $l_{i+1}$ 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 $l_{i+1} \setminus \bigcup m$ , where $m$ 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 $l_{i+1} \setminus \bigcup m$ 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 $(l_ i)_{i \in \mathbb {N}}$ , 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 $\mathbb {R}^2$ that are not in our collection.

We could persist and pick a new line again. Call it (say) $l_\omega$ . Suppose it has less than two black points on it. Can we still paint some points on $l_\omega$ 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 $l_\omega$ is uncountable, and there’s only a countable number of “forbidden” points on $l_\omega$ . But still, this starts to look dangerous. Ok, we build $l_\omega$ , and then probably the next line $l_{\omega + 1}$ , 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 $L$ be the set of all lines in $\mathbb {R}^2$ . By exercise 3 we can assume that $L$ is well-ordered in such a way that every proper initial segment in $L$ has cardinality strictly less than $L$ .

Exercise 19. $|L| = |\mathbb {R}|$ . (Hint: use exercise 11 or lemma 9).

Definition. A partial solution is a pair $(P,B)$ where $P \sqsubseteq L$ , $B \subseteq \mathbb {R}^2$ , and the following conditions hold:

$B \subseteq \bigcup _{l \in P}l$ .
For every line $l \subset \mathbb {R}^2$ we have $|l \cap B| \leqslant 2$ , and $|l \cap B| = 2$ if $l \in P$ .

Let $\mathcal{X}$ be the set of all partial solutions. Let us impose a partial order $\leqslant$ on $\mathcal{X}$ like this: $(P, B) \leqslant (P', B')$ if $P \sqsubseteq P'$ and $B \subseteq B'$ .

Exercise 20. Check that $\leqslant$ is indeed a partial order on $\mathcal{X}$ .

Exercise 21. If $\mathcal{Y} = \left\{ (P_ j, B_ j) \right\} _{j \in J}$ is a nonempty chain of partial solutions (i.e. a totally ordered subset of $\mathcal{X}$ ), then pair

$\displaystyle \left(\bigcup _{j \in J} P_ j, \bigcup _{j \in J} B_ j\right)$

is also a partial solution.

Proof of lemma 17. By exercise 20 $\mathcal{X}$ is a partially ordered set. It is non-empty because $(\varnothing ,\varnothing ) \in \mathcal{X}$ . It satisfies the chain condition by exercise 21. Therefore, by Zorn’s lemma, there exists a maximal partial solution $(P, A) \in \mathcal{X}$ .

Assume that $P \neq L$ , i.e. $P$ is a proper initial segment. By our choice of ordering on $L$ , $|P| < |L|$ and, by exercise 19, $|P| < |\mathbb {R}|$ . Now, by definition of partial solutions, $A$ is contained in the union of all the lines in $P$ , and each of these lines contains exactly two points from $A$ . Therefore $|A| \leqslant |P \times \{ 0,1\} |$ . By corollary 16 we have $|A| \leqslant |P| < |\mathbb {R}|$ .

Let $K$ be the set of all the lines that have exactly two points in common with $A$ :

$\displaystyle K = \left\{ l \in L\, |\, |l \cap A| = 2 \right\} .$

Each line in $K$ is determined by a pair of points in $A$ , therefore $|K| \leqslant |A \times A|$ . From lemma 9 we deduce that $|K| \leqslant |A|$ , and $|K| < |\mathbb {R}|$ .

Finally, let $l$ be the minimal line in $L \setminus P$ . Either $|l \cap A| = 2$ or $|l \cap A| < 2$ . If $|l \cap A| = 2$ , then $(P \cup \{ l\} , A)$ is a partial solution, which contradicts the maximality of $(P,A)$ . We conclude that $|l \cap A| < 2$ , which means that $l \not\in K$ . Now, each line in $K$ intersects $l$ in at most one point, therefore

$\displaystyle \left| l \cap \bigcup _{k \in K} k\right| \leqslant |K| < |\mathbb {R}|.$

Since $|l| = |\mathbb {R}|$ , it follows that set $l \setminus \bigcup _{k \in K} k$ is infinite. Pick a subset $\Delta \subset l \setminus \bigcup _{k \in K} k \setminus A$ consisting of $2 - |l \cap A|$ (that is, one or two) points. A routine check shows that $(P \cup \{ l\} ,A \cup \Delta )$ is a partial solution, again contradicting the maximality of $(P,A)$ .

This contradiction shows that $P = L$ . But then it follows from the definition of partial solutions that $A$ 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 $A$ and $B$ 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 $A \subset \mathbb {R}^2$ that has only one point in common with each vertical line (i.e. line parallel to $\{ 0\} \times \mathbb {R}$ ) and two points in common with every other line. Then $A$ would be a graph of a function, and so would be any parallel shift of $A$ .

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 $A \subset \mathbb {R}P^2$ on the real projective plane such that $|A \cap l| = 2$ for any projective line $l \subset \mathbb {R}P^2$ .

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 $\mathbb {R}^2$ of the form $\{ x\} \times \mathbb {R}$ vertical, and $\mathbb {R}\times \{ y\}$ — horizontal.

Lemma 24. There exists a set $B \subset \mathbb {R}^2$ such that for every line $l \subset \mathbb {R}^2$ we have $|B \cap l| = 1$ if $l$ is vertical or horizontal, and $|B \cap l| = 2$ otherwise.

Proof. We can treat $\mathbb {R}^2$ as a subset of the projective plane $\mathbb {R}P^2$ by means of the injection

$\displaystyle i:\mathbb {R}^2 \to \mathbb {R}P^2 \quad ,\quad (x,y) \to x:y:1.$

Lemma 22 guarantees the existence of a set $A$ having exactly two points in common with every projective line in $\mathbb {R}P^2$ . In particular, $A$ has two points in common with the line at infinity $l_\infty = \left\{ x:y:0\, |\, (x,y) \in \mathbb {R}^2\setminus \{ (0,0)\} \right\}$ . By applying an appropriate projective transformation, we can guarantee that these two points are $h = 1:0:0$ and $v = 0:1:0$ .

Now, let $l$ be an arbitrary projective line distinct from $l_\infty$ . It is clear that $l \cap \mathbb {R}^2$ is then an affine line, and each affine line in $\mathbb {R}^2$ can be obtained this way. Furthermore, $l \cap \mathbb {R}^2$ is horizontal iff $h \in l$ , and $l \cap \mathbb {R}^2$ is vertical iff $v \in l$ .

From the previous passage it follows that subset $B = A \cap \mathbb {R}^2 \subset \mathbb {R}^2$ 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 $f: \mathbb {R} \to \mathbb {R}$ such that its graph $F$ has exactly two points in common with each line $y = \alpha x + \beta$ , where $\alpha \neq 0$ .

Now, if we take such a function $f$ and (say) $g: x \to f(x)+1$ , then $f$ and $g$ are the solution that we’ve been looking for. Done!

One Comment to “An exercise in transfinite magic”

手機外殼 says:

June 15, 2013 at 8:45 am

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.

Dan Shved