Bobby Russell
I/O

# Cantor’s Diagonal Argument

Posted on November 1st, 2013 by bobby.

The coolest thing that I’ve learned so far in my Discrete Mathematics class is Cantor’s Diagonal Argument. This argument reveals that there are atleast two ways to talk about the cardinality of infinite sets: countably infinite and uncountably infinite. A countably infinite set is countable (i.e., there exists an algorithm to reveal that sets cardinality.)

A countably infinite set is a set such there is a 1:1 corresponce, otherwise known as a bijection, between the elements in a set and the and the set of all Counting numbers ({1,2,3,4,5…}); it is uncountably infinite if the set is infinite and there isn’t a bijection between that set and the Counting numbers. Alright, fine…but how do you know when you can count the numbers of elements in a set and when you can’t…

That’s what Cantor shows. Take an infinite set (like the set of Real numbers,) and enumerate it (like you can with all countable sets, DUH!) Then suppose that you have a sequence Bbar. Bbar is, by definition, a sequence Bbar such that Bbar = .bbarsub11, bbarsub22, .. bbarsubnn, when n in the position of that particular bbar in a matrix. Because Bbar means that b is necessarily different from the Bbar, each Bbar can never be the same as the b that shares its index.

If you can count the number of Real numbers, then you should be able to enumerate them when you’re asked to. There’s a shitload of sequences in the set of Real numbers, so we can’t really do that, but we can think of a sequence called Bbar! Bbar traverses the diagonal of the Real number matrix, and we know that if there’s atleast 1 digit of the of any one of our sequences B that is not the same as Bbar, then there isn’t a bijection between the countable numbers and the Real numbers. If that’s true, then we can’t say that the cardinality of countable numbers is the same; both are incountable, but the Real number set has a cardinality that is somehow different than the set of counting numbers. Because of the nature of Bbar, we know that there’s always some index nn where the nn in Bbar and b are different by virtue of fact that n is countable and infinite!

Cantor was such a smartass. My mind is blown right now.