# How do we determine if the set of rational numbers and the set of all english sentences are countable or not?

How do we determine if the set of rational numbers and the set of all english sentences are countable or not? I had proved it for the set of Integers in graduation. Our instructor at that time told us that there is some special way to prove it for these two sets but he did not say how. :(

-
Reposted from mathoverflow.net/questions/105740/… as requested. – Joel Reyes Noche Aug 29 '12 at 0:07

A simple way you can order the positive rationals $m/n$ is by "packets" in which $m+n$ is constant and within each packet, which consists of finitely many fractions, by size of $m$. So the list starts $$0,1,1/2,2,1/3,3,1/4,2/3,3/2,4,1/5,\ldots.$$ Then you insert the negative in alternate places and you get a complete list of rationals: $$0,1,-1,1/2,-1/2,2,-2,1/3,-1/3,3,-3,1/4,-1/4,2/3,\ldots.$$ For English (or whatever language) you do basically the same thing using the alphabetic order instead: you start with all the 1 letter sentences, then all the 2 letter sentences and so on. This list contains all sentences because every sentence has a finite length.

-

Observe that if a set $A$ is countable then $A\times A$ is also countable: to convince you that it is the case just try to make a picture and represent a set $A$ as a discrete half-line. Then $A\times A$ can be represented by an infinite grid of points. Just draw a line starting form one of its corner and going through all of its points (every point visited once), its easy :)

Now observe that every rational number can be represented by a pair of two integers (not uniquely!) and thus the cardinality of $\mathbb{Q}$ is at most as big as the cardinality of $\mathbb{Z}\times\mathbb{Z}$ -which is a countable set. Since $\mathbb{N}\subset\mathbb{Q}$ and $\mathbb{Q}$ is at most countable it is indeed a countable set.

By the way observe that every finite cartesian product of counatable sets is countable itself.

Now for the set of all English sentences. Every English sentence is a finite string of symbols, those symbols are taken from a finite set (all letters and some special characters).

So there is finitly many sequences of length $0$ :), finitly many sentences of length $1$, finitly many sentences of length $2$ and so on. Therefore a set of all sentences in English is a union of a countably many finite sets, and thus is countable.

In general a countable union of countable sets is a countable set. This fact is a little bit harder to show so just look into any textbook about set theory to see the details.

-

Just because I was curious how well this would work without a nice diagram package...

The method Andrea Mori suggested (and perhaps the reason it was referred to as Cantor's diagonal argument in another answer) has a nice geometric flavour. Make a diagram of (positive) rational numbers in an array, where each row has the same numerator, and each column has the same denominator.

$$\begin{array}{cccccccc} \frac11 & \frac12 & \frac13 & \frac14 & \frac15 & \frac16 & \frac17 & \cdots\\ \frac21 & \frac22 & \frac23 & \frac24 & \frac25 & \frac26 & \frac27 & \cdots\\ \frac31 & \frac32 & \frac33 & \frac34 & \frac35 & \frac36 & \frac37 & \cdots\\ \frac41 & \frac42 & \frac43 & \frac44 & \frac45 & \frac46 & \frac47 & \cdots\\ \frac51 & \frac52 & \frac53 & \frac54 & \frac55 & \frac56 & \frac57 & \cdots\\ \frac61 & \frac62 & \frac63 & \frac64 & \frac65 & \frac66 & \frac67 & \cdots\\ \frac71 & \frac72 & \frac73 & \frac74 & \frac75 & \frac76 & \frac77 & \cdots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}$$

