Completions, Cauchy sequences, and countability

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Meteoric
Posts: 333
Joined: Wed Nov 23, 2011 4:43 am UTC

Completions, Cauchy sequences, and countability

Postby Meteoric » Mon Jun 13, 2016 5:57 am UTC

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.
No, even in theory, you cannot build a rocket more massive than the visible universe.

Tub
Posts: 475
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Completions, Cauchy sequences, and countability

Postby Tub » Mon Jun 13, 2016 9:40 am UTC

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... ;)

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Completions, Cauchy sequences, and countability

Postby Cauchy » Mon Jun 13, 2016 9:42 am UTC

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|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: Completions, Cauchy sequences, and countability

Postby benneh » Mon Jun 13, 2016 10:38 am UTC

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.

Code: Select all

    s0  s1  s2  ..
s0   1   0   1  ..
s1   0   1   0  ..
s2   1   1   1  ..
..  ..  ..  ..  ..
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}.

User avatar
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

Postby jestingrabbit » Mon Jun 13, 2016 11:36 am UTC

@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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Meteoric
Posts: 333
Joined: Wed Nov 23, 2011 4:43 am UTC

Re: Completions, Cauchy sequences, and countability

Postby Meteoric » Mon Jun 13, 2016 12:50 pm UTC

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.

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

Re: Completions, Cauchy sequences, and countability

Postby LucasBrown » Wed Jun 15, 2016 6:02 pm UTC

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.

User avatar
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

Postby Yakk » Thu Jun 23, 2016 10:48 am UTC

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.
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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 11 guests