{"id":521,"date":"2019-06-29T22:08:55","date_gmt":"2019-06-29T22:08:55","guid":{"rendered":"http:\/\/funfacts.104.42.120.246.xip.io\/?page_id=521"},"modified":"2019-11-18T22:22:15","modified_gmt":"2019-11-18T22:22:15","slug":"cantor-diagonalization","status":"publish","type":"page","link":"https:\/\/math.hmc.edu\/funfacts\/cantor-diagonalization\/","title":{"rendered":"Cantor Diagonalization"},"content":{"rendered":"\n
\"\"<\/figure><\/div>\n\n\n\n

We have seen in the Fun Fact How many Rationals? that the rational numbers are countable, meaning they have the same cardinality as the set of natural numbers.<\/p>\n\n\n\n

So are all infinite sets countable?<\/p>\n\n\n\n

Cantor shocked the world by showing that the real numbers are not countable… there are “more” of them than the integers! His proof was an ingenious use of a proof by contradiction. In fact, he could show that there exists infinities of many different “sizes”!<\/p>\n\n\n\n

Presentation Suggestions:<\/strong>
If you have time show Cantor’s diagonalization argument, which goes as follows. If the reals were countable, it can be put in 1-1 correspondence with the natural numbers, so we can list them in the order given by those natural numbers. Now use this list to construct a real number X that differs from every number in our list in at least one decimal place, by letting X differ from the N-th digit in the N-th decimal place. (A little care must be exercised to ensure that X does not contain an infinite string of 9’s.) This gives a contradiction, because the list was supposed to contain all real numbers, including X. Therefore, hence a 1-1 correspondence of the reals with the natural numbers must not be possible.<\/p>\n\n\n\n

The Math Behind the Fact:<\/strong>
The theory of countable and uncountable sets came as a big surprise to the mathematical community in the late 1800’s.<\/p>\n\n\n\n

By the way, a similar “diagonalization” argument can be used to show that any set S and the set of all S’s subsets (called the power set<\/em> of S) cannot be placed in one-to-one correspondence. The idea goes like this: if such a correspondence were possible, then every element A of S has a subset K(A) that corresponds to it. Now construct a new subset of S, call it J, such that an element A is in J if and only if A is NOT in K(A). This new set, by construction, can never be K(A) for any A, because it differs from every K(A) in the “A-th element”. So K(A) must not run through the entire power set of A, hence the 1-1 correspondence asserted above must not be possible.<\/p>\n\n\n\n

This proof shows that there are infinite sets of many different “sizes” by considering the natural numbers and its successive power sets! The “size” of a set is called is cardinality.<\/p>\n\n\n\n

How to Cite this Page:<\/strong>\u00a0
Su, Francis E., et al. “Cantor Diagonalization.”\u00a0Math Fun Facts<\/em>. <http:\/\/www.math.hmc.edu\/funfacts>.<\/p>\n\n\n\n

References:<\/strong>
A classic text on real analysis is Walter Rudin’s Principles of Mathematical Analysis.<\/a><\/em><\/p>\n\n\n\n

Fun Fact suggested by:<\/strong>
Francis Su<\/p>\n","protected":false},"excerpt":{"rendered":"

We have seen in the Fun Fact How many Rationals? that the rational numbers are countable, meaning they have the same cardinality as...<\/p>\n","protected":false},"author":7,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"tags":[57,20,70,69,9,71,67,60,68,81],"class_list":["post-521","page","type-page","status-publish","hentry","tag-advanced","tag-analysis","tag-cantors-diagonal-argument","tag-cantors-diagonalization-argument","tag-combinatorics","tag-diagonalization-proof","tag-how-many-real-numbers","tag-real-analysis","tag-uncountable-infinity","tag-uncountable-sets"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/521","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/comments?post=521"}],"version-history":[{"count":3,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/521\/revisions"}],"predecessor-version":[{"id":1376,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/521\/revisions\/1376"}],"wp:attachment":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/media?parent=521"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/tags?post=521"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}