The most commonly presented proof the uncountability of the reals is the diagonalization argument, using decimal representations. While clearly valid, this has never been particularly satisfying to me. Perhaps I am unfairly biased against decimal representations.

Recently, studying the p-adics has introduced me to the concept of a "completion", of which the reals are an example. Every real number is an equivalence class of Cauchy sequences of rationals (and can be thought of as the limit of those sequences). This seems like it ought to almost invoke Cantor's Theorem somehow: the set of possible Cauchy sequences of rationals ought to be more numerous than the set of rationals in the same way P(S) has greater cardinality than S. Is it possible to show that the equivalence classes of Cauchy sequences of rationals (and thus, the reals) are uncountable by such an argument? Or even just that the set of Cauchy sequences is uncountable?

I've made some attempts in the "obvious" way, trying to directly mirror the proof of Cantor's Theorem, but this runs into several problems. Instead of constructing the set of naturals not contained in their image, we'd want to construct a sequence of rationals (and if we're dealing with equivalence classes, we can't even say "the set of rationals which are not an element of their mapped sequence"). Since it's a sequence instead of a set, we'd need some way to decide what order those rationals should go in. Worse, such a sequence isn't guaranteed to be Cauchy, which makes it harder to find a contradiction.

It's pretty easy to show that each equivalence class is uncountable by a diagonalization argument. But of course, that's what I'm trying to avoid, haha.

## Completions, Cauchy sequences, and countability

**Moderators:** gmalivuk, Moderators General, Prelates

### Completions, Cauchy sequences, and countability

No, even in theory, you cannot build a rocket more massive than the visible universe.

### Re: Completions, Cauchy sequences, and countability

Meteoric wrote:Perhaps I am unfairly biased against decimal representations.

use binary then :p

Meteoric wrote:the set of possible Cauchy sequences of rationals ought to be more numerous than the set of rationals in the same way P(S) has greater cardinality than S.

Well, that part seems trivial, but the cardinality of cauchy sequences is at least as high as the cardinality of equivalence classes of cauchy sequences, so that result alone wouldn't tell you much about the cardinality of the reals.

How would you prove it? I think diagonalization works, but it's more tricky than cantor's original proof. You have to construct a sequence not contained in the countable set, and constructing it in such a way that you can still prove it to be cauchy will get verbose. Realizing that a decimal representation is just a kind of cauchy sequence, you're trying to create a more general proof for a weaker result. I'm not sure if that's an improvement.

If you want to prove it on the equivalence classes, I have no idea how you'd do that. Diagonalization could only work if you could map each equivalence class to a representative sequence from a smaller set. Like, for example, using the decimal expansion...

### Re: Completions, Cauchy sequences, and countability

I don't know how to write such a proof that mirrors Cantor's argument, since non-equivalence is a tail condition, and hence you can't pick only one sequence member per equivalence class you're trying to avoid. And while I can pretty easily construct a sequence that isn't any of the equivalence classes (by interleaving tails), I don't know how to do so while making sure it's Cauchy. Of course, you could always just calculate the appropriate decimal position of each equivalence class (by seeing what appropriately widthed interval a sample member of each class lives in) for the original Cantor diagonal argument and then present the sequence of partial sums for the decimal representation the original Cantor diagonal argument gives, but that seems like maybe not what you're looking for.

(∫|p|

Thanks, skeptical scientist, for knowing symbols and giving them to me.

^{2})(∫|q|^{2}) ≥ (∫|pq|)^{2}Thanks, skeptical scientist, for knowing symbols and giving them to me.

### Re: Completions, Cauchy sequences, and countability

Maybe I'm misinterpreting your dissatisfaction, but isn't Cantor's theorem also a diagonalisation argument?

If you identify a subset of S with its characteristic function S -> {0, 1}, then it's probably slightly clearer. Given an injective function f: S -> P(S), you can lay out all of the characteristic functions in a table, like so.

So, in this example, f(s0) is a subset of S containing s0 and s2, but not s1; f(s1) is a subset of S containing s1, but not s0 or s2; and f(s2) is a subset of S containing s0, s1 and s2. Hopefully, it's clear what's going on.

Then, to construct the subset which gives you your contradiction, you just take the diagonal and negate each element. It seems to me that this is almost identical in form to the diagonalisation proof of the uncountability of the reals. You're just concerned with functions whose codomain is the set {0, 1} rather than the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

If you identify a subset of S with its characteristic function S -> {0, 1}, then it's probably slightly clearer. Given an injective function f: S -> P(S), you can lay out all of the characteristic functions in a table, like so.

Code: Select all

` s0 s1 s2 ..`

s0 1 0 1 ..

s1 0 1 0 ..

s2 1 1 1 ..

.. .. .. .. ..

