Just in case any casual reader might be wondering if chinglu has a point, I present the "conventional" argument. Go compare

Suppose that there exist a random sequence of 1's and 0's which, as a set, has countably infinite cardinality. Then by the definition of a sequence of this sort, it makes sense to refer to the n-th element in the sequence where

.

Suppose further that there exists a

**countable** infinity of such sequences, each one unique. Then it makes sense to refer to the n-th sequence. Let's call it as

Putting these together, it makes sense to refer to the n-th element of

All with me so far?

This implies that, as sets, the cardinality of each

is equal to the cardinality of the set of ALL such sequences. Which in turn implies there exists an array generated by "listing" the

which is square iff these 2 cardinalities are the same.

I assert that the existence of a "true" diagonal of any array implies it is square, where I DEFINE the "true" diagonal

as the sequence for which

*for each and all , the n-th element in is the n-th element in *
Now by assumption, the "list" of all

is complete. This implies there exists

for some particular

such that the p-th element is NOT the p-th element in

. Call it

for "complement"

BUT, by construction of the diagonal, the p-th element of

is the p-th element in

, and yet by the definition of the complement, the p-th element in

is NOT the p-th element in

So our contradiction:

**the p-th element in is NOT the p-th element in .**

So

as defined does not exist, our array cannot be square and as sets the cardinality of any sequence cannot be equal to the cardinality of the list of all such sequences.

It remains as an exercise for the reader (as they say) to show the the cardinality of the list is strictly greater than that of any sequence