I seem to have trouble remembering Cantor’s ingenious diagonal slash method/proof concerning the cardinality of the counting numbers and of higher sets. Any help?
I dunno… does 99 come before 98?
<marquee></marquee>
<marquee> </marquee>
Well, in a nutshell:
Let X be a set, P(X) its power set. Suppose f:X -> P(X). Consider the set of all x in X such that x is not in f(x). Call this set A. Suppose f(x) = A.
Is x in A? By definition of A, then x is not in A.
Is x not in A? By definition of A, then x is in A.
Contradiction, so no such x exists, so f can’t be onto, so the cardinality of P(X) is greater than the cardinality of X.
This seems to be a pretty good explanation of the Diagonal Proof:
http://www.seanet.com/~ksbrown/kmath371.htm
“Drink your coffee! Remember, there are people sleeping in China.”
Argh! I just noticed that I gave you the wrong link. Try this one
http://users.javanet.com/~cloclo/cantdiag.html
(Sigh) Copy/paste strikes again…
“Drink your coffee! Remember, there are people sleeping in China.”
Thank you much for the links. Yes that cleared it up for me. Well sort of. Well it’s off to “power set” land for me. And BTW cabbage you crack me up!! :o