1
$\begingroup$

This concept has been troubling me. For example, I want to prove that $$\mathbb Q \times \mathbb Q \sim \mathbb N.$$

This is what my professor has told us:

$$\mathbb Q \sim \mathbb N$$

$$\Rightarrow \mathbb Q \times \mathbb Q \sim \mathbb N \times \mathbb N \sim \mathbb N$$ $$\Rightarrow \mathbb Q \times \mathbb Q \sim \mathbb N$$

But this isn't a complete proof because I haven't shown why $\mathbb Q \sim \mathbb N$, and I'm not sure how to do that. I know that if a set is denumerable, that means that it is equinumerous with $\mathbb N$. And I also know that if one is equinumerous with another, that means that there exists a bijection between the two sets. I'm just having trouble putting all of these ideas together into one proof.

  • 0
    It won't be easy to create a bijection, if you wish to do so, look at, e.g. [Stern-Brocot tree](http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree). On the other hand, it would be quite easy to find injections $f$ and $g$ such that $\mathbb{Q}\times\mathbb{Q} \xrightarrow{f} \mathbb{N}$ and $\mathbb{N} \xrightarrow{g} \mathbb{Q}\times\mathbb{Q}$.2012-12-11
  • 0
    Can you prove that $\mathbb{N}\sim \mathbb{Z}$? Because then you could try to find an injection $\mathbb{Q} \hookrightarrow \mathbb{Z}\times \mathbb{N}$...2012-12-11

4 Answers 4

2

Do you know the Schröder-Bernstein theorem? With it you need only find an injection from $\Bbb N$ to $\Bbb Q$, which is trivial, and from $\Bbb Q$ to $\Bbb N$. The latter is easily done using a pairing function from $\Bbb N\times\Bbb N$ to $\Bbb N$: just map each rational as the ordered pair of its numerator and denominator when it’s written in lowest terms with positive denominator.

1

Here is a "graphical" construction of a bijection between $\mathbb{Q}$ and $\mathbb{N}$ - it's going to be really hard to put into a formula, but I believe, and hope you will too, that it constitutes a valid proof:

We're going to build a sequence $q_n$ of all rational numbers such that each rational number appears only once. (This is exactly the meaning of a bijection.)

  1. Draw an infinite two-dimensional grid, such that at each square in the grid you have two integers: The "x" coordinate and the "y" coordinate. The "center" square is $(0, 0)$.

  2. Traverse the grid "inside out", by starting at the center square and going counterclockwise in a spiral: $(0, 0), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (1, 2), (0, 2), ...$

  3. Whenever you are at a square $(x, y)$, if $y=0$ then skip this square. Otherwise, use $x/y$ as the next element of your sequence $q_n$, unless you've already used this exact value, in which case - skip this square.

0

You'll agree that $\mathbb{Z}$ is equipotent to $\mathbb{N}$; $\mathbb{Q}$ is defined as a quotient of $ \mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$, thus the cardinality of $\mathbb{Q}$ is less or equal to that of $\mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$, which is the same as the cardinality of $\mathbb{N}$. Of course you have the opposite "inequality" (think of $\mathbb{N}$ as included in $\mathbb{Q}$, even if it's not correct), and you conclude by Schroeder-Bernstein theorem.

0

You can say that theorems in mathematics are like 'strategic acquisitions'. But even if the OP is lacking the theoretical underpinnings, we can still rigorously describe a bijection between $\mathbb N$ and $\mathbb Q$, and describe a tactical context.

We can 'acquire' a countably infinite set by 'building it up', one element at a time, from finite sets; here is the formal statement

Proposition 1: A set $A$ is countably infinite if there exist a family of subsets of $A$,
$(A_n)_{\, n \ge 0}$ satisfying

Moreover, the chain $A_0 \subset A_1 \subset A_2 \dots$ defines an explicit bijective enumeration of the set $A$.

$\quad |A_n| = n$
$\quad A_k \subset A_{k+1} \; \text{ for } k \ge 0$
$\quad A = \bigcup_k A_k$

Proof
Given such a chain of finite subsets, for every $k \ge 1$ there exist one and only one element $a_k \in A_k$ such that $a_k \notin A_{k-1}$. One can also easily show that $(a_k)_{\,k \ge 1}$ is a bijective enumeration of $A$. $\quad \blacksquare$

For the OP's problem, we want an (recursive) algorithm to create these subsets. Every finite set of $\Bbb Q$ is bounded, so tactically you want to 'crank-out' sets contained in $[-m, +m]$ and at some point widen the interval and simultaneously get better at 'adding in the still missing numbers'.

We are going to write the proof in the following section, using definitions to make the argument easier to follow. The detail seems appropriate since the OP's question has the tag proof-writing.


Definition: If $R$ is a nonempty finite subset $\Bbb Q$ then let $m$ be the smallest positive integer $m$ such that $R \subset [-m, +m]$. We call this interval the integer interval container for $R$.

For any $m \gt 0$ define the finite sets

$\quad R_m = \{ \frac{n}{d} \, | \, n \in \Bbb Z \land [1 \le d \le m] \land [-m \le \frac{n}{d} \le m]\}$

It is easy to see that the integer interval container for $R_m$ is $[-m, +m]$.

Let $R$ be any finite subset of $\mathbb Q$ with integer interval container $[-m, +m]$. If $R$ doesn't completely contain $R_m$, let $\mathcal{A}(R) = t$ where $t$ is the smallest number in $R_m$ such that $t \notin R$.

We are now ready to recursively construct our chain of subsets (see proposition 1), and $m$ will be associated with the integer interval container construct.

With $A_1 = \{0\}$ and given $A_k$ with $k \ge 0$, define

$$ A_{k+1} = \left\{\begin{array}{lr} A_k \, \cup \, \{m+1\}, & \text{when } R_m \subset A_k \\ A_k \, \cup \, \mathcal{A}(A_k) , & \text{when } \mathcal{A} \text{ can be applied} \end{array}\right\} $$

Setting $A_0 = \emptyset$, this recursion, produces just what we need to apply proposition 1. Here are the first few terms

$A_1 = \{0\} \quad m = 1$
$A_2 = \{-1, 0\}$
$A_3 = \{-1, 0,1\} \quad \text{contains } R_1$
$A_4 = \{-1, 0,1,2\} \quad m = 2$
$A_5 = \{-2, -1, 0,1,2\}$
$A_6 = \{-2,-\frac{3}{2}, -1, 0,1,2\}$

and just keep turning the 'recursive crank'