Thread: Proving equal cardinality of sets using Cantor-Bernstein theorem

Hello,

I have to prove, that the sets , which is a set containing Cartesian product of elements from the set of integers and from the set of positive natural numbers, has the same cardinality as , a set of rational numbers using Cantor-Bernstein theorem, which states that two sets have the same cardinality, if we can create two injective functions, one from the first set to the other, and the second from the second set to the first.

So in my opinion these are the two functions:



For the function gives a such that:

1)if then

2)if then

Because if we will get integers, but no other in natural numbers divides , so we will get fractions, and because every time is different, so the prime factors of the whole thing will be different, so we will get a different rational number every time.

3)if then

Because so every time in my formula, so when we can put in the numerator.



For any we choose such that and :
1) if we return
2) if we return .


Are those two function correct?

Your mapping from is good.

The mapping for also looks good.

For the first injection is following map also correct?



For the function gives a such that:

Originally Posted by MachinePL1993

For the first injection is following map also correct?



For the function gives a such that:

That is correct. Probably the most natural thing to have done here would be to define by exactly which is an injection by the fundamental theorem of arithmetic. Then, the backwards injection could have been where are coprime and .