Infinitely many elements between two Dedekind's cuts

I have a problem with an informal argument I found in Pugh's book on real analysis (p.13) concerning Dedekind's cuts (notice that, in a sense, I am extrapolating from the text a formal argument).

Let $x = A|B$ and $y=C|D$ be two Dedekind's cuts, with $x < y$. Hence, $A \subset C$, with $A \neq C$.

"Proposition:" If $x < y$, then $C \setminus A$ is nonempty, and there are infinitely many elements in it.

Proof: From $x < y$ there is a $c_0 \in C \setminus A$. Since the $A$-set of a cut contains no largest element (Pugh is most probably referring to the "left" set of a cut, hence here it is $C$), there is a $c_1 \in C$ such that $c_0 < c_1$, and all the $c \in \mathbb{Q}$ such that $c_0 \leq c \leq c_1$ are in $C \setminus A$.

Thus, my problem is with the fact that here we are dealing with uncountably infinite elements (even if Pugh does not talk about different infinity magnitude), but I do not know how the uncountability pops up, considering the reference is to the rationals $c \in \mathbb{Q}$.

I do see there is another layer of infinity, namely that there is a chain $c_0 < c_1 < c_2 < \dots$ that goes on. But still, I do not find how to make the jump to the uncountability.

Any help is greatly appreciated.
Thank you for your time.

• Where in your quote did you see the word "uncountable"? I only see "infinitely many" which can also mean a countable infinity. And indeed, between any two rational numbers, there are countably infinitely many other rational numbers. – LutzL Nov 30 '16 at 17:24
• @LutzL Indeed, it is not a quote, but just a "formal" translation of the argument. Actually, the point of my question was answered by Noah Schweber below. – Kolmin Nov 30 '16 at 18:52
• @LutzL Actually, another part of the question that is not addressed in the answer below (I pointed this in a comment below the answer) is if we get the same result (uncountably many elements) via the argument based on the chain $c_0 < c_1 < c_2 < \dots$. – Kolmin Nov 30 '16 at 18:59

If I understand correctly, you are asking how to prove that if $x<y$ are Dedekind cuts, then there are uncountably many Dedekind cuts $z$ with $x<z<y$ - the issue being that Dedekind cuts seem to come from rationals, and there are only countably many of those.

The point is that Dedekind cuts don't come from rationals, but rather sets of rationals, and there are uncountably many of these. The proof I give below is essentially Cantor's original proof of the uncountability of the reals:

Suppose there were only countably many Dedekind cuts between $x$ and $y$. List them as $$\{(E_n\vert F_n): n\in\mathbb{N}\},$$ and say that a rational interval $(p, q)$ is $n$-good if

• $x<p<q<y$ (so $(p, q)$ is a nonempty subset of the region we're looking at),

and

• $(p, q)\subseteq E_n$ or $(p, q)\subseteq F_n$ (so the $n$th Dedekind cut doesn't "split" this interval).

The key point is the following:

Exercise: For every nonempty rational interval $(p, q)$ and every $n$, there is a subinterval $(p', q')\subseteq (p, q)$ which is $n$-good.

So we can build a sequence of rational intervals $(p_n, q_n)$ such that

• $(p_0, q_0)\supseteq (p_1, q_1)\supseteq ... \supseteq (p_n, q_n)\supseteq (p_{n+1}, q_{n+1})\supseteq . . .$ (they're getting smaller), and

• Each $(p_n, q_n)$ is $n$-good.

Now let $G_0=\{r\in\mathbb{Q}: \exists n(r<p_n)\}$, $H_0=\{r\in\mathbb{Q}: \exists n(q_n<r)\}$. Every element of $H_0$ is bigger than every element of $G_0$, $G_0$ has no maximal element, and $H_0$ has no minimal element;so we can find a Dedekind cut $(G\vert H)$ with $G_0\subseteq G$ and $H_0\subseteq H$.

Now: Can $(G\vert H)=(E_n\vert F_n)$ for any $n$? HINT: $(G\vert H)$ lies inside the interval $(p_n, q_n)$ . . .

• Note that when I write e.g. "$x<q$" for $x$ a Dedekind cut and $q$ a rational, I'm conflating $q$ with its Dedekind cut $Cut(q)=(\{r\in\mathbb{Q}: r<q\}\vert\{r\in\mathbb{Q}: r>q\})$. Also I'm denoting a cut by "$(X\vert Y)$" as opposed to "$X\vert Y$" - I find it slightly more readable this way. – Noah Schweber Nov 30 '16 at 17:29
• First of all, thanks a lot for the superdetailed answer. Thus, I will carefully read it. Just one – first – quick question: can we get to the result that there are (uncountably) infinite many cuts via the chain I was referring to, i.e. $c_0 < c_1 < c_2 < \dots$? This would be a different way in comparison to Pugh, but it seems to me we end up getting the same thing. – Kolmin Nov 30 '16 at 18:54
• @kolmin no, that will only get us countably many. between any two D cuts is a rational, so a discrete chain like that can't be uncountable – Noah Schweber Nov 30 '16 at 19:19
• But that's a chain of cuts, not rational cuts. Why does it not work? – Kolmin Nov 30 '16 at 20:46
• @Kolmin Like I said, there's a rational between each pair of cuts. In particular, this gets us an injection from the cuts you're looking at to the rationals: for each cut $z$, let $q_z$ be some rational between $z$ and the "next" cut in the sequence. As long as every cut has a next cut, this map will be injective. So any uncountable set of cuts has to be "non-sequential": there have to be lots of cuts with no "next cut". – Noah Schweber Nov 30 '16 at 20:55