1
$\begingroup$

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?

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

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).

$\endgroup$
0
$\begingroup$
Consider the first (in lexicographic, say) sequence of rational numbers not describable in the English language...

It is safe to say that in order to actually describe a sequence, one must provide a canonical algorithm for generating it. Thus, this is equivalent to providing a Turing machine that generates the sequence. From here, we see that constructable sequences are indeed sequentially ordered, (since Turing machines are).

$\endgroup$
  • $\begingroup$ But as per @Carl Mummert, BISH does not require sequences to be constructable. That's what I didn't seem to have absorbed from his description, though in retrospect his proposed pathological sequence involving Fermat's theorem should have clued me in. $\endgroup$ – bimargulies Jan 26 '14 at 13:11
  • 2
    $\begingroup$ @bimargulies: On the other hand, BISH is also compatible with the assumption that every function from the naturals to the naturals is computable. BISH is neutral on that subject, allowing many interpretations. Certainly Bishop advocated constructivism, after all. $\endgroup$ – Carl Mummert Jan 26 '14 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.