Talk:Real Numbers are Uncountably Infinite

From ProofWiki
Jump to navigation Jump to search

It's the same proof, but a bit more pictorial, and slightly more general by omitting the integer part. --Linus44 13:06, 6 March 2011 (CST)

Ça plane pour moi --prime mover 15:13, 6 March 2011 (CST)

... but one more thing: what's with the $\hookrightarrow$ notation? --prime mover 15:25, 6 March 2011 (CST)

$\hookrightarrow$ for an injection, $\twoheadrightarrow$ for a surjection, when either I feel it needs emphasizing or I feel like having a prettier arrow. --Linus44 16:16, 6 March 2011 (CST)
... completely endorse that - how about a citation, or (better still) add them to the pages for Injection and Surjection? --prime mover 17:12, 6 March 2011 (CST)
Any way to render the combination of the two for a bijection, with both the hook and two heads? On an unrelated note, do we really need the min function in $f_n = \min\left\{d_{nn} + 1\right\}$ since it's just the min of one thing (or was that supposed to be a comma instead of a plus?) --Alec (talk) 23:36, 6 March 2011 (CST)


For a bijection we have $\leftrightarrow$ which gets used occasionally. We have also used $\rightarrowtail$ for injection - clearly these symbols are fairly arbitrary and not de rigueur enough to introduce without defining them each time, e.g. "... where $\twoheadrightarrow$ denotes a surjection" or whatever.
I've raised the question of varying notation before (everyone has their own faves and tends to get protective of them) - I wonder whether it's worth specifying the "house style" for various bones of contention. --prime mover 00:31, 7 March 2011 (CST)
The $\min$ can go, it was going to allow for $d_{nn}+1 = 10$, but I thought it was simpler to say "cycle modulo 10" and forgot to get rid of the min. There isn't a hooktwoheadarrow that I've seen; you can concoct one:
\newcommand{\twoheadhookarrow}{\ensuremath{\lhook\joinrel\relbar\joinrel\twoheadrightarrow}}
but MathJax doesn't like it. Personally I like $\stackrel{\sim}{\longrightarrow}$ for isomorphisms, that way all three are easy to distinguish in commutative diagrams. --Linus44 03:33, 7 March 2011 (CST)
Stumbled across Power Set of Natural Numbers is not Countable and thought another proof was in order. --Linus44 09:16, 7 March 2011 (CST)

I'm not clear on what the function $f$ specified in Another Proof is, but off hand it doesn't look like it would be onto $[0,1]$ if it's based on strings of just 0s and 1s base 10. Can you give a more explicit function? --Alec (talk) 00:54, 8 March 2011 (CST)

It's in base 2, not base 10 --Linus44 06:14, 8 March 2011 (CST)
I may just be being obtuse now, but how can we just disallow infinite strings of 9s in the diagonal argument proof and 1s in another proof? For example in "Another Proof," the set $A=\N\setminus\{1\}$ is a perfectly valid element of $\mathcal P (\N)$, but it would create an infinite string of 1s in the binary expansion of $f(A)$. For the diagonal argument proof, we could just switch to mod 9 to eliminate the problem since then the binary expansion wouldn't have 9s at all, but I don't see a similar idea for another proof. Thoughts/what am I missing? --Alec (talk) 21:37, 8 March 2011 (CST)
You're right "Another proof" isn't quite correct $[0,1]\hookrightarrow \mathcal P(\N)$ isn't a bijection, I'll fix it.
I think the diagonal proof is fine - since $0.999\ldots = 1$, throwing away decimals with an infinite sting of 9's doesn't change the size of $[0,1]$ so we are still counting (or, technically, not counting) the same set. --Linus44 11:18, 9 March 2011 (CST)
In fact I changed it a little -- I added the proof because there's already a proof that $\mathcal P(\N)$ is uncountable, so we just needed that $\#\mathcal P(\N) \geq \#\R$, hopefully that's a bit clearer now.
The injection isn't a very neat but it does assign a real number to every subset of $\N$, there must be a better choice but I can't think of it... --Linus44 11:55, 9 March 2011 (CST)
Sorry, it proves nothing. $\#\mathcal P(\N) \geq \#\R$ all right but then yeah $\#\mathcal P(\N) \geq \#\N$. Not convinced. --prime mover 14:09, 9 March 2011 (CST)
Sorry, meant $\#\mathcal P(\N) \leq \#\R$; $f$ injects $\mathcal P(\N) \to \R$. --Linus44 14:48, 9 March 2011 (CST)
Okay I think there's the glimmerings of something. Needs tightening: you mention $f$ and again a few lines down but don't actually specify that $f$ is the function being defined in between. Doesn't matter too much, just leaves an irritation like the incorrect use of its/it's or a dangling participle. I may get round to tightening it unless you want to. --prime mover 15:37, 9 March 2011 (CST)
You go for it; it turned out to be more work than I thought, I was hoping because uncountability was done for $\mathcal P(\N)$ it would just be a couple of lines, but I can't see such an easy construction. --Linus44 16:04, 9 March 2011 (CST)
Actually thinking about it maybe a page something like "uncountability properties" would be good, with a bunch of uncountability tests such as image of injection from uncountable is uncountable etc. Depends what you think. --Linus44 16:14, 9 March 2011 (CST)
(steps back, takes a good look ...) ... occurs to me what's being proved here is tantamount to the Continuum Hypothesis. Think I need to go re-read my Rucker. --prime mover 16:57, 9 March 2011 (CST)
That'd be nice, although somewhat controversial. Who has the publishing rights? --Linus44 17:48, 9 March 2011 (CST)

Back to the diagonal argument proof: I realized that on most of the site we have been including 0 with the natural numbers and here we don't (for good reason I think, since it makes it neater). Would it make sense to add some comment noting that?

I might not bother myself. There's already a comment on the page on natural numbers that mentions the ambiguity. --prime mover 15:23, 10 March 2011 (CST)

And as for the string of 9s, the issue more arises with $0.f_1 f_2 f_3\ldots$ being a string of nines. For example let $1\leftrightarrow .8$, $2\leftrightarrow .08$, and so on. Then $9= f_1 = f_2 =\ldots$ and $y = .999\ldots = 1$. Of course, 1 still isn't a member of our initial set of real numbers in this case, but it doesn't seem trivial that it couldn't be in some similar example. Making $f_1 = d_{11} + 1 \pmod 9$ would just avoid the issue of strings of nines all together, and I don't really see a downside (I guess it's a little less elegant, but not much nor is that a big deal). --Alec (talk) 11:27, 10 March 2011 (CST)

It's not an issue there... if $f_i \equiv 9$ then every decimal on the list contains an $8$, and therefore the list is not an enumeration of the reals $\R \cap [0,1]$ (what we needed to prove).
The only problem that comes from infinite string of nines is that there are precisely two representations for a large class of decimal numbers.
Disallowing the second representation of such numbers (which could equally have been the one not containing infinite strings of $9$'s) simply ensures that each decimal can appear at most once on the list.
It doesn't prevent any decimal from appearing on the list because we still have the second representation.
Therefore by constructing any decimal number not on the list proves uncountability.
You example shows that if the number $0.f_1\ldots$ is an infinite string of $9$'s then it has two equal representations, but your construction also insists that the $n^\text{th}$ number on the list contains an $8$ in the $n^\text{th}$ place, and therefore none of them equals $1=0.9999\ldots$. --Linus44 12:15, 10 March 2011 (CST)