johne
Reputation
283
Next privilege 500 Rep.
Access review queues
 Dec2 awarded Notable Question Oct22 awarded Good Question Aug9 awarded Yearling May14 awarded Popular Question May16 awarded Nice Question May16 comment How does Cantor's diagonal argument work? @Arturo: wrt/ accepting your answer. I have no problem awarding you the "prize" considering how much effort you have spent trying to "correct my (almost certainly incorrect) understanding of Cantors diagonal argument." :) I appreciate you putting up with me! May16 comment How does Cantor's diagonal argument work? @Arturo: $P \to \lnot P$ does not prove Cantors diagonal argument, it only proves that $P = \bot$. But in order for the proof to work, $P$ must be $\top$- You can not have a "list of all reals" ($P = \top$) and "a real that is not on the list" ($\lnot P = \top$). If you have a real that was not on the list, then by $P \to \lnot P$, you did not have a list of all the reals, which pretty much scuttles the whole proof since it doesn't work if $P \ne$ "a list of all the reals". May16 awarded Commentator May16 comment How does Cantor's diagonal argument work? @Arturo: In fact, "hence the conclusion is that $\lnot P$ is true" does means precisely "given a list of reals, there is a real not on that last [sic]", which is not the same thing as "given a list of all reals, there is a real not on that last [sic]", which was the original premiss: $P$="the list contains all reals". This, I think, is why I have trouble with the Cantor's diagonal argument: I don't see how it proves anything if you drop the all qualification. May16 comment How does Cantor's diagonal argument work? @Arturo: $(P \to \lnot P) \to \lnot P$, or more specifically "$P \to \lnot P$ ", does not reflect what it is you are asserting or trying to prove. What you are trying to prove is $P \land \lnot P$ : $P$="the list contains all reals", $\lnot P$="there is a real not on the list". If $\lnot P$ is "a real not on the list", then $P \cup \lnot P \ne P$, but $P$ is "a list that contains all reals" if, and only if, $P \cup \lnot P = P$. Both must be true simultaneously- $P \land \lnot P$, not if / then $P \to \lnot P$. May16 comment How does Cantor's diagonal argument work? I believe we have a terminology impedance mismatch, and since we're on the math side of the fence, the fault is mine. When you write "$2^{\mathbb{N}}$", I read "the unordered set of the infinite tuple permutations of $\lbrace 0,1 \rbrace$ such that $2^{\mathbb{N}} =\lbrace (0),(1),(00),(01),(10),(11), \dots \rbrace$, which I have ordered lexically for notational description convenience, but continues on to infinity in the customary pattern." Am I mistaken? May16 comment How does Cantor's diagonal argument work? The definition for countable is given as "A set $X$ is said to be countable if and only if there exists a function $f:\mathbb{N} \to X$ that is surjective." Must the function be pedantically surjective, or can it also be bijective? (I suspect bijection is a special case of surjection). May15 comment How does Cantor's diagonal argument work? In the very first proof block quote, I interpret the first paragraph to mean "Your typical $\mathbb{N} \to$ base 2 mapping, which is typically used in computers to represent unsigned numbers (i.e., not grey coded, etc)." Is this interpretation correct? My understanding was that this "typical $\mathbb{N} \to$ base 2" was bijective, am I mistaken on this point? The next paragraph then states "If $f:\mathbb{N} \to 2^{\mathbb{N}}$ is a function, then $f$ is not surjective." I don't understand how this follows given the first paragraph? May15 comment How does Cantor's diagonal argument work? Just for the record, I did see that question, but it has to do with why Cantor's diagonal argument is or isn't applicable to the natural numbers. My question, or misunderstanding, is that I don't get how Cantor's diagonal argument works fundamentally. The description given at wikipedia and @Arturo Magidin's answer have (at first approximation) slightly different pedantic semantics, and @Asaf Karagila's answer definitely has different pedantic semantics. In good faith, I do believe they are different, or at least they seem different to me (which may not mean much if I don't understand it). May15 comment How does Cantor's diagonal argument work? And also, let me say how impressed I am that you are willing to take the time to give such a comprehensive answer to someone who is obviously a "newb". This is the type of community I liked at stackoverflow, and I've written my share of lengthy answers there. The community and moderators over at cstheory sucks and, IMHO, is the antithesis to the whole stackoverflow idea. May15 comment How does Cantor's diagonal argument work? I don't quite follow how this argument ensures that "you have a sequence which is none of the $a_i, i \in \mathbb{N}$". You can certainly construct such sequences, but I do not see how it guarantees that "none of the $a_i, i \in \mathbb{N}$". In my question, the first (non-alternate) $s_4$ would appear to be just such a number. I think your description captures the essence of why I'm confused: I don't understand how the argument goes from "can be true (but might not be)" to "must be true under all circumstances". May15 awarded Scholar May15 awarded Supporter May15 accepted How does Cantor's diagonal argument work? May15 comment How does Cantor's diagonal argument work? I really appreciate your comprehensive answer, and I wish there was a better way to ask followup questions. :( I have a number of additional questions that I'd love to ask, would you mind if I emailed you them?