here is one of cantors diagonal arguments as i recall it from high school, about 45 years ago:
assume there is the same number of real numbers between 0 and 1, even those having only zeroes and 1's in their decimal expansion, as there are positive integers.
that means we canj write down a list (infinitely long) containing all those real numbers.
so we write down first the decimal corresponding to the integer 1, then under it we write down the real decimal corresponding to 2, etc...
this yields a doubly infinite array of the digits 0 and 1. i.e. we have an infinitely long list of decimals, and in each row we have an infinitely long decimal, possibly ending in all zeroes after a while.
Then we will construct another decimal that is actually not in the list as follows:
Just run along the "diagonal" of the list. i.e. the "diagonal decimal" is the decimal whose first entry is the first entry of the first decimal in the list. its second entry is the second entry of the second decimal in the list. its third entry is the third entry of the third decimal in the list...etc...
now with this decimal in hand, go down it entry by entry and change every single entry to the opposite choice. i.e. for each entry which is a 1, change it to a zero, and vice versa.
the result will be a decimal which does not equal any of the decimals in the list, since to differ from a decimkal in the list it suffices to differ in only one entry, and this new decikmal differs from the nth decimal in the list by its nth entry.
now since every list of decimals gives rise to a decimal not in the list, it follows that no such list can contain them all. hence it is not true that there are the same number of such decimals as positive integers.
to abstract this argument, consider the set of positive integers as a given set N, and think about all subsets S of that set. To describe one subset S of N, means for each element of N, i.e. for each positive integer, we must decide whether or not it belongs to our subset S. If it does assign a 1, if not assign a 0. this gives us an infinite sequence of 0's and 1's, lo and behold, precisely an infinite decimal containing only 0's and 1's.
hence if there were the same number of subsets of N as elements of N< then we could write down a list of those subsets and hence of those decimals, each numbered by a positive integer.
we are back where we were before. since there is no such list of decimkals there is no such list of subsets, and so in fact there are mroe subsets of N than there are elements of N.
more abstractly, if N is any set at all, and we find a map f from N to the set of all subsets of N, we can construct a subset S of N, using the map f, as follows: let x belong to S if and only if x does not belong to f(x).
i.e. the "diagonal subset" contains x if and only if x does belong to f(x), and we change it to the opposite subset, where for every x in S, x does not belong to f(x).
then this new subset S is not f of any x, since if S = f(x), then x does not belong to f(x), i.e. x does not belong to S. But by definition of S, if x does not belong to S, then x did belong to f(x). Since we are assuming S = f(x), this is a contradiction.
this argument proves there is no surjection from N to the set of all subsets of N, for any set N at all. hence any set, even an infinite one, has more subsets than elements.
Why the heck didn't i think about N & Q? 