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. :(
 A: 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.
A: 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.
A: 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.
A: 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?
