5

Here is the proof from my lecture notes that if you have two countable sets $A$ and $B$, you can make another countable set $A \times B$ from them.

Let $A$ and $B$ be countable sets. Let $f : A \rightarrow \mathbb{N}$ and $g : B \rightarrow \mathbb{N}$ be injective. Claim: $A × B$ is countable. Proof: Define $h: A × B \rightarrow \mathbb{N}$ by $h(a, b) = 2^{f(a)+1}3^{g(b)+1}$ for $a \in A $ and $ b \in B$. Then uniqueness of factorisation in $\mathbb{N}^{>0}$ implies $h$ is injective.

I think I understand most of this, but what I don't get is why you can't let $h(a, b) = 2^{f(a)}3^{g(b)}$? If $f(a) = g(b) = 0$ then $h(a,b) = 1 \in \mathbb{N}$ which is fine, if either $f(a) = 0$ or $g(b) = 0$ but not both, then $h(a,b) = 2^{f(a)} \in \mathbb{N}$ or $h(a,b) = 2^{g(b)} \in \mathbb{N}$ and both are uniquely defined, so it's still injective. So I don't see the necessity of having $+1$ in the powers?

Could someone please explain this.

Thank you.

Elise
  • 705

1 Answers1

4

There's no reason for the $+1$. Indeed, if you let $h(a,b) = 2^{f(a)+1}3^{g(b)+1}$ and $h'(a,b) = 2^{f(a)}3^{g(b)}$, then you'll see that $h(a,b) = 6 h'(a,b)$. So one is injective if and only if the other is.

mathmandan
  • 2,014