Infinite Sets

Apr 2010
6
0
I am trying to prove why N x N x N is countable. N being the natural numbers. I am wondering how it needs to be changed from just N x N. Help!
 

Drexel28

MHF Hall of Honor
Nov 2009
4,563
1,566
Berkeley, California
I am trying to prove why N x N x N is countable. N being the natural numbers. I am wondering how it needs to be changed from just N x N. Help!
There are zillions of ways to do this.

The easiest is to notice that \(\displaystyle f:\mathbb{N}^3\to \mathbb{N}:n\mapsto 2^n3^n5^n\) is an injection. Why does that help?
 
Apr 2010
6
0
It means that it is one-to-one and the graph will hit all the natural numbers.... ?
 
Feb 2010
470
154
Since you have that NxN is countable, it follows that (NxN)xN is countable and that Nx(NxN) is countable. Just use these facts, for any sets S and T:

If S is equinumerous with R, then SxT is equinumerous with RxT.

If S is equinumerous with R, then TxS is equinumerous with TxR.

In fact, for any natural number k, by induction, we may infer that

Nx(N...xN) (i.e. "k number of times") is equinumerous with N
and
(N...xN)xN (i.e. "k number of times") is equinmumerous with N
 

Drexel28

MHF Hall of Honor
Nov 2009
4,563
1,566
Berkeley, California
Since you have that NxN is countable, it follows that (NxN)xN is countable and that Nx(NxN) is countable. Just use these facts, for any sets S and T:

If S is equinumerous with R, then SxT is equinumerous with RxT.

If S is equinumerous with R, then TxS is equinumerous with TxR.

In fact, for any natural number k, by induction, we may infer that

Nx(N...xN) (i.e. "k number of times") is equinumerous with N
and
(N...xN)xN (i.e. "k number of times") is equinmumerous with N
But isn't proving these facts the point of the exercise then? I know you know why they are correct, but does the OP?

Of course:

If you have that \(\displaystyle \left\{f_\alpha\right\}_{\alpha\in\mathcal{A}}\) is a set of bijections from the corresponding \(\displaystyle \left\{U_\alpha\right\}_{\alpha\in\mathcal{A}}\) to the corresponding \(\displaystyle \left\{V_\alpha\right\}_{\alpha\in\mathcal{A}}\) then \(\displaystyle \prod_{\alpha\in\mathcal{A}}f_\alpha:\prod_{\alpha\in\mathcal{A}}U_\alpha\to\prod_{\alpha\in\mathcal{A}}V_\alpha:\prod_{\alpha\in\mathcal{A}}\{x_\alpha\}\mapsto\prod_{\alpha\in\mathcal{A}}\left\{f_\alpha(x_\alpha)\right\}\) is a bijection. Or, for just the two case that MoeBlee stated just take \(\displaystyle f_1\times f_2:U_1\times U_2\to V_1\times V_2:(x_1,x_2)\mapsto (f_1(x_1),f_2(x_2))\)

Prove it!
 
Feb 2010
470
154
Yes, it is always a question: What theorems have been proven previous to the stated exercise?

I would think that in a set theory course (is this exercise from a set theory course?) the more basic theorem about Cartesian products would have been proven previously (and if it had not been, then it should be as soon as possible).

My point would be that there's no reason for the exercise to mention 'N' specifically when the result is general anyway, unless the intent of the exercise was just to remind the student to apply the more general result to N in particular. Moreover, as a matter of "style" I'd prefer a proof that appeals to the more general principle than to one that appeals to specific properties of N (that is, all other things being equal, better to prove something in a general way).

Anyway, the general theorem about Cartesian products is itself quite easy to prove just by putting the given bijections to their obvious use.