# Cardinality and infinite sets: naturals, integers, rationals, bijections

I have alot of questions.

• Do Infinite sets have the same cardinality when there is a bijection between them?

• Are $\mathbb{N}$ and $\mathbb{Z}$ infinite sets? I assume they are, but why? Why does there not exist a bijection between them?

• Why do $\mathbb{N}, \mathbb{Z}, \mathbb{Q}$ have the same cardinality? I assume there exists a bijection between them, but how can I find this function?

-
In your second question you ask why there does not exist a bijection between $\mathbb{N}$ and $\mathbb{Z}$ yet in your third question you assume there exists a bijection between them (and with $\mathbb{Q}$). I think your questions should be edited, since I doubt you intended to have such a contradiction. –  Quinn Culver Oct 22 '11 at 13:16
Your question suggests that you have heard some interesting words somewhere (perhaps in a popular work?), but don't have access to a textbook or lecture notes that develop their most basic features. That's no fault of yours, of course -- but it would help us giving good answers if you had described in your question what prompted you to ask: where did you hear about cardinalities and how much did this source tell you? –  Henning Makholm Oct 22 '11 at 13:20

First of all, I suggest you find a good article/book on Cantor's work on multiple infinities. Reading that will enlighten you and answer probably most of the questions you have concerning this subject. Try these lecture notes.

But to give a brief answer to your current questions:

1. Per definition, two sets have the same cardinality if there exists a bijection between them. This definition was introduced by Cantor because for infinite sets, you could not just count the elements. Not all infinite sets have the same cardinality. For example, the natural numbers $\mathbb{N}$ and the real numbers $\mathbb{R}$ do not have the same cardinality. This was proven with the diagonal argument.

2. $\mathbb{N}$ and $\mathbb{Z}$ are both infinite sets. I suggest you check out their definitions on wikipedia (the natural numbers, the integers). They also, like Ali said in his post, have the same cardinality. The bijection that was given by him is probably the easiest one to grasp.

3. As for $\mathbb{Q}$, the rational numbers, this is also an infinite set that has the same cardinality as $\mathbb{N}$ (and thus also $\mathbb{Z}$). I suggest you check out the bijection that is given in the lectures notes that I linked above, that one is probably the clearest one.

-

Let us define what cardinality is.

$A\preceq B$ if and only if there exists an injection from $A$ to $B$.

1. The identity shows that $A\preceq A$, therefore this is a reflexive relation
2. Suppose $A\preceq B$ and $B\preceq C$ then there are injections $f\colon A\to B$ and $g\colon B\to C$. Composing them yields an injection from $A$ to $C$, demonstrating transitivity.

This is a quasi-order, since it is not anti-symmetric. However we can now take the equivalence relation:

$$A\sim B\iff A\preceq B\ \text{and}\ B\preceq A$$

The Cantor-Bernstein theorem tells us that $\sim$ is exactly the relation defined as $A\sim B$ if and only if there exists a bijection between $A$ and $B$.

Now we denote $|A|$ to be the equivalence class of $A$ under $\sim$, if the axiom of choice is assumed then we can define a canonical representative for this equivalence class, namely $\aleph$ numbers and natural numbers.

This should answer thoroughly the first question. Yes, two sets have the same cardinality if and only if there exists a bijection between them. This is not only for infinite sets, but for finite sets as well. For example $\{0,1,2\}$ has exactly the same number of elements as $\{2134,5786,x\}$.

For the second two questions, first you need to remember that if you did not find it that does not mean that it does not exist. An explicit bijection between from $\mathbb N$ to $\mathbb Z$ can be given as follows:

$$f(n) = \begin{cases} \frac{n}{2} &n=2k\\ \frac{-n-1}{2} &n=2k+1\end{cases}$$

In a nutshell, we map the odd numbers as negative integers and the even numbers as positive integers, zero stays as zero.

To find a map from $\mathbb N$ to $\mathbb Q$ explicitly one has to work harder. Instead, we can use the fact I have used when defining cardinality. Namely, show that $\mathbb Q\preceq\mathbb N$ and $\mathbb N\preceq\mathbb Q$.

The identity map shows that $\mathbb N\preceq\mathbb Q$, as it can be treated as as subset of the rational numbers, and the identity map is always injective.

In the other direction, let $\frac{p}{q}\in\mathbb Q$ be a fraction such that:

1. $p$ and $q$ are coprime so the fraction is irreducible (that is $\frac{1}{3}$ is chosen instead of $\frac{2}{6}$)
2. $q>0$ and $p\in\mathbb Z$ (so $\frac{-1}{3}$ is taken and not $\frac{1}{-3}$)

