# Bishop's paradox of the countability of sequences

In 'Foundations of Constructive Analysis', in the notes at the end of the first chapter, Bishop poses an apparent paradox as an exercise for the reader:

Since every sequence of rational numbers can presumably be described by a phrase in the English language, and since the phrases in the English language can be sequentially ordered, the regular sequences of rational numbers can be sequentially ordered, in contradiction to Theorem 1.

'Theorem 1,' for those of you without the book open in front of you, is essentially Cantor's diagonal proof applied to Bishop's construction of the reals.

Is the exit here that the notion that phrases are 1-1 with sequences is misleading? Aren't some phrases schemata for infinite collections of sequences? In another direction, can't there be Chaitin-esque sequences that are legitimate but, in fact, not expressible as phrases in English? If you generate a sequence with the help of a physical source of entropy (and scale the values so that they meet the definition of a regular sequence) is it admissible in Bishop's definition or not?

• I would just like to note that the question is not specific to constructive mathematics. It and the solution apply equally well classically. – Andrej Bauer Jan 25 '14 at 22:34
• Well, my last subquestion about generating a sequence with a bowl of goldfish is probably more narrowing constructive :-) – bimargulies Jan 25 '14 at 22:37
• The first clause in the Bishop quote is blatantly untrue, unless you are a constructivist. – John Bentin Jan 25 '14 at 22:51
• See also mathoverflow.net/questions/44102/…. – Joel David Hamkins Jan 26 '14 at 15:33
• @Carl: That's an amusing name, because in Hebrew (originally from Aramaic) the word Bish (ביש) means bad (as in bad luck, for example). :-) – Asaf Karagila Jan 28 '14 at 0:58

A similar "paradox" occurs if you replace "describable in English" with computable. I'll show how the paradox is resolved in this case. Also, I'll do this for Baire space (the set of functions from $\mathbb{N}$ to $\mathbb{N}$) to make life simple.
The set of all computable (possibly partial) functions is countable. However, the elements of $\mathbb{N}^\mathbb{N}$ only correspond to the total computable functions. This is a subset of a countable set, but it isn't necessarily countable itself (in constructive mathematics we refer to such sets as subcountable). From a computability point of view, the set of (codes of) total computable functions is not computably enumerable. One way to show this set is not computably enumerable is suggested by the "paradox" itself ie a diagonalisation argument. Alternatively you can note that the set of total computable functions has degree $0''$ whereas any ce set has degree below $0'$.