Show F is Injective & Cardinality of Domain

[knowLittle]

Homework Statement

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.

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?

 

[LCKurtz]

Homework Statement

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.

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.

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

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

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

 

[knowLittle]

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

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. :/

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

"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 :/

 

[LCKurtz]

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.

That is a correct argument.

"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 :/

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?

 

[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.

 

[LCKurtz]

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.

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.

 

[knowLittle]

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.

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$

 

[LCKurtz]

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$

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.

 

[knowLittle]

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.

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.

 

[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.

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?

 

[LCKurtz]

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.

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?

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?

 

[knowLittle]

Thanks.

 

[LCKurtz]

Thanks.

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.