# Homework Help: Show F is Injective & Cardinality of Domain

1. May 18, 2014

### knowLittle

1. The problem statement, all variables and given/known data
Let $S = \{ (m,n) : m,n \in \mathbb{N} \} \\$
a.) Show function $f: S -> \mathbb{N}$ defined by $f(m,n) = 2^m 3^n$ is injective
b.) Use part a.) to show cardinality of S.

3. The attempt at a solution
a.) $f(a,b) = f(c, d ) ; a,b,c,d \in \mathbb{N} \\\\ 2^a 3^b = 2^c 3^d,$ then $a =c \\ b=d\\$
Therefore, f is injective.

b.) Since (m,n) belong to the naturals. Their cardinality is equal to them $\equiv \aleph_0$

Am I right?

2. May 18, 2014

### LCKurtz

You are given $2^a3^b=2^c3^d$. What is your argument to show a=c and b=d?

(m,n) is not a natural. What is the "their" and "them"?

3. May 18, 2014

### knowLittle

I could state in another way, but I still have no argument as to why they are equal.
I was thinking that I could say
$2^{a-c} = 3^{ d-b}$ and somehow since there is not a power other than 0 that satisfies then
a =c and d =b. But, I am not sure what is this "somehow" or if it is even truth. :/
"Their" in my little head means the set S and "them" means the Natural numbers. Since the set S is denumerable, their cardinality is equal to the natural numbers.
I am not sure, if I am right :/

4. May 19, 2014

### LCKurtz

That is a correct argument.

Isn't S being denumerable what you are trying to prove? From part (a) you have found an injection from S to N. That isn't enough to show they have the same cardinality. What else do you need to show?

5. May 19, 2014

### knowLittle

I have to show an injective relation from N into S. Can I say that g(x,y) = (x,y), where x and y $\in \mathbb{N}$

Therefore, by Cantor, Schroder, Bernstein's theorem $\mathbb{N} \wedge S$ have the same cardinality.

6. May 19, 2014

### LCKurtz

The domain of a function from N to S is the positive integers. g can not be a function of two variables. You need g(n) = something in S.

7. May 19, 2014

### knowLittle

You are right. Just to make this clear to myself, I will define g as strictly injective and very non-surjective.
g(n) = (n, 1), where ( n,1) $\in S$

8. May 19, 2014

### LCKurtz

Good. Now you are getting somewhere. It's trivial, but you need to write down the steps to show g is injective. Then you can apply Shroeder-Bernstein.

Earlier when you had the equation $2^{a-c}=3^{d-b}$ the reason that the exponents must both be zero is the unique factorization theorem for natural numbers. A number with only factors of 2 can't equal a number with only factors of 3.

9. May 20, 2014

### knowLittle

To show that $g$ is injective:
$g(a) = g(b ) \\ (a,1 ) = (b ,1 )$

Then, $a$ must be equal to $b$ and $g$ is injective.

Thank you for the unique factorization explanation.

10. May 20, 2014

### knowLittle

Now, I am wondering... do they have to be equal? a =2 and b =3. If the only restriction is that a,b $\in \mathbb{N}$
What would be an argument against what I just wrote?

11. May 20, 2014

### LCKurtz

No, your original argument is correct. (a,b) = (c,d) if and only if a=c and b=d. Otherwise they are different points in the plane, no?

12. May 20, 2014

### knowLittle

Thanks.

13. May 20, 2014

### LCKurtz

You're welcome. I just want to point out additionally, that when you have two sets like in this problem, where one of the sets seems "larger" than the other (informally, the plane seems larger than the line), the injection one way is usually a lot easier than the other way. So the map $f(n) = (n,1)$ was real easy for you to come up with. The other way $f(a,b) = 2^a3^b$ is much more difficult to dream up and I daresay you might not have ever thought of it. Me neither if I hadn't seen it before. That's why it was given as a hint.