# Proving equal cardinality of sets using Cantor-Bernstein theorem

• Dec 15th 2012, 06:07 AM
MachinePL1993
Proving equal cardinality of sets using Cantor-Bernstein theorem
Hello,

I have to prove, that the sets $Z \times N^{+}$, 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 $Q$, 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:

$f1: Z \times N^{+} \rightarrow Q$

For $ \in Z \times N^{+}$ the function gives a $q \in Q$ such that:

1)if $a>0$ then $q=\frac{(b+1)^{a}}{b}}$

2)if $a<0$ then $q=\frac{-(b+1)^{-a}}{b}}$

Because if $b=1$ we will get integers, but no other $b$ in natural numbers divides $b+1$, so we will get fractions, and because every time $a$ 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 $a=0$ then $q=\frac{(1)}{b}}$

Because $b \in N^{+}$ so $b+1>=2$ every time in my formula, so when $a=0$ we can put $1$ in the numerator.

$f2: Q \rightarrow Z \times N^{+}$

For any $q \in Q$ we choose $m,n \in N$ such that $\frac{m}{n}=|q|$ and :
1) if $q>=0$ we return $$
2) if $q<0$ we return $<-m,n>$.

Are those two function correct?
• Dec 15th 2012, 07:05 AM
jakncoke
Re: Proving equal cardinality of sets using Cantor-Bernstein theorem
Your mapping from $\mathbb{Z} \times \mathbb{N^{+}} \to \mathbb{Q}$ is good.

The mapping for $\mathbb{Q} \to \mathbb{Z} \times \mathbb{N^{+}}$ also looks good.
• Dec 16th 2012, 05:03 PM
MachinePL1993
Re: Proving equal cardinality of sets using Cantor-Bernstein theorem
For the first injection is following map also correct?

$f1: Z \times N^{+} \rightarrow Q$

For $ \in Z \times N^{+}$ the function gives a $q \in Q$ such that:

$q=\frac{2^{a}}{3^{b}}}$
• Dec 17th 2012, 03:23 PM
Drexel28
Re: Proving equal cardinality of sets using Cantor-Bernstein theorem
Quote:

Originally Posted by MachinePL1993
For the first injection is following map also correct?

$f1: Z \times N^{+} \rightarrow Q$

For $ \in Z \times N^{+}$ the function gives a $q \in Q$ such that:

$q=\frac{2^{a}}{3^{b}}}$

That is correct. Probably the most natural thing to have done here would be to define $\mathbb{Z}\times\mathbb{N}\to\mathbb{Q}$ by exactly $(a,b)\mapsto 2^a 3^b$ which is an injection by the fundamental theorem of arithmetic. Then, the backwards injection could have been $\frac{a}{b}\mapsto (a,b)$ where $a,b$ are coprime and $b\in\mathbb{N}$.