Prove that $\{(i, j, k)$ in $\mathbb{N}\}$ is countable

Question

I have the following definition... $$T=\{(i,j,k)\mid i, j, k \in\mathbb{N}\}$$

How do I prove whether it is countable? My understanding is that I need to prove that every subset of $(i,j,k)$ maps to some number $n$.

For example...

$1$ maps to $(1,1,1)$

$2$ maps to $(1,1,2)$

etc...

But I'm not sure how to show my proof. Can I possibly use Cantor's argument? How would that work here?

There is something wrong with this task. $(i,j,k)$ is no subset of $\mathbb{N}$, it is not even a set. — Cornman, Oct 22 '17 at 21:08
@Cornman ok maybe it is not a subset. I assumed it was because it was in the brackets. — buydadip, Oct 22 '17 at 21:11
When you want to make brackets you have to write { ... } and not just { ... }. :-) — Cornman, Oct 22 '17 at 21:14

score 2 · Accepted Answer · answered Oct 22 '17 at 21:51

2

Regard this mapping \begin{align} \phi: \left\{ \begin{array}{rcl} T & \to & \mathbb{N} \\ (i,j,k) & \mapsto & 2^i 3^j 5^k \end{array} \right. \end{align} It is certainly injective. Therefore $|T| \leq |\mathbb{N}|$.

answered Oct 22 '17 at 21:51

Nathanael Skrepek

2,558

can you just explain why it is so obviously injective? Im confused, lets say $i$ $j$ and $k$ are $1$. Then all three map to the same value? In this case they map to $30$? – buydadip Oct 23 '17 at 00:20
1

Each number has an unique factorization, then this function is injective. – 7697 Oct 23 '17 at 01:33
$(i,j,k)$ is one element! So "Then all three map to the same value" doesn't make any sense. – Nathanael Skrepek Oct 23 '17 at 07:17
it is called godel coding. $f(i,j,k) =2^i 3^j 5^k$. It uses the fundamental theorem of arithmetic to encode an ordered tuple from $N^n$ into a unique natural number. For example $f(2,1,3)=(2)(2)(3)(5)(5)(5)= 1500$. To find what unique tuple corresponds to 1500, find the prime factors $1500=(2)(2)(3)(5)(5)(5)$, then the number of 2s goes to the i position, the number of 3s goes to the j position, the number of 5s goes to the k position. In otherwords $f^{-1}(1500)=(2,1,3)$. – Christopher Rose Nov 02 '17 at 02:33

score 1 · Answer 2 · answered Oct 22 '17 at 21:11

1

Hint:

$T = \Bbb N \times \Bbb N \times \Bbb N$. Now if you could show that if $A, B$ are countable then so is $A \times B$...

answered Oct 22 '17 at 21:11

cronos2

1,947

I'm still a little confused, what do A and B represent? – buydadip Oct 22 '17 at 21:30
@Bolboa just generic sets with the property of being countable. – cronos2 Oct 22 '17 at 21:31
so I have to first prove that a generic set is countable? – buydadip Oct 22 '17 at 21:49
@Bolboa That will prove to be rather difficult since it's just false. The cartesian product of two countable sets is itself a countable set. That's what you ought to show. – cronos2 Oct 22 '17 at 21:50

7697 · Answer 3 · 2017-10-22T21:22:39.170

You only need show that exists a injective function from $T \to \mathbb{N}$.

I believe that is more interesting prove that finite cartesian product of countable set is countable. Your exercise will be a particular result.

Now for prove that cartesian product you can use induction in number of set (n). For n=2, you can only think about $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$(why?). To construct injective function $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ you can think about prime factorization.

Prove that $\{(i, j, k)$ in $\mathbb{N}\}$ is countable

3 Answers3