[FOM] Combinatorial objects with no computable instances
Timothy Y. Chow
tchow at alum.mit.edu
Mon Jan 30 11:59:37 EST 2012
On Gasarch's blog, he mentions Specker's 1969 result that there exists a
recursive binary relation R on N such that no recursively enumerable
infinite subset of N is R-homogeneous.
http://blog.computationalcomplexity.org/2012/01/result-of-specker-in-recursive.html
Gasarch then goes on to remark, "Specker's result is probably the first
theorem in infinite combinatorics to be proven to be non-constructive."
I take Gasarch to be referring to theorems of the general form, "For every
combinatorial object A, there exists a combinatorial object B" with the
property that there are computable instances A for which every such B is
uncomputable. Was Specker's result indeed the first of this kind?
The word "combinatorial" is a bit vague. For example, I thought of
Orevkov's 1963 paper in which he gave constructive counterexamples to
Brouwer's fixed-point theorem. However, intuitively, Orevkov's functions
are not "combinatorial."
Tim
More information about the FOM
mailing list