Now because the fraction $\frac ab$ occurs in row $a$ and column $b$, we know this "box" contains every (positive) rational number. Now, can we use this to see that the (positive) rationals are countable? Sure! We simply need to find a way to list them (all) as a sequence. Note that if we wanted to go row by row, we'd never get to the end of the first row, so that won't work. Similarly, if we want to go column by column, we'll never get from the first column to the second (and on from there!). So we'll use a diagonal approach. We start in the top left corner, and go right, then diagonally down left as follows: $$\begin{array}{cccc} \frac11 & \rightarrow & \frac12 & \cdots \\ & \swarrow & & \\ \frac21 & & \frac22 & \cdots \\ \vdots & & \vdots & \ddots \end{array}$$ We've got all three of the "top left" elements (our sequence is $1, \frac12, \frac21$), so go down, and grab everything along the diagonal again. $$\begin{array}{ccccccc} \frac11 & \rightarrow & \frac12 & & \frac13 & \cdots \\ & \swarrow & & \nearrow & & \\ \frac21 & & \frac22 & & \frac23 & \cdots \\ \downarrow & \nearrow & & & & \\ \frac31 & & \frac32 & & \frac33 & \cdots \\ \vdots & & \vdots & & \vdots & \ddots \end{array}$$ We've got everything at the top left corner again (our sequence is now $1, \frac12, \frac21, \frac31, \frac22, \frac13$). Go right and diagonal, down and diagonal, right and diagonal, and keep going. You'll never miss a number in the box! (Here goes...) $$\begin{array}{ccccccccccccccc} \frac11 & \rightarrow & \frac12 && \frac13 & \rightarrow & \frac14 && \frac15 & \rightarrow &\frac16 && \frac17 &\rightarrow & \cdots\\ & \swarrow && \nearrow && \swarrow && \nearrow && \swarrow && \nearrow &&& \\ \frac21 & &\frac22 && \frac23 && \frac24 && \frac25 && \frac26 && \frac27 && \cdots\\ \downarrow & \nearrow && \swarrow && \nearrow && \swarrow && \nearrow &&&&& \\ \frac31 && \frac32 && \frac33 && \frac34 && \frac35 && \frac36 && \frac37 && \cdots\\ & \swarrow && \nearrow && \swarrow && \nearrow &&&&&&& \\ \frac41 && \frac42 && \frac43 && \frac44 && \frac45 && \frac46 && \frac47 && \cdots\\ \downarrow & \nearrow && \swarrow && \nearrow &&&&&&&&& \\ \frac51 && \frac52 && \frac53 && \frac54 && \frac55 && \frac56 && \frac57 && \cdots\\ & \swarrow && \nearrow && &&&&&&&&& \\ \frac61 && \frac62 && \frac63 && \frac64 && \frac65 && \frac66 && \frac67 && \cdots\\ \downarrow & \nearrow &&&&&&&&&&&&& \\ \frac71 && \frac72 && \frac73 && \frac74 && \frac75 && \frac76 && \frac77 && \cdots\\ \vdots && \vdots && \vdots && \vdots && \vdots && \vdots && \vdots && \ddots \end{array}$$

So what have we done? We've got a sequence containing all the positive rational numbers, and so this "box" has a countable number of elements. We've actually got more than just the positive rational numbers, since for example, $\frac11 = \frac22 = \frac33 = \cdots$ and a lot of cancellation is occuring, but that doesn't really matter, because it means the positive rationals are contained in a countable set, and so must be countable. I suppose I can mention, if you look along any of the diagonals, all the fractions have the same sum of numerator and denominator, which is how Andrea Mori suggested you count them. This is just a fun way of looking at things :)

Now, adding the negative of each element just "doubles the size" (just like going from natural numbers to the integers), and so is a way to see the rational numbers are countable.

Others have already mentioned why the set of all English sentences is countable, so I'll leave that for now, though if you still have questions, feel free to ask!

-

In general you need to use a bijection, which relates one element of the first set to one of the other, with no leftovers in each set. Looking at infinite countable sets actually makes this relatively simple in abstract: though specific examples may be different. the idea is that if we can show a set is countable if we can form a bijection between it and the natural numbers. To do this, list the members of the set:

$$a_1,a_2,a_3,a_4...$$

where $a_n$ is the $n^{th}$ element of the set in this list.

And you're done! The fact that you have $a_{\textbf{1}}, a_{\textbf{2}}, a_{\textbf{3}},$ etc. is a bijection to the naturals already. So if you can find a way to list all the elements of the set, and show that the set is infinite, then you're done! Can you think of ways to list these? $\textbf{Hint:}$ The rationals can't be listed in order, but they can be listed.

-

For the set of rationals, you might want to google "Cantor's diagonal argument zig-zag function" and read up :) (The diagonal argument is interesting too, but not what I intended...)

Would you agree that the set of English sentences can be fully described as "finite strings of a finite collection of symbols"? (You would probably want all the letters, all punctuation and then spaces, I would assume. That's still a finite set though!)

If you are using a set of symbols $S$, that would make English sentences a subset of the produt of countably many copies of $S$ ($\prod_{i=1}^\infty S$). Do you know anything about this set's cardinality?

-
Actually Cantor's diagonal argument shows that the reals are not countable. – Andrea Mori Aug 28 '12 at 20:55
What you're looking for is probably "Cantor's zig-zag function". – Henning Makholm Aug 28 '12 at 21:14
@AndreaMori I'm speechless. My brain must be running out of storage and the gnomes are starting to stack two things in the same spot... – rschwieb Aug 29 '12 at 1:33