Richard Ketchersid and I have submitted the paper A dichotomy theorem in natural models of 
In this paper, we prove the following result:
Theorem. Assume that
and that
be any partially ordered set. Then either there is an injection of the full binary tree
into
such that no two points in its image are
-comparable, or else
can be written as a well-ordered union of
-chains.
This statement should be reminiscent of the Harrington-Marker-Shelah theorem on Borel orderings, and in a sense our argument is a generalization of this result.
Two corollaries are worth pointing out: Suppose first that 
Corollary. Assume that
and that
injects into
or else
This can be seen as a generalization of Silver’s theorem on co-analytic equivalence relation. In particular, we have the following basis result:
Corollary. Assume that
injects into every infinite set, and if
or
injects into
Our arguments make use of technology developed by Woodin. First, any model of 
In the second case, one argues via an analysis of the 
In the first case, one uses the argument above to see that a set 
As an application, we consider the countable-finite game due to Scheepers. In this game, one fixes a set 
Corollary. Assume that
For a brief presentation of these results, see the talks that Richard and I gave at BEST 18, available here or at my talks page.
let ![X^{[2]}=\{(n,m)\in X^2:n<m\}](http://s3.wordpress.com/latex.php?latex=X%5E%7B%5B2%5D%7D%3D%5C%7B%28n%2Cm%29%5Cin+X%5E2%3An%3Cm%5C%7D&bg=ffffff&fg=000000&s=0 "X^{[2]}=\{(n,m)\in X^2:n<m\}")
. A function ![f:X^{[2]}\to{\mathbb N}](http://s1.wordpress.com/latex.php?latex=f%3AX%5E%7B%5B2%5D%7D%5Cto%7B%5Cmathbb+N%7D&bg=ffffff&fg=000000&s=0 "f:X^{[2]}\to{\mathbb N}")
is regressive iff 
for all 
in 
. A set 
is min-homogeneous for 
iff 
whenever 
and 
.
there exists 
such that if 
and ![f:X^{[2]}\to{\mathbb N}](http://s2.wordpress.com/latex.php?latex=f%3AX%5E%7B%5B2%5D%7D%5Cto%7B%5Cmathbb+N%7D&bg=ffffff&fg=000000&s=0 "f:X^{[2]}\to{\mathbb N}")
is regressive, then there is 
and min-homogeneous for 
.
to be homogeneous, i.e., in general ![f\upharpoonright H^{[2]}](http://s1.wordpress.com/latex.php?latex=f%5Cupharpoonright+H%5E%7B%5B2%5D%7D&bg=ffffff&fg=000000&s=0 "f\upharpoonright H^{[2]}")
will not be constant. For example, consider 
. Notice also that without loss of generality 
, since 
. It is natural to try to establish the rate of growth of the function 
that to each 
assigns the least 
as in the theorem. Using tools of mathematical logic, as part of a more general result about regressive functions of 
variables, Kanamori and McAloon showed:
grows faster than any primitive recursive function.
grows precisely as fast as Ackermann’s function. This is obtained as part of an analysis of a more general function 
of two variables, defined as 
. Obviously, 
and 
. The situation for 
is less clear, although it is of exponential growth.
, 
, 
, 
.
, so 
for 
.
.
hold?
