Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I know how to do the proof in terms of using Analysis but how do you do the proof for someone that does not have that much proof experience:

Prove that $\Bbb Q$ is a countable set.

share|improve this question
2  
What proof in terms of analysis are you referring to? –  gnometorule Feb 19 '13 at 2:57
2  
@DramaFreak you should show what you have and where you are stuck. –  gekkostate Feb 19 '13 at 2:59
    
I am confused how to start the proofs with the student. –  Username Unknown Feb 19 '13 at 3:01
    
@DramaFreak: I replied to your last comment in my answer. –  Asaf Karagila Feb 20 '13 at 17:03

5 Answers 5

up vote 5 down vote accepted

There are three equivalent ways to define countability (which include finite sets, if your definition excludes finite sets from being countable, as sometimes people do, add the requirement the set is infinite as well).

Theorem. Let $A$ be a set, then the following are equivalent:

  1. There exists an injection from $A$ into $\Bbb N$.
  2. There exists a surjection from $\Bbb N$ onto $A$.
  3. $A$ is finite or there exists a bijection between $A$ and $\Bbb N$.

In the case of proving the rationals are countable the easiest method is to use the first definition, that is simply show an injection from $\Bbb Q$ into $\Bbb N$. This is the easiest method because the order of the rationals is the "biggest" possible way to linearly order a countable set, and $\Bbb N$ has the "smallest" order possible of a countable set. So any concrete bijection is going to be ugly. But injections are a lot easier to work with.

If $x$ is a rational number then there is a unique way of writing $x=\frac pq$ where $p$ is any integer (negative, zero or positive), and $q$ is a positive integer, and either $p=0, q=1$ or $\gcd(p,q)=1$. That is, a reduced fraction. We use this to define the following injection:

$$f\left(\frac pq\right)=\begin{cases} 2^p\cdot 3^q & q>0\\ 2^p\cdot 5^{-q} & q<0\end{cases}$$

It is easy to see that this is an injection, if $f(x)=f(y)$ then by the uniqueness of factorization into prime factors we can show that $x=y$.


As for your comment about how to start the proofs, there is really just one way to start working on a proof when you are unfamiliar with a topic.

You open the notes, or the book, or the notebook, to the page where the definitions of what is "countable", and you understand it fully. If you are not quite clear about one or two points, e.g. what is a function or what is an injective function, then you flip to the relevant page and understand that as well.

After that you have understood all the relevant definitions well, you start by showing that these definitions hold in this case. Proofs in introductory level are hardly ever beyond the exercise in applying definitions, and are often coupled with the "right" definitions to begin with.

You should probably be familiar with previous theorems, previous exercises, other possibly-useful information that was given. This will make things easier to handle. If you already know that $\mathbb Z$ is countable and that $\mathbb {N\times N}$ is countable, then you can show that $\mathbb{Z\times N}$ is countable and map $\frac pq$ to $\langle p,q\rangle$ instead of a strange looking number; or if you have the second definition of countability available instead, simply map $\langle p,q\rangle$ to $\frac pq$, and show this is a surjection.

This is the simplest, clearest, and most direct way to approach a problem.

share|improve this answer
1  
This is my favorite proof that $\mathbb{Q}$ is countable. It also extends easily to prove other results, like the fact that (finite) Cartesian product of countable sets is countable. –  Aeolian Feb 19 '13 at 23:12
2  
Huh. I wonder why the downvote. Maybe $\Bbb Q$ is uncountable and I didn't know? –  Asaf Karagila Feb 20 '13 at 9:14
1  
I want to add to your advice about starting a proof: Coming up with examples and counter-examples is also excellent work for understanding the relevant definitions and theorems. In this case, for example, I might work with some small finite sets and create explicit injections, surjections, and bijections between them. Reading other proofs is also very helpful. In this case, looking at a proof that $\mathbb{Z}$ is countable and maybe a proof that $\mathbb{R}$ is uncountable might yield some good ideas. –  Todd Wilcox Feb 20 '13 at 20:03

Here is a proof that only involves countability of $\mathbb{Z}$ and $\mathbb{Q} \backslash \mathbb{Z}$. (http://www2.fiu.edu/~storferr/rat.num.ctble%5b1%5d.pdf)

share|improve this answer

You need to find show that a one-to-one correspondence exists between the rational numbers and the integers, which are countable. There are a number of ways to do this.

If you haven't yet proven that a there is a bijection ( a mapping, or one to one correspondence) between the set of integers and the natural numbers, which are countable, and hence the integers are countable, that might be your first step.


See, too, this one to one correspondence between $\mathbb N$ and $\mathbb Q$: it follows the statement of the theorem that the set of rationals $(\mathbb Q)$ is countable.

Finally, see this link for one route to use to prove the countability of $\mathbb{Q}^+$

share|improve this answer
    
Nice deduction amWhy. you did it. –  Babak S. Feb 21 '13 at 12:38

You find a way to pair up the rationals with the naturals. One way is described in wikipedia under theorem Q is countable

share|improve this answer

Consider running Euclid's algorithm (that calculates the gcd of two numbers):

Either (a,b) is taken to (a-b,b) or (a,b-a) depending on whether a>b or not.

Starting from the output (1,1), which says we started with a coprime pair.. we can consider running the algorithm in reverse to generate every possible coprime pair.

There are two choices, either we take (x,y) to (x+y,y) or (x,x+y) giving either (2,1) or (1,2)

For each of these there are again two choices: (3,1), (2,3) or (3,2), (1,3)

For each of these there are again two choices: (4,1), (3,4) or (5,3), (2,5) or (5,2), (3,5) or (4,3), (1,4)

etc..

Label each choice by 0 or 1: This shows that the finite binary strings e.g. 01 are in bijection with pairs of coprime numbers i.e. (2,3).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.