Prove: if N is denumerable, then N^k is denumerable.

[toughcookie723]

Prove: if N is denumerable, then N^k is denumerable.

So I was thinking about doing this proof by induction.

To prove NxN is denumerable use the Diagonal argument (construct a matrix of natural numbers)

From there: If N^k is denumerable then N^(k+1) is denumerable.
Once again, I was going to use diagonal argument. Saying that since N^k is denumerable (by Induction premise) , let pk be the kth element of N^k. So the diagonal argument is going to be

p1 p2 p3 p4
1(p1,1) (p2,1)
2 (p1,2) (p2,2)
3 (p1,3) (p2,3)

-> N^(k+1) is also denumerable.

Is this a correct proof? Thanks for your help!

​

 

[pka]

Prove: if N is denumerable, then N^k is denumerable.

There is a bijection \(\displaystyle f:N \leftrightarrow \mathbb{N}\).
Suppose that \(\displaystyle p_1,p_2,\cdots,p_k\) is a listing of the first \(\displaystyle k\) primes.

Define \(\displaystyle \Phi :N^k \to \mathbb{N}\) by \(\displaystyle \left( {x_1 ,x_2 , \cdots ,x_k } \right) \mapsto p_1 ^{f(x_1 )} \cdot p_2 ^{f(x_2 )} \cdots p_n ^{f(x_n )} \).

Prove that \(\displaystyle \Phi\) is an injection.

 

[daon2]

I don't see a problem with your proof, toughcookie. There is a closed form for that sequence as well, it involves sums of triangular numbers. Though unless the definition specifies it, N^(k+1) and N^k x N might not be the same, but they are equivalent.