1

I have the following question in my textbook:

Prove that the set of triples $\{(a,b,c)|a,b,c \in \mathbb{N}\}$ is countable

Now I know that $\mathbb{N}$ is countable already, and I have completed a non-rigorous proof of this before, but I am unsure of how having a set of triples changes things, nor do I understand what a set of triples pertains to. I assume I am missing some fundamental knowledge in solving this problem?

My guess is that a set of triples is: $(a,b,c)$ so $(1,1,1),(1,1,2),(1,1,3)...(2,1,1),(2,1,2)...(3,1,1)...$ etc

I imagine I can show this to be countable via pictures if my guess is correct. But how would I go about proving it rigorously?

Katie
  • 826
  • Group the elements such that a+b+c=3,4,5..... Then proceed as in countability on N, the set of natural numbers – Swapnil Tripathi Apr 08 '14 at 07:59
  • Let $\mathbb{N}^3$ denote the set of triples of integers. Can you find a bijection or at least a surjection from $\mathbb{N}^3$ to $\mathbb{N}$. – Bill Trok Apr 08 '14 at 08:00
  • @ZubinMukerjee a = 1, b = 1, c = 2, for Lacarguy answer that was deleted. 5^1, 3^0, 2^0 I think it was. – Katie Apr 08 '14 at 08:05
  • That would give $f(1,1,2)=5$, not $7$. – Zubin Mukerjee Apr 08 '14 at 08:07
  • @ZubinMukerjee I must have misunderstood what he had written. I saw $2^{a-1} + 3^{b-1} + 5^{c-1}$ nevermind he put it back up, I see it is multiplication now. – Katie Apr 08 '14 at 08:09

4 Answers4

2

It is possible to show this without actually constructing a bijection. Let $$S=\{(a,b,c)|a,b,c\in \mathbb N\}.$$ If you define $$A_n=\{(a,b,c)\in S|a+b+c=n\},$$

then it is clear that $A_n$ is finite for every value $n\in \mathbb N$. For example, $|A_1|=|A_2|=0$, $|A_3|=1$, $|A_4|=3$ and so on.

Then, you can show that $$S=\bigcup_{i\in\mathbb N} A_i.$$

Because a countable union of finite set is countable, that means that $S$ is countable.

5xum
  • 123,496
  • 6
  • 128
  • 204
1

Consider the function $f: \mathbb{N}^3 \to \mathbb{N}$ given by: $f(a,b,c) = 2^{a-1}\cdot 3^{b-1} \cdot 5^{c-1}$. We can prove that $f$ is one-to-one and this suffices to show that $\mathbb{N}^3$ is countable.

DeepSea
  • 77,651
  • Consider $7 \in \mathbb{N}$. There is no triple $(a,b,c)$ such that $7 = 2^{a-1} \cdot 3^{b-1} \cdot 5^{c-1}$. Therefore your function is not a bijection. – Zubin Mukerjee Apr 08 '14 at 08:03
  • 1
    I cannot edit the comment I wrote above, but it was in response to a previous edit of LAcarguy's answer, which stated that $f$ was a bijection. The answer, as it is now, is correct. – Zubin Mukerjee Apr 08 '14 at 08:11
1

It is possible to count the triples $(a,b,c)$ such that $a+b+c$ is (not strictly increasing). The first few are $$(1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1), \text{etc.}$$

Since every triple must correspond to a sum $a+b+c$, and every triple for each sum is listed in the method for counting above, this is a bijection between $\mathbb{N}$ and $\mathbb{N}^3$.

Zubin Mukerjee
  • 17,832
0

Standard proof of countability of $\mathbb{Q}$ relies on proving that $\mathbb{N}\times \mathbb{N} \simeq \mathbb{N}$. With this you can show that $\mathbb{N}\times \mathbb{N} \times \mathbb{N} \simeq \mathbb{N} \times \mathbb{N} \simeq \mathbb{N}$

Community
  • 1
tom
  • 4,596