[FOM] Combinatorial objects with no computable instances

[Timothy Y. Chow]

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