0

Let $A:=\{2^a\cdot3^b: a,b\in\mathbb{N}\}$. Show that $|\mathbb{N}\times \mathbb{N}|=|A|$.

I need to show that the cardinality is the same for $\mathbb{N}\times \mathbb{N}$ and $A$ by showing that the function is bijective. I think I figured out how to show that the function is injective, but I am stuck on surjective. I think I need to set y equal to the equation and solve for the variables, and then plug them back into the equation, but I'm not sure how to handle the 2 variables in the exponents. Thanks.

Robert Z
  • 145,942
Alexis112
  • 1
  • Given that $A$ is defined as the set of function results, I don't see how the function could not be surjective on $A$. – celtschk Nov 11 '16 at 08:24

2 Answers2

0

The function $f(a,b)=2^a\cdot 3^b$ is injective by the unique factorization theorem and it is surjective on $A:=\{f(a,b): (a,b)\in\mathbb{N}\times \mathbb{N}\}$ by construction.

Robert Z
  • 145,942
0

Any number in $A $ is of the form $2^i3^j $ and we want to show that $A $ has the same cardinality as $\Bbb N \times \Bbb N $.

We consider $f(x, y) = 2^x3^y $. $f: \Bbb N \times \Bbb N \longrightarrow A $ is clearly surjective because of the way $A $ was constructed! All numbers in $A $ are a power of 2 times a power of 3. Therefore if $a \in A, a = 2^i3^j, f(i, j) = a $.

Now we only need to show that $f$ is injective. But a bit of Algebra is enough. We know that any integer has a unique prime decomposition. Hence if $f(x, y) = f(i, j)$ then $x = i, y =j $ because 2 and 3 are primes and uniquely define the prime factorization of the number.

RGS
  • 9,719