Then, to construct the subset which gives you your contradiction, you just take the diagonal and negate each element. It seems to me that this is almost identical in form to the diagonalisation proof of the uncountability of the reals. You're just concerned with functions whose codomain is the set {0, 1} rather than the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

- jestingrabbit
- Factoids are just Datas that haven't grown up yet
**Posts:**5967**Joined:**Tue Nov 28, 2006 9:50 pm UTC**Location:**Sydney

### Re: Completions, Cauchy sequences, and countability

@OP: are you familiar with the first proof of uncountability that cantor wrote?

https://en.wikipedia.org/wiki/Georg_Can ... nd_theorem

It does produce two Cauchy sequences, and I think its very nearly what you want.

https://en.wikipedia.org/wiki/Georg_Can ... nd_theorem

It does produce two Cauchy sequences, and I think its very nearly what you want.

ameretrifle wrote:Magic space feudalism is therefore a viable idea.

### Re: Completions, Cauchy sequences, and countability

benneh wrote:Maybe I'm misinterpreting your dissatisfaction, but isn't Cantor's theorem also a diagonalisation argument?

Huh, you're right! I hadn't thought of it that way before.

Diagonalization on decimal representations feels kind of hacked together, because you need to invoke the additional fact that decimal representations are unique (except repeating (base-1)s, which you must exclude). But this, and diagonalization in general, is growing on me.

jestingrabbit wrote:@OP: are you familiar with the first proof of uncountability that cantor wrote?

https://en.wikipedia.org/wiki/Georg_Can ... nd_theorem

It does produce two Cauchy sequences, and I think its very nearly what you want.

Ooh, I like this one. Thank you!

No, even in theory, you cannot build a rocket more massive than the visible universe.

- LucasBrown
**Posts:**299**Joined:**Thu Apr 15, 2010 2:57 am UTC**Location:**Poway, CA

### Re: Completions, Cauchy sequences, and countability

If it's just decimals that you don't like, then I recommend using continued fractions instead. There is a 1-to-1 correspondence between infinite simple continued fractions and irrational numbers: each infinite SCF converges to a single value, and each irrational number has a unique SCF that represents it. We therefore don't have to worry about the 0.99999... == 1 thing. Furthermore, truncating an SCF produces a rational number, and truncating a given SCF at a later point produces a rational that is strictly closer to the limit than a truncation at an earlier point. This is also true of decimals, but SCF convergents alternate between over- and under-estimating the limit, which bears some resemblance to Dedekind cuts and reminds us that we're working with the completion of the rationals.

- Yakk
- Poster with most posts but no title.
**Posts:**11129**Joined:**Sat Jan 27, 2007 7:27 pm UTC**Location:**E pur si muove

### Re: Completions, Cauchy sequences, and countability

You can rebuild the decimal argument in cauchy sequences.

We take f:N->Q and for each n, we pick an element e_n of Q that is both far from f(n), not equal to any other e_n, and collectively is Cauchy. Which is what the decimal one does.

We can make it strictly increasing to avoid e_n colliding. So e_{n+1} is either e_n + 1/5^n if f(n) >= e_n + 2/5^n, or e_n + 3/5^n otherwise.

This is bounded above by sum (3 / 5^i), and below by 0, so showing it is Cauchy should be easy.

It is strictly increasing, so if e_n >= f(n) then it is bounded away from it by 1/5^(n+1).

If e_n < f(n), then f(n) -e_n >= 1/5^n. 3 * Sum (i = n+1 to infinity) 1/5^n is 3 * (1/5^(n+1) * 1/(1-1/5)) = 12/25 * 1/5^n < 1/5^n.

So the Cauchy sequence e_n does not converge to any f(n).

You might notice that this is the decimal argument (well, base 5) basically restated.

We take f:N->Q and for each n, we pick an element e_n of Q that is both far from f(n), not equal to any other e_n, and collectively is Cauchy. Which is what the decimal one does.

We can make it strictly increasing to avoid e_n colliding. So e_{n+1} is either e_n + 1/5^n if f(n) >= e_n + 2/5^n, or e_n + 3/5^n otherwise.

This is bounded above by sum (3 / 5^i), and below by 0, so showing it is Cauchy should be easy.

It is strictly increasing, so if e_n >= f(n) then it is bounded away from it by 1/5^(n+1).

If e_n < f(n), then f(n) -e_n >= 1/5^n. 3 * Sum (i = n+1 to infinity) 1/5^n is 3 * (1/5^(n+1) * 1/(1-1/5)) = 12/25 * 1/5^n < 1/5^n.

So the Cauchy sequence e_n does not converge to any f(n).

You might notice that this is the decimal argument (well, base 5) basically restated.

One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

### Who is online

Users browsing this forum: No registered users and 11 guests