[FOM] Combinatorial objects with no computable instances

[Ali Enayat]

This is a reply to a query of Timothy Chow (Jan 30), in which he asked
whether Specker's 1969 result (about the recursive failure of the
infinite Ramsey theorem) is the first instance in infinite
combinatorics where a classical result was proved to be
nonconstructive (as conjectured by Gasarch).

The short answer to the query is "no", since Specker's result was
predated by--and is a more elaborate version of--an earlier
1952-result of Kleene which shows the recursive failure of *Konig's
tree-lemma*.

More specifically, in 1952 Kleene showed the existence of an infinite
recursive subtree T of the full binary tree such that T has no
recursive branch. A similar argument can be used to show the recursive
failure of the Heine-Borel theorem (cf. sec. 1.8 of Simpson's
monograph SOSOA). Both constructions are based on a classical theorem
of recursion theory stating the existence of disjoint  recursively
enumerable sets A and B that are recursively inseparable (i.e., there
is no recursive set that contains one and is disjoint from the other).

Best regards,

Ali Enayat