Now we map $\frac{p}{q}$ to the positive integer $2^p\cdot 3^q$. Using the fundamental theorem of arithmetics this map is indeed injective. It is quite plain that it is far from being bijective though, since $5$ is not in the range.

However this shows that $\mathbb Q\preceq\mathbb N$, which is what we need to run the Cantor-Bernstein theorem and have a bijection between the two.

Added: I should probably add the definition of an infinite set, which is less trivial than one thinks.

A set is finite if for some $n\in\mathbb N$ there is a bijection between the set and $\{0,\ldots,n-1\}$.

We have that a set is infinite if and only if it is not finite, and in the case of the natural numbers it can be shown easily that there is no finite set whose cardinality is the same.

-
Nicely done! I like the map from $\frac{p}{q}$ to $2^p\cdot3^q$ particularly. (+1) –  robjohn Oct 22 '11 at 14:12
Incidentally, the map $\frac p q\mapsto 2^p\cdot 3^q$ only works as a map from the non-negative rationals into $\Bbb N$. –  Cameron Buie Jun 23 '13 at 11:05
@Cameron: Of course. One can easily overcome this by requiring that $\frac{-p}q\mapsto 5^p\cdot 3^q$ (where $p,q\geq 0$ and coprime). –  Asaf Karagila Jun 23 '13 at 14:24
Sure, that works. Alternately, you could use the non-negative rationals only, and then use the given map to construct a bijection $\Bbb N\to\Bbb Q$ by taking $0\mapsto 0$, and for all positive $n\in\Bbb N,$ take $2n-1$ to the rational with the $n$th least $2^p3^q$ value--$1\mapsto 1,3\mapsto 2, 5\mapsto\frac12,$ and so on--then taking $2n$ to the opposite (e.g.: $2\mapsto -1$). Then there's no need for CSB. –  Cameron Buie Jun 23 '13 at 14:40
@Cameron: Yes, that also works. I won't edit any of that in because there's little sense in bumping this ancient thread for such an insignificant matter. –  Asaf Karagila Jun 23 '13 at 14:41

I answer your question in the order.

First, infinite sets do not have the same cardinality. Two infinite sets have the same cardinality if and only if there exists a bijection between them.

$\mathbb{N}$ and $\mathbb{Z}$ are both infinite sets and they have the same cardinality. A bijection between $\mathbb{N}$ and $\mathbb{Z}$ is for instance a map $\mathbb{Z} \to \mathbb{N}$ sending $k \mapsto 2k$ and $-k \mapsto 2k+1$ for $k \in \mathbb{Z}$ and $k > 0$ and $0 \mapsto 0$ which is easily seen to be bijective.

I have just showed that $\mathbb{N}$ and $\mathbb{Z}$ have the same cardinality. Now for $\mathbb{Q}$ just observe that there is an injection $\mathbb{Q} \to \mathbb{Z} \times \mathbb{N}$ sending $m /n \mapsto (m,n)$ for $m \in \mathbb{Z}$ and $n \in \mathbb{N}$ (such that $m$ and $n$ are coprime) and then you can easily construct a bijection from $\mathbb{N} \times \mathbb{N}$ onto $\mathbb{N}$. For example the mapping $0 ↔ (0,0), 1 ↔ (1,0), 2 ↔ (0,1), 3 ↔ (2,0), 4 ↔ (1,1), 5 ↔ (0,2), 6 ↔ (3,0)$ is such a bijection. Of course, I did not construct a "bijection" from $\mathbb{Q}$ onto $\mathbb{N}$ explicitly but when you have an injection from an infinite set to another infinite set this means that the cardinality of the first set is less or equal to the cardinality of the second set. But since $\mathbb{N} \subset \mathbb{Q}$ it follows also there is an injection from $\mathbb{N}$ to $\mathbb{Q}$ hence they have the same cardinality.

-
The map $\mathbb{Q} \to \mathbb{Z} \times \mathbb{N}$ sending $m/n \mapsto (m,n)$ is not well-defined until you specify $gcd(|m|,n)=1$ and define $0 = 0/1$. Fortunately, this does not ruin the proof: The map becomes an injection $\mathbb{Q} \hookrightarrow \mathbb{Z} \times \mathbb{N}$, proving the cardinality of $\mathbb{Q}$ is no greater than the cardinality of $\mathbb{Z} \times \mathbb{N}$. –  Shaun Ault Oct 22 '11 at 12:45
Shaun: Thank you for the precision. –  user17090 Oct 22 '11 at 12:50