(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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

2. Relevant equations

3. 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?

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Showing two countably infinite sets have a 1-1 correspondence

**Physics Forums | Science Articles, Homework Help, Discussion**