# Why do the rationals, integers and naturals all have the same cardinality?

So I answered this question: Are all infinities equal? I believe my answer is correct, however one thing I couldn't explain fully, and which is bugging me, is why the rationals $\mathbb Q$, integers $\mathbb Z$ and naturals $\mathbb N$ all have cardinality $| \mathbb Q |=| \mathbb Z | = |\mathbb N| = \aleph_0$, when $\mathbb N \subsetneq \mathbb Z \subsetneq \mathbb Q$.

The basic proof of the other question, from my answer, is that for any $r$ in $\mathbb Q$ there is a single function $f(r)$ such that $f(r) \in \mathbb Z$, and the same holds between $\mathbb Z$ and $\mathbb N$. Because there is this 1:1 transformation possible, there must be the same number of numbers in the three sets, because otherwise there would be a number in one set for which the bijection could not produce a number of the other set, and this is not so.

Now, Belgi explained why $1<2$ in the other question by defining the value 0 as the cardinality of the empty set $\emptyset$, 1 as the cardinality of a set of sets containing only the empty set, and 2 as the set of sets containing the empty set and a set containing the empty set, then proceeding as follows:

Now that we have defined the natural numbers we can define when one number is smaller than another. The definition is $x<y$ is $x\subset y$ and $x\neq y$ .

Clearly $\{\emptyset\}\neq\{\emptyset,\{\emptyset\}\}$ and $\{\emptyset\}\subset\neq\{\emptyset,\{\emptyset\}\}$ So this a proof, by definition, of why $1<2$.

... however, by the same definition, because $\mathbb N \subsetneq \mathbb Z \subsetneq \mathbb Q$, then $| \mathbb N | < | \mathbb Z | < |\mathbb Q|$ and thus a maximum of one of these quantities can be the ordinal quantity $\aleph_0$.

• Usually, the integers are denoted by $\mathbb{Z}$, the rationals by $\mathbb{Q}$. The reals are denoted by $\mathbb{R}$. Please, consider editing you text. – Sigur Aug 13 '12 at 22:52
• That definition only works for finite sets. For infinite sets, it conflicts with the notion that two sets have the same cardinality if and only if there's a bijection between them. One of the two ideas has got to go, and for good reasons the convention is to keep the bijection concept and scrap the other one. – Gerry Myerson Aug 13 '12 at 22:53
• This answer of mine might be relevant here. – Asaf Karagila Aug 13 '12 at 22:55
• the integers are just 2 copies of the naturals, the rationals are a subset of the set of pairs of integers. explicitly $f:\mathbb{N}\to\mathbb{Z}, f(2k)=k, f(2k+1)=-k$ is a bijection, while one for the rationals would be more complicated – butt Aug 13 '12 at 23:08
• Possible duplicate of Produce an explicit bijection between rationals and naturals? – Xander Henderson Mar 20 '18 at 2:13

The first thing you need to ask yourself, about finite sets, is this: When do two sets have the same cardinality?

The way mathematics works is to take a property that we know very well, and do our best to extract its abstract properties to describe some sort of general construct which applies in as many cases as possible.

So how do we compare the sizes of two finite sets? If we can write a table, in one column the set $A$ and in the other the set $B$, and each element from $A$ appears in a unique cell; and each element of $B$ appears in a unique cell. If this table have no rows in which there is only one element, then the sets $A$ and $B$ are equal. For example: $$\begin{array}{lc} \text{Two equal sets:} & \begin{array}{c|c|c}A & a_1& a_2\\\hline B & b_1& b_2\end{array} \\ \text{Non-equal sets:} & \begin{array}{c|c|c|c}A & a_1 & a_2 & a_3\\\hline B & b_1 & b_2\end{array} & \end{array}$$

It is clear that this methods captures exactly when two sets have the same size. We don't require one set to be the subset of another; nor we require that they share the same elements. We only require that such table can be constructed.

Well, the generalization is simply to say that there exists a function from $A$ to $B$ which is injective and surjective, namely every element of $A$ has a unique element of $B$ attached to it; and every element of $B$ has a unique element of $A$ attached to it.

It turns out, however, that this notion has a quirky little thing about infinite sets: infinite sets can have proper subsets with the same cardinalities.

Why is this happening? Well, infinity is quite the strange beast. It goes on without an end, and it allows us to "move around" and shift things in a very nice way. For example consider the following table: $$\begin{array}{c|c|c|c|c|c} \mathbb N&0&1&\cdots&n&\cdots\\\hline \mathbb N\setminus\{0\}& 1&2&\cdots & n+1&\cdots \end{array}$$

It is not hard to see that this table has no incomplete rows and that every element of the left set ($\mathbb N$) appears exactly once, and every element of the right set ($\mathbb N\setminus\{0\}$) appears exactly once!

This can get infinitely more complicated, and so on and so on.

One can ask, maybe we are thinking about it the wrong way? Well, the answer is that it is possible. We can define "size" in other ways. Cardinality is just one way. The problem is that there are certain properties we want the notion of "size" to have. We want this notion to be anti-symmetric and transitive, for example.

Namely, if $A$ is smaller or equal than $B$ and $B$ is smaller or equal in size than $A$, then $A$ and $B$ have the same size; if $B$ also has the same size as $C$ as well, then $A$ and $C$ are of the same size too. It turns out that the notion described by functions has these properties. Other notions may lack one or both. Some notions of "size" lack anti-symmetry, others may lack transitivity.

So it turns out that cardinality is quite useful and it works pretty fine. However it has a peculiarity... well, who hasn't got one these days?

To overcome this, we need to change the way we think a bit: proper subset need not have a strictly smaller cardinality. It just should have not a larger cardinality. This is the right generalization from the finite case, rather than the naive "strict subset implies strictly smaller".

• As always, @Asaf gives a very cogent answer. – Code-Guru Aug 13 '12 at 23:56
• @Code-Guru: Thanks! – Asaf Karagila Aug 14 '12 at 0:44

We can build a couple of bijections among $\mathbb{Q}$, $\mathbb{Z}$ and $\mathbb{N}$.

First we can construct a bijective function $f: \mathbb{N}_{+} \rightarrow \mathbb{N}$.

$$f (n) = n-1 \\ f^{-1} (n) = n+1$$

This can be proven by induction. I think this gives you an idea that even if $\mathbb{N}_{+} \subsetneq \mathbb{N}$, but $|\mathbb{N}_{+}| = |\mathbb{N}|$.

You doubt is concurred by Cantor: Je le vois, mais je le ne crois pas!

• $f: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$.

• $f: \mathbb{N}^{m} \rightarrow \mathbb{N}$, m is a finite natural, proved also by induction

• $f: \mathbb{Z} \rightarrow \mathbb{N}$, positive numbers onto evens, negative numbers to odds

• $f: \mathbb{Q} \rightarrow \mathbb{N}$, a rational is a fraction of two integers, i.e.

$$f: \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{N}$$

Let q = m/n be a positive rational with positive m,n in lowest terms.
Map q to $2^m × 3^n$.
As this map is an injection into N, the positive rationals are countable.
With that it is easy to show that Q is countable.