Showing two countably infinite sets have a 1-1 correspondence

  • Thread starter k3k3
  • Start date
  • #1
78
0

Homework Statement


Suppose A and B are both countably infinite sets. Prove there is a 1-1 correspondence between A and B.


Homework Equations





The Attempt at a Solution



Since A is countably infinite, there exists a mapping f such that f maps ℕto A that is 1-1 and onto.

Similarly for B, there exists a mapping g such that g maps ℕto B that is 1-1 and onto.

Since g is 1-1 and onto, g^-1 exists and g^-1 maps B into ℕ

Hence g^-1(b)=n for all b in B.

Since f(n)=a for all n in ℕ, then f(g^-1(b))=a for all b in B since g^-1(b) yields its corresponding number from ℕ.

Since f and g are bijective, we can define h as a mapping from B to A by h(b)=a for all b in B by using the ordering created by the mapping g.

Does this make sense?
 

Answers and Replies

  • #2
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,473
255

Homework Statement


Suppose A and B are both countably infinite sets. Prove there is a 1-1 correspondence between A and B.


Homework Equations





The Attempt at a Solution



Since A is countably infinite, there exists a mapping f such that f maps ℕto A that is 1-1 and onto.

Similarly for B, there exists a mapping g such that g maps ℕto B that is 1-1 and onto.

Since g is 1-1 and onto, g^-1 exists and g^-1 maps B into ℕ
Everything is fine up to this point.

Hence g^-1(b)=n for all b in B.
What is n?

Since f(n)=a for all n in ℕ,
What? This means that f is a constant function, certainly not a bijection.

You have the right idea, but you aren't expressing it correctly.

f is a 1-1 mapping of N onto A
g is a 1-1 mapping of N onto B

You seek a 1-1 mapping of A onto B. What is that mapping, and how do you know that it is 1-1 and onto?
 
  • #3
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,377
1,038

Homework Statement


Suppose A and B are both countably infinite sets. Prove there is a 1-1 correspondence between A and B.

Homework Equations



The Attempt at a Solution



Since A is countably infinite, there exists a mapping f such that f maps ℕto A that is 1-1 and onto.

Similarly for B, there exists a mapping g such that g maps ℕto B that is 1-1 and onto.

Since g is 1-1 and onto, g^-1 exists and g^-1 maps B into ℕ

Hence g^-1(b)=n for all b in B.

Since f(n)=a for all n in ℕ, then f(g^-1(b))=a for all b in B since g^-1(b) yields its corresponding number from ℕ.

Since f and g are bijective, we can define h as a mapping from B to A by h(b)=a for all b in B by using the ordering created by the mapping g.

Does this make sense?
Not really.

At least three of your statements say something other than what you probably intended.

"Hence g^-1(b)=n for all b in B." says every b in B gets mapped to the same n in .

Similarly, "Since f(n)=a for all n in ℕ" says that all of the elements of get mapped to the same element of A.

Also, "then f(g^-1(b))=a for all b in B" says that all of the elements of B get mapped to one single element of A.

It should be enough to note that since g is a bijection, then so is g-1. Then since f and g-1 are bijections, so is f○g-1.
 
  • #4
78
0
n is supposed to be some n in ℕ. What ever it is mapped to.

I think the mapping is the composite function f(g^-1(n)) and since f and g are 1-1 and onto, the composite function is too.
 
  • #5
78
0
I am trying to say that f(some n) = some unique a when I say "f(n)=a". Should I say that for all a in A and n in ℕ?
 
  • #6
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,377
1,038
I am trying to say that f(some n) = some unique a when I say "f(n)=a". Should I say that for all a in A and n in ℕ?
What you want to say is covered by the composition, of f with g-1 being a bijection.

Otherwise:
Each element of ℕ is the image of exactly one element of B.

etc.​
would be OK, I suppose.
 
  • #7
78
0
Here is my revised argument:

Since A is countably infinite, there exists a mapping f such that f maps ℕto A that is 1-1 and onto.
Similarly for B, there exists a mapping g such that g maps ℕto B that is 1-1 and onto.

Since g is 1-1 and onto, g-1 exists and g-1 is 1-1 and onto and maps B into ℕ.

Then for every element of ℕ, there exists exactly one b that it is the image of.
Hence there exists a b in B such that g-1(b)=n for some n in ℕ

Using g-1 in f creates the 1-1 correspondence from A to B.

Therefore f○g-1 is a bijective mapping from A to B.
 

Related Threads on Showing two countably infinite sets have a 1-1 correspondence

Replies
1
Views
3K
Replies
11
Views
3K
Replies
3
Views
10K
Replies
8
Views
1K
  • Last Post
Replies
6
Views
2K
  • Last Post
2
Replies
29
Views
8K
Replies
3
Views
2K
  • Last Post
Replies
9
Views
7K
Top