# 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. Jan 25, 2014 at 22:34
• Well, my last subquestion about generating a sequence with a bowl of goldfish is probably more narrowing constructive :-) Jan 25, 2014 at 22:37
• The first clause in the Bishop quote is blatantly untrue, unless you are a constructivist. Jan 25, 2014 at 22:51
• @Carl: That's an amusing name, because in Hebrew (originally from Aramaic) the word Bish (ביש) means bad (as in bad luck, for example). :-) Jan 28, 2014 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'$.