The rationals and their initial segments, edited version

Question

This post was inspired by an Alon Amit post on Quora. The Quora problem posed to AA was something like, only slightly more confused than, this: How can the set of initial segments of the rational numbers have a cardinality greater than that of the set of rational numbers themselves? Amit cleared up what seemed to be one confusion in the question, that each initial segment had a greatest element (in which case the cardinalities would indeed be equal) by pointing out that most initial segments of rationals don't have a greatest element, they are open at the top. Amit left it at that, but I thought the paradox wasn't cleared up.

I posted a related question in MSE on 2023/7/27, asking for an intuitive reason for the fact, a proof of which I knew and believed, even though I found the fact itself almost incredible, that the set ℐ of initial segments of ℚ (the rational numbers, with the usual order) is uncountably infinite even though ℚ itself is only countably infinite, but the question was closed on the grounds that it needed details (f)or clarity. (The two people who commented or answered my question before it was closed seemed to understand the question itself quite well, even though their comments and answers didn't cure my puzzlement.)

Let ℐ be the set of open initial segments of ℚ, ordered by inclusion. (Initial segments of ℚ are those sets I ⊆ ℚ which have a rational upper bound and are such that ∀ q,p ∈ ℚ, if q ∈ I & q > p, then p ∈ I.) ℐ is used in the Dedekind cut method of defining the real numbers ℝ on the basis of ℚ . Each I ∈ ℐ defines just one r ∈ ℝ (in Dedekind's definition, r is defined to be I; in modern terminology, r = l.u.b. (least upper bound of) (I)), and each r ∈ ℝ is defined by just one I ≡ the set of q ∈ ℚ such that q < r. Thus, the cardinality | ℝ| of the set of so-defined reals is equal to the cardinality |ℐ| of the set of open initial segments of rationals.

The only way I know of proving that ℝ, and so ℐ, is uncountable uses the arithmetic, metric properties of ℚ that are involved in the other, equivalent way I know of defining ℝ on the basis of ℚ, which is the completion of a metric space involving Cauchy sequences of rationals. This definition allows the representation of reals as infinite sequences of integers, e.g. binary or decimal, the sequences standing for convergent sums of rationals, this allowing Cantor's diagonal argument proof of the uncountability of ℝ. While this procedure also shows the uncountability of ℐ, and each step is fairly intuitively clear, the total procedure is complex enough that the resultant proof of the uncountability of ℐ is to me intuitively less compelling than the, shown by logic to be false, argument that the cardinality of the initial segments ℐ must be the same as the cardinality of the set ℚ that they are initial segments of. Let me sharpen and strengthen that argument.

As one moves down a finite segment of the reals, say from 1 to 0, one passes a countable number of rationals, but, according to correct but unintuitive reasoning, an uncountable number of reals that are the l.u.b.'s of initial segments of those rationals. This is hard enough to imagine. A slightly intuitively even more improbable situation results from realizing that the reals can be put into a 1-1 correspondence with the initial segments of the reals they are l.u.b.'s of. This results in the initial segments of the countable, totally (linearly) ordered set ℚ being in a 1-1, order preserving correspondence with the initial segments of the uncountable, totally (linearly) ordered set ℝ of which ℚ is a proper subset and whose order relation it inherits. It is important to realize that this correspondence is between initial segments of fixed total orders of ℚ and ℝ; reordering them or deleting some of them is not involved, the only thing varying is the upper cutoff point. I find this correspondence imposssible to imagine, and would like to be able to do so at least somewhat better than I can now.

This is a paradox of the Banach-Tarski kind, very peculiar but not really a contradiction, as distinguished from what Russell's paradox is still by many believed to be, but isn't, a contradiction in logic. This initial segment paradox's formulation doesn't even require the Axiom of Choice (as far as I can see), which the B-T paradox is said to require. That this I. S. paradox isn't well-known, or at least isn't commonly mentioned, even among mathematicians, leads me to believe that it may have a simple resolution, and all my going-on is inappropriate.

I have decided that the major cause of my failure to be able to imagine this correspondence is the proof that the initial segments of ℚ form an uncountable set, which proof is logically compelling but in total unintuitive, and I think this is due to the use of metric concepts in it, instead of only the order concepts which are involved in defining those initial segments. Thus I come now to the almost precise request that I am making: I want someone to find or invent a proof using only order (of ℚ and ℝ) concepts (and of course cardinality ideas), with no mention of the arithmetic, metric properties of anything involved (although arithmetic properties of ℚ are the ultimate basis of its order relation), that ℐ, the set of initial segments of the rationals, is uncountable (and enter it as an answer or comment to this post!) Of course, I can't make "using only order concepts" precise, but I think that any not-too-complicated order-based proof that doesn't obviously invoke the arithmetic of rational or real numbers would make the uncountability of ℐ follow much more obviously from its definition based on the order properties of ℚ than does the only proof that I currently know (described above), at least for me. I should add that I don't know that a purely order-based proof of the uncountability of ℐ is possible, or even that the order relations involved entail this uncountability, although I think they do. Also, if someone comes up with some argument different from such a proof that they think would help clarify the situation, that would be welcome. This paradox is implicit in the Dedekind cut method of defining the reals, which I was exposed to years ago, I just didn't think of that method's paradoxical aspects until I read the Alon Amit Quora post. I suspect that, now that I've explained my puzzlement, that puzzlement will be shared by many who read this who didn't share it before.

Answer 1

I think the idea behind your intuition is: As we move along the real number line, at each point $r\in\Bbb R$ we have some initial segment $\{q\in \Bbb Q:q\le r\}$, and this initial segment only changes when we go past an element of $\Bbb Q$, so we can't visit more initial segments than rationals.

The problem with this is that the initial segment changes not only when we go past an individual rational but also when we finish going past an entire infinite set of rationals such as $A=\{q\in\Bbb Q:q<0\}$ or $B=\{q\in\Bbb Q:q^2<2\}$. Since the rationals are densely ordered, this is happening all the time. Sometimes it coincides with passing an individual rational (as with $A$), but usually it doesn't (as with $B$).

Answer 2

I don't know whether this answer will resolve the veridical paradox for you or not, but it at least addresses the issue you mention that the standard diagonal argument doesn't seem to connect in an intuitive way to initial segments.

As nice as the diagonal argument is, you may get more mileage from Cantor's first proof that the reals are uncountable. I modified the proof a bit here to use the language of initial segments of $\mathbb{Q}$ more directly. We'll structure the proof as a game.

---

Setup: Alice and Bob take turns picking rational numbers. Alice starts by picking some $a_1\in\mathbb{Q}$, and then Bob picks $b_1>a_1$. After this, Alice and Bob alternate: each player must pick a rational number greater than all of Alice's previous plays, and less than all of Bob's previous plays. That is, after Alice's $n$-th turn, we have $$a_1<a_2<\cdots<a_{n-1}<a_n<b_{n-1}<\cdots<b_2<b_1,$$ and then Bob picks $b_n$ between $a_n$ and $b_{n-1}$. This continues for all $n\in\mathbb{N}$. If there exists an initial segment of $\mathbb{Q}$ containing every $a_n$ but no $b_n$, then Alice wins; otherwise Bob wins.

Lemma: If there are countably many initial segments of $\mathbb{Q}$, then Bob can win.

Proof: Enumerate the initial segments so that $I_n$ denotes the $n$-th initial segment. To decide what Bob does on his $n$-th turn, we divide into cases:

• If there exists $x\in I_n$ with $a_n < x < b_{n-1}$, set $b_n:=x$ (so $b_n\in I_n$).
• If there is no $x\in I_n$ satisfying $a_n < x < b_{n-1}$, Bob can play any legal move; Alice's next move $a_{n+1}$ will necessarily satisfy $a_n < a_{n+1} < b_{n-1}$, and so $a_{n+1}\notin I_n$.

We see that for every initial segment $I_n$, either it contains $b_n$, or it fails to contain $a_{n+1}$. Thus the condition "contains all of Alice's points and none of Bob's" cannot be satisfied by any initial segment, and Bob wins.

Lemma: Alice always wins.

Proof: The set $I=\{x\in\mathbb{Q}:x\leq a_n\text{ for some }n\}$ is an initial segment that contains all of Alice's points and none of Bob's.

---

A few notes:

• This is still a diagonalization argument in a broader sense: you start by assuming the set can be enumerated, then construct a new element one step at a time, where on the $n$-th step you guarantee that your new element isn't the $n$-th element in the list. (In this case, Bob plays his "winning strategy" to ensure $I\neq I_n$ on step $n$, and then at the end Alice hands you the new element $I$).
• The only facts about $\mathbb{Q}$ we used in this proof is that it's a totally ordered set $S$ with at least two elements such that for all $a,b\in S$ with $a<b$, there exists $x\in S$ with $a<x<b$. So the same proof shows that for any nontrivial totally ordered set with this "in between" property, the collection of intial segments is uncountable.

In summary: the fact that there exists a rational number between any two given rational numbers is exactly what you need to construct an initial segment different from any initial segment in a countable list.