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

Solution 1:

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.

Solution 2:

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.

Solution 3:

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.