Locally countable graphs of 2nd projective class not generated by projective functions

A graph \(G\) is said to be \(F\) [1] if for any \(x,y\) in the domain of \(G\), it holds e* x G y fF (x=f(y) y=f(x)). Such a graph has to be locally countable, of course, provided the family \(F\) is countable or finite and each \(f\in F\) is \({\le}\alo\)-to-1 (, the \(f\)-preimage of every element is at most countable). Conversely, using the axiom of choice, one easily proves that every locally countable graph is generated by a countable family of functions, by necessity of type \({\le}\alo\)-to-1.

The inverse problem becomes more involved in the case where definability of generating functions is required depending on the definability of a given graph. In particular, as shown in [1], every locally countable Borel graph is generated by a countable family of Borel functions. This is because any Borel set with countable sections is a countable union of Borel uniform sets by a well-known theorem of classical descriptive set theory.

This paper is devoted to the problem of generation of graphs of second projective level by systems of projective and real-ordinal definable functions.

At the \(\fs12\) side, we prove (Theorem [t2]) that every locally countable \(\fs12\) graph is generated by a family of \(\ali\)-many Borel functions, by necessity of type \({\le}\alo\)-to-1. Then we consider the equi-constructibility \(\is12\) graph e| xy := -  x,y; the irreflexive part of the equivalence relation of equi-constructibility on \(\dn.\) Its properties depend on a model in which \(\cL\) is considered. In particular, in \(\rL\), the constructible universe, any reals \(x\ne y\) in \(\dn\) are \(\cL\)-adjacent, and, by Theorem [t2+] below, \(\cL\) is generated by a countable family of \(\is12\) functions (not necessarily of type \({\le}\alo\)-to-1).

A similar positive result also holds for some models of the form \(\rL[a]\), for instance, in the case of Sacks-generic reals \(a\in\dn.\) However Lemma [sax] solves the issue in the negative provided we require countable families of functions to generate \(\cL\). The lengthy proof of the lemma involves some specific properties of the Sacks forcing, and the result itself is the key ingredient in the proof of the following theorem.

It is true in the Solovay model that \(\cL\) is a locally countable \(\is12\) graph not generated by countably many real-ordinal definable (ROD, for brevity) functions.

As usual in descriptive set theory, the case of \(\fp12\) graphs causes even greater difficulties. The following theorem is our second main result.

There exists a model of set theory \(\zfc\) in which there is a locally countable \(\ip12\) graph \(G\) on \(\dn\) not generated by countably many \(\ROD\) functions.

Theorem [mt] answers in the positive the question on the existence of such a model and a graph in [2], with the required example of a graph presented in the special form of the irreflexive part of a countable \(\ip12\) equivalence relation. The proof of this result in § [p12] makes use of a model defined in [3], in which there exists a planar \(\ip12\) set with countable sections, not uniformizable by ROD (including projective) sets.

The reader is assumed to have a basic knowledge of descriptive set theory and forcing. However we have to review here some more special notions.

As is customary, we take \(\bai\) as the principal domain, and also consider \(\bai\ti\bai\) , as well as the \(\dn\sq\bai.\) Elements of \(\bai\) are called . Sets \(X\sq\bai,\) \(X\sq(\bai\ti\bai)\), are , collections of pointsets are . In particular, such pointclasses as \(\fd11\) (Borel sets), \(\fs11\) (analytic or Suslin sets), \(\fp11\) (coanalytic or co-Suslin sets), \(\fs1n\yi\fp1n\yi\fd1n\) (projective classes), \(\fs1\iy=\fp1\iy\) (all projective sets) are systematically studied by descriptive set theory (see [4] or [5]).

Such pointclasses as \(\OD\) (ordinal-definable sets), \(\OD(P)\) (elements \(p\in P\) are admitted as parameters along with ordinals), and \(\ROD=\OD(\bai)\) (real-ordinal-definable sets) are considered in more abstract branches of set theory. See [5] or [6] on OD and ROD.

\(\bse\) is the set of all (finite) of numbers \(0\) and \(1\), including the empty tuple \(\etu\). The of \(s\in\nse\) is denoted by \(\lh s\). If \(s\in\nse\) and \(j=0,1\) then \(s\we j\in\bse\) is obtained by adding \(j\) as the new rightmost term. Generally, \(s\we t\) is the concatenation. Then, \(s\su t\) means that a tuple \(t\) extends \(s\), and \(\su\) means proper extension.

