Here's an argument I've found sometimes works better for people who can't see what the diagonal from the list is supposed to do, or if they think it's rather arbitrary. It's essentially the same argument, just written differently.<p>Definitions: 2 is the set {0,1}. N is the set of natural numbers {0,1,2,...}. An infinite sequence of 0's and 1's c_0,c_1,c_2,... can be thought of as a function c : N -> 2 (that is, the values in a sequence are a function of their position: c_i = c(i)). A set X is countably infinite if there is an invertible function f : N -> X (which, in other words, is a sequence f_0,f_1,f_2,... where each element of X appears exactly once). Let's write A -> B for the set of functions from A to B, rather than the usual B^A.<p>Suppose for sake of contradiction (N -> 2) is countably infinite, so there is an invertible function f : N -> (N -> 2). Let F : (N -> 2) -> N be the inverse, so I can save having to type f^-1. Let g : N -> 2 be defined by g(n) = 1 - f(n)(n). Then, g(F(g)) = 1 - f(F(g))(F(g)) = 1 - g(F(g)), so g(F(g)) must be 1/2, contradicting the fact that it ought to be 0 or 1 instead.