Many people object to what is taught to beginning students as "The diagonalization proof," and for good reason. It's not what Cantor wrote, and it is wrong. The problem is that, as beginning students, they are not taught enough mathematics to understand why it is wrong. They sense that there are flaws, but try to associate them with the premise rather than the incorrect presentation.
To avoid length, I'll explain this without the rigor of defining functions and bijections and all that. If you have advanced far enough past being a beginning student, understand how they apply, you can translate what I say into better language. If not, I hope this is easier to understand.
First, the premise is "There is an infinite set that cannot be counted," not "The real numbers can't be counted." Cantor's first proof of this premise was published 16 years before diagonalization. It used the reals only as the example, not as the intended subject. But other mathematicians had objections about assumptions he made, so he devised diagonalization specifically because it does not use real numbers. It used (and you cited this, but I'm not sure you understood all of it) the set of all infinite-tuples of two characters. I'll call this set T, as Wikipedia does. But note that the two characters don't have to be "0" and "1." In fact, Cantor used "m" and "w."
Second, what is typically taught as diagonalization was only a visualization of the more formal proof, which is sometimes called the power-set proof (if I find time, I will explain more in a comment). I'm not saying there is anything wrong with it, just that there is a more rigorous proof for more advanced students.
Third, the visualization is NOT a proof by contradiction. Say you assume A&B (that is, two disjoint propositions). If you can derive a contradiction that follows from A alone, then all you have proven is that A alone must always be false. Not that B must always be false. What Cantor proved follows only from the assumption that you have counted a subset of T, not that you have counted all of T. All Cantor meant when he used the word "Widerspruch," which can mean "opposition" or "contradiction," is that finding an element that is not in the set you counted is in opposition to having all of T.
What diagonalization is, is a proof by contraposition. That is, if you prove "If A then ~B," then you have also proven "If B, then ~A." What Diagonalization proves directly, is "If a subset S of T that can be counted, then it is not all of T." By contraposition, it also proves "If a set S is all of T, then it cannot be counted."
Here's an outline of the proof, modeled on what is in Wikipedia but corrected for my points and made clearer to address your questions:
- Let T be the set of all infinite-tuples of the two characters "0" and "1." Call these tuples "Cantor Strings."
- Let S be any infinite set of Cantor Strings that is countable.
- Being countable means that for any integers $n$ and $m$, there is a function $d(n,m)$ that represents the $m$th character of the $n$th Cantor String in the counting we assumed exists.
- Let $a(n)$ be the opposite character of $d(n,n)$.
- So $a$ is Cantor String, and it cannot be in S.
- But since T is the set of all Cantor Strings, $a$ must be in T.
- This directly proves "If S is a countable set of Cantor Strings, then it is not all of T.
- By contraposition, it also proves "If S is all of T, then it is not countable.
To address your issues:
"The $n$th element of $s_f$ would be defined as the opposite of itself." No. You are confusing what I called $a(n)$ with what I called $d(n,n)$.
"I could demonstrate that the 'missing' element was the within a constant distance from the last element in the 'series'." Only if you assume that S is all of T, which is not a part of the (correct) proof.
f(n)
with a particularn
as matching the definition, instead of attempting to find then
that matched that definition. By forcing a particularf(n)
to have the value ofs_f
I ran into the element defined in terms of itself issue. So the whole thought was stupid from the get-go. $\endgroup$ – Mooing Duck Apr 12 '12 at 18:08