5
$\begingroup$

By definition, a set $S$ is called countable if there exists an bijective function $f$ from $S$ to the natural numbers $N$.

If we take a function $g\colon\mathbb{Z\times N\to Q}$ given by $g(m, n) = \frac{m}{ n} $ to "construct" rational numbers, $g$ would only be a surjection from the countable set $\mathbb{Z\times N}$ to $\mathbb Q$. It's not injective, or is it?

$\endgroup$
9
  • 3
    $\begingroup$ If there's a surjection then there is an injection. You may need here the Axiom of Choice, though. $\endgroup$
    – Timbuc
    Feb 6, 2015 at 10:57
  • $\begingroup$ I don't agree. A function can be surjective and not injective. $\endgroup$ Feb 6, 2015 at 11:03
  • $\begingroup$ I didn't say otherwise: I wrote that if you have a surjection then you can build, with AC, and injection, not that the surjection has to be also an injection. $\endgroup$
    – Timbuc
    Feb 6, 2015 at 11:10
  • $\begingroup$ @user1511417 You got the tricky part. It is not just the same case like counting $\mathbb{N}^2$. $\endgroup$
    – mvw
    Feb 6, 2015 at 11:20
  • 1
    $\begingroup$ @Timbuc: Why involve the axiom of choice, where all the sets you deal with are countable? $\endgroup$
    – Asaf Karagila
    Feb 6, 2015 at 11:22

6 Answers 6

9
$\begingroup$

Explicit bijections are overrated.

We can prove the following three things (without the axiom of choice, which has been mentioned in the comments):

  1. If $A\subseteq\Bbb N$ then it is either finite or countably infinite.
  2. If $f\colon\Bbb N\to X$ is surjective, then $X$ is finite or countably infinite.
  3. There is a surjection from $\Bbb N$ onto $\Bbb Q$.

The first proof is quite easy, we simply start to enumerate $A$ according to the order induced from the usual order of the the natural numbers. Either we "finish" the set, in which case it's finite, or the enumeration produces a bijection of $A$ with $\Bbb N$.

The second proof is also easy, since the function is a surjection, every $x\in X$ has a least $n\in\Bbb N$ such that $f(n)=x$. This minimal $n$ is unique, so we defined an injection from $X$ into $\Bbb N$, which is a bijection with a subset of $\Bbb N$. By the first claim, $X$ is finite or countably infinite.

The last proof is also not difficult. First write a surjection of $\Bbb N$ onto $\Bbb{N\times N}$ and a surjection from $\Bbb N$ onto $\Bbb Z\setminus\{0\}$, compose them to a surjection from $\Bbb N$ onto $\Bbb{N\times (Z\setminus\{0\})}$. Then you the surjection you have defined, $(n,m)\mapsto\frac nm$.

Now we can conclude the fourth statement:

  1. $\Bbb Q$ is countably infinite.

Of course $\Bbb Q$ is not finite, and since there is a surjection from $\Bbb N$ onto $\Bbb Q$, the claim is proved.

$\endgroup$
2
$\begingroup$

Here's an intuitive but very helpful to understand picture. enter image description here

$\endgroup$
1
  • $\begingroup$ This suits bharb's explanation. $\endgroup$ Feb 6, 2015 at 11:21
1
$\begingroup$

You are correct. In fact, this is not the function used to count rational numbers.

Imagine listing all of those numbers excluding the ones in which the fraction can be simplified.

A possible bijection could be that function that gives the position of the rational number in that list. Since the list contains each rational number, the function is surjective. But each number has a different position in the list: hence, the function is surjective.

This is an "intuitive" point of view. If you want a more formal demonstration here it is:

Define the mapping $\psi: \mathbb Q \rightarrow \mathbb Z \times \mathbb N$ such that for every $\frac{m}{n} \in \mathbb Q$ in canonical form $\psi(\frac{m}{n})=(m,n)$

Then $\psi$ is clearly injective. From the fact that cartesian product of countably infinite sets is countably infinite, $\mathbb Z \times \mathbb N$ is countable. Because the domain of injection to a countable set is countable, $\mathbb Q$ is countable.

$\endgroup$
10
  • $\begingroup$ That is not the bijection used for anything: that function simply is not a bijection. $\endgroup$
    – Timbuc
    Feb 6, 2015 at 11:13
  • $\begingroup$ Timbuc, you are right. I meant function. Thanks for the comment, I'll edit the post $\endgroup$
    – Lonidard
    Feb 6, 2015 at 11:14
  • $\begingroup$ That's plausible for me. Thanks. For a bijection it's a prerequisite that $Q$ is in its canonical form. $\endgroup$ Feb 6, 2015 at 11:20
  • $\begingroup$ Exactly. In most of the proofs I've seen, this is part of the requirements. $\endgroup$
    – Lonidard
    Feb 6, 2015 at 11:26
  • 1
    $\begingroup$ Wait, how is $\psi$ surjective? $(2,4)$ is not in its image, and if it is then $(1,2)$ is not, and if it is, then it's not a function! $\endgroup$
    – Asaf Karagila
    Feb 6, 2015 at 11:31
0
$\begingroup$

Consider the plane $\mathbb Z\times\mathbb Z$. Clearly you can fill it by spiraling from the origin. Avoid counting the undefined fractions and those already seen before (after simplification).

$\endgroup$
1
  • $\begingroup$ I preferred to work in $\mathbb Z\times\mathbb Z$ as the trajectory can be described with just one word. $\endgroup$
    – user65203
    Feb 6, 2015 at 11:37
0
$\begingroup$

The Farey sequence gives a bijection between the nonnegative rationals and $\mathbb{N}$.
Step 0: Start with two numbers $\frac01,\frac10$ ($\frac10$ is just a place-holder.) $\frac01$ is rational number $1$.
Step N: between consecutive numbers$\frac{a}{b},\frac{c}{d}$, write $\frac{a+c}{b+d}$ These are rationals number $2^{N-1}+1$ to number $2^N$
The sequence starts
$$\frac01,\frac10\\ \frac01,\frac11,\frac10\\ \frac01,\frac12,\frac11,\frac21,\frac10\\ \frac01,\frac13,\frac12,\frac23,\frac11,\frac32,\frac21,\frac31,\frac10$$
To include the negatives, put the negative numbers in the even positions and positive numbers in the odd positions.

$\endgroup$
0
$\begingroup$

Let us enumerate the elements of $\{0\}\cup\{1,2,...\}\!\!\times\!\!\{1,2,...\}\!\!\times\!\!\{+,-\}$. Start with $0$. Then, for given $n$, list all $2n$ elements $(j,k,\pm)$ such that $j+k=n$, successively in the order $(1,n-1),...,(n,1)$, with $+$ signs attached, followed by the same elements with $-$ signs. Do this consecutively for $n=1,2,...$. This list is countable. Now run through the list in order and delete any element $(l,m,\pm)$ for which there was an earlier-occurring element $(j,k,\pm)$ (with the same sign) such that $j/k=l/m$. Now we have a countable list that is in one-to-one correspondence with the rational numbers $\Bbb Q$: namely, $(j,k,\pm)$ corresponds to $q\in\Bbb Q$ if and only the signs are the same and $j/k=q$, with the initial $0$ corresponding to the $0$ in $\Bbb Q$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .