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?



Bishop's paradox of the countability of sequences
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'$.


You can adapt this idea to English descriptions by saying that if we are given a phrase in English, we have no way of knowing whether or not it refers to a well defined real number, so we have no way of constructing a sequence of all such phrases (even though, in classical mathematics we could deduce the existence of such a sequence from a sequence consisting of all English phrases including those that don't refer to reals).


