Thread: Countable infinte or uncountable infinite

Hi,

I am taking a course in computability and logic at my university and am reading about countable and uncountable infinites.

According to my book the set (N X N X N X N...) - where N is a natural number - any finite number of times is countable. I can see how you can reach this conclusion, so that is not my problem.

However what happens if the set (N X N X N ... ) have infinitely many dimensions? Then it becomes uncountable I would say, as you can make a diagonalization argument, but just want to make sure, I have understood it properly.

Many thanks in advance for your help.

T

Hello,

There are well known results about this matter:

i) A countable union of contable sets, is countable.

ii) A finite product of countable sets is again, countable.

But, a countable product doesn't need to be countable. If X = {1, 2} then the sets of functions from N (natural numbers) to X is not countable, because, as you said, one can use a diagonalization argument. (Which means that the countable product of X is not countable)

See the first chapter of "Topology" of Munkres.

Maurcd is perfectly correct. But to see this more intuitively, notice that the example of an countable product of N's:
N X N X N.......
is just N^N which has the same cardinality of 2^N which has the same cardinality of the power set of N which has the same cardinality of the real numbers which is, of course, uncountable. So if you use a diagonal argument, you are re-inventing the wheel.
Similarly, if you have a larger cardinality of dimensions, say M, then you will end up with the cardinality of the power set of a set with cardinality M.