1. Introduction
Recent research has focused on the projective complexity of various Borel combinatorial properties of Borel graphs, equivalence relations, etc. For instance, the main result of [Reference Todorcevic and Vidnyánszky12] is that the set of (codes for) Borel 3-colorable Borel graphs is
$\mathbf {\Sigma }^1_2$
complete. Such a complexity lower bound rules out dichotomy theorems like the
$G_0$
dichotomy characterizing countably Borel colorable graphs [Reference Kechris, Solecki and Todorcevic6]. It also implies the existence of
$\Delta ^1_1$
graphs which are Borel 3-colorable but not
$\Delta ^1_1$
3-colorable. In this note, we explain a modification of the Gandy–Harrington forcing arguments for dichotomy theorems which yields effectivization results. That is, we show how Borel witnesses to combinatorial properties of
$\Delta ^1_1$
objects imply the existence of
$\Delta ^1_1$
witnesses. This kind of effectivization implies a strong upper bound on projective complexity, and can be construed as a sort of weak dichotomy theorem. Our methods give short and simple proofs of these weak dichotomies even for properties where an actual dichotomy is unwieldy, and they allow us to make a fairly sweeping generalization of many known results.
The basic tool that we use is the observation that, for
$\Phi $
among a large class of properties including what we will call independence properties, if B is a Borel set, A is a Gandy–Harrington condition,
$\Phi (B)$
, and
$A\Vdash \dot x\in B$
, then
$\Phi (A)$
. So, for instance, if a space can be covered with countably many Borel independent sets, then in any nonempty
$\Sigma ^1_1$
set we can use the forcing relation to find an independent set, so by a reflection argument we have a cover by independent
$\Delta ^1_1$
sets. This is made precise in Lemma 3.4 and Theorem 3.5.
In the next section we give three illustrative examples, including a short proof that smooth
$\Delta ^1_1$
equivalence relations are
$\Delta ^1_1$
-reducible to equality. In Section 3 we define a large class of properties
$\Phi $
where this method works and prove some general results. In Section 4 we give several applications. We prove effective versions of the Lusin–Novikov and Feldman–Moore theorems (Theorem 4.1). We show that any
$\Delta ^1_1$
graph generated by a single Borel function, a countable family of Borel functions, or a Borel free action of
$\mathbb {Z}^2$
must be generated by a
$\Delta ^1_1$
function, countable family of functions, or
$\mathbb {Z}^2$
-action (Theorems 4.5, 4.3, and 4.11, respectively). We show that if G is locally countable,
$\Delta ^1_1$
, and admits a Borel end selection, then it admits a
$\Delta ^1_1$
end selection (Theorem 4.10). And, we prove effectivization for Borel local colorings in the sense of Miller’s
$(\mathbb {{G}}_0, \mathbb {{H}}_0)$
dichotomy (Theorem 4.17). In the last section we prove a handful of new dichotomy theorems related to some of the effectivization results in Section 4. In particular, we prove an equivariant version of the
$G_0$
dichotomy which implies the results about generating graphs with functions (Theorem 5.2). And, we prove a dichotomy for Schreier graphs of Borel actions of
$\mathbb {Z}^2$
which generalizes Miller’s characterization of undirectable forests of lines (Theorem 5.16).
1.1. Conventions and notation
Throughout, graphs are simple and undirected. Formally, a graph on a vertex set X is a symmetric, irreflexive subset of
$X^2$
. An edge in a graph is some ordered pair in the graph (so our edges are directed, and our graphs contain both possible directions).
For an edge e, we typically write
$e_0$
and
$e_1$
for its left and right coordinate (its tail and head), so
$e=(e_0,e_1)$
. And, we write
$-e$
for the edge with the opposite direction, i.e.,
$-(e_0,e_1)=(e_1,e_0)$
. For a set of edges A, let
$-A=\{-e: e\in A\}.$
We write
$\mathcal {N}$
for Baire space, i.e.
$\omega ^\omega $
with the product topology. The map
$\pi _i:\mathcal {N}^n\rightarrow \mathcal {N}$
is projection onto the
$i^{th}$
coordinate. A box is a subset of
$\mathcal {N}^n$
of the form
$A_1\times \dots \times A_n$
for some
$A_1,\dots ,A_n\subseteq \mathcal {N}$
.
We use lightface capital Greek letters to refer to the effective projective hierarchy. So first,
$A\in \Delta ^1_1(x)$
means that A is Borel and there is some code for A which is computable in x. We will remain agnostic about the exact details of the coding, but one could code a Borel by a labelled well-founded tree whose leaves correspond to open sets and whose other nodes are labelled with union, intersection, and complement. And,
$A\in \Sigma ^1_1(x)$
means that for some
$B\in \Delta ^1_1(x),$
$$\begin{align*}y\in A\Leftrightarrow (\exists z) \; (y,z)\in B,\end{align*}$$
and
$A\in \Pi ^1_1(x)$
means that, for some
$B\in \Delta ^1_1,$
$$\begin{align*}y\in A\Leftrightarrow (\forall z)\; (y,z)\in A.\end{align*}$$
In general
$\Sigma ^1_{n+1}(x)$
sets are projections of
$\Pi ^1_n(x)$
, and
$\Pi ^1_n(x)$
sets are complements of
$\Sigma ^1_n(x)$
sets. We will mostly be concerned with
$n=1$
or
$2$
here.
Let us stress that the set of codes for
$\Delta ^1_1$
sets is
$\Pi ^1_1$
, but that if we write
$C(x)$
for the set coded by x, then there is an arithmetic property
$\Phi $
so that for any code x,
$y\in C(x)\Leftrightarrow \Phi (x,y)$
.
We say that a property
$\Phi $
of subsets of X is
$\Pi ^1_1$
on
$\Sigma ^1_1$
if, whenever
$A\subseteq Y\times X$
is
$\Sigma ^1_1$
$$\begin{align*}\{y\in Y: \Phi(A_x)\}\in \Pi^1_1.\end{align*}$$
That is,
$\Phi $
is
$\Pi ^1_1$
on
$\Sigma ^1_1$
if the set of sections with property
$\Phi $
in any
$\Sigma ^1_1$
set is
$\Pi ^1_1$
. For instance, being empty is
$\Pi ^1_1$
on
$\Sigma ^1_1$
:
$$\begin{align*}\Phi(A)\Leftrightarrow (\forall y) \; y\not\in A.\end{align*}$$
$\Sigma ^1_1$
on
$\Sigma ^1_1$
and similar notions are defined mutatis mutandis. The most important fact about these kinds of properties are the reflection theorems:
Theorem 1.1 (Reflection theorems, [Reference Harrintgon, Marker and Shelah2, Lemma 1.4], [Reference Marks7, Theorem 2.27]).
Say a property is monotone if it passes to supersets and continuous if it passes to decreasing intersections.
-
(1) If
$\Phi $
is
$\Pi ^1_1$
on
$\Sigma ^1_1$
,
$A\in \Sigma ^1_1$
, and
$\Phi (A)$
, then there is some
$B\supseteq A$
so that
$B\in \Delta ^1_1$
and
$\Phi (B)$
. -
(2) For
$\Phi $
a property of two sets,
$\Phi $
is
$\Pi ^1_1$
on
$\Pi ^1_1$
, monotone in both coordinates, and continuous downward in the second coordinate, and if
$\Phi (A,\mathcal {N}\smallsetminus A)$
for some
$A\in \Pi ^1_1$
, then there is
$B\subseteq A$
so that
$B\in \Delta ^1_1$
and
$\Phi (B,\mathcal {N}\smallsetminus B)$
.
We say that a fact about
$\Sigma ^1_n$
or
$\Pi ^1_n$
relativizes if it remains true if we replace
$\Sigma ^1_n$
with
$\Sigma ^1_n(x)$
for some oracle x (and likewise for
$\Pi $
). The reflection theorems relative.
Bold-faced Greek letters are the classical projective hierarchy, which we can equivalently define as
$$\begin{align*}\mathbf{\Sigma}_{n}^{1}=\bigcup_{x\in \mathbb{R}} \Sigma^1_n(x),\quad \mathbf{\Pi}_{n}^{1}=\bigcup_{x\in \mathbb{R}} \Pi^1_n(x).\end{align*}$$
So, facts about the effective Projective hierarchy which relativize are also true about the classical hierarchy. We will be interested to the extent to which the converse is true.
We will work with Gandy–Harrington forcing on
$\mathcal {N}^n$
, i.e., the poset of non-empty
$\Sigma ^1_1$
subsets of
$\mathcal {N}^n$
ordered by inclusion. We write for
$\mathbb {{P}}_n$
this forcing, and we write
$\dot x$
for the standard name for the real coded by a
$\mathbb {{P}}_1$
-generic filter,
$(\dot x,\dot y)$
for the name for the reals coded by a
$\mathbb {{P}}_2$
-generic, and
$\dot {\mathbf x}=(\dot x_1,\dots ,\dot x_n)$
for the
$\mathbb {{P}}_n$
-generic reals.
For a Borel set B, when we write
$\Vdash \dot x\in B$
or consider B in some generic extension, we mean the set in coded in the extension by some ground model code for B. In particular,
$\Phi (B)$
is absolute whenever
$\Phi $
is
$\mathbf {\Pi }_{1}^{1}$
on
$\mathbf {\Delta }_{1}^{1}$
.
When we say a
$\Delta ^1_1$
sequence of
$\Delta ^1_1$
sets
$\langle {A_\alpha : \alpha \in \beta } \rangle $
(for a computable ordinal
$\beta $
), we mean that there is a
$\Delta ^1_1$
order
$\prec $
on
$\omega $
and
$\Delta ^1_1$
set of pairs
$(c_\alpha , i_\alpha )$
so that
$i_\alpha \in \omega $
has order type
$\alpha $
in
$\prec $
and
$c_\alpha $
is a code for
$A_\alpha $
. A family of Borel sets is
$\Pi ^1_1$
in the codes if the set of Borel codes for Borel sets in this family is
$\Pi ^1_1.$
Our references for effective descriptive set theory are Marks’s lecture notes [Reference Marks7] and the paper by Harrington, Marker, and Shelah [Reference Harrintgon, Marker and Shelah2].
When
$s_1,s_2,s_3,\dots $
are ordinal length sequences, say
$s_i\in A^{\alpha _i}$
for some A, then their concatenation,
$s=s_1^\smallfrown s_2^\smallfrown s_3^\smallfrown \dots $
is the sequences of length
$\sum _i \alpha _i$
defined by
$$\begin{align*}s(\beta)=s_i(\gamma):\Leftrightarrow \beta=(\sum_{j<i}\alpha_j )+\gamma.\end{align*}$$
2. First examples
We begin with three examples. First we reprove the effectivization consequences of the
$G_0$
dichotomy:
Theorem 2.1. If g is a code for a Borel graph G on
$\mathcal {N}$
, and G admits a Borel countable coloring, then G admits a
$\Delta ^1_1(g)$
countable coloring.
Proof By relativization, we may assume
$g\in \Delta ^1_1.$
We first show that G admits a
$\Delta ^1_1$
coloring if and only if
$\mathcal {N}$
is a union of
$\Delta ^1_1\ G$
-independent sets. If
$f:\mathcal {N}\rightarrow \omega $
is a coloring, then
$\mathcal {N}=\bigcup _i f^{-1}(i)$
and each of the fibers is G-independent and
$\Delta ^1_1$
. For the converse, suppose every x is in some
$\Delta ^1_1$
independent set. Then
$$\begin{align*}\{(x,i):i\mbox{ codes a set }A\in \Delta^1_1, \; x\in A,\; A\mbox{ is }G\mbox{ independent}\}\end{align*}$$
is a
$\Pi ^1_1$
total relation, so admits a
$\Delta ^1_1$
uniformization by [Reference Marks7, Theorem 2.15]. The uniformizing function is a countable coloring.
Let
$X=\mathcal {N}\smallsetminus \bigcup \{A\in \Delta ^1_1: A\mbox { is }G\mbox { independent}\}$
. Note that X is
$\Sigma ^1_1$
. Suppose
${X\not =\emptyset .}$
(If we were to try to prove a dichotomy result here we would start trying to build some generic obstruction to colorability.) Suppose toward contradiction f is a Borel countable coloring of G.
Recall that
$\mathbb {{P}}_i$
is Gandy–Harrington forcing on
$\mathcal {N}^i$
. By absoluteness, the interpretation of the code for f remains a Borel coloring in any extension by a
$\mathbb {{P}}_i$
-generic. We can find some
$A\in \mathbb {{P}}_1$
below X so that
$A\Vdash f(\dot x)=i$
, where
$\dot x$
is a name for the generic real. If A is not independent, then
${B=\{(x,y): (x,y)\in G, x, y\in A\}}$
is a condition in
$\mathbb {{P}}_2$
and
$$\begin{align*}B\Vdash f(\dot x)=f(\dot y)\; \wedge \; (\dot x,\dot y)\in G,\end{align*}$$
which is a contradiction. Since being independent is
$\Pi ^1_1$
on
$\Sigma ^1_1$
, A is contained in some
$\Delta ^1_1$
independent set. But this means
$A\cap X=\emptyset $
, contradicting our choice of
$A.$
Corollary 2.2. The set of Borel countably colorable graphs is
$\Pi ^1_1$
in the codes.
Proof Write
$B_c$
for the set coded by a Borel code c, and write
$\phi _n^x$
for the partial function computed by the nth oracle machine with oracle x.
For any
$g\in \mathcal {N}$
, g codes a graph with a countable coloring if and only if g codes a graph G, and
$$\begin{align*}(\exists f\in \Delta^1_1(g))\; f\mbox{ is a countable coloring of }G.\end{align*}$$
In detail, this second clause says
$$\begin{align*}(\exists n\in \omega) \; \phi^g_n \mbox{ is a Borel code, and }B_{\phi_n^g}\mbox{ is a countable coloring of }G.\end{align*}$$
And f is a countable coloring of G if and only if
$$ \begin{align*}f\subseteq \mathcal{N}\times \omega & \wedge (\forall x,i,j)\;(x,i),(x,j)\in f\rightarrow i\not=j \\ & \wedge (\forall x,y,i)\;(x,i),(y,i)\in f\rightarrow (x,y)\not\in G.\end{align*} $$
This all
$\Pi ^1_1$
.
We will only state results for
$\Delta ^1_1$
sets below, but every statement relativizes and gives a complexity bound as above.
The general outline of the method is as follows: We first reduce whatever problem is at hand to the problem of covering some set X by countably many Borel sets satisfying some property
$\Phi $
(this is usually the combinatorial heart of the problem). Then we suppose that some
$X\in \Delta ^1_1$
can be covered by Borel sets
$\langle {A_i:i\in \omega } \rangle $
satisfying
$\Phi $
, but not by
$\Delta ^1_1$
sets. We get a contradiction by forcing below
$$\begin{align*}\widetilde X := X\smallsetminus\bigcup\{A\in\Delta^1_1: \Phi(A)\}\end{align*}$$
to find some p and i with
$$\begin{align*}p\Vdash \dot x\in A_i.\end{align*}$$
We then show by contradiction that in fact
$\Phi (p)$
, so by a reflection argument
$p\cap X=\emptyset .$
In the next section, we formalize this proof sketch and offer some technical variations on the idea.
Our second example involves a case where we want our covering sets to satisfy a notion of independence and a kind of closure. We can give a much simplified proof of the effectivization consequences of Harrington–Kechris–Louveau [Reference Miller10, Theorem 5.2.7] by considering boxes in
$\mathcal {N}^2$
which avoid a given equivalence relation.
Theorem 2.3. If E is a
$\Delta ^1_1$
equivalence relation and Borel reducible to
$(=_{2^\omega })$
, then E is
$\Delta ^1_1$
reducible to
$(=_{2^\omega })$
.
Proof First, say that a subset of
$\mathcal {N}^2$
is a box if it is a product of two subsets of
$\mathcal {N}$
, and note that E is
$\Delta ^1_1$
(or Borel) reducible to
$(=_{2^\omega })$
if and only if
$E^c$
is covered by a countable
$\Delta ^1_1$
(or Borel) family of boxes which all avoid E. Indeed, if f is a reduction, then we can set
$$\begin{align*}A_i=\{x: f(x)(i)=0\}\mbox{ and }B_i=\{x: f(x)(i)=1\}\end{align*}$$
and consider the boxes
$A_i\times B_i$
. Conversely, suppose
$E^c$
can be covered by
$\Delta ^1_1$
boxes. Setting
$\mathcal {{C}}=\{n\in \omega : n\mbox { is a code for a}\ \Delta ^1_1\ \mbox {box avoiding }E\}$
, we have
$$\begin{align*}(\forall (x,y)\not\in E) (\exists n\in\omega)\; n\in \mathcal{{C}}\wedge (x,y)\mbox{ is in the set coded by }n.\end{align*}$$
This is
$\Pi ^1_1$
on
$\Pi ^1_1$
as a property of
$\mathcal {{C}}$
, so by the first reflection theorem (applied to the complement) there is a
$\Delta ^1_1$
subset of
$\mathcal {{C}}$
, say
$\mathcal {{D}}$
with the same property. We can enumerate
$\mathcal {{D}}$
to get a
$\Delta ^1_1$
covering sequence
$\langle {A_i\times B_i:i\in \omega } \rangle $
. By the second reflection theorem applied to
$$\begin{align*}\Phi(Z,Y):\Leftrightarrow (\forall (x,y)\in E) \; x\in Z\vee (y\in Y \wedge x\not\in B_i),\end{align*}$$
we can assume each
$A_i$
is E-invariant and avoids
$B_i$
, and we can define a reduction by
$f(x)(i)=0$
if and only if
$x\in A_i$
.
Suppose
$E\in \Delta ^1_1$
,
$X=E^c\smallsetminus \bigcup \{A\times B: A,B\in \Delta ^1_1, \left (A\times B\right )\cap E=\emptyset \}$
is nonempty, and
$E^c=\bigcup _i A_i\times B_i$
with
$A_i,B_i$
Borel. A set
$Y\subseteq \mathcal {N}^2$
is a box if and only if
$$\begin{align*}\bigl(\forall (x,y),(a,b)\in Y\bigr)\;(x,b)\in Y.\end{align*}$$
So again by the second reflection theorem applied to
$$\begin{align*}\Phi(Z,Y):\Leftrightarrow\left(\forall (x,y),(a,b)\not\in Z\right)\; (x,b)\in Y\mbox{ and }(x,y)\not\in E ,\end{align*}$$
X does not meet any
$\Sigma ^1_1$
boxes avoiding E. Also note that X is
$\Sigma ^1_1.$
Since
$X\Vdash (\dot x,\dot y)\not \in E$
, there is some
$p\subseteq X$
so that
$$\begin{align*}p\Vdash \dot x\in A_i\;\wedge \; \dot y\in B_i.\end{align*}$$
And, since any
$\mathbb {{P}}_2$
generic
$(x,y)$
has x and y separately
$\mathbb {{P}}_1$
-generic, it must be that
$A=\pi _1(p)\Vdash \dot x\in A_i$
and
$B=\pi _2(p)\Vdash \dot x\in B_i$
. So,
$A\times B$
must avoid E or else
$\left (A\times B\right )\cap E\Vdash (x,y)\in E\cap \left (A_i\times B_i\right )$
.
But then since X doesn’t meet any boxes which avoid E,
$p\subseteq A\times B\cap X=\emptyset $
, which is a contradiction.
Corollary 2.4. The set of smooth relations is
$\Delta ^1_1$
in the codes.
Proof A real c codes a smooth relation E if and only if
$$\begin{align*}(\exists f\in \Delta^1_1)(\forall x,y) f(x)=f(y)\leftrightarrow x E y.\end{align*}$$
As above,
$(\exists f\in \Delta ^1_1)$
is equivalent to a universal quantifier over
$\mathcal {N}.$
Our last example involves an ordinal length construction. It turns out we can also effectivize the ordinals length of the sequence to lie below
$\omega _1^{CK}$
. This gives another proof of the effectivization consequences of a dichotomy due independently to Kanovei and Louveau [Reference Miller10, Theorem 5.2.3].
Definition 2.5. For an ordinal
$\alpha $
,
$\leq _{lex}^\alpha $
is the lexicographic order on
$2^\alpha $
, i.e.,
$$\begin{align*}x\leq_{lex}^\alpha y:\Leftrightarrow x=y \mbox{ or }(\exists \beta<\alpha)\left[ (x\upharpoonright \beta)=(y\upharpoonright \beta)\mbox{ and }x(\beta)<y(\beta)\right].\end{align*}$$
Theorem 2.6. Suppose R is a quasi-order on
$\mathcal {N}$
with a Borel homomorphism to
$\leq _{lex}^{\alpha }$
for some
$\alpha <\omega _1$
which induces an injection on
$\mathcal {N}/\equiv _R$
. Then there is a
$\Delta ^1_1$
homomorphism of R to
$\leq _{lex}^{\alpha '}$
for some
$\alpha '<\omega _1^{CK}$
which induces an injection on
$\mathcal {N}/\equiv _R$
.
Proof Given a family of functions
$\mathcal {{F}}$
on
$\mathcal {N}$
, define an equivalence relation by
$$\begin{align*}x\equiv_{\mathcal{{F}}}y \;:\Leftrightarrow\;(\forall f\in \mathcal{{F}})\; f(x)=f(y).\end{align*}$$
And for a function f, let
$(\equiv _f)=(\equiv _{\{f\}})$
. We want to find some
$\Delta ^1_1$
homomorphism, say f, from R to a lexicographic ordering so that
$(\equiv _R)=(\equiv _f)$
.
Consider
$$\begin{align*}\mathcal{{F}}=\{f: (\exists \alpha<\omega_1^{CK})\;f\mbox{ is a}\ \Delta^1_1\ \mbox{homomorphism from}\ R\ \mbox{to }\leq_{lex}^\alpha \}.\end{align*}$$
Note that
$\mathcal {{F}}$
is
$\Pi ^1_1$
and
$(\equiv _R)\subseteq (\equiv _{\mathcal {{F}}})$
. If
$(\equiv _R)=(\equiv _{\mathcal {{F}}})$
, then since this is a
$\Pi ^1_1$
on
$\Pi ^1_1$
statement about subsets of
$\mathcal {{F}}$
, by reflection there is a
$\Delta ^1_1$
set
$\mathcal {{G}}\subseteq \mathcal {{F}}$
so that
$(\equiv _{\mathcal {{G}}})=(\equiv _R)$
. We can then enumerate
$\mathcal {{G}}$
as
$\langle {f_i: i\in \omega } \rangle $
with a
$\Delta ^1_1$
enumeration. So each
$f_i$
is a homomorphism from R to some
$\leq _{lex}^{\alpha _i}$
with
$\alpha _i<\omega _1^{CK}$
. Then
$(\equiv _R)=(\equiv _f)$
where
$$\begin{align*}f(x)=f_0(x)^\smallfrown f_1(x)^\smallfrown f_2(x)^\smallfrown \dots .\end{align*}$$
Now suppose towards contradiction that
$X=(\equiv _{\mathcal {{F}}})\smallsetminus (\equiv _R)$
is nonempty, and fix a Borel homomorphism g from R to some
$\leq _{lex}^{\tilde \alpha }$
. To get our contradiction we use a reflection argument to find a
$\Delta ^1_1$
homomorphism which refines
$\equiv _{\mathcal {{F}}}$
.
We have that
$$\begin{align*}X\Vdash g(\dot x)(\alpha)\not=g(\dot y)(\alpha) \mbox{ for some }\alpha.\end{align*}$$
So we can define
$$\begin{align*}\alpha_0=\min\{\alpha: (\exists p\subseteq X)\; p\Vdash g(\dot x)(\alpha)\not=g(\dot y)(\alpha)\}. \end{align*}$$
Note that
$X\Vdash g(\dot x)\upharpoonright \alpha _0=g(\dot y)\upharpoonright \alpha _0$
.
Choose
$p\subseteq X$
witnessing the above formula. Without loss of generality, we may assume
$p\Vdash g(\dot x)(\alpha _0)=1\; \wedge \; g(\dot y)(\alpha _0)=0$
. Let
$A=\pi _1(p)$
and
$B=\pi _2(p)$
. Then, if
$q=(A\times B)\cap R\cap (\equiv _{\mathcal {{F}}})\not =\emptyset $
,
$$\begin{align*}q\Vdash g(\dot x)(\alpha_0)>g(\dot y)(\alpha_0)\;\wedge\; g(\dot x)\upharpoonright \alpha_0=g(\dot y)\upharpoonright \alpha_0\;\wedge \; x R y\end{align*}$$
which contradicts the fact that g is a homomorphism.
So,
$(A\times B)\cap R\cap (\equiv _{\mathcal {{F}}})=\emptyset $
. By the second reflection theorem we may assume A is
$\Delta ^1_1$
and closed upwards under
$R\cap (\equiv _{\mathcal {{F}}})$
and avoids B. By reflection there is a
$\Delta ^1_1$
sequence of functions
$\langle {f_i: i\in \omega } \rangle $
so that each
$f_i$
is in
$\mathcal {{F}}$
and
$$\begin{align*}(A\times B)\cap R\cap (\equiv_{\{f_i:i\in\omega\}})=\emptyset.\end{align*}$$
Suppose
$f_i$
is a homomorphism into the lexicographic order on
$\alpha _i$
. We can define a homomorphism into the lexicographic order on
$\gamma :=(\sum _i \alpha _i)+1$
as follows. Set
$f_{\infty }(x)=1$
if and only if
$x\in A$
and
$$\begin{align*}f(x):=\left(f_0(x)^\smallfrown f_1(x)^\smallfrown \dots \right)^\smallfrown f_{\infty}(x).\end{align*}$$
To check this is a homomorphism, suppose
$x R y$
. If
$f_i(x)<_{lex}^{\alpha _i}f_i(y)$
for some i, then
$f(x)\leq _{lex}^\gamma f(y)$
. Otherwise
$x\equiv _{\mathcal {{ F}}}y$
, and so if
$x\in A$
then
$y\in A$
by our closure assumption. This means
$f_{\infty }(x)\leq f_{\infty }(y)$
. In any case
$f(x)\leq _{lex}^{\gamma }f(y)$
and f is a homomorphism.
This means
$f\in \mathcal {{F}}$
, so
$f(x)=f(y)$
for
$(x,y)\in X$
, but for
$(x,y)\in p\subseteq X$
we have
$f(x)\not =f(y)$
which is a contradiction.
3. General results
Our first goal in this section is to prove a general result on effectivizing countable covers by Borel sets satisfying some property,
$\Phi $
. We can do this when
$\Phi $
is conjunction of what we call independence properties and closure properties. These notions are defined below, but an informal description is as follows:
$\Phi $
is an independence property if
$\Phi (A)$
says all points in A satisfy a combinatorial relation (e.g., A is G-independent for a graph G), and
$\Psi $
is a closure property if
$\Psi (A)$
says that A contains all points which stand in a combinatorial relation with points from A (e.g., A is a box).
Definition 3.1. We say that a property
$\Phi (A)$
of a subset of
$\mathcal {N}$
is an independence property if there is some
$\Delta ^1_1$
property
$\phi $
such that
$$\begin{align*}\Phi(A)\Leftrightarrow \neg (\exists \mathbf{x},y )\; \mathbf{x}\in A^k\mbox{ and }\phi(x_1,\dots,x_k,y).\end{align*}$$
Note that if
$\Phi $
is an independence property then
$\Phi $
is
$\Pi ^1_1$
on
$\Sigma ^1_1$
. In practice, many
$\Pi ^1_1$
on
$\Sigma ^1_1$
properties are independence properties. But the two notions are not equivalent, and it is unclear how far beyond independence properties the results below generalize.
Definition 3.2. A property
$\Psi (A)$
of sets is a closure property if there is a
$\Delta ^1_1$
property
$\psi $
so that
$\Psi (A)$
if and only if
$$\begin{align*}(\forall \mathbf{x}\in A^k)(\forall y,z) \; \psi(\mathbf{x},y,z)\rightarrow z\in A.\end{align*}$$
For a closure property
$\Psi $
and set A, the
$\Psi $
-closure of A is
$A^{\Psi }:=\bigcup _m f^m(A)$
, where
$$\begin{align*}f(A):=A\cup \{z: (\exists \mathbf{x}\in A^k)(\exists y) \psi(x,y,z)\}.\end{align*}$$
Of course, the
$\Psi $
-closure of any set satisfies
$\Psi $
. And, if A is
$\Sigma ^1_1$
, then so is
$A^{\Psi }$
.
The key point about an independence property, closure property, or a conjunction thereof, say
$\Phi $
, is that any time a Gandy–Harrington condition p forces the generic to be in set with property
$\Phi $
, p is contained in a
$\Delta ^1_1$
set with property
$\Phi $
.
Definition 3.3. A property
$\Phi (A)$
is reflectable if it is
$\Pi ^1_1$
in the codes (i.e.,
$\{c: c\mbox { codes }A, \Phi (A)\}$
is
$\Pi ^1_1$
),
$\Phi (B)$
is absolute between V and
$V[G]$
for any
$\mathbb {{P}}_i$
-generic G and Borel set B, and the following condition holds: whenever B is Borel,
$A\in \mathbb {{P}}_1$
,
$A\Vdash \dot x\in B$
, and
$\Phi (B)$
, there is some
$\tilde A\in \Delta ^1_1$
so that
$A\subseteq \tilde A$
and
$\Phi (\tilde A)$
.
One subtlety to point is out that by property we mean first-order property in the language of set theory with parameters. So there should never be any confusion about how to interpret
$\Phi $
in different models (provided all the relevant parameters are present). In practice we may be ambiguous about exactly what property we mean, but there should always be a
$\Delta ^1_1$
translation between any reasonable interpretations. Also, most natural properties which are
$\Pi ^1_1$
in the codes are uniformly
$\Pi ^1_1(x)$
in the codes for
$\Delta ^1_1(x)$
sets, so this absoluteness assumption is usually automatic.
Lemma 3.4. The following properties are all reflectable:
-
(1)
$\bigvee _{i\in \omega } \Phi _{i\in \omega }(A)$
, where
$\langle {\Phi _i:i\in \omega } \rangle $
is a sequence of reflectable properties which are uniformly
$\Pi ^1_1$
in the codes. -
(2)
$\Phi (f[A])$
, where
$\Phi $
is reflectable and
$f:\mathcal {N}\rightarrow \mathcal {N}$
is a
$\Delta ^1_1$
bijection. -
(3)
$\Phi \wedge \Psi $
where
$\Phi $
is an independence property and
$\Psi $
is a closure property.
Proof Checking
$(1)$
and
$(2)$
is routine. For
$(3)$
, suppose
$A\Vdash \dot x\in B$
and
$(\Phi \wedge \Psi )(B)$
. We first show by induction on m that
$f^m(A)\Vdash \dot x\in B$
, with f as in the definition of
$A^\Psi $
. The base case
$m=0$
is our assumption that
$$\begin{align*}f^0(A)=A\Vdash \dot x\in B.\end{align*}$$
Suppose toward contradiction that
$f^m(A)\Vdash \dot x\in B$
, but that there is some
$p\subseteq f^{m+1}(A)$
so that
$p\Vdash \dot x\not \in B.$
We have a nonempty condition
$$\begin{align*}q:=\{(\mathbf{x},y,z):\mathbf{x}\in (f^m(A))^k,\; z\in p,\mbox{ and}\;\psi(\mathbf{x},y,z) \}\in \mathbb{{P}}_{k+2}.\end{align*}$$
The first k projections of q are contained in
$f^m(A)$
, so by the induction hypothesis
${q\Vdash \dot { \mathbf {x}}\in B^k}$
. Since the projection of q onto the z-coordinate is contained in p, our assumption about p gives
${q\Vdash \dot z\not \in B}$
. And the definition of q ensures
${q\Vdash \psi (\dot {\mathbf {x}}, y,z)}$
. So,
$$\begin{align*}q\Vdash \dot{\mathbf{x}}\in B^k\wedge \dot z\not\in B\wedge (\exists w)\psi(\dot{x},w,\dot z).\end{align*}$$
Thus we can find generics in the extension witnessing that
$\neg \Psi (B)$
, but in the ground model
$\Psi (B)$
contradicting Schoenfield absoluteness.
Now suppose that
$A\Vdash \dot x\in B$
and
$(\Phi \wedge \Psi )(B)$
. From the above, we may assume
$A^{\Psi }=A$
. Suppose toward contradiction that
$\neg \Phi (A)$
. Then
$$\begin{align*}C=\{(\mathbf{x},y): \mathbf{x}\in A^k\mbox{ and } \phi(\mathbf{x},y)\}\in \mathbb{{P}}_{n\times k} \end{align*}$$
and since
$A\Vdash \dot x\in B$
,
$$\begin{align*}C\Vdash \dot {\mathbf{x}}\in B^k\;\wedge\; \phi(\dot {\mathbf{x}},\dot y ) \end{align*}$$
which, just as above, contradicts the fact that
$\Phi (B).$
So,
$(\Phi \wedge \Psi )(A)$
, and by the second reflection theorem applied to
$$\begin{align*}\Theta(X,Y):=(\forall \mathbf{x}\in (\mathcal{N}\smallsetminus X)^k, y,z) \;\left(\psi(\mathbf{x},y,z)\rightarrow z\in Y\right)\mbox{ and }\; \neg \phi(\mathbf{x},y)\end{align*}$$
there is a
$\Delta ^1_1$
set
$\tilde A\supseteq A$
so that
$(\Phi \wedge \Psi )(\tilde A).$
With the lemma above in hand, we can quickly prove a general effectivization result for countable covers by independent sets.
Theorem 3.5. Fix a reflectable property
$\Phi $
. Suppose
$X\in \Delta ^1_1$
and
$X\subseteq \bigcup _{i\in \omega } B_i$
, where each
$B_i$
is a Borel set so that
$\Phi (B_i)$
. Then there is a
$\Delta ^1_1$
sequence of
$\Delta ^1_1$
sets
$\langle {A_i: i\in \omega } \rangle $
so that
$\Phi (A_i)$
for all i and
$X\subseteq \bigcup _{i\in \omega } A_i$
.
Proof Suppose toward contradiction X admits no
$\Delta ^1_1$
sequence as described. Consider the following set:
$$\begin{align*}X'=X\smallsetminus \bigcup\{A\in \Delta^1_1 : \Phi(A)\}.\end{align*}$$
We want to check that
$X'$
is
$\Sigma ^1_1$
. The set of codes for sets with property
$\Phi $
is
$\Pi ^1_1$
by the definition of reflectable, so
$$\begin{align*}x\in \bigcup\{A\in \Delta^1_1: \Phi(A)\}\Leftrightarrow (\exists n\in \omega)\;n\mbox{ codes a set }A\wedge x\in A.\end{align*}$$
Since
$\Pi ^1_1$
sets are closed under number quantifiers, this is
$\Pi ^1_1$
.
By assumption,
$X'$
is nonempty, so it is in
$\mathbb {{P}}_1$
. We have
$$\begin{align*}X'\Vdash (\exists i) \; \dot x\in B_i\end{align*}$$
so for some
$i\in \omega $
and
$A\subseteq X',$
$$\begin{align*}A\Vdash \dot x\in B_i.\end{align*}$$
But then,
$\Phi \bigl (\tilde A\bigr )$
for some
$\Delta ^1_1$
set
$\tilde A\supseteq A$
. So A avoids X, which contradicts our choice of A.
3.1. Minor technical variations
We want two minor technical variations on this theorem. The first of these variations says that we can effectivize countable Borel families whose projections cover a given space, provided the projection map has countable fibers.
Theorem 3.6. Suppose that
$\Phi (A)$
is a reflectable property,
$R\subseteq \mathcal {N}^{2}$
is
$\Delta ^1_1$
with countable sections, and
$\Phi (A)$
implies
$A\subseteq R$
. If
$X\subseteq \mathcal {N}^n$
admits a countable cover by Borel sets of the form
$\pi _1(A)$
with
$\Phi (A)$
, then X admits a cover by
$\Delta ^1_1$
sets of this form.
Proof By the effective Feldman–Moore theorem (see Theorem 4.1 and the preceding comments in Section 4), there is a
$\Delta ^1_1$
sequence of involutions
$\langle {f_i:i\in \omega } \rangle $
so that, for any
$x\in \mathcal {N}$
and
$(x,y)\in R$
,
$$\begin{align*}\{(x,y'): (x,y')\in R\}=\{f_i(x,y): i\in\omega\}.\end{align*}$$
Then,
$X=\bigcup _i \pi _1(A_i)$
if and only if
$$\begin{align*}\{(x,y)\in R: x\in X\}=\bigcup_i\bigcup_j \{f_j(x,y): (x,y)\in A_i\}.\end{align*}$$
So, X admits a cover by
$\Delta ^1_1$
sets of the form
$\pi _1(A)$
with
$\Phi (A)$
if and only if
$\widetilde X=\{(x,y)\in R: x\in X\}$
admits a cover by
$\Delta ^1_1$
sets so that
$(\exists i)\Phi (f_i[A])$
holds. By Lemma 3.4,
$(\exists i)\Phi (f_i[A])$
is reflectable, and we can apply the previous theorem.
The second variation generalizes beyond covering spaces with unions of sets to covering spaces with unions of intersections of unions of sets. One could extend this further to arbitrary finite alternations of unions and intersections with mostly notational changes.
Theorem 3.7. Fix a sequence of reflectable properties
$\langle {\Phi _{ij}:i,j\in \omega } \rangle $
which are uniformly
$\Pi ^1_1$
in the codes. Suppose there is a family of Borel sets
$\langle {B_{i,j,k}: i,j,k\in \omega } \rangle $
such that
$$\begin{align*}\widetilde X=\bigcup_{i} \bigcap_{j}\bigcup_{k} B_{i,j,k},\end{align*}$$
where
$\widetilde X\subseteq \mathcal {N}$
is
$\Delta ^1_1$
and for all
$i,j,k\in \omega $
$$\begin{align*}\Phi_{i,j}(B_{i,j,k}).\end{align*}$$
Then there is a
$\Delta ^1_1$
such family.
By uniformity here we mean
$\{(n,i,j):n\mbox { codes a set }A, \Phi _{ij}(A)\}$
is
$\Pi ^1_1$
.
Proof Let
$$\begin{align*}X=(\widetilde X\times \omega^2)\smallsetminus \bigcup\{ A\times \{(i,j)\} : A\in \Delta^1_1, (i,j)\in \omega^2,\Phi_{i,j}(A)\}.\end{align*}$$
If we have that
$$\begin{align*}(\forall x )(\exists i )(\forall j )\; (x,i,j)\not\in X,\end{align*}$$
then we can find our
$\Delta ^1_1$
family by letting
$B_{ijk}$
be a
$\Delta ^1_1$
enumeration of the
$\Delta ^1_1$
sets with
$\Phi _{ij}(B_{ijk})$
. So suppose towards contradiction that
$$\begin{align*}(\exists x)(\forall i )(\exists j )\; (x,i,j)\in X.\end{align*}$$
We can find a condition
$p\subseteq \{x: (\forall i)( \exists j )\;(x,i,j)\in X\}$
, and an index
$\tilde i$
so that
$$\begin{align*}p\Vdash (\forall j)(\exists k)\; \dot x\in B_{\tilde i, j,k}.\end{align*}$$
Refining p, we can find some
$\tilde j$
so that
$$\begin{align*}p\subseteq \{x: (x,\tilde i,\tilde j)\in X\}.\end{align*}$$
But then, refining p again, we can find
$\tilde k$
so that
$$\begin{align*}p\Vdash \dot x\in B_{\tilde i,\tilde j,\tilde k}.\end{align*}$$
But then p is contained in a
$\Delta ^1_1$
set
$\tilde p$
so that
$\Phi _{\tilde i,\tilde j}(\tilde p)$
, and
$\tilde p\times \{(\tilde i,\tilde j)\}\cap X=\emptyset $
, which contradicts the fact that
$p\subseteq \{x: (x,\tilde i,\tilde j)\in X\}$
.
3.2. Transfinite constructions
Our last variation is somewhat more complicated and covers situations where we want to cover an object with some ordinal length sequence of sets. This generalizes Theorem 2.6.
Definition 3.8. Given
$\overline A=\langle {A_{\alpha }:\alpha <\beta } \rangle $
a countable ordinal length sequence of sets in
$\mathcal {N}$
and
$X\subseteq \mathcal {N}$
, define
$$\begin{align*}X_{\overline A}=X\smallsetminus \bigcup_{\alpha<\beta} A_{\alpha}.\end{align*}$$
So, in particular,
$\mathcal {N}_{\overline {A}}=\mathcal {N}\smallsetminus \bigcup _{\alpha <\beta } A_\alpha $
And, given
$\mathcal {{F}}$
a set of such sequences, let
$$\begin{align*}X_{\mathcal{{F}}}=X\smallsetminus \bigcup_{\overline A\in \mathcal{{F}}}\bigcup_{\alpha<\beta} A_{\alpha}=\bigcap_{\overline A\in \mathcal{{F}}} X_{\overline A}.\end{align*}$$
Abusing notation slightly, identify the ordinal product
$\omega \cdot \alpha $
with the lexicographic order on
$\alpha \times \omega $
. For
$\overline A=\langle {A_{\beta }:\beta \in \omega \cdot \alpha } \rangle =\langle {A_{\beta , i}: (\beta ,i)\in \alpha \times \omega } \rangle $
, set
$\overline A_0=\langle {A_{\beta , 0}: \beta \in \alpha } \rangle .$
Say that a property
$\Phi (\langle { A_{\beta }: \beta \in \omega \cdot \alpha } \rangle )$
of an ordinal length sequence of sets (with length of the form
$\omega \cdot \alpha $
for some countable ordinal
$\alpha $
) is a refinement property if for some
$\Delta ^1_1$
sequence of
$\Sigma ^1_1$
properties
$\langle {\phi _i:i\in \omega } \rangle $
(all with arity k, though this is just a notational convenience) and
$\Delta ^1_1$
sequence of closure properties
$\langle {\Psi _i:i\in \omega } \rangle $
,
$\Phi (\overline A)$
if and only if
$$\begin{align*}(\forall \beta, i)\left[ \Psi_i(A_{\beta, i})\wedge \left(\forall \mathbf{x}\in (\mathcal{N}_{(\overline A_0\upharpoonright \beta)})^k \right)\; \mathbf{x}\in A_{\beta,i}^k\rightarrow\neg \phi_i(\mathbf{x}) \right]. \end{align*}$$
Informally, a refinement property says an independence property holds for each
$A_{\alpha ,i}$
if we ignore points in earlier
$A_{\alpha ,0}$
’s, and each
$A_{\alpha ,i}$
is
$\Psi _i$
-closed. For any refinement property property
$\Phi $
, the set
${\{\overline A\in \Delta ^1_1: (\forall \beta )\; A_\beta \in \Delta ^1_1\mbox { and }\Phi (\overline A)\}}$
is
$\Pi ^1_1.$
If some countable collection of sequences satisfies a refinement property, so does the sequence obtained by concatenating them together. We will often use this in conjunction with the following proposition.
Proposition 3.9. Suppose
$\mathcal {{F}}$
is a
$\Pi ^1_1$
family of
$\Delta ^1_1$
sequences which is closed under
$\Delta ^1_1$
concatenations. For any
$\Sigma ^1_1$
set
$p\subseteq \mathcal {N}^n$
, whenever
$p\cap (X_{\mathcal {{ F}}})^n=\emptyset $
there is a single
$\Delta ^1_1$
sequence
$\overline A\in \mathcal {{F}}$
so that
$p\cap (X_{\overline A})^n=0$
.
Proof For any
$\Sigma ^1_1$
sets X and p,
$p\cap (X_{\mathcal {{F}}})^n=\emptyset $
if and only if
$$ \begin{align} (\forall \mathbf{x})\;\mathbf{x}\not\in p\mbox{ or }(\exists \overline A_1,\dots,\overline A_n\in \Delta^1_1)(\forall i)\left[ \,\overline A_i\in \mathcal{{F}}\mbox{ and }(\exists \alpha_i<\omega_1^{CK})\; x_i\in (A_i)_{\alpha_i} \right]. \end{align} $$
As usual, existential quantifiers over
$\Delta ^1_1$
are equivalent to universal quantifiers, so
$$\begin{align*}(\exists \alpha<\omega_1^{CK})\,x\in A_\alpha\Leftrightarrow (\exists n\in\omega)\,n\mbox{ is a code for a well-order, }\alpha\; \&\; x\in A_\alpha\end{align*}$$
is
$\Pi ^1_1$
on
$\Pi ^1_1$
. Likewise,
$(*)$
is
$\Pi ^1_1$
on
$\Pi ^1_1$
as a property of
$\mathcal {{F}}$
. So, if
$\mathcal {{F}}$
is a
$\Pi ^1_1$
collection of sequences with
$p\cap X_{\mathcal {{F}}}^n=\emptyset $
, we can find a
$\Delta ^1_1$
subset
$\mathcal {{G}}\subseteq \mathcal {{F}}$
so that
$p\cap X_{\mathcal {{G}}}^n=\emptyset $
. We can find a
$\Delta ^1_1$
enumeration of the sequences in
$\mathcal {{G}}$
and concatenate them together to get a single sequence
$\overline A$
so that
$p\cap X^n_{\overline A}=\emptyset .$
We can prove that if there is some family of ordinal length sequence of Borel sets satisfying a refinement property that covers a
$\Delta ^1_1$
space, then there is a
$\Delta ^1_1$
such sequence (whose length is an effective ordinal).
Theorem 3.10. Suppose that
$\Phi $
is a refinement property,
$X\subseteq \mathcal {N}$
is
$\Delta ^1_1$
, and there a sequence of Borel sets
$\overline B=\langle {B_{\beta }: \beta \in \omega \cdot \alpha } \rangle $
with
$X_{\overline B}=\emptyset $
,
$\alpha <\omega _1$
, and
$\Phi (\overline B)$
. Then, there is a
$\Delta ^1_1$
sequence of
$\Delta ^1_1$
sets
$\overline A=\langle { A_{\beta }: \beta \in \omega \cdot \alpha '} \rangle $
so that
$X_{\overline A}=\emptyset $
,
$\Phi (\overline A)$
and
$\alpha '<\omega _1^{CK}$
.
Of course one can work in
$\mathcal {N}^n$
for some n with only notational changes, or using the fact that
$\mathcal {N}$
and
$\mathcal {N}^k$
are computably isomorphic.
Proof First, define
$\mathcal {{F}}$
by
$$\begin{align*}\mathcal{{F}}=\bigl\{\,\overline A\in \Delta^1_1:\Phi(\overline A ),\mbox{ and } (\forall \beta)\; A_\beta\in \Delta^1_1\bigr\}.\end{align*}$$
If
$X_{\mathcal {{F}}}=\emptyset $
, then by Proposition 3.9, there is single
$\Delta ^1_1$
sequence
$\overline A$
so that
$X_{\overline A}=\emptyset $
. So, suppose toward contradiction that
$X_{\mathcal {{F}}}\not =\emptyset $
. Note that
$X_{\mathcal {{F}}}$
is
$\Sigma ^1_1.$
So,
$$\begin{align*}X_{\mathcal{{F}}}\Vdash \dot x\in B_{\alpha,i}\mbox{ for some }\alpha.\end{align*}$$
Define
$$\begin{align*}\alpha_0:=\min\{\alpha: (\exists p\subseteq X_{\mathcal{{F}}},i\in\omega)\; p\Vdash \dot x\in B_{\alpha,i}\}\end{align*}$$
and fix some
$i\in \omega $
and
$p\subseteq X_{\mathcal {{F}}}$
so that
$p\Vdash \dot x\in B_{\alpha _0,i}$
. By the proof of Lemma 3.4, we may assume
$\Psi _i(p)$
.
Let
$\phi _i$
be as in the definition of refinement property. So
$\phi $
is
$\Sigma ^1_1$
and has arity k. If
$q=\{(x_1,\dots ,x_k)\in p^k: \phi _i(x)\}\cap (X_{\mathcal {{F}}})^k$
is nonempty, then
$$\begin{align*}q\Vdash \dot x_1,\dots,\dot x_k\in B_{ \alpha_0,i}\wedge \;\phi_i(\dot x_1,\dots,\dot x_k).\end{align*}$$
Since
$\Phi (\overline B)$
, by absoluteness
$q\Vdash (\exists j,\beta <\alpha _0)\; x_j\in B_{ \beta ,0}$
. But then we can find a condition below p forcing
$\dot x\in B_{\beta ,0}$
with
$\beta <\alpha _0$
, contradicting minimality.
So,
$\{(x_1,\dots ,x_k)\in p^k: \phi _i(x)\}\cap (X_{\mathcal {{F}}})^k=\emptyset $
, and by Proposition 3.9 there is a single
$\Delta ^1_1$
sequence
$\overline A$
so that
$\{(x_1,\dots ,x_k)\in p^k: \phi (x_1,\dots ,x_k)\}\cap (X_{\overline A})^k=\emptyset $
. But then by reflection we can find a
$\Delta ^1_1$
set
$A'\supseteq p$
so that
$\Psi _i(A')$
and
$\phi _i(\mathbf x)$
for
$\mathbf {x}\in (A')^k\cap (\mathcal {N}_{\overline {A}_0})^k$
. Then, setting
$A^{\prime }_j=A'$
if
$j=i$
and
$A^{\prime }_j=A_{0,j}$
otherwise, we get a
$\Delta ^1_1$
sequence of sets
$\overline A'=\langle {A^{\prime }_j:j\in \omega } \rangle $
so that
$p\subseteq A_i$
and
$\overline A^\smallfrown \overline A'\in \mathcal {{F}}$
, contradicting our choice of p.
The only application of this theorem we give below is to local colorings of graphs equipped with quasi-orders. However, we point out that the “forceless, ineffective, and powerless” proofs of Miller typically work by marrying sequences of Borel sets satisfying a refinement property to the usual derivative process on a tree of attempts to build a homomorphism from a canonical obstruction (so that there is no homomorphism if and only if the tree is well-founded if and only if there a sequence of refining sets that cover
$\mathcal {N}$
). So Theorem 3.10 should usually apply whenever Miller’s methods apply.
4. Applications
In this section we give several applications of the results above to the study of Borel graphs and relations. Throughout, we assume that our graphs and relations are on
$\mathcal {N}$
. The complexity results lift to other spaces by standard universality arguments. We start by giving proofs of two folklore theorems.
The classical Lusin–Novikov uniformization theorem says that any Borel relation with countable sections is the union of countably many Borel partial functions [Reference Kechris4, Theorem 18.10]. One important corollary is the Feldman–Moore theorem, which says that any countable Borel equivalence relation is induced by a Borel group action and in fact is a union of countably many Borel involutions [Reference Kechris and Miller5, Theorem 1.3]. There are elegant effective proofs of these theorems based on the effective perfect set theorem, but these effective proofs do not seem to be recorded in the literature. Here we show how the effective versions of these theorems can be deduced from the classical versions.
Theorem 4.1. If R is
$\Delta ^1_1$
relation with countable sections, then
$R=\bigcup _i f_i$
where
$\langle {f_i:i\in \omega } \rangle $
is a
$\Delta ^1_1$
sequence of
$\Delta ^1_1$
partial functions. Further, if R is an equivalence relation, then each
$f_i$
can be chosen to be an involution.
Proof The classical Lusin–Novikov theorem tells us that R is a union of Borel partial functions. A set
$f\subseteq \mathcal {N}^2$
is a partial function if and only if
$$\begin{align*}(\forall x,y,y')\;(x,y),(x,y')\in f\rightarrow y=y'.\end{align*}$$
This is an independence property, so by Theorem 3.5 R is a union of a
$\Delta ^1_1$
sequence of
$\Delta ^1_1$
partial functions.
And if R is an equivalence relation, then the classical Feldman–Moore theorem says that R is a union of Borel involutions. A set
$f\subseteq \mathcal {N}^2$
is a partial involution if and only if
$$\begin{align*}f\mbox{ is a function}\mbox{ and }(\forall x,y)\;(x,y)\in f\rightarrow (y,x)\in f.\end{align*}$$
This is a conjunction of an independence property and a closure property. So again by Theorem 3.5, R is a union of a
$\Delta ^1_1$
sequence of
$\Delta ^1_1$
partial involutions.
To finish, we need to show that any partial
$\Delta ^1_1$
involution extends to an involution. The domain of any
$\Delta ^1_1$
partial function is
$\Delta ^1_1$
, so we can then extend a partial involution f by setting
$f(x)=x$
for
$x\not \in \operatorname {dom}(f)$
.
Next, we can characterize graphs which can be (not necessarily symmetrically) generated by countable families of functions. That is, we reprove [Reference Thornton11, Theorem 4.1].
Definition 4.2. A graph G is generated by a list of functions
$\langle {f_i: i\in I} \rangle $
if
$G\subseteq \{(x,y): y=f_i(x)\mbox { or }x=f_i(y)\}.$
We could equivalently require
$G=\{(x,y): y=f_i(x)\mbox { or }x=f_i(y)\}$
if we allow partial functions. Since any
$\Delta ^1_1$
partial function extends to a
$\Delta ^1_1$
total function, this equivalence holds even when we restrict to Borel or
$\Delta ^1_1$
functions.
Theorem 4.3. If G is a
$\Delta ^1_1$
graph generated by a countable list of Borel functions, then G is generated by a
$\Delta ^1_1$
list of
$\Delta ^1_1$
functions.
Proof A graph G is generated by a countable list of functions if and only if G can be covered by countably many sets f so that f is a partial function or
${-}f$
is a partial function (where
${-}(x,y)=(y,x)$
). Since being a function is an independence property and
$e\mapsto {-}e$
is a
$\Delta ^1_1$
bijection, Lemma 3.4 tells us that this is a reflectable property. So, if we have a Borel cover we have a
$\Delta ^1_1$
cover by Theorem 3.6.
Corollary 4.4. The set of Borel graphs generated by a countable family of Borel functions is
$\Pi ^1_1$
in the codes.
We can prove a similar result for graphs generated by a single function. This argument is inspired by Hjorth and Miller’s dichotomy for end selection, but we need to make use of some features of acyclic graphs to get around their assumption that G is locally countable. This settles [Reference Thornton11, Problem 4.5].
Theorem 4.5. If G is
$\Delta ^1_1$
and generated by a single Borel function, then it is generated by a single
$\Delta ^1_1$
function.
Proof For this theorem, the reduction to a covering problem is nontrivial. First we reduce to the case where G is acyclic.
Any graph generated by a single function is a sidewalk.Footnote 1 Let
$$\begin{align*}A=\{x\in \mathcal{N}: [x]_G\mbox{ contains a cycle}\}.\end{align*}$$
Each component contains at most one cycle, so this set is
$\Delta ^1_1$
, and we can select a single vertex from each component of
$G\upharpoonright A$
in a
$\Delta ^1_1$
way as follows: each vertex in A can enumerate the vertices in its cycle using the effective Luzin–Novikov theorem, and then we choose a vertex if it is the smallest vertex in a cycle according to some
$\Delta ^1_1$
linear order
$\mathcal {N}$
. From this selector, it is straightforward to construct a function which generates
$G\upharpoonright A$
.
Therefore, without loss of generality we may assume that G is acyclic. This means simple paths between points are unique, so the connectedness relation is
$\Delta ^1_1$
.
Definition 4.6. A (directed) edge
$e=(e_0,e_1)$
points to a vertex x if x and
$e_0$
are connected and the simple path from
$e_0$
to x goes through
$e_1$
. We write
$ePx.$
Write
$eIe'$
if
$e\not =e'$
,
$e_0,e^{\prime }_0$
are connected, and neither
$eP e^{\prime }_0$
nor
$e'P e_0.$
Write
$e\prec e' $
if
$e P e^{\prime }_0$
but not
$e'P e_0.$
A set of edges A is consistent if
$(\forall e,e'\in A) \;\neg ( e I e')$
.
The simple path from a vertex x to itself contains only x. So, if A is consistent, then we cannot have
$(x,y)$
and
$(x,y')$
both in A unless
$y=y'$
. That is, any consistent set must be a partial function. For any
$\Delta ^1_1$
consistent set A, we can take its downward closure under
$\prec $
to get a
$\Sigma ^1_1$
consistent
$\prec $
-closed set. By the second reflection theorem, any
$\Sigma ^1_1$
consistent
$\prec $
-closed set extends to a
$\Delta ^1_1$
consistent
$\prec $
-closed set.
Lemma 4.7.
$G=\bigcup _i ( A_i\cup ({-}A_i))$
where
$\langle {A_i:i\in \omega } \rangle $
is a
$\Delta ^1_1$
sequence of consistent sets if and only if G is generated by a
$\Delta ^1_1$
function.
Proof of lemma
Suppose f generates. We want to show that
$f\cap G$
is consistent. Otherwise, there are some
$e,e'\in f$
so that
$eIe'$
. If there are n undirected edges on the simple path between
$e_0$
and
$e^{\prime }_0$
, there are
$n-1$
vertices on the path besides
$e_0$
and
$e^{\prime }_0.$
Label these vertices
$v_1,\dots ,v_{n-1}$
. Since
$f(e_0)$
and
$f(e^{\prime }_0)$
point off of the path and f generates G, there can only be the
$n-1$
edges on the path of the form
$\{v_i, f(v_i)\}$
. This is a contradiction. So if f generates, then
$G\subseteq f\cup ({-}f)$
gives a cover.
For the other direction we may assume each
$A_i$
is
$\prec $
-closed. Note that if
$X,Y$
are
$\prec $
-closed and consistent, then so is
$Y\cup (X\smallsetminus ({-}Y))$
. Define
$f_i$
inductively by
$f_{i+1}=f_{i}\cup (A_{i+1}\smallsetminus ({-}f_i) ),$
and set
$f=\bigcup _i f_i$
. Then f is a partial function so that
$G=f\cup ({-}f)$
, and G is generated by a single function.
So, G is generated by a (Borel)
$\Delta ^1_1$
function if and only if G is covered by (Borel)
$\Delta ^1_1$
sets A such that A is consistent and
${-}A$
is consistent.
Corollary 4.8. The set of graphs generated by a Borel function is
$\Pi ^1_1$
in the codes.
We can also prove an effectivization result for end selection in locally countable graphs using an argument of Hjorth and Miller [Reference Hjorth and Miller3]. Note, their dichotomy was proven without effective methods and only gives a complexity upper bound of
$\mathbf {\Delta }^1_2$
for end selection. In the proof we will use Hjorth and Miller’s characterization of end selection, but for completeness we include the definition of end and end selection below:
Definition 4.9. For a graph G, write
$[G]^{<\omega }$
for the G-connected finite subsets of G. (Note that if G is locally countable, this can be coded as a subset of
$\mathcal {N}$
using the effective Lusin–Novikov theorem.) For
$S\in [G]^{<\omega }$
,
$[S]_G$
is the connected component of G. If v is a vertex, we write
$[v]_G$
for
$[\{v\}]_G$
. Write
$G\smallsetminus S$
for the induced subgraph on the complement of S.
If G is a locally countable connected graph, then an end in G is an equivalence class of infinite injective paths in G with respect to the equivalence relation
$$\begin{align*}\langle {v_i:i\in\omega} \rangle\sim \langle {u_i:i\in\omega} \rangle:\Leftrightarrow (\forall S\in [G]^{<\omega})(\exists N\in\omega)(\forall i,j>N)\,v_i\in [u_i]_{G\smallsetminus S}.\end{align*}$$
That is, an end is a class of paths which eventually land in the same complement if we cut out any finite set.
An end selection in a graph G is a choice of infinite paths for each vertex so that vertices in the same component choose paths which represent the same end.
Theorem 4.10. If G is a locally countable
$\Delta ^1_1$
graph which admits a Borel end selection, then G admits a
$\Delta ^1_1$
end selection.
Proof Since G is locally countable,
$E_G$
is
$\Delta ^1_1$
. Let
$$\begin{align*}R=\{(S,x): S\in [G]^{<\infty}, x\in [S]_G\}.\end{align*}$$
Note that R has countable sections over
$[G]^{<\infty }$
. Following [Reference Hjorth and Miller3],
$\mathcal {{D}}\subseteq [G]^{<\infty }\times \mathcal {N}$
is directed if:
-
(1)
$\mathcal {{D}}\subseteq R.$
-
(2) For all
$(S,x)\in \mathcal {{D}}$
,
$x\not \in S.$
-
(3) If
$(S,x), (S', x')\in \mathcal {{D}}$
and S and
$S'$
are in the same G-component, then and
$x',x$
are connected in at least one of
$G\smallsetminus S$
or
$G\smallsetminus S'$
.
Note that directedness is an independence property. And, [Reference Hjorth and Miller3, Proposition 3.4] says a locally countable Borel graph G admits a Borel end selection if and only
$[G]^{<\infty }$
can be covered by projections of Borel directed sets. It is straightforward to check that one can replace Borel with
$\Delta ^1_1$
in their proof. We can then apply Theorem 3.6.
The theorem above implies that any
$\Delta ^1_1$
Schreier graph of a free Borel action of
$\mathbb {Z}$
is the Schreier graph of a free
$\Delta ^1_1$
action. Or, in the language of [Reference Miller8], the set of directable forests of lines is
$\Pi ^1_1$
in the codes. We can generalize this to effectivize Borel actions of
$\mathbb {Z}^2$
.
Theorem 4.11. If G is a
$\Delta ^1_1$
graph and the Schreier graph of free Borel action of
$\mathbb {Z}^2$
with the usual generating set, then G is the Schreier graph of a free
$\Delta ^1_1$
action of
$\mathbb {Z}^2.$
Proof All components of G are isomorphic the Cayley graph of
$\mathbb {Z}^2$
. In particular G is locally countable.
Definition 4.12. A straight line is a directed path so that no other path of the same or shorter length has the same endpoints. A rectangle is a simple directed cycle that can be divided into four straight lines.
Two directed edges
$e,e'$
are parallel if they lie on some straight line together or if
$({-}e)$
and
$e'$
are on opposite sides of a rectangle. We write
$e \| e'$
. We say
$e,e'$
are anti-parallel if
$({-}e) \| e$
. And we say
$e,e'$
are perpendicular if they are in the same component and are neither parallel nor anti-parallel. We write
$e\perp e'.$
Note that all of these relations are
$\Delta ^1_1.$
Definition 4.13. Let
$\{a,b,{-}a,{-}b\}$
be the usual generating set for
$\mathbb {Z}^2$
. For a graph G, say that a partial function
$f:G \rightarrow \{a, b, {-}a, {-}b\}$
is a partial diagram if for all
$e, e'$
,
-
(1) if
$e\|e'$
, then
$f(e)=f(e'),$
-
(2) if
$e\|({-}e')$
then
$f(e)={-}f(e'),$
-
(3) if
$e\perp e'$
then
$f(e)$
and
$f(e')$
have different letters (i.e.
$f(e)\not =\pm f(e')$
).
A Cayley diagram is a partial diagram whose domain is all of G.
We first check that being induced by a free
$\mathbb {Z}^2$
action is equivalent to having Cayley diagram. If
$a:\mathbb {Z}^2\curvearrowright \mathcal {N}$
is an action generating G, then any straight line is of the form
$\{n\gamma \cdot x: n\in \mathbb {Z}\}$
for some generator
$\gamma $
of
$\mathbb {Z}^2$
. It follows that
$f(x,\gamma \cdot x)=\gamma $
defines a Cayley diagram. Conversely, given a Cayley diagram f, we can define an action of a generator c by
$c\cdot x=y\Leftrightarrow f(x,y)=c$
. To see this extends to an action of
$\mathbb {Z}^2$
, note that, for any
$x,y,\ f(x,y)=-f(y,x)$
so
$(\gamma -\gamma )\cdot x=x$
, and
$(x, a\cdot x, (b+a)\cdot x,(-a+b+a)\cdot x,(-b-a+b+a)\cdot x)$
must be a rectangle, so
$x=(-b-a+b+a)\cdot x.$
Since being a partial diagram is an independence property, it suffices to show that any sequence of partial diagrams whose domains cover G can be patched together into a Cayley diagram.
Suppose we have two
$\Delta ^1_1$
partial diagrams f and g. We show how to modify and glue them together to get a partial diagram whose domain is the union of their domains. The result then follows by induction. Define h by:
-
(1) if
$e\in \operatorname {dom}(f)$
, then
$h(e)=f(e),$
-
(2) if
$e\in \operatorname {dom}(g)\smallsetminus [\operatorname {dom}(f)]_G$
,
$h(e)=g(e),$
-
(3) else if
$e\in \operatorname {dom}(g)$
and
$e\|e'$
for some
$e'\in \operatorname {dom}(f)$
(or
$e\|(- e')$
), then
$h(e)=f(e')$
(or
$-f(e')$
), -
(4) else if
$e\perp e'\in \operatorname {dom}(f)$
,
$h(e)$
has the sign of
$g(e)$
and the opposite letter of
$f(e')$
.
It is straightforward to check that h is a partial diagram.
Corollary 4.14. The set of Schreier graphs of Borel
$\mathbb {Z}^2$
actions is
$\Pi ^1_1$
in the codes.
A similar idea works for
$\mathbb {Z}^n$
. We can also effectivize a recent result of Miller which we will use in the next section.
Theorem 4.15 (cf. [Reference Miller9, Theorem 1]).
If
$\langle {G_{i,j}: i,j\in \omega } \rangle $
is a
$\Delta ^1_1$
array of graphs, and there are Borel sets
$B_i$
such that
$\mathcal {N}=\bigcup _i B_i$
and
$G_{i,j}\upharpoonright B_i$
has a Borel countable coloring for every j, then there are
$\Delta ^1_1$
sets
$A_i$
so that
$G_{i,j}\upharpoonright A_i$
has a
$\Delta ^1_1$
countable coloring for all j.
Proof This is equivalent to effectivizing sequences
$\langle {A_{ijk}: i,j,k\in \omega } \rangle $
of sets so that
$A_{ijk}$
is
$G_{ij}$
-independent and so that for all x there is an i so that for all j there is a k so that
$x\in A_{ijk}$
. The result then follows from Theorem 3.7.
Corollary 4.16. The set of arrays of Borel graphs
$G_{i,j}$
so that there are Borel sets
$B_i$
with
$\chi _B(G_{i,j}\upharpoonright B_i)\leq \aleph _0$
for all
$i,j$
and
$\mathcal {N}=\bigcup _i B_i$
is
$\Pi ^1_1$
in the codes.
Finally, we can effectivize Miller’s dichotomy for local colorings of graphs equipped with quasi-orders [Reference Miller10, Theorem 5.1.2].
Theorem 4.17. If
$(G,R)$
is a
$\Delta ^1_1$
graph and quasi-order on
$\mathcal {N}$
so that R admits a Borel homomorphism, f, to some
$\leq _{lex}^\alpha $
with
$\alpha <\omega _1$
with
$G\cap (\equiv _f)$
countably Borel colorable, then
$(G,R)$
admits a
$\Delta ^1_1$
such homomorphism into some
$\leq _{lex}^\alpha $
with
$\alpha <\omega _1^{CK}$
.
Proof First we show that such a homomorphism from R is equivalent to a sequence of pairs of sets
$\langle {(R_\alpha , S_\alpha ):\alpha <\beta } \rangle $
in
$\mathcal {N}^2$
with:
-
(1) Each
$R_\alpha $
is a box
$A_\alpha \times B_\alpha $
, and each
$S_\alpha $
is a box
$C_\alpha \times D_\alpha .$
-
(2)
$\left (R_\alpha \cap R\right )\smallsetminus \left (\bigcup _{\gamma <\alpha }R_\gamma \right )=\emptyset .$
-
(3)
$\left (C_\alpha ^2\cap G\right )\smallsetminus \left (\bigcup _{\gamma <\alpha }R_\gamma \right )=\emptyset. $
-
(4)
$C_\alpha \cap D_\alpha =\emptyset .$
-
(5)
$G\subseteq \bigcup _{\alpha <\beta } R_\alpha \cup S_\alpha $
.
Given such a sequence, we may assume each
$A_\alpha $
is closed upwards under the quasi-order generated by
$R\smallsetminus \left (\bigcup _{\gamma <\alpha }R_\gamma \right )$
. So,
$f(x)(\alpha )=\chi _{A_\alpha }(x)$
defines a homomorphism. And
$c(x)=\min \{\alpha : x\in C_\alpha \}$
gives a coloring of
$G\cap (\equiv _f)$
. Conversely, given a homomorphism and coloring we can get such a sequence by considering the color classes and the sets of the form
$\{x: f(x)(\alpha )=i\}$
for
$i\in \{0,1\}$
.
Since
$(1),(2),(3),$
and
$(4)$
describe a refinement property, we can apply Theorem 3.10.
Corollary 4.18. The set of pairs
$(G,R)$
where G is a Borel graph and R is a Borel quasi-order with a homomorphism and coloring as above is
$\Pi ^1_1$
in the codes.
5. Some dichotomies
We end by establishing some dichotomy theorems related to some of the new effectivization results of the previous section. Our two results about generating graphs with functions can be deduced from a dichotomy for graphs equipped with group actions.
Definition 5.1. For G a Borel graph on X,
$\Gamma $
a countable group, and a an action of
$\Gamma $
on X, we say that
$f:\mathcal {N}\rightarrow \omega \times \Gamma $
is an a-coloring of
$(G,a)$
if, for all
$n\in \omega $
,
$\{h\cdot _a x: f(x)=(n,h)\}$
is G-independent.
Fix
$\langle {(\gamma _n,s_n):n\in \omega } \rangle $
a sequence with
$(\gamma _n,s_n)\in \Gamma \times 2^n$
such that, for each
$\gamma \in \Gamma $
,
$\gamma =\gamma _n$
for infinitely many n, and every string in
$2^{<\omega }$
is extended by some
$s_n$
. Call such a sequence generic. Then
$G_\Gamma $
is the graph on
$\Gamma \times 2^\omega $
defined by
$$ \begin{align*} x G_\Gamma y:\Leftrightarrow & (\exists z\in 2^\omega,n\in\omega) \left[x=s_n^\smallfrown 0 ^\smallfrown z\mbox{ and }y=s_n^\smallfrown 1 ^\smallfrown z \right].\end{align*} $$
We equip
$\Gamma \times 2^\omega $
with the obvious
$\Gamma $
action,
$a_\Gamma $
: for any
$z\in 2^\omega $
$$\begin{align*}\gamma\cdot (\gamma',z)=(\gamma\gamma',z).\end{align*}$$
Note that a graph G is generated by a countably family of functions if and only if there is an a-coloring of
$(G', a)$
where
$G'$
is the graph on G given by
$$\begin{align*}G'= \{(e,e')\in G^2: e_0=e^{\prime}_0\}\end{align*}$$
and a is the action of
$C_2=(\{\pm 1\},\times )$
given by
$$\begin{align*}{-}1\cdot (x,y)=-(x,y)=(y,x).\end{align*}$$
This along with the following theorem settles [Reference Thornton11, Problem 4.4]. Similarly, a graph is generated by a single function if and only if there is an a-coloring of
$(G",a)$
, where
$eG" e'$
if and only if
$e I e'$
(with I as in Definition 4.6) and a is as before.
Theorem 5.2. For any Borel graph G and Borel action of
$a:\Gamma \curvearrowright \mathcal {N}$
, either
$(G,a)$
admits a Borel a-coloring or there is an equivariant homomorphism from
$G_\Gamma $
to G, i.e., a map
$f: \Gamma \times 2^\omega \rightarrow \mathcal {N}$
so that:
-
(1)
$f(h\cdot _{a_\Gamma } x)=h \cdot _a f(x).$
-
(2) If
$x G_\Gamma y$
then
$f(x) G f(y).$
Proof First we show that the two options are mutually exclusive. If c is an a-coloring of
$(G,a)$
and f is an equivariant homomorphism of
$(G_\Gamma , a_\Gamma )$
into G, then
$c\circ f$
is an a-coloring of
$G_\Gamma .$
So, it suffices to show no such a-coloring exists. Suppose
$c:\Gamma \times 2^\omega \rightarrow \omega \times \Gamma $
is a Borel a-coloring. Then, for some
$(n,\gamma )$
,
$c^{-1}(n,\gamma )$
is nonmeager. Since
$\Gamma $
acts by homeomorphisms,
${U=\gamma \cdot c^{-1}(n,\gamma )}$
is also nonmeager. Suppose U is comeager in
$N_{(\gamma ', s)}$
. By genericity of
$\langle {(\gamma _n,s_n):n\in \omega } \rangle $
, there is some n with
$\gamma '=\gamma _n$
and
$s\subseteq s_n$
. Let t be the homeomorphism that flips the
$(n+1)$
th bit of a string. Then, every
$(\gamma ',\sigma )\in N_{(\gamma _n,s_n)}$
has a neighbour
$(\gamma ',t(\sigma ))\in N_{\gamma ',s}$
. So, by Baire category, there is a nonmeager set of points in U with a neighbour in U. This contradicts the definition of a-colorings.
For
$\gamma \in \Gamma $
, define
$G_\gamma $
by
$x\; G_\gamma \; y$
if and only if
$\gamma \cdot x \;G \;\gamma \cdot y$
. Then, there is an a-coloring of
$(G,a)$
if and only if there a cover of X by sets which are independent for some
$G_\gamma $
.
Let
$G_{0,\gamma }$
be the graph on
$2^\omega $
given by
$$\begin{align*}x \; G_{0,\gamma}\; y:\Leftrightarrow (\exists z\in 2^\omega, n\in\omega)\; \gamma_n=\gamma, x=s_n^\smallfrown 0^\smallfrown z, y=s_n^\smallfrown 1^\smallfrown z.\end{align*}$$
Suppose
$(G,a)$
does not admit an a-coloring. By [Reference Miller9] and the genericity of
$\langle {(\gamma _n,s_n):n\in \omega } \rangle $
, there is some
$g: 2^\omega \rightarrow G$
which is a homomorphism from
$G_{0,\gamma }$
to
$G_\gamma $
for every
$\Gamma $
.
Now define
$f(\gamma ,x)=\gamma \cdot g(x)$
. We show this is an equivariant homomorphism from
$(G_\Gamma , a_\Gamma )$
to
$(G,a)$
. Equivariance is clear from the definition, and if
$(\gamma , x) G_\Gamma (\gamma , y)$
, then
$x \; G_{0,\gamma }\; y$
, so
$g(x)\; G_\gamma \; g(y) $
and
$\gamma \cdot g(x)\; G \;\gamma \cdot g(y)$
.
Corollary 5.3. The set of pairs of Borel graphs and actions which admit a-colorings is
$\Pi ^1_1$
in the codes.
Proof The proof above gives a reduction to the set of codes for sequences of graphs as in Theorem 4.15.
So, a graph G is generated by a countable family of Borel functions if and only if there is an equivariant homomorphism from
$(G_{C_2}, a_{C_2})$
to
$(G', a)$
as defined in the comments after Definition 5.1. We can refine this analysis somewhat to eliminate reference to the auxiliary graph
$G'$
.
Definition 5.4. For tuples of relations
$R=(R_1,\dots ,R_n)$
on X and
$S=(S_1,\dots ,S_n)$
on Y, a homomorphism from R to S is a function
$f:X\rightarrow Y$
so that, for each i, f is a homomorphism from
$R_i$
to
$S_i$
:
$R_i(x_1,\dots ,x_k)$
implies
$S_i(f(x_1),\dots ,f(x_k)).$
As usual,
$C_2=\{1,-1\}$
acts on
$C_2\times 2^\omega $
by
$a\cdot (b,x)=(ab,x).$
Theorem 5.5. Define graphs R and
$G^{-}_{C_2}$
on
$C_2\times 2^{\omega }$
as follows:
$$\begin{align*}R=\{(x,(-1)\cdot x): x\in C_2\times 2^{\omega}\}\end{align*}$$
and
$$\begin{align*}G^{-}_{C_2}=\{((-1)\cdot x,(-1)\cdot y): (x,y)\in G_{C_2}\}.\end{align*}$$
A graph G on X is generated by a countable family of Borel functions if and only if there is no homomorphism from
$(G_{C_2},G^{-}_{C_2}, R)$
to
$(=, \not =, G).$
Proof Let’s abbreviate
$(-1)\cdot x$
by
$-x$
for
$x\in C_2\times 2^\omega $
. So, a homomorphism from
$(G_{C_2}, G^-_{C_2}, R)$
to
$(=,\not =, G)$
amounts to a map
${f: C_2\times 2^\omega }$
so that:
-
(1)
$f(x)=f(y)$
if
$(x,y)\in G_{C_2}.$
-
(2)
$(f(x), f(- x))\in G.$
-
(3) If
$-x G_{C_2} -y$
, then
$f(x)\not =f(y)$
(or equivalently if
$x G_{C_2} y$
then
$f(-x)\not =f(-y)$
).
We will show that such a map exists if and only if there is an equivariant homomorphism from
$(G_{C_2}, a_{C_2})$
into the graph
$\widetilde G=\{((x,y),(x,y')): (x,y), (x,y')\in G\}$
on G.
Suppose f is a map as above. Then define
$\tilde f:C_2\times 2^\omega \rightarrow G$
by
$\tilde f(x)=(f(x), f(- x)).$
This is well-defined by property
$(2)$
. If
$x,y$
are neighbours in
$G_{C_2}$
, then by property
$(3)$
,
$f(- x)\not =f(- y)$
, and by property
$(1)\ f(x)=f(y)$
. So,
$\tilde f(x)=(f(x),f(- x))= (f(y),f(- x))$
and
$\tilde f(y)=(f(y),f(- y))$
are neighbours in
$\widetilde G$
.
Suppose f is an equivariant homomorphism from
$(G_{C_2}, a_{C_2})$
to
$\widetilde G$
. Then define
$\tilde f: C_2\times 2^\omega \rightarrow X$
by
$\tilde f(x)=x_0$
where
$f(x)=(x_0,x_1)$
. If
$f(x)=(x_0, x_1)\in G$
, then
$f(- x)=-{(x_0,x_1)}=(x_1,x_0)$
, so
$\tilde f(- x)=x_1$
. This means
$\tilde f(x)$
and
$\tilde f(- x)$
share an edge in G, giving property
$(2)$
. And, if x and y are neighbours in
$G_{C_2}$
, then
$f(x)$
and
$f(y)$
are neighbours in
$\widetilde G$
, so
$x_0=y_0$
and
$x_1\not =y_1$
; this gives properties
$(1)$
and
$(3)$
above.
Note that
$(1)$
and
$(2)$
above say that f descends to a homomorphism to G from the graph on
$(C_2\times 2^\omega )/E_{G_{C_2}}$
with edges
$([x],[-x])$
.
We can also characterize graphs induced by an action of
$\mathbb {Z}^2$
. There are two canonical obstructions in this case, one in two dimensions and one in one dimension.
Definition 5.6. A square lattice is a graph isomorphic to the usual Cayley graph on
$\mathbb {Z}^2$
. A graph is locally a square lattice if each component is a square lattice.
For G locally a square lattice, let
$\perp _G$
denote the graph whose vertex set is G and two vertices (meaning edges in G) are adjacent if they are perpendicular in the sense of Definition 4.12.
The proof of Theorem 4.11 gives the following:
Proposition 5.7. If G is locally a square lattice, then G is induced by a free Borel action of
$\mathbb {Z}^2$
if and only if
$\perp _G$
admits a Borel 2-coloring and any forest of straight lines in G is directable.
We think of
$\perp _G$
having a 2-coloring as a two-dimensional requirement, and having all forests of straight lines be directable as one-dimensional. These two requirements are independent.
Proposition 5.8. There are Borel graphs G,
$\Gamma $
where
$\perp _G$
admits a Borel 2-coloring, and every forest of lines in
$\Gamma $
is directable, but where neither is induced by a Borel free action of
$\mathbb {Z}^2.$
Proof Let
$E=\{e_0,e_1,-e_0,-e_1\}$
be the standard generating set for
$\mathbb {Z}^2$
, and let
$\langle {n,m} \rangle $
be the canonical image of
$(n,m)\in \mathbb {Z}^2$
in
$\operatorname {Aut}(\operatorname {Cay}(\mathbb {Z}^2, E))$
. Suppose
${\Gamma \subseteq \operatorname {Aut}(\operatorname {Cay}(\mathbb {Z}^2, E))}$
is a subgroup so that
$\gamma (0)=0$
and
$\langle {\gamma (n,m)} \rangle ^{-1}\gamma \langle {n,m} \rangle \in \Gamma $
for all
$\gamma \in \Gamma $
. Note that such a group must be finite.
Let
$\mathrm {Fr}_\Gamma $
be the free part of
$[0,1]^{\mathbb {Z}^2}$
. The group
$\operatorname {Aut}(\operatorname {Cay}(\mathbb {Z}^2, E))$
acts on
$\mathrm {Fr}_\Gamma $
by shifting indices,
$\gamma \cdot x=x\circ \gamma ^{-1}$
. Let
$\tilde S_\Gamma $
be the graph on
$\mathrm {Fr}_\Gamma /\Gamma $
defined by
$$\begin{align*}\tilde S_\Gamma:= \{([x],[\langle {a} \rangle\cdot x]): x\in \mathrm{Fr}_\Gamma, a\in E\}.\end{align*}$$
First, we show that
$\tilde S_\gamma $
is always locally isomorphic to
$\operatorname {Cay}(\mathbb {Z}^2,E).$
In fact, for any
$x\in \mathrm {Fr}_{\gamma }$
,
$(a,b)\mapsto [\langle {a,b} \rangle \cdot x]$
is an isomorphism from
$\operatorname {Cay}(\mathbb {Z}^2,E)$
to the component of
$[x]$
. Clearly, this map is a homomorphism. The relation
$$\begin{align*}\gamma\cdot \left(\langle {n,m} \rangle\cdot x\right)=\langle {\gamma(n,m)} \rangle\cdot \left(\langle {\gamma(n,m)^{-1}} \rangle\gamma\langle {n,m} \rangle\cdot x\right)\end{align*}$$
says that, for every
$n,m\in \mathbb {Z}$
and
$\gamma \in \Gamma $
, there are unique
$(a,b)\in \mathbb {Z}^2$
and
$\delta \in \Gamma $
so that
$\gamma \cdot (\langle {n,m} \rangle \cdot x)=\langle {a,b} \rangle \cdot (\delta \cdot x)$
. So this map is a bijection. And since
$\Gamma $
acts freely and preserves E, the same relation implies that non-edges are sent to non-edges.
Second, we show that if
$\Gamma $
is nontrivial, then
$\tilde S_\Gamma $
is not the Cayley graph of a Borel action of
$\mathbb {Z}^2.$
Suppose otherwise and for
$x\in \mathrm {Fr}_\Gamma $
consider the bijection
$f_x:E\rightarrow E$
defined by
$$\begin{align*}f_x(a)=b:\Leftrightarrow [\langle {a} \rangle\cdot x]=b\cdot [x].\end{align*}$$
The same relation as above says that
$f_{\gamma \cdot x}(a)=f_x(\gamma (b)^{-1})$
for
$\gamma \in \Gamma $
. And
$f_{\langle {n,m} \rangle \cdot x}=f_{x}$
for
$n,m\in \mathbb {Z}^2$
since
$\langle {n,m} \rangle $
commutes with
$\langle {a} \rangle $
for
$a\in E$
.
For some
$f:E\rightarrow E$
, the set
$\{x: f_x=f\}$
has positive measure and is
$\mathbb {Z}^2$
-invariant. By ergodicity of the shift action, this set has measure one. But then
$f_x=f_{\gamma \cdot x}$
for some x, which is a contradiction.
All that remains is to find suitable
$\Gamma $
and
$\Delta $
so that
$\perp _{\tilde S_\Gamma }$
has a Borel 2-coloring and every forest of straight lines in
$\tilde S_\Delta $
is directable.
Let
$\Gamma $
be the group generated by
$t_0$
and
$t_1$
where
$t_0(n,m)=(-n,m)$
and
$t_1(n,m)=(n,-m)$
. Since
$t_i(\pm e_j)\in \{e_j,-e_j\}$
for each
$i,j$
, we can define a Borel 2-coloring of
$\tilde S_\Gamma $
by
$$\begin{align*}f([x],[\pm e_i\cdot x])=i.\end{align*}$$
Let
$\Delta $
be the group generated by s where
$s(n,m)=(m,n)$
. Since
$s(-e_i)=-s(e_i)$
for each i, we can define an orientation o of
$\tilde S_\Delta $
by
$$\begin{align*}o=\{([x],[y]): x=e_0\cdot y\mbox{ or }x=e_1\cdot y\}.\end{align*}$$
This orientation is balanced when restricted to any straight line, so gives a direction to every forest of straight lines.
Miller’s
$\mathcal {{L}}_0$
dichotomy characterizes undirectable forests of lines [Reference Miller8], and a result of Carroy, Miller, Schrittesser, and Vidyanszky characterizes 2-colorable graphs [Reference Carroy, Miller, Schrittesser and Vidnyanszky1]. In the case of
$\perp _G$
, we can reflect this to a characterization of G, but we need to strengthen the results in [Reference Carroy, Miller, Schrittesser and Vidnyanszky1].
Definition 5.9. Let
$s_0=\emptyset $
, and for
$n>0$
let
$s_n=0^{n-1}1$
. Define a graph
$\mathcal {{L}}$
on
$2^\omega $
by
$\{x,y\}\in \mathcal {{L}}$
if and only if
$$\begin{align*}(\exists z\in 2^\omega, n\in\omega) x=s_n^\smallfrown 0^\smallfrown z, y=s_n^\smallfrown 1^\smallfrown z. \end{align*}$$
Let
$d_G$
be the graph metric for G, i.e., for vertices
$x,y$
,
$d_G(x,y)$
is the minimal number of edges in a path from x to y (or infinite if x and y are not connected). For any graph G, let
$G_{odd}=\{(x,y): d_G(x,y)\mbox { is odd}\}.$
If we let
$G_n$
be the graph on
$2^n$
gotten by restricting the definition of G to strings of length n, then G is a projective limit of the sequence
$\langle {G_n:n\in \omega } \rangle $
. Each
$G_n$
is a path graph, and
$G_{n+1}$
is gotten by connecting two endpoints of two copies of
$G_{n+1}$
.
Theorem 5.10 (Ess. [Reference Carroy, Miller, Schrittesser and Vidnyanszky1, Theorem 1.1]).
If G is a Borel graph and not Borel 2-colorable, then there is a homomorphism of
$\mathcal {{L}}$
into
$G_{odd}$
.
Note that if G is locally a square lattice, then
$(\perp _G)_{odd}=\perp _G$
. The strengthening we need is a strong form of local injectivity for the homomorphism given by the theorem above.
Theorem 5.11. If G is locally a square lattice, and
$\perp _G$
does not admit a Borel 2-coloring, then there is a Borel homomorphism from
$\mathcal {{L}}$
into
$\perp _G$
so that, if
$x,y$
are connected and
$x\not =y$
, then
$f(x)$
and
$f(y)$
do not lie on a straight line.
Proof By relativization, we may assume G is
$\Delta ^1_1$
. Suppose
$\perp _G$
does not admit a
$\Delta ^1_1$
2-coloring. Define
$$\begin{align*}X:=G\smallsetminus\bigcup \{A\in \Delta^1_1: A\mbox{ is }\perp_G\mbox{-independent}\}.\end{align*}$$
By reflection, X is the same as G without its
$\Sigma ^1_1$
independent sets. If X is empty, then we can construct a
$\Delta ^1_1$
2-coloring of
$\perp _G$
. So X is nonempty.
As usual, we will build a homomorphism by constructing trees of conditions forcing the graph relations we want. To ensure we get the kind of injectivity we want, we will make sure our generics force points in the image of our homomorphism to be far apart.
For edges
$e,e'$
let
$d_G(e,e')=d_G(e_0,e^{\prime }_0)$
with respect to the graph metric. Say that
$e,e'$
are n-spaced if, whenever we have intersecting paths
$p,p'$
which are perpendicular line segments such that
$e_0$
is on p and
$e^{\prime }_0$
is on
$p'$
, then the length of
$p,p'$
are both of length at least n.
Say that
$\langle {U_\sigma : \sigma \in 2^\omega } \rangle $
and
$\langle {R_{\sigma ,\tau }:(\sigma ,\tau )\in G_n} \rangle $
are an n-approximation with spread d if:
-
(1)
$U_\sigma \subseteq X$
and
$R_{\sigma ,\tau }\subseteq \perp _{G.}$
-
(2) If
$\langle {x_\sigma :\sigma \in 2^n} \rangle $
satisfies
$(\forall \sigma ,\tau \in G_n) \,(x_\sigma ,x_\tau )\in R_{\sigma ,\tau }$
, then for all
$\sigma ,\tau \in 2^n$
,
$d_G(x_\sigma ,x_\tau )<d$
. -
(3) For any
$x\in U_\rho $
there is
$\langle {x_\sigma : \sigma \in 2^n} \rangle $
so that
$(\forall (\sigma ,\tau )\in G_n)\,(x_\sigma ,x_\tau )\in R_{\sigma ,\tau }$
and
$x_\rho =x.$
We want to build a tree of generics which contain nice approximations. I claim that for any n-approximation with spread d,
$\langle {R_{\sigma ,\tau }:(\sigma ,\tau )\in G_n} \rangle $
and
$\langle {U_{\sigma }: \sigma \in 2^n} \rangle $
, and any dense sets of conditions
$E\subseteq \mathbb {{P}}_1$
and
$F\subseteq \mathbb {{P}}_2$
there is an
$(n+1)$
-approximation
$\langle {R_{\sigma ,\tau }:(\sigma ,\tau )\in G_{n+1}} \rangle $
and
$\langle {U_{\sigma }:\sigma \in 2^{n+1}} \rangle $
so that:
-
a)
$U_{\sigma ^\smallfrown i}\subseteq U_\sigma $
and
$R_{\sigma ^\smallfrown i,\tau ^\smallfrown i}\subseteq R_{\sigma ,\tau }$
for all
$\sigma , \tau \in G_n$
and
$i\in \{0,1\}.$
-
b) For all
$\sigma ,\tau $
,
$U_\sigma \subseteq E$
and
$R_{\sigma ,\tau }\subseteq F.$
-
c) Any pair of points
$(x_{\sigma _n^\smallfrown 0},x_{\sigma _n^\smallfrown 1})\in R_{\sigma _n^\smallfrown 0,\sigma _n^\smallfrown 1}$
are at least
$(3d+1)$
-spaced.
To this end, define V to be the set of realizations of our n-approximation
$$\begin{align*}V:=\{x: (\exists \langle {x_{\sigma}:\sigma\in 2^n} \rangle) \,x=x_{\sigma_n}, x_{\sigma}\in U_\sigma, x_{\sigma,\tau}\in R_{\sigma\tau}\}. \end{align*}$$
Since V is a nonempty
$\Sigma ^1_1$
subset of X, it must not be independent. That is V contains two perpendicular edges. We need V to contain two edges which are perpendicular and
$(3d+1)$
-spaced. If we can’t find such edges, then the intersection of V with any component is either finite or bounded by two parallel lines. But then, in either case, we can refine V to an independent set:
-
• if V meets a component in a finite set can choose a single point from that component (say the least according to some
$\Delta ^1_1$
order, -
• if V is bounded by two parallel lines we can take all edges parallel to these lines (or perpendicular if none are parallel).
This contradicts the fact that X doesn’t contain any
$\Sigma ^1_1$
independent sets. So, we can let
$R_{\sigma _n^\smallfrown 0,\sigma _n^\smallfrown 1}$
be any condition in F below
$$\begin{align*}\{(x,y)\in V^2\cap (\perp_G): x,y\mbox{ are }(3d+1)\mbox{-spaced}\}.\end{align*}$$
Since
$G_n$
is acyclic, the rest of our approximation can be built by iteratively refining out from here, just as in the proof of the
$G_0$
-dichotomy.
From the claim above, working over a countable transitive model of a large enough fragment of ZFC, we can build a sequence of n-approximations with spread
$d(n)$
so that if
$(x,y)\in R_{\sigma _n^\smallfrown 0,\sigma _n^\smallfrown 1}$
then
$x,y$
are
$(3d(n)+1)$
-spaced, and we can build a tree of generics
$\langle {x_s: s\in 2^\omega } \rangle $
so that:
-
• For all n,
$x_s\in U_{s\upharpoonright n}.$
-
• If
$(s,t)\in \mathcal {{L}}$
then for all n either
$s\upharpoonright n=t\upharpoonright n$
or
$(x_s,x_t)\in R_{s\upharpoonright n,t\upharpoonright n}$
.
In particular,
$s\mapsto x_s$
is a homomorphism from
$\mathcal {{L}}$
to
$\perp _G$
. Now we check that no two connected points get sent to the same straight line. Suppose
$(s,t)\in \mathcal {{L}}$
, say
$s=\sigma ^\smallfrown 0^\smallfrown z$
and
$t=\tau ^\smallfrown 1^\smallfrown z$
with
$|\sigma |=|\tau |=n$
. Then by our assumption on spread
$d_G(x_s, x_{\sigma _n^\smallfrown 0^\smallfrown z})<d(n)$
and likewise for
$x_t$
and
$x_{\sigma _n^\smallfrown 1^\smallfrown z}$
. And since
$x_{\sigma _n^\smallfrown 0^\smallfrown z}$
and
$x_{\sigma ^\smallfrown 1^\smallfrown z}$
are at least
$(3d(n)+1)$
-spaced, we must have that
$x_s$
and
$x_t$
are on different straight lines.
With this in place, we can start characterizing graphs G where
$\perp _G$
admits a Borel 2-coloring.
Definition 5.12. If G and H are graphs on
$X,Y$
which are locally square lattices, then say
$f:X\rightarrow Y$
is a conformal map from G to H if, for any vertices
$x,y$
of G,
$x,y$
are on a straight line if and only if
$f(x),f(y)$
are on a straight line.
Conformal maps preserve perpendicularity, so we can pull a 2-coloring back from
$\perp _G$
to
$\perp _H$
whenever there is a conformal map from H to G.
Proposition 5.13. If there is a Borel conformal map from H to G and
$\perp _G$
has a Borel 2-coloring, then
$\perp _H$
has a Borel 2-coloring.
Proof First note that if
$v_1,v_2,v_3,$
and
$v_4$
are consecutive corners of a rectangle in a square lattice if and only
$v_i$
and
$v_j$
are on straight line exactly when
$i=j\pm 1$
(mod 4). So the corners of a rectangle in H are sent to the corners of a rectangle in G by any conformal map.
Now suppose that f is a Borel conformal map from H to G and g is a Borel 2-coloring of
$\perp _G$
. Then we have a Borel map
$\tilde g:H\rightarrow 2$
given by
$\tilde g(e_0,e_1)=g(e')$
for any edge
$e'$
on the straight line between
$f(e_0)$
and
$f(e_1)$
. If
$e\perp _H e'$
, then possibly replacing e with
$-e$
, we can find a rectangle containing
$e,e'$
. This rectangle is sent by f to a rectangle with consecutive sides containing
$f(e_0), f(e_1)$
and
$f(e^{\prime }_0),f(e^{\prime }_1)$
. The coloring g must assign opposite colors to all edges on consecutive sides of a rectangle, so
$\tilde g(e)\not =\tilde g(e').$
Our goal is to show there is a minimal square lattice with respect Borel conformal maps among those where
$\perp $
is not Borel 2-colorable.
Definition 5.14. Let
$X_{\mathbb {{S}}_0}=\{(x,y)\in 2^\omega : d_{\mathcal {{L}}}(x,y)\mbox { is odd}\}/E$
with the quotient Borel structure, where
$[(x,y)]_E=\{(x,y),(y,x)\}$
. Abbreviate
$[(x,y)]_E$
by
$[x,y]$
. Then
$\mathbb {{S}}_0$
is the graph on
$X_{\mathbb {{S}}_0}$
defined by
$$\begin{align*}[x,y]\; \mathbb{{S}}_0\; [a,b]:\Leftrightarrow x=a,d_{\mathcal{{L}}}(y,b)=2\mbox{, or }y=b,d_{\mathcal{{L}}}(x,a)=2.\end{align*}$$
Before proving our dichotomy, let us show that
$\mathbb {{S}}_0$
is locally a square lattice.
Proposition 5.15.
$\mathbb {{S}}_0$
is locally a square lattice.
Proof Fix a component C of
$\mathbb {{S}}_0$
. The corresponding component of
$\mathcal {{L}}$
is 2-regular and acyclic, so we can fix an isomorphism between it and the usual Cayley graph for
$\mathbb {Z}$
. So we can represent C as
$\{(n,m): n\in 2\mathbb {Z}, m\in 2\mathbb {Z}+1\}$
. And we have that
$(n,m)$
and
$(\ell ,k)$
are adjacent if
$n=\ell \pm 2$
or
$m=k\pm 2.$
Thus
$(a,b)\mapsto (2a, 2b+1)$
defines an isomorphism between the usual Cayley graph for
$\mathbb {Z}^2$
and C.
Theorem 5.16. If a Borel graph G is locally a square lattice, then either
$\perp _G$
admits a Borel 2-coloring, or there is a Borel conformal map from
$\mathbb {{S}}_0$
to G.
Proof First we show
$\mathbb {{S}}_0$
does not admit a conformal map into any graph G where
$\perp _G$
is Borel 2-colorable. It suffices to show
$\perp _{\mathbb {{S}}_0}$
does not admit a Borel 2-coloring. Note that the straight lines in
$\mathbb {{S}}_0$
are the sets
$L_a=\{[a,b]: d(a,b)\mbox { is odd}\}$
for
$a\in \mathcal {{L}}$
. Suppose
$f: G\rightarrow 2$
is a Borel 2-coloring of
$\perp _{\mathbb {{S}}_0}$
. Then for each a, the edges in
$L_a$
are all assigned the same color by f. This defines a Borel function
$g:\mathcal {{L}}\rightarrow 2$
. Suppose
$d(a,b)$
is odd,
$d(a,a')=d(b,b')=2$
. Then
$([a,b], [a',b])$
and
$([a,b],[a,b'])$
are perpendicular edges in
$L_b$
and
$L_a$
respectively, so edges in
$L_a$
and
$L_b$
are assigned different colors by f, and
$g(a)\not =g(b)$
. Thus g is a Borel 2-coloring of
$\mathcal {{L}}$
, which is a contradiction.
Now suppose G is locally a square lattice and
$\perp _G$
does not admit a Borel 2-coloring. So, there is a Borel homomorphism f from
$\mathcal {{L}}$
to
$\perp _G$
which sends connected vertices to edges which are not on a straight line. Define an map g from
$\mathbb {{S}}_0$
to G by setting
$g([a,b])$
to be the unique point on both the straight line containing
$f(a)$
and the straight line containing
$f(b)$
. This is well-defined since any two perpendicular lines in the same plane must intersect. All that remains is to check this is conformal.
Suppose
$[x,y_0]$
and
$[x,y_1]$
are two points on a straight line
$L_x$
. Then
$g([x,y_0])$
and
$g([x,y_1])$
are on the straight line through
$f(x)$
. Conversely, suppose
$[x_0,x_1]$
and
$[y_0,y_1]$
are not a straight line, and
$d_{\mathcal {{L}}}(x_0,y_0)=0\;(\mbox {mod } 2)$
. Then,
$x_0\not =y_0$
and
$x_1\not =y_1$
. So
$f(x_0)$
,
$f(y_0)$
,
$f(x_1)$
, and
$f(y_1)$
are all on different straight lines. So,
$g([x_0,x_1])$
and
$g([y_0,y_1])$
are not on a straight line. Thus g is conformal.
Combining this with Miller’s
$\mathcal {{L}}_0$
dichotomy for directable forests of lines, we get the following:
Corollary 5.17. If G is a Borel graph, either G is the Schreier graph of a free Borel action of
$\mathbb {Z}^2$
or at least one of the following holds:
-
(1) G is not locally a square lattice.
-
(2) There is a Borel conformal map from
$\mathbb {{S}}_0$
to
$G.$
-
(3) There is a Borel betweenness-preserving embedding of
$\mathcal {{L}}_0$
into some forest of straight lines in
$G.$
Acknowledgements
Thanks to Andrew Marks for helpful comments on earlier drafts of this paper, and thank you to the reviewer for many helpful comments.
Funding
The author was supported by the NSF grant DMS-1764174.