A set \(T\sq\bse\) is a iff (1) \(s\su t\in T\imp s\in T\), and (2) \(s\in T\imp \sus j\,(s\we j\in T)\), and a tree if additionally \(\kaz s\in T\,\sus t\in T\,\sus j\ne i\in\ans{0,1}\, (t\we i\in T\land t\we j\in T)\). Then \([T]=\ens{x\in\dn}{\kaz m\,(x\res m\in T)}\) is a perfect subset of \(\dn.\)

A will be any \(G\sq\dn\ti\dn,\) (\({x\mre G y}\eqv {y\mre G x}\)), and (\({x\mre G y}\imp {x\ne y}\)). Here and below \({x\mre G y}\) is a shortcut for \(\ang{x,y}\in G\). A graph \(G\) is (say \(K=\fd11=\) Borel) if \(G\) belongs to \(K\) as a set of pairs. Thus a Borel graph \(G\) means that \(G\) is a Borel set.

Elements of the set \(|G|=\ens{x}{\sus y\,(x\mre G y)}\) are of \(G\) while the pairs in \(G\) are its . Occasionally, graphs \(G\) with \(|G|\sq{\bai\ti\bai}\) will be considered as well. A graph \(G\) is if for any vertice \(x\in |G|\) the set \(\ens{y}{x\mre G y}\) of all vertices is at most countable. This is equivalent to the countability of every of \(G\).

The notion of a graph \(G\) \(F\), based on [e*], was given in Introduction. Here we suppose that each \(f\in F\) is a function \(f:\dom f\sq|G|\to |G|\), and \(\dom f=|G|\) is not assumed, while an equality like \(y=f(x)\) means \(x\in\dom f\land y=f(x)\).

We prove here two rather elementary theorems. By the way, they are not used in the proofs of Theorems [mts] and [mt] below – our main results.

Assume that \(G\sq\dn\ti\dn\) is a locally countable \(\fs12\) graph. Then \(G\) is generated by a family \(F=\enx{f_\al}{\al<\omi}\) of \(\ali\) \(\fd12\) functions. Let \(G\) be a \(\is12(p_0)\) set; \(p_0\in\dn\) is fixed in the proof. If \(x\in\dn\) then the set \(G(x)=\ens{y}{x\mathrel G y}\) of all \(G\)-adjacent elements is a countable \(\is12(p_0,x)\) set, so that \(G(x)\sq\rL[p_0,x]\). It follows that \(G(x)\sq\ens{h(\al, p_0, x )}{\al<\omi}\), where \(h(\al, p, x)\) is the \(\al\)th element of the set \(\dn\cap\rL[p,x]\) in the sense of the canonical Gödel of \(\dn\cap\rL[p,x]\). We recall that \(h:\omi\ti\dn\ti\dn\to\dn\) is known to be a \(\id\hc1\) function.

We let \(f(\al, x)=h(\al, p_0, x)\) whenever \(x\mG h(\al, p_0, x)\). Thus \(f\) is function defined on \(D=\dom f := \enx{\ang{\al,x}\in\omi\ti\dn} {x\mathrel G h(\al, p_0, x)},\) and in fact a \(\is\hc1(p_0)\) function, as the set of tuples \(\ens{\ang{\al,x,f(\al, x)}}{\ang{\al,x}\in D}\), by the above. It follows that every \(f_\al(x):=f(\al,x)\) is a \(\fs12\) function from \(D_\al=\ens{x\in\dn}{\ang{\al,x}\in D}\) to \(\dn.\) Prove that \(G\) is generated by the family \(F=\enx{f_\al}{\al<\omi}\).

Assume that \(x\mathrel G y\), hence \(y\in G(x)\). Then \(y=h(\al,p_0,x)=f(\al,x)=f_\al(x)\) for some \(\al<\omi\) by construction. Conversely suppose that \(y=f_\al(x)=f(\al,x)\) for some \(\al\); then we have \(x\mathrel G y\).

It is true in \(\rL\) that the equi-constructibility \(\is12\) graph \(\cL\) is generated by a countable family \(F=\enx{f_n}{n<\om}\) of \(\id12\) functions.

