Show F is Injective & Cardinality of Domain

In summary: To show that ## g## is injective:## g(a) = g(b...g(a-1)) = g(a) g(b) g(a-1) = 2^a 3^b...3^a 2^a = 2^c 3^d##.
  • #1
knowLittle
312
3

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?
 
Physics news on Phys.org
  • #2
knowLittle said:

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"?
 
  • #3
LCKurtz said:
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 :/
 
  • #4
knowLittle said:
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?
 
  • #5
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
knowLittle said:
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.
 
  • #7
LCKurtz said:
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 ##
 
  • #8
knowLittle said:
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.
 
  • #9
LCKurtz said:
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.
 
  • #10
knowLittle said:
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?
 
  • #11
knowLittle said:
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 said:
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?
 
  • Like
Likes 1 person
  • #12
Thanks.
 
  • #13
knowLittle said:
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.
 

1. What is the definition of an injective function?

An injective function, also known as a one-to-one function, is a function where each element in the domain maps to a unique element in the range. In other words, no two elements in the domain can map to the same element in the range.

2. How can you prove that a function F is injective?

To prove that a function F is injective, you can use the horizontal line test. This involves drawing horizontal lines on the graph of the function and checking if each line intersects the graph at most once. If this is true for all horizontal lines, then the function is injective.

3. What is the cardinality of the domain of an injective function?

The cardinality, or size, of the domain of an injective function is equal to the cardinality of its range. This means that the number of elements in the domain is equal to the number of elements in the range.

4. Can a function be injective if its domain and range have different cardinalities?

No, an injective function must have the same cardinality for its domain and range. If the cardinalities are different, then the function is not one-to-one and cannot be considered injective.

5. Are all bijective functions also injective?

Yes, all bijective functions are also injective. This is because a bijective function is both injective and surjective, meaning that it is one-to-one and onto. In other words, each element in the domain maps to a unique element in the range, and every element in the range is mapped to by at least one element in the domain.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Precalculus Mathematics Homework Help
Replies
5
Views
871
  • Precalculus Mathematics Homework Help
Replies
3
Views
754
  • Precalculus Mathematics Homework Help
Replies
4
Views
770
  • Precalculus Mathematics Homework Help
Replies
7
Views
762
  • Precalculus Mathematics Homework Help
Replies
27
Views
2K
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
19
Views
2K
  • Precalculus Mathematics Homework Help
Replies
13
Views
161
Back
Top