We argue in \(\rL\). Let \(\lc\) be the Gödel of \(\rL\). If \(x\in\dn\) then let \(\ens{h(n,x)}{n<\om}\) be the \(\lc\)-least enumeration of the set \(\ens{y\in\dn}{y\lc x}\). We put \(f_n(x):=h(n,x)\). Separately for the \(\lc\)-least real \(x_0\in\dn\) put \(f_n(x_0):=x_1\), where \(x_1\in\dn\) is the \(\lc\)-next element.

We consider the \(\is12\) equi-constructibility graph \(x\mcL y\) iff \(x\ne y\) but \(\rL[x]=\rL[y]\) on \(\dn.\) Lemma [sax] below presents a rather difficult negative result for the Sacks-generic extensions, which will be used in the proof of Theorem [mts].

Recall that the Sacks forcing \(\saf z\) for a model of the form \(\rL[z]\) consists of all perfect trees \(T\in\rL[z]\), \(T\sq\bse.\) It adjoins a \(a\in\dn\) to \(\rL[z]\). In the proof of Lemma [sax], we will use the following well-known properties of the Sacks forcing, for which see, for example, [7] or [5, Sec. 15].

Assume that \(\zo\in\dn.\) Then\(:\) if \(a\in\dn\) is \(\saf\zo\)-generic over \(\rL[\zo]\), and \(b\in\dn\cap\rL[\zo,a]\) then either \(b\in\rL[\zo]\) or \(a\in\rL[\zo,b]\) and the real \(b\) also is \(\saf\zo\)-generic over \(\rL[\zo]\,;\)

the forcing \(\saf\zo\) is homogeneous, , if \(S,T\in\saf\zo\), then the cones \(K_S=\ens{S'\in\saf\zo}{S'\sq S}\) and \(K_T\) are \(\sq\)-isomorphic in \(\rL[\zo]\,;\)

as a standard consequence of [sx3], if some \(S\in\saf\zo\) forces a closed formula \(\Phi\) with parameters only from \(\rL[\zo]\), then any other tree \(T\in\saf\zo\) also forces \(\Phi\). 0◻

Suppose that \(\zo\in\bai,\) and \(\ao\in\dn\) is a Sacks-generic real over \(\rL[\zo]\). Let, in \(\rL[\zo,\ao]\), \(F=\sis{f_n}{n<\om}\) be an \(\OD(\ans\zo)\) sequence of functions \(f_n:\dn\to\dn\). Then, in \(\rL[\zo,\ao]\), \(\cL\) is not generated by \(F.\)

If \(x,y\in\bai\) then let \(\sko xy\in\bai\) be the stepwise concatenation, that is, \((\sko xy)(2k)=x(k)\) and \((\sko xy)(2k+1)=y(k)\), \(\kaz k\).

Suppose to the contrary that, in \(\rL[\zo,\ao],\) the family \(F\) generates \(\cL\).

All statements about forcing below in the course of the proof are related only to forcing \(\saf\zo\) over \(\rL[\zo]\). We consider the tree \[T_0=\ens{s\in\bse}{\kaz n=2k<\lh s\,(s(2k)=\zo(k))} \in\saf\zo\,,\] so that \([T_0]=\ens{\sko\zo y}{y\in\dn}\).

Under our assumptions, there is a formula \(\vpi(n,x,y)\) with parameters \(\zo\) and some \(\al_1,\dots,\al_m\in\Ord\) not explicitly indicated, such that it is true in \(\rL[\zo,\ao]\) that \(f_n=\ens{\ang{x,y}}{\vpi(n,x,y)}\) for each \(n\). Let \(\barf n\) be the shorthand for \(\ens{\ang{x,y}}{\vpi(n,x,y)}\). Then the following sentence

\(\kaz n\,(\barf n:\dn\to\dn)\) and the family \(\ens{\barf n}{n<\om}\) generates \(\cL\) holds in \(\rL[\zo,\ao]\) by the above. It follows that any condition in \(\saf\zo\), in particular \(T_0\), forces \(\Phi\) over \(\rL[\zo]\) by item [sx4] of Proposition [sx].

From now on, we argue in \(\rL[\zo]\). Let \(\una\) be the canonical \(\saf\zo\)-name for the principal Sacks-generic real in \(\dn.\) We claim that

Indeed suppose towards the contrary that \(T\in\saf\zo\) is a counterexample. Then there is a real \(y\in\rL[\zo]\cap\dn\) such that in fact \(T\) forces \(\barf n(\una)=y\) over \(\rL[\zo]\). We know that \(\ao\) is a Sacks-generic real over \(\rL[\zo]\). It follows that there is a Sacks-generic real \(a\in [T]\) over \(\rL[\zo]\) – by item [sx3] of Proposition [sx]. Then we have \(\barf n(a)=y\) by the genericity, and hence \(a\mcL y\) holds in \(\rL[\zo,a]\) because \(T_0\) forces \(\Phi\).

However \(y\in\rL[\zo]\) whereas \(a\nin\rL[\zo]\) by the genericity. Therefore \(\rL[a]=\rL[y]\) is definitely impossible. This contradiction completes the proof of [saxA].

The following is an easy corollary of [saxA].

Now, still arguing in \(\rL[\zo]\), we prove that In \(\rL[\zo]\), there exists a system of trees \(U_s\) and tuples \(r_s\), where \(s\in\bse,\) and tuples \(\vt^n_s\), where \(s\in\bse\) and \(n<\lh s\), satisfying the following conditions [sax1]–[saxf]: \(U_s\in\saf\zo\), \(U_s\sq T_0\), \(r_s\in U_s\), \(\vt^n_s\in\bse\);

if \(s\in\bse\) and \(n<\lh s\) then \(\lh \vt^n_s\ge\lh s\);

if \(s\in\bse\) then \(\lh r_s\ge \lh s\) and \(r_s\) is \(\sq\)-comparable with each \(t\in U_s\);

if \(s\su t\) belong to \(\bse\) and \(n<\lh s\) then \(r_s\su r_t\), \(U_t\sq U_s\), \(\vt^n_s\su\vt^n_t\);

if \(s\ne t\in\bse\) and \(n<\lh s=\lh t\) then \(r_{s}\) and \(r_{t}\) are \(\sq\)-incomparable, and \(\vt^n_{s}\), \(\vt^n_{t}\) are \(\sq\)-incomparable as well;

if \(s\in\bse\) and \(n<\lh s\) then \(U_s\) forces \(\vt^n_s\su \barf n(\kn a)\) over \(\rL[\zo]\). The construction goes on in \(\rL[\zo]\) by induction on \(\lh s\).

We put \(U_\etu=T_0\) and \(r_\etu=\etu\), where \(\etu\in\bse\) is the empty tuple and the perfect tree \(T_0\in\saf\pu\) was chosen above.

Now suppose that \(m<\om\), and \(U_s,r_s,\vt^n_s\) have been defined for all \(s\in2^m\) (dyadic tuples of length \(m\)) and \(n<m\), and satisfy conditions [sax1]–[saxf].

Step 1. Do the following for each \(s\in2^m.\) Let \(\rho_s=\roo{U_s}\) be the largest tuple \(\rho\in U_s\) \(\sq\)-comparable with each \(u\in U_s\). Then \(r_s\sq\rho_s\) by [sax3]. For \(i=0,1\) define \(r_{s\we i}=\rho_s\we i\) and \(\baU_{s\we i}= \ens{u\in U_s}{u\sq r_{s\we i}\lor r_{s\we i}\su u}\). Thus \(r_\sg\), \(\baU_\sg\) are defined for all \(\sg\in2^{m+1}.\) The values \(r_\sg\) are final, whereas the trees \(\baU_\sg\) are temporary; they will be shrinked at the following steps. Note that the relevant parts of [sax1],[sax3],[sax4],[sax5] transfer to the level \(m+1\) from level \(m\), and will hold after any shrinking of the trees \(\baU_\sg\) within \(\saf\zo\).

Step 2. Do the following for all \(s\in2^m\), \(i=0,1\), \(n\le m\).

Put \(\sg=s\we i\). Define a temporary tuple \(\bavt^n_\sg\) as follows. Recall that \(T_0\) forces \(\Phi\), hence so does \(\baU_\sg\), in particular \(\baU_\sg\) forces \(\barf n:\dn\to\dn.\) Therefore there is a tree \(U\in\saf\zo\), \(U\sq \baU_\sg\), and a tuple \(\vt\in\bse\) with \(\lh\vt>m\) and, if \(n<m\) strictly (so that \(\vt^n_s\) has been defined) then \(\lh{\vt^n_s}<\lh\vt\), and in addition \(U\) forces \(\vt\su \barf n(\kn a)\).

We let \(\bavt^n_\sg\) be such an \(\vt\), and let the associated \(U\) be the “new” \(\baU_\sg\).

This definition obviously honors [sax2], the last claim in [sax4], and [saxf].

Step 3. To fix [sax5], do the following for all \(n\le m\) and \(\sg\ne \ta\) in \(2^{m+1}.\)

Arguing as above (Step 2) and using [saxB], we find trees \(U,U'\in\saf\zo\), \(U\sq\baU_\sg\), \(U'\sq\baU_\ta\), and tuples \(\vt,\vt'\in\bse\) with \(\bavt^n_\sg\su\vt\) and \(\bavt^n_\ta\su\vt'\), such that \(U\) forces \(\vt\su \barf n(\kn a)\), \(U'\) forces \(\vt'\su \barf n(\kn a)\), and (this is where [saxB] works!) for some \(k<\lh\vt,\lh\vt'\) and \(j\ne\ell\) we have \(\sg(k)=j\) and \(\sg'(k)=\ell\).

The latter condition implies that tuples \(\vt,\,\vt'\) are \(\sq\)-incomparable.

Let \(\vt\) be the “new” \(\bavt^n_\sg\), \(\vt'\) be the “new” \(\bavt^n_\ta\), \(U\) be the “new” \(\baU_\sg\), \(U'\) be the “new” \(\baU_\ta\). Go to the next triple of \(n\le m\) and \(\sg\ne \ta\) in \(2^{m+1}.\)

Step 3 – finalization. After processing all triples of \(n\le m\) and \(\sg\ne \ta\) in \(2^{m+1},\) we let \(U_\sg\) be the final tree \(\baU_\sg\), and let \(\vt^n_\sg\) be the final tuple \(\bavt^n_\sg\) — for all \(n\le m\) and \(\sg\in 2^{m+1}.\)

Step 4 – conclusion. One easily sees that this construction yields a system of trees \(U_s\) and tuples \(r_s,\,\vt^n_s\) satisfying [sax1]–[saxf]. This ends the proof of [saxC].

To make use of this system, still arguing in \(\rL[\zo]\), we consider the tree \(U=\ens{r\in\bse} {\sus s\in\bse(r\sq r_s)}\); \(U\sq U_\etu\sq T_0\) by construction. Note that \(U\) is a perfect tree by [sax5] (regarding \(r_s,r_t\)), hence \(U\in\saf\zo\). Let us prove two claims in connection with this tree \(U\).

\(\saf\zo\) forces, over \(\rL[\zo]\), that “each \(\barf n\) is 1–1 on the set \(X_U\) of all reals \(x\in[U]\) \(\saf\zo\)-generic over \(\rL[\zo]\)”.

Indeed, arguing in a \(\saf\zo\)-generic extension \(\rL[\zo,a]\) of \(\rL[\zo]\), consider any \(n<\om\) and any reals \(x\ne y\) in \(X_U\). It follows from the definition of \(U\) and [sax3] that \([U]=\bigcap_m\bigcup_{s\in2^m}[U_s]\). Then, as \(x\ne y\), there exist \(m>n\) and \(s\ne t\) in \(2^m\) such that \(x\in [U_s]\) and \(y\in [U_t]\). Then the tuples \(\vt^n_{s}\) and \(\vt^n_{t}\) are \(\sq\)-incomparable by [sax5]. On the other hand, by [saxf], we have \(\vt^n_s\su f_n(x)\) and \(\vt^n_t\su f_n(y)\). We conclude that \(f_n(x)\ne f_n(y)\), as required.

\(\saf\zo\) forces that “(a) the set \(X_U\) as in [saxD] is uncountable, and (b) \(X_U\) consists of pairwise \(\cL\)-adjacent reals”.

Indeed (a) follows from item [sx2] of Proposition [sx], because it immediately implies \(X_U=[U]\bez\rL[\zo]\).

To prove (b) note that if \(x,y\) are \(\saf\zo\) generic over \(\rL[\zo]\) then \(\rL]\zo,x]=\rL[\zo,y]\) by item [sx2] of Proposition [sx]. However, by construction \(U\sq T_0\) and hence any real \(z\in[U]\) satisfies \(\zo\in\rL[z]\). Therefore the equality \(\rL]\zo,x]=\rL[\zo,y]\) implies \(\rL[x]=\rL[y]\), hence \(x\mcL y\), provided \(x\ne y\) belong to \([U]\), as required.

Thus it holds in the model \(\rL[\zo,\ao]\) of Lemma [sax] by [saxD],[saxE], that there is an uncountable set \(X\sq\dn\) of \(\mcL\msur\)-adjacent elements, on which each \(f_n\) is 1–1. Therefore, if \(x_0\in X\) is fixed, then any \(x\ne x_0\) in \(X\) satisfies \(x=f_n(x_0)\) or \(x_0=f_n(x)\). Thus the set of all adjacent elements is countable due to the bijectivity of each \(f_n\). This contradiction ends the proof of Lemma [sax].

Here we prove Theorem [mts]. The following definition introduces a particular form of the Solovay model we deal with in this theorem.

Let \(\rL\) be the ground model and \(\Om\in\rL\) be an inaccessible cardinal in \(\rL\). Following [5], [8], [6], we let \(\gN\) be the Levy–Solovay \(\text{Coll}(\om,{<}\Om)\)-generic extension of \(\rL\); this is a model of \(\ZFC\).

The next proposition presents three well-known properties of the Solovay model which we’ll use in the proof of Theorem [mts] below.

It is true in the model \(\gN\) just defined that\(:\) if sets \(X_0,X_1,X_2,\dots\) are real-ordinal definable (ROD, for brevity), then the sequence \(\sis{X_k}{k<\om}\) is \(\ROD\) as well\(;\)

if \(z\in\dn\) and a set \(X\sq\rL[z]\) is \(\OD(z)\) (, ordinal-definable with \(z\) as an extra parameter) then \(X\in\rL[z]\,;\)

if \(a\in\dn\) and a countable set \(X\sq\bai\) is \(\OD(a)\) then \(X\in\rL[a]\,;\)

if \(z,a\in\dn\) and a set \(X\sq\bai\) is \(\OD(z)\) then the set \(X'=X\cap\rL[z,a]\) belongs to \(\rL[z,a]\) and is \(\OD(z)\) in \(\rL[z,a]\,;\)

if \(z\in\dn\) then the set \(\rL[z]\cap\bai\) is countable \((\)in \(\gN\,)\). 0◻

We skip the well-known parts of the theorem. For instance the local countability follows from Proposition [sm][sm5].

Let’s focus on the key non-generation claim. .

Fix a family \(F=\ens{f_n}{n<\om}\) of arbitrary ROD functions \(f_n:\dn\to\dn.\) (If some \(f_n\) originally has \(\dom f_n=D\sneq\dn\) then we extend it by \(f_n(x)=x^-\) for \(x\nin D\), where \(x^-(k)=1-x(k)\) for all \(k\).) Suppose towards the contrary that \(\cL\) is generated by \(F.\) We observe that the whole sequence \(S=\sis{f_n}{n<\om}\) is ROD (in \(\gN\)) by Proposition [sm][sm1], hence there is a single real \(z_0\in\dn\) such that \(S\) is \(\OD(z_0)\). Fix such a real \(z_0\).

, we also fix a real \(\ao\in\dn\) Sacks-generic over \(\rL[\zo]\).

Then by [sm4] of Proposition [sm] each \(f'_n=f_n\cap\rL[\zo,\ao]\) belongs to \(\rL[\zo,\ao]\) and is \(\OD(\zo)\) in \(\rL[\zo,\ao]\), and moreover, the whole sequence \(S'=\sis{f'_n}{n<\om}\) belongs to \(\rL[\zo,\ao]\) and is \(\OD(\zo)\) in \(\rL[\zo,\ao]\).

On the other hand, given any \(x\in\rL[\zo,\ao]\cap\dn,\) we have \(f_n(x)\in\rL[\zo,\ao]\) and \(f_n\obr(x)\sq\rL[z_0,\ao]\) (because \(f_n\obr(x)\) is countable) by resp.[sm2] and [sm3] of Proposition [sm]. It follows that \(f'_n=f_n\res{(\dn\cap\rL[z_0,\ao])}\), and hence it is true in \(\rL[z_0,\ao]\) that the \(\OD(\zo)\) sequence \(S'\) generates \(\cL.\) But this contradicts Lemma [sax] !

Our proof of Theorem [mt] here is based on a model defined in [3], in which there exists a non-\(\ROD\)-uniformizable \(\ip12\) planar set with countable cross-sections. For the convenience of the reader, we present here this construction, without going into technical details, and then show how to convert it into an example for Theorem [mt] in the same model.

Beginning with \(\rL\) as the ground model, we defined in [3] a sequence \(\sis{\dP_\xi}{\xi<\omi}\in\rL\) of forcing notions \(\dP_\xi\). Each of \(\dP_\xi\) consists of perfect trees \(T\sq 2^{<\om}\) and is rather similar to the Jensen minimal-\(\id13\)-real forcing considered in detail in [5] or [9].

Then the finite-support product \(\dP=\prod_{\xi<\omi}\prod_{k<\om}\dP_{\xi k} \in\rL\) is defined in [3], where each factor \(\dP_{\xi k}\) is equal to \(\dP_\xi\), and we proved the following there:

\(\dP\) does not collapse \(\rL\)-cardinals;

\(\dP\) adjoins a generic array \(X=\sis{x_{\xi k}}{\xi<\omi,\,k<\om}\) of reals \(x_{\xi k}\in 2^\om\);

each \(x_{\xi k}\) is \(\dP_\xi\)-generic over \(\rL\), and conversely, every real \(x\in\rL[X]\), \(\dP_\xi\)-generic over \(\rL\), is equal to one of \(x_{\xi k},\:k<\om\);

the relation \(\text{\rm Gen}(\xi,x):=\) “\(\xi<\omi\) and \(x\in2^\om\) is \(\dP_\xi\)-generic over \(\rL\)” is \(\ip\HC1\) in \(\rL[X]\), where \(\HC=\) all hereditarily countable sets\(;\)

by the finite-support product forcing theory, if \(A\in\rL\), \(A\sq\omi\ti\om\), and \(\ang{\xi,k}\nin A\) then \(x_{\xi k}\nin \rL[X\res A]\), where \(X\res A=\sis{x_{\xi k}}{\ang{\xi,k}\in A}\), and moreover, \(x_{\xi k}\nin \OD(X\res A)\) in \(\rL[X]\). We used these properties of the generic model \(\rL[X]\) in [3] to prove that the set \(W=\ens{\ang{\xi,x_{\xi k}}}{\xi<\omi\land k<\om}\) is a non-\(\ROD\)-uniformizable \(\ip\HC1\) set with countable sections \(W_\xi=\ens{x_{\xi k}}{k<\om}\) in \(\rL[X]\).

This set was easily converted in [3] to a \(\ip12\) set \(W'\sq\dn\ti\dn\) in \(\rL[X]\) with the same properties. Indeed let \(\text{\ubf WO}\sq\bai\) be the standard \(\ip11\) set of codes for countable ordinals, and if \(w\in \text{\ubf WO}\) then let \(|w|<\omi\) be coded by \(w\). The set \(W'=\ens{\ang{w,x_{\xi k}}} {w\in \text{\ubf WO}\land |w|=\xi\land k<\om}\) is then a non-\(\ROD\)-uniformizable \(\ip12\) set with countable sections in \(\rL[X]\).

Now we work towards the proof of Theorem [mt]. If \(p=\ang{w,x_{\xi k}}\) and \(q=\ang{w',x_{\xi', n}}\) belong to \(W'\) then define \(p \mG q\) iff \(w=w'\), \(\xi=\xi'\), and \(k\ne n\). Thus, in \(\rL[X]\), \(G\) is a locally countable graph of class \(\ip12\) with \(W'=|G|\) as the set of vertices.

To complete the proof of Theorem [mt], it remains to show that, in \(\rL[X]\), \(G\) is not generated by a countable family \(F=\ens{f_n}{n<\om}\) of ROD functions \(f_n:W'\to W'\). Assume to the contrary that \(G\) is generated by such an \(F.\)

, for any \(n\) there is a real \(u_n\in\dn,\) such that \(f_n\) is \(\OD(\ans{u_n})\). Then by [e3] above there also exists a countable set \(A_n\sq \omi\ti\om\) with \(u_n\in\rL[X\res A_n]\). The set \(A=\bigcup_nA_n\) is countable as well, hence there exist pairs \(\ang{\xi,k}\) and \(\ang{\xi,n}\) in \((\omi\ti\om)\bez A\), with the same \(\xi\) and with \(k\ne n\). Pick a code \(w\in\text{\boldsymbol{W}O}\) with \(|w|=\xi\). Then the according elements \(p=\ang{w,x_{\xi k}}\) and \(q=\ang{w,x_{\xi n}}\) in \(W'\) satisfy \(p=f_m(q)\) or \(q=f_m(p)\) for some \(m\) by the contrary assumption above.

Let say \(p=f_m(q)\). Then \(x_{\xi k}\) is \(\OD(\ans{w,x_{\xi n},u_m})\) in \(\rL[X]\) because \(f_m\) is \(\OD(\ans{u_m})\). It follows that \(x_{\xi k}\) is \(\OD(\ans{x_{\xi n},X\res A})\) since \(w\in\rL\). But this contradicts [e7] as \(\ang{\xi,k}\notin A\cup\ans{\ang{\xi,n}}\).

Our Theorem [mt] solves, in the positive, a problem on the existence of locally countable \(\ip12\) graphs non-generated by countable families of definable functions. Two separate results are obtained for \(\fs12\) graphs in § [s12]. Two non-generation results on the \(\is12\) equi-constructibility graph \(\cL\) (Lemma [sax] and Theorem [mts]) are obtained in §§ [saxm],[solm]. We expect that the results obtained and methods developed will find further applications in modern research in descriptive set theory and forcing.

We finish with the following problems that arise from our study.

Is there a locally countable \(\fp11\) graph in the Solovay model \(\gN\) (as in Definition [LN]) not generated by a countable family of \(\ROD\) functions?

A possible plan to solve the problem could be as follows. Using the Novikov-Kondo-Addison uniformization, we can start with a \(\ip11\) set \(U\sq(\dn)^3\), uniform in the sense \((\dn\ti\dn)\ti\dn,\) and such that \({x\mcL y}\eqv \sus p\,U(x,y,p)\). Consider the \(\ip11\) graph \(\cH\) whose domain satisfies \(|\cH|\sq\dn\ti\dn,\) defined so that \(\ang{x,p} \cH \ang{y,q}\) iff \(p=q\) and \(U(x,y,p)\). Clearly \(\cH\) is locally countable in the Solovay model \(\gN\). It remains to show that \(\cH\) is not generated by a countable family of \(\ROD\) functions in \(\gN\).

Does Lemma [sax] remain true for reals \(\ao\) Cohen-generic or Solovay-random (or any other popular type of generic reals)?

Find a simpler proof of Theorem [mts], circumventing Lemma [sax].

The following argument may be suggested. , that the graph \(\cL\) is generated by a family \(F=\ens{f_n}{n<\om}\) of ROD functions \(f_n:\dn\to\dn\) in the Solovay model \(\gN\). According to the general properties of the model, there is a perfect tree \(T_0\sq\bse\) such that all restricted functions \(f_n\res[T_0]\) are continuous. Further, according to the properties of the Cantor discountinuum \(\dn,\) there is a perfect tree \(T\sq T_0\) such that each \(f_n\res[T]\) is either 1–1 or a constant. The case of a constant is rejected by the local countability of the graph \(\cL\) in the Solovay model \(\gN\), and therefore we assume that all \(f_n\res[T]\) are 1–1.

There is a real \(\zo\in\dn,\) such that both \(T\) and a suitable sequence of codes for continuous functions \(f_n\res[T]\) belong to \(\rL[\zo]\). Now, to deduce the contradiction as in the proof of Theorem [mts] above, it would be enough to find an \(\rL[\zo]\)-uncountable set \(X\sq[T]\) of \(\cL\)-adjacent elements, in \(\rL[\zo]\) or in an \(\rL[\zo]\)-uncountability preserving generic extension of the model \(\rL[\zo]\). This seems doable in the case where \(\zo\) preserves \(\rL\)-uncountability, but in the general case it remains an interesting open question.

References

References↩︎