# Coloring closed Noetherian graphs1112000 AMS subject classification 03E35,
05C15, 14P99.

Jindřich Zapletal
University of Florida
Academy of Sciences, Czech Republic

###### Abstract

If $\Gamma$ is a closed Noetherian graph on a $\sigma$-compact Polish space
with no infinite cliques, it is consistent with the choiceless set theory
ZF+DC that $\Gamma$ is countably chromatic and there is no Vitali set.

##  1 Introduction

Chromatic numbers of algebraic and $\sigma$-algebraic graphs on Euclidean
spaces have been studied extensively in both ZFC and choiceless ZF+DC context
[3, 4, 6, 10]. In this paper, I show it consistent for many such graphs
$\Gamma$ that ZF+DC holds, chromatic number of $\Gamma$ is countable, yet
there is no Vitali set. The main feature of the graphs exploited here is
omission of several simple subgraphs.

######  Definition 1.1.

The _half graph_ is the graph on the vertex set $\omega\times 2$, connecting
vertices $\langle n,0\rangle$ and $\langle m,1\rangle$ if $m<n$ and containing
no other edges. A _variation_ of the half graph is a graph obtained from the
half graph by making vertices $\langle n,0\rangle$ for $n\in\omega$ either all
pairwise connected or all pairwise disconnected, and similarly for vertices
$\langle n,1\rangle$ for $n\in\omega$. The _three-quarter graph_ is the graph
on the same vertex set, connecting vertices $\langle n,0\rangle$ and $\langle
m,1\rangle$ if $m\neq n$ and containing no other edges. Variations of the
three-quarter graph are defined in the same way.

Thus, the half graph and the three-quarter graph have four variations each.

######  Definition 1.2.

A graph $\Gamma$ on a set $X$ is _Noetherian_ if it does not contain a
variation of the half graph or the three quarter graph as a vertex-induced
subgraph.

Interesting examples of Noetherian graphs are included in Section 3. The
precise preservation result obtained in this paper concerns Hamming graphs.

######  Definition 1.3.

The _infinite breadth Hamming graph_ $\mathbb{H}_{\omega}$ is the graph on
$\omega^{\omega}$ connecting two points if they differ in exactly one entry.
The _diagonal Hamming graph_ $\mathbb{H}_{<\omega}$ is the restriction of
$\mathbb{H}_{\omega}$ to the diagonal set $\prod_{n}(n+1)$.

It is not difficult to see that the Hamming graphs are Noetherian.

######  Theorem 1.4.

Suppose that $\Gamma$ is a closed Noetherian graph on a $\sigma$-compact
Polish space $X$.

  1. 1.

If $\Gamma$ contains no infinite clique, then it is consistent relative to an
inaccessible cardinal that ZF+DC holds, the chromatic number of $\Gamma$ is
countable while that of $\mathbb{H}_{\omega}$ is not;

  2. 2.

if there is a number $n\in\omega$ such that the graph $\Gamma$ contains no
clique of cardinality $n$, then it is consistent relative to an inaccessible
cardinal that ZF+DC holds, the chromatic number of $\Gamma$ is countable while
that of $\mathbb{H}_{<\omega}$ is not.

The inaccessible cardinal assumption is necessary only to make the proof fit
the set-up of geometric set theory [5] and probably can be dropped. Similarly,
the $\sigma$-compact assumption, satisfied in the important algebraic
examples, is only necessary to evaluate the complexity of the coloring poset
in Proposition 4.4 and probably can be dropped.

In both cases, the conclusion excludes a Vitali set. To see this, let
$\\{\varepsilon_{n,m}\colon n,m\in\omega\\}$ be a collection of pairwise
distinct positive rationals with a finite sum, and let
$h\colon\omega^{\omega}\to\mathbb{R}$ be the function defined by
$h(x)=\Sigma_{n}\varepsilon_{n,x(n)}$. The function $h$ is a homomorphism from
either of the Hamming graphs to the Vitali equivalence relation, and if
$A\subset\mathbb{R}$ were a Vitali set, then the $h$-preimages of $A$ and its
rational shifts would show that the chromatic numbers of the Hamming graphs
are countable.

Theorem 1.4 is stated in a way which covers many special cases. To state a
couple of more specific consequences, for $n\geq 1$ and a set $a$ of positive
real numbers let $\Gamma_{na}$ be the graph on $\mathbb{R}^{n}$ consisting of
pairs of points whose Euclidean distance belongs to $a$.

######  Corollary 1.5.

Let $n\geq 1$ be a number and let $a$ be a countable bounded set of positive
reals with $0$ as the only accumulation point. Then it is consistent relative
to an inaccessible cardinal that ZF+DC holds, the chromatic number of
$\Gamma_{na}$ is countable, yet there is no Vitali set.

This stands in contradistinction with the case in which $a$ is the set of all
positive rationals, where the countable chromatic number of $\Gamma_{na}$
yields a Vitali set by the definitions. To prove the corollary, first use
Example 3.7 to show that the graph $\Gamma_{na}$ is closed and Noetherian.
Theorem 1.4(1) then proves consistency of ZF+DC plus the chromatic number of
$\Gamma_{na}$ is countable while there is no Vitali set.

For the next corollary, let $\langle\varepsilon_{n}\colon n\in\omega\rangle$
be a sequence of positive real numbers such that
$\Sigma_{n}(n+1)\varepsilon_{n}<\infty$. Let $a=\\{m\varepsilon_{n}\colon
n\in\omega,m\in n+1\\}$.

######  Corollary 1.6.

Let $n\geq 1$ and let $\Gamma$ be an arbitrary algebraic graph on a Euclidean
space, without a perfect clique. It is consistent relative to an inaccessible
cardinal that ZF+DC holds, the chromatic number of $\Gamma$ is countable, yet
the chromatic number of $\Gamma_{1a}$ is uncountable.

This shows that it is possible to color algebraic graphs in general without
coloring even quite simple instances of the distance graphs which are
$\sigma$-algebraic. To prove the corollary, first observe that the Hamming
graph $\mathbb{H}_{<\omega}$ can be homomorphically embedded into
$\Gamma_{1a}$ by a function $h\colon\prod_{n}(n+1)\to\mathbb{R}$ defined by
$h(x)=\Sigma_{n}x(n)\cdot\varepsilon_{n}$. Now, use Theorem 3.2 to see that
there is a finite bound on the cardinality of $\Gamma$-cliques. Theorem 1.4(2)
then shows the consistency of ZF+DC plus the chromatic number of $\Gamma$ is
countable while that of $\mathbb{H}_{<\omega}$ is not–which by the existence
of the homomorphism means that the chromatic number of $\Gamma_{1a}$ is
uncountable as well.

The techniques of this paper provide much more detailed information about the
models obtained than what fits into the statements of the main theorems.
However, a number of questions remain open. An affirmative answer to the
following question would be a natural strengthening of the main results of
this paper.

######  Question 1.7.

Let $\Gamma$ be a closed Noetherian graph on a $\sigma$-compact Polish space
without an infinite clique. Is it consistent with ZF+DC that $\Gamma$ is
countably chromatic, yet there is no linear ordering of the set of all Vitali
classes?

To describe the architecture of the paper, in Section 2 I provide basic
insights into closed Noetherian graphs without infinite cliques. In
particular, they carry a canonical Noetherian topology, and they are countably
chromatic in ZFC. Section 3 provides examples associated with Euclidean
spaces, which are the most interesting from historical point of view. Many
quite different examples will doubtless be found in the future. Section 4
analyzes a canonical coloring poset used over the Solovay model to add a
coloring of closed Noetherian graphs without infinite cliques. Section 5
discusses the main technical tool to control the generic extension of the
Solovay model, namely the finite condition coloring poset known from the work
of Todorcevic and others. Finally, Section 6 wraps up the proofs using the
technology of [5, Chapter 11].

The notation of the paper follows the set theoretic standard of [1]. A graph
$\Gamma$ on a Polish space $X$ is closed if the relation $\\{\langle
x,y\rangle\in X^{2}\colon x\mathrel{\Gamma}y$ or $x=y\\}$ is a closed subset
of $X^{2}$. A topology $\mathcal{T}$ on a set $X$ is Noetherian if there are
no infinite sequences of $\mathcal{T}$-closed sets strictly decreasing with
respect to inclusion, or equivalently, the intersection of any collection of
$\mathcal{T}$-closed sets is equal to the intersection of a finite
subcollection. The Vitali equivalence relation on $\mathbb{R}$ connects points
$x,y$ if $x-y$ is a rational number; a Vitali set is a subset of $\mathbb{R}$
which intersects each class of the Vitali equivalence relation in exactly one
point.

##  2 Initial observations

This section contains basic definitions and facts about Noetherian graphs
without infinite cliques. In particular, they carry a canonical Noetherian
topology which will be used repeatedly in the paper. I will use the following
notation regarding graph neighborhoods throughout.

######  Definition 2.1.

Let $\Gamma$ be a graph on a set $X$.

  1. 1.

If $x\in X$ is a vertex, the symbol $\Gamma(x)$ denotes the set $\\{y\in
X\colon y=x\lor y\mathrel{\Gamma}x\\}$;

  2. 2.

for a finite set $a\subset X$, $\Gamma(a)$ is the set $\bigcap_{x\in
a}\Gamma(x)$;

  3. 3.

the _$\Gamma$ -topology_ or the _graph topology_ is the smallest topology on
$X$ in which all sets $\Gamma(x)$ for $x\in X$ are closed.

As is suggested by the terminology, the graph topology of Noetherian graphs is
Noetherian. This feature will be used throughout the paper.

######  Theorem 2.2.

Let $\Gamma$ be a graph on a set $X$. The following are equivalent:

  1. 1.

$\Gamma$ is Noetherian;

  2. 2.

the $\Gamma$-topology is Noetherian.

###### Proof.

Failure of (1) immediately implies the failure of (2). Let
$\pi\colon\omega\times 2\to X$ be an isomorphism of a variation of the half
graph to a subgraph of $X$. Let $a_{n}=\\{\pi(m,0)\colon m\in n\\}$, and
observe that the sets $\Gamma(a_{n})$ all contain all but finitely many points
in the set $\\{\pi(m,1)\colon m\in\omega\\}$ while their intersection contains
none of these points. An identical argument works for an embedding of a
variation of the three-quarter graph.

Now, suppose that (1) holds and work to establish (2).

######  Claim 2.3.

There is no sequence $\langle a_{n}\colon n\in\omega\rangle$ of finite subsets
of $X$ such that the sets $\Gamma(a_{n})$ strictly decrease with $n$.

###### Proof.

Suppose towards a contradiction that there is such a sequence. Without loss
assume that the sets $a_{n}$ increase with $n\in\omega$, and, erasing needless
entries if necessary, assume that there are points $x_{n}$ such that
$a_{n+1}=a_{n}\cup\\{x_{n}\\}$. Note that the points $x_{n}$ for $n\in\omega$
must be pairwise distinct. For each number $n\in\omega$, let
$y_{n}\in\Gamma(a_{n})\setminus\Gamma(x_{n})$ be an arbitrary point; note that
these points also have to be pairwise distinct and in addition $x_{n}\neq
y_{n}$. Repeatedly using the Ramsey theorem, find an infinite set
$b\subset\omega$ such that

  * •

each of the sets $\\{x_{n}\colon n\in b\\}$ and $\\{y_{n}\colon n\in b\\}$ is
either a $\Gamma$-clique or a $\Gamma$-anticlique, and they are disjoint;

  * •

either for every pair $m<n$ of numbers in $b$, $y_{m}\mathrel{\Gamma}x_{n}$
holds, or for every pair $m<n$ of numbers in $b$, $y_{m}\mathrel{\Gamma}x_{n}$
fails.

Now, let $\pi\colon\omega\to b$ be the increasing enumeration. Define the
injection $h\colon\omega\times 2\to X$ by $h(n,0)=y_{\pi(n)}$ and
$h(n,1)=x_{\pi(n)}$. If the “either” case in the second item above prevails,
then $h$ is an isomorphism of a variation of the three-quarter graph to a
subgraph of $\Gamma$. If the “or” case prevails, then $h$ is an isomorphism of
a variation the half graph to a subgraph of $\Gamma$. Both cases are ruled out
by (1). A contradiction. ∎

Now, consider the collection $\mathcal{T}$ of all finite unions of sets
$\Gamma(a)$ as $a$ ranges over all finite subsets of $X$.

######  Claim 2.4.

There are no infinite strictly descending sequences of sets in $\mathcal{T}$.

###### Proof.

This is a standard argument. Towards a contradiction, assume that
$\\{C_{n}\colon n\in\omega\\}$ is a inclusion-decreasing sequence of sets in
$\mathcal{T}$ which does not stabilize. By recursion on $m\in\omega$ build
numbers $n_{m}$ and finite sets $a_{m}\subset X$ such that

  * •

$n_{0}\in n_{1}\in\dots$;

  * •

$\Gamma(a_{m})\subseteq C_{n_{m}}$ and the sequence
$\\{C_{n}\cap\Gamma(a_{m})\colon n\in\omega\\}$ does not stabilize;

  * •

$\Gamma(a_{m+1})$ is a strict subset of $\Gamma(a_{m})$.

The base step is subsumed in the recursion step. For the recursion step,
suppose that $n_{m},a_{m}$ have been constructed. Since the sequence
$\\{C_{n}\cap\Gamma(a_{m})\colon n\in\omega\\}$ does not stabilize, there must
be a number $n_{m+1}>n_{m}$ such that
$C_{n}\cap\Gamma(a_{n})\neq\Gamma(a_{n})$. Since the set $C_{n_{m+1}}$ is a
finite union of sets of the form $\Gamma(a)$, there must be a finite set
$a\subset X$ such that $\Gamma(a)\subseteq C_{n_{m+1}}$ and the sequence
$\\{C_{n}\cap\Gamma(a_{m})\cap\Gamma(a)\colon n\in\omega\\}$ does not
stabilize. Set $a_{m+1}=a_{n}\cup a$ and observe that the recursion step has
been successfully performed.

In the end, the sets $\Gamma(a_{m})$ contradict the conclusion of Claim 2.3.
Thus, $\mathcal{T}$ contains no infinite strictly decreasing sequences of
sets. ∎

Now, observe that $\mathcal{T}$ is closed under finite intersections and
unions by its definition. It is also closed under arbitrary intersections: the
nonexistence of infinite strictly decreasing sequences of sets in
$\mathcal{T}$ implies that an intersection of arbitrary collection of sets in
$\mathcal{T}$ is equal to an intersection of a finite subcollection. Thus,
$\mathcal{T}$ is exactly the collection of closed sets in the
$\Gamma$-topology. The Noetherian property of the topology follows immediately
from Claim 2.4. ∎

The next result quantifies the complexity of the graph topology from
descriptive point of view.

######  Theorem 2.5.

Suppose that $\Gamma$ is a closed Noetherian graph on a $\sigma$-compact
Polish space $X$. Then the $\Gamma$-topology is analytic.

###### Proof.

This is to say [11] that in the usual topology on the space $F(X)$ of all
closed subsets of $X$, the collection of all sets closed in the
$\Gamma$-topology is analytic.

Since the space $X$ is $\sigma$-compact, the intersection and union functions
on $F(X)$ are both Borel, and if $Y$ is a Polish space and $C\subset Y\times
X$ is a closed set, the map $y\mapsto C_{y}$ is a Borel map from $Y$ to $F(X)$
[2, Section 12.C]. It follows that for every $n,k\in\omega$, the map
$\pi_{nk}\colon(X^{n})^{k}\to F(X)$ given by $\pi_{nk}(y)=\bigcup_{i\in
k}\bigcap_{j\in n}\Gamma(y(i)(j))$ is Borel. Theorem 2.2 shows exactly that
the $\Gamma$-topology is the union of the ranges of all functions $\pi_{nk}$,
and therefore analytic in $F(X)$. ∎

Finally, I show that all closed Noetherian graphs without uncountable cliques
are countably chromatic in ZFC.

######  Theorem 2.6.

Let $\Gamma$ be a closed Noetherian graph on a Polish space $X$, without an
uncountable clique. The chromatic number of $\Gamma$ is countable.

The proof uses a definition and a proposition which will be of use later.

######  Definition 2.7.

Let $\Gamma$ be a graph on a set $X$.

  1. 1.

Let $a\subset X$ be a finite set. Then $\heartsuit(a)$ denotes the set
$\\{x\in X\colon\forall y\in a\ x=y$ or $x\mathrel{\Gamma}y$, and $\forall
z\in X\ \forall y\in a(z=y\lor z\mathrel{\Gamma}y)\to(x=z\lor
x\mathrel{\Gamma}z)\\}$;

  2. 2.

a set $A\subset X$ is _$\Gamma$ -good_ if for every finite subset $a\subset
A$, $\heartsuit(a)\subset A$.

It is obvious that $\heartsuit(a)$ is a $\Gamma$-clique and that
$\Gamma$-goodness is a closure property. In particular, an increasing union of
$\Gamma$-good sets is again $\Gamma$-good, and if no uncountable cliques exist
in $\Gamma$ then every infinite subset of $X$ can be enclosed in a
$\Gamma$-good set of the same cardinality.

######  Proposition 2.8.

Let $\Gamma$ be a closed Noetherian graph on a Polish space $X$. Let $A\subset
X$ be a $\Gamma$-good set. For every point $x\in X\setminus A$ there is a
basic open set $O\subset X$ containing $x$ and containing no elements of $A$
which are $\Gamma$-connected with $x$.

###### Proof.

Suppose that $a\subset A$ is a set of points, all connected to a point $x\in
X$ which is an accumulation point of $a$. It will be enough to show that $x\in
A$ holds.

To this end, use Theorem 2.2 to find a finite set $b\subset a$ such that the
set $\Gamma(b)$ is as small as possible. Note that $x\in\Gamma(b)$. Moreover,
$x$ is $\Gamma$-connected to every point $y\in\Gamma(b)$ distinct from $x$. To
see this, use the choice of the set $b$ to observe that the point $y$ is
$\Gamma$-connected to every element of $a$. Since the graph $\Gamma$ is closed
and $x$ is an accumulation point of $a$, $x\mathrel{\Gamma}y$ follows.

It follows that $x\in\heartsuit(b)$, therefore $x\in A$ holds by the goodness
of the set $A$. The proof is complete. ∎

###### Proof of Theorem 2.6.

Call a partial $\Gamma$-coloring $c$ _suitable_ if its range consists of basic
open subsets of $X$ and for each $x\in\mathrm{dom}(c)$, $x\in c(x)$ holds. By
transfinite induction on the cardinality of an infinite $\Gamma$-good set
$A\subset X$ prove that if $d$ is a function with domain $A$ assigning to any
point $x\in A$ its basic open neighborhood $d(x)$, then there is a suitable
coloring $c$ with domain $A$ such that $c(x)\subset d(x)$ holds for every
$x\in A$. This will prove the theorem: in the end, one can apply it to $A=X$.

The statement is clear for countable $A$ as the coloring $c$ can in such a
case be selected as an injection. Now, suppose that $A$ is a $\Gamma$-good set
of uncountable cardinality, such that for all good sets of smaller cardinality
the statement is known. Let $d$ be a function with domain $A$ such that for
each $x\in A$ the value $d(x)$ is an open neighborhood of $A$. Express
$A=\bigcup_{\beta\in\alpha}A_{\beta}$ as an increasing union of $\Gamma$-good
sets of smaller cardinality. For each $\beta\in\alpha$ let $d_{\beta}$ be a
function with domain $A_{\beta}$ such that for every $x\in A_{\beta}$,
$d_{\beta}(x)$ is an open neighborhood of $x$ which is a subset of $d(x)$ and
if $x\notin\bigcup_{\gamma\in\beta}A_{\gamma}$, then $d_{\beta}(x)$ contains
no elements of $\bigcup_{\gamma\in\beta}A_{\gamma}$ which are
$\Gamma$-connected to $x$. This is possible by Proposition 2.8. By the
induction hypothesis, find suitable colorings $c_{\beta}$ with domain
$A_{\beta}$ such that for every point $x\in A_{\beta}$, $c_{\beta}(x)\subset
d_{\beta}(x)$. Now, let $c$ be the function with domain $A$ defined by
$c(x)=c_{\beta}(x)$ where $\beta\in\alpha$ is the smallest ordinal such that
$x\in A_{\beta}$. It is not difficult to see that $c$ is a suitable
$\Gamma$-coloring of the set $A$ verifying the induction step. ∎

##  3 Initial examples

The main theorems of the paper need a supply of examples of Noetherian graphs
to be meaningful. I concentrate on algebraic graphs and certain special type
of $\sigma$-algebraic graphs on Euclidean spaces.

######  Definition 3.1.

Let $X$ be a Euclidean space of dimension $n\geq 1$. A graph $\Gamma$ on $X$
is _algebraic_ if there is a polynomial $\phi(\bar{u},\bar{v})$ of $2n$ free
variables and real parameters such that for distinct points $x,y\in X$,
$x\mathrel{\Gamma}y$ if and only if $\phi(x,y)=0$.

######  Theorem 3.2.

Let $\Gamma$ be an algebraic graph on a Euclidean space $X$. Then $\Gamma$ is
Noetherian, and exactly one of the following occurs:

  1. 1.

$\Gamma$ contains a perfect clique;

  2. 2.

$\Gamma$ is Noetherian, and there is a number $m\in\omega$ such that $\Gamma$
contains no clique of cardinality greater than $m$.

###### Proof.

To prove the Noetherian property of the graph $\Gamma$, work to exclude a
variation of the three quarter graph from it (the half graph is treated in the
same way). Suppose towards a contradiction that $x_{n},y_{n}\colon n\in\omega$
are vertices in $X$ which induce a copy of a variation of the three quarter
graph. Consider the intersection of sets $\Gamma(x_{n})$ for $n\in\omega$.
This is an intersection of an infinite collection of algebraic sets which
contains no points $y_{n}$ for $n\in\omega$ since $x_{n}$ is disconnected with
$y_{n}$. However, the intersection of any finite subcollection contains all
but finitely many points $x_{n}$ for $n\in\omega$. This contradicts the
Hilbert basis theorem.

(1) clearly implies the failure of (2). To show that the failure of (1)
implies a finite bound on the size of $\Gamma$-cliques, I will need a general
claim.

######  Claim 3.3.

There is a number $k$ such that for every finite set $a\subset X$ there is a
set $b\subseteq a$ of cardinality at most $k$ such that $\Gamma(b)=\Gamma(a)$.

###### Proof.

Write $n$ for the dimension of $X$ and $l$ for the degree of the polynomial
defining the graph $\Gamma$. As a quite inefficient estimate,
$k=n(2^{n}l)^{n}$ will work. To see this, by tree recursion build a tree $T$
and functions $f,g$ on $T$ so that

  * •

$f(0)=X$ and for every $t\in T$, $f(t)\subseteq X$ is always an irreducible
algebraic subset of $X$;

  * •

for every node $t\in T$, $g(t)$ is some element of $a$ such that
$\Gamma(g(t))\cap f(t)\neq f(t)$ if it exists, otherwise $g(t)=!$ and $t$ is a
terminal node of $T$;

  * •

for every node $t\in T$, if $g(t)\in a$ then the set $\\{f(s)\colon s$ is an
immediate successor of $t$ in $T\\}$ lists irreducible components of the
algebraic set $\Gamma(g(t))\cap f(t)$ without repetition.

It turns out that the cardinality of the tree $T$ is at most $k$. To see this,
work to estimate the depth of the tree and the rate at which it branches.
Since the function $f$ maps the tree ordering on $T$ to strict inclusion of
irreducible algebraic subsets of $X$, the depth of the tree is at most $n$. By
induction on $|t|$, where $t\in T$, argue that the set $g(t)\subseteq X$ is
defined by a polynomial of degree at most $2^{|t|}l$. To see that, note that
if $p$ is a polynomial defining $g(t)$, then for every immediate successor $s$
of $t$, $g(s)$ is defined by an irreducible factor of $p^{2}+q^{2}(f(t))$
where $q(f(t))$ is the polynomial defining $\Gamma(f(t))$, which is of degree
at most $l$. Lastly, since the immediate successors of the node $t$ are
labeled with irreducible components of $g(t)$ and these are given by
irreducible factors of $p^{2}+q^{2}(f(t))$, the node $t$ can have at most
$2^{|t|+1}l$ many immediate successors. Simple arithmetic then shows that
$|T|\leq k$.

In the end, let $b=\mathrm{rng}(f)$ and observe that the set $b$ works: the
sets $\Gamma(a)$ and $\Gamma(b)$ are both equal to the union of $f(t)$ as $t$
ranges over all terminal nodes of the tree $T$. ∎

Now, suppose that $\Gamma$ has no perfect clique. Let $k\in\omega$ be a number
which works as in the claim. Consider the set $B\subset X^{k}\times X$ defined
by $\langle x,y\rangle\in B$ if $y\in\heartsuit(\mathrm{rng}(x))$. The set $B$
is semi-algebraic, and all of its vertical sections are semi-algebraic
$\Gamma$-cliques. None of them are uncountable by the assumption on $\Gamma$,
and since every semi-algebraic set is either finite or uncountable, all
vertical sections of $B$ are finite. Every semi-algebraic set with finite
vertical sections enjoys a finite bound on the cardinality of vertical
sections [9, Chapter 3, Lemma 1.7]. Let $m\in\omega$ be such a bound for the
cardinality of vertical sections of $B$. I claim there are no $\Gamma$-cliques
of cardinality greater than $m$.

To see this, suppose that $a\subset X$ is a $\Gamma$-clique. Let $b\subset a$
be a set of cardinality at most $k$ such that $\Gamma(b)=\Gamma(a)$. Let $x\in
X^{k}$ enumerate, with possible repetitions, all elements of $b$. Clearly,
$a\subseteq\heartsuit(b)$ holds, therefore $|a|\leq m$ as desired. ∎

######  Example 3.4.

Let $C\subset\mathbb{R}^{2}$ be an irreducible algebraic curve containing the
origin, and not equal to a line through the origin. Let $\Gamma_{C}$ be the
graph on $\mathbb{R}^{2}$ connecting distinct points $x,y$ if $x-y\in C$ or
$y-x\in C$. The graph $\Gamma_{C}$ has no uncountable clique. In fact, there
is a number $n\in\omega$ such that $\Gamma_{C}$ does not contain the bipartite
graph $K_{2,n}$ as a subgraph.

###### Proof.

First argue that $\Gamma_{C}$ does not contain $K_{2,\omega}$. Suppose towards
a contradiction that $x_{0},x_{1}\in\mathbb{R}^{2}$ are distinct points and
$a\subset\mathbb{R}^{2}$ is an infinite set of points all of which are
connected to both $x_{0}$ and $x_{1}$. For definiteness, assume that the set
$b=\\{y\in a\colon y-x_{0}\in C$ and $y-x_{1}\in C\\}$ is infinite. Then the
set $b$ is an infinite subset of $(C+x_{0})\cap(C+x_{1})$. Since the two
algebraic sets in this intersection are irreducible, their intersection is
either finite or equal to both. In conclusion, $C+x_{0}=C+x_{1}$ holds, in
other words $C+(x_{0}-x_{1})=C$. Since $0\in C$, this means that
$n(x_{0}-x_{1})\in C$ for any $n\in\omega$, and $C$ has infinite intersection
with the line through the origin of direction $x_{0}-x_{1}$. An irreducibility
argument again shows that $C$ has to be equal to that line, contradicting the
initial choice of $C$.

Now, consider the algebraic set $B=\\{\langle
z,y\rangle\in(\mathbb{R}^{2})^{2}\times\mathbb{R}^{2}\colon$ the two entries
of $z$ are distinct and $y$ is $\Gamma_{C}$-related to each$\\}$. This is a
semi-algebraic set with finite vertical sections by the previous paragraph. By
[9, Chapter 3, Lemma 1.7], there is a number $n\in\omega$ such that all
vertical sections of the set $B$ have cardinality at most $n$. This completes
the proof. ∎

######  Definition 3.5.

Let $X$ be a Euclidean space of dimension $n\geq 1$. A graph $\Gamma$ on $X$
is _tight $\sigma$-algebraic_ if there are algebraic graphs $\Gamma_{m}$ for
$m\in\omega$ on $X$ such that $\Gamma=\bigcup_{m}\Gamma_{m}$ and the real
numbers $\varepsilon_{m}=\sup\\{d(x,y)\colon x\mathrel{\Gamma}_{m}y\\}$ tend
to zero.

######  Theorem 3.6.

Let $\Gamma$ be a tight $\sigma$-algebraic graph on a Euclidean space $X$.
Then $\Gamma$ is Noetherian and exactly one of the following occurs:

  1. 1.

$\Gamma$ contains a perfect clique;

  2. 2.

$\Gamma$ contains no infinite clique.

###### Proof.

Let $\Gamma=\bigcup_{m}\Gamma_{m}$ be a witness to the tight
$\sigma$-algebraicity of $\Gamma$. To verify the Noetherian property of
$\Gamma$, suppose towards a contradiction that $x_{n},y_{n}\colon n\in\omega$
are vertices in $X$ which induce a copy of a variation of the three quarter
graph (the half graph is treated in the same way). Thinning out if necessary I
may assume that the set $\\{x_{n},y_{n}\colon n\in\omega\\}$ is discrete. It
follows that for each $n\in\omega$ there is a number $m_{n}\in\omega$ such
that the points $x_{n}$ are $\bigcup_{m\in m_{n}}\Gamma_{m}$-connected to
points $y_{k}$ for all $k\neq n$. Consider the intersection of all sets
$\bigcup_{m\in m_{n}}\Gamma_{m}(x_{n})$ for $n\in\omega$. This is an
intersection of an infinite collection of algebraic sets which contains no
points $y_{n}$ for $n\in\omega$. The intersection of any finite subcolection
contains all but finitely many points $y_{n}$ for $n\in\omega$. This
contradicts the Hilbert basis theorem.

Clearly (1) implies the failure of (2). Now, suppose that (2) fails and work
to confirm (1). Let $\\{x_{n}\colon n\in\omega\\}$ is an infinite
$\Gamma$-clique. I will produce a number $m\in\omega$ such that an infinite
subset of this clique forms a $\Gamma_{m}$-clique. Then, an application of
Theorem 3.2 provides a perfect $\Gamma_{m}$-clique, therefore a perfect
$\Gamma$-clique.

Thinning out the clique if necessary, assume that it is discrete. By recursion
on $k\in\omega$ build numbers $n_{k},m_{k}$, and infinite sets
$b_{k}\subset\omega$ such that

  * •

$n_{k+1}>n_{k}$, $b_{k+1}\subset b_{k}$;

  * •

$n_{k}\in b_{k}$;

  * •

$x_{n_{k}}\mathrel{\Gamma}_{m_{k}}x_{n}$ for all $n\in b_{k+1}$.

To start, let $n_{0}=0$ and $b_{0}=\omega$. Since $x_{0}$ is an isolated point
of the clique, the tightness condition on the graph $\Gamma$ implies that
there are only finitely many numbers $m$ such that $x_{0}\Gamma_{m}x$ holds
for some $x\neq x_{0}$ in the clique. It follows that there must be a number
$m_{0}$ such that the set $b_{1}=\\{n\in\omega\colon
x_{0}\mathrel{\Gamma}_{m_{0}}x_{n}\\}$ is infinite. The recursion step is
performed in a similar way.

Now, observe that the set $\\{m_{k}\colon k\in\omega\\}$ must be finite.
Otherwise, consider the intersection $\bigcap_{k}\Gamma_{m_{k}}(x_{n_{k}})$.
This is an intersection of of an infinite collection of algebraic sets. It
contains no elements of the set $\\{x_{n_{k}}\colon k\in\omega\\}$ since all
elements of this set are isolated in it and the numbers $m_{k}\in\omega$ grow
arbitrarily large. Intersection of any finite subcollection always contains
all but finitely many of the set $\\{x_{n_{k}}\colon k\in\omega\\}$. This
contradicts the Hilbert basis theorem.

It is then possible to find a number $m\in\omega$ such that the set
$c=\\{k\in\omega\colon m_{k}=m\\}$ is infinite. The set $\\{x_{n_{k}}\colon
k\in c\\}$ is an infinite $\Gamma_{m}$-clique as desired. ∎

######  Example 3.7.

If $a\subset\mathbb{R}$ is a bounded countable set of positive reals with $0$
as the only accumulation point, the graph $\Gamma$ on a Euclidean space $X$
connecting points whose distance belongs to the set $a$ is tight
$\sigma$-algebraic. It contains no infinite clique.

###### Proof.

Suppose towards a contradiction that $\\{x_{n}\colon n\in\omega\\}$ is an
infinite $\Gamma$-clique. Thinning out if necessary, assume that the clique is
discrete. For every number $n\in\omega$, there must be a finite set
$b_{n}\subset a$ such that the distance of the point $x_{n}$ from any point
$x_{m}$ for $m\neq n$ belongs to the set $b_{n}$. Let $A_{n}\subset X$ be the
algebraic set of all points in $X$ whose distance from $x_{n}$ belongs to the
finite set $b_{n}$. The intersection of all sets $A_{n}$ for $n\in\omega$
contains no elements of the clique since $x_{n}\notin A_{n}$. On the other
hand, intersection of any finite subcollection contains all but finitely many
elements of the clique. This contradicts the Hilbert basis theorem. ∎

##  4 A balanced coloring poset

This section contains a description of a canonical poset adding a coloring to
a closed Noetherian graph without an uncountable clique. The poset is balanced
in the sense of [5, Chapter 5]. Its further preservation properties will be
proved in Section 6.

######  Definition 4.1.

Let $\Gamma$ be a closed Noetherian graph on a $\sigma$-compact Polish space
$X$ without an uncountable clique. The _coloring poset_ $P_{\Gamma}$ consists
of countable partial $\Gamma$-colorings $p$ such that

  1. 1.

$\mathrm{dom}(p)$ is a countable $\Gamma$-good subset of $X$;

  2. 2.

$\mathrm{rng}(p)$ consists of basic open subsets of $X$ and for each
$x\in\mathrm{dom}(p)$, $x\in p(x)$ holds.

The ordering is defined by $q\leq p$ if $p\subseteq q$ and for every point
$x\in\mathrm{dom}(q\setminus p)$, the set $q(x)$ contains no elements of
$\mathrm{dom}(p)$ which are $\Gamma$-connected to $x$.

Verification of the key properties of the poset $P_{\Gamma}$ proceeds by a
series of propositions.

######  Proposition 4.2.

$P_{\Gamma}$ is a $\sigma$-closed transitive relation.

###### Proof.

The transitivity is clear. If $\langle p_{i}\colon i\in\omega\rangle$ is a
descending sequence of conditions in $P_{\Gamma}$, then $\bigcup_{i}p_{i}$ is
their common lower bound. ∎

######  Proposition 4.3.

Suppose that $a\subset P_{\Gamma}$ is a finite set. The following are
equivalent:

  1. 1.

$a$ has a common lower bound in $P$;

  2. 2.

for every point $x\in X$, $a$ has a common lower bound in $P$ which contains
$x$ in its domain;

  3. 3.

$\bigcup a$ is a function and for any two distinct conditions $p_{0},p_{1}\in
a$ and any two $\Gamma$-connected points $x_{0}\in\mathrm{dom}(p_{0}\setminus
p_{1})$ and $x_{1}\in\mathrm{dom}(p_{1}\setminus p_{0})$, the sets
$p_{0}(x_{0})$ and $p_{1}(x_{1})$ do not contain $x_{1}$ and $x_{0}$
respectively.

In particular, a finite subset of $P_{\Gamma}$ has a common lower bound if and
only if it consists of pairwise compatible conditions.

###### Proof.

(2) implies (1) which implies (3) by the definition of the ordering. To show
that (3) implies (1), fix the finite set $a\subset P_{\Gamma}$ and a point
$x\in X$, assume that (3) holds, and work to find a common lower bound of $a$
which contains $x$ in its domain.

Let $b\subset X$ be a $\Gamma$-good countable set containing $\mathrm{dom}(p)$
for every $p\in a$ and the point $x$ as well. I will produce a lower bound $q$
of $a$ such that $b=\mathrm{supp}(q)$. To this end, let
$d=b\setminus\bigcup_{p\in a}\mathrm{dom}(p)$. For every point $y\in d$, use
Proposition 2.8 to find an open neighborhood $O_{y}\subset X$ of $y$ such that
$O_{y}$ contains no point in $\bigcup_{p\in a}\mathrm{dom}(p)$ which is
$\Gamma$-connected to $y$. Then, find an injection $r$ from $d$ to basic open
subsets of $X$ such that for every point $y\in d$, $r(y)\subset O_{y}$ and
$y\in r(y)$ holds. It will be enough to show that $q=r\cup\bigcup_{p\in a}p$
is a common lower bound of the set $a$.

First of all, argue that $q$ is a $\Gamma$-coloring. To see this, suppose that
$x_{0},x_{1}\in\mathrm{dom}(q)$ are distinct $\Gamma$-connected points. There
are several cases.

Case 1. $x_{0},x_{1}\in d$. In this case, $q(x_{0})\neq q(x_{1})$ since
$q\restriction d$ is an injection.

Case 2. Exactly one point among $x_{0},x_{1}$, say $x_{0}$ belongs to $d$. By
the choice of the set $O_{x_{0}}$, $x_{1}\notin q(x_{0})$ holds. At the same
time, $x_{1}\in q(x_{1})$ holds and therefore $q(x_{0})\neq q(x_{1})$ as
desired.

Case 3. Neither $x_{0}$ nor $x_{1}$ belongs to $d$. Pick conditions
$p_{0},p_{1}\in a$ such that $x_{0}\in\mathrm{dom}(p_{0})$ and
$x_{1}\in\mathrm{dom}(p_{1})$ holds. If either $x_{0}\in\mathrm{dom}(p_{1})$
or $x_{1}\in\mathrm{dom}(p_{0})$ holds, then $x_{0},x_{1}$ receive distinct
colors since each $p_{0},p_{1}$ is separately a $\Gamma$ coloring. Otherwise,
it must be the case that $x_{0}\in\mathrm{dom}(p_{0}\setminus p_{1})$ and
$x_{1}\in\mathrm{dom}(p_{1}\setminus p_{0})$ holds, and then $q(x_{0})\neq
q(x_{1})$ holds by (3) and the definition of the ordering $P_{\Gamma}$.

Second, show that for each $p\in a$, $q\leq p$ holds. To this end, let
$y\in\mathrm{dom}(q\setminus p)$ be an arbitrary point; the value $q(y)$ must
not contain any point $z\in\mathrm{dom}(p)$ which is $\Gamma$-connected to
$y$. This is clear if $y$ belongs to the domain of some other condition in $a$
by (3). Otherwise, $y\in d$ holds and then $z\notin O_{y}$ and $z\notin q(y)$
holds by the choice of the set $O_{y}$. The proof is complete. ∎

######  Proposition 4.4.

$P_{\Gamma}$ is a Suslin forcing.

###### Proof.

The complexity calculation starts with an easy initial observation.

######  Claim 4.5.

For every $n\in\omega$ the set $B_{n}\subset X^{n}\times X$ of all pairs
$\langle y,x\rangle$ such that $x\in\heartsuit(\mathrm{rng}(y))$ is Borel.

###### Proof.

To show that the set $B_{n}$ is Borel, for every relatively open set $O\subset
X$ define $C_{O}=\\{y\in X^{n}\colon\exists x\in O\ \forall
z\in\mathrm{rng}(y)\ x\mathrel{\Gamma}z\lor x=z\\}$. Since the set $O\subset
X$ is $K_{\sigma}$, a compactness argument shows that $C_{O}\subset X^{n}$ is
$K_{\sigma}$ as well. Then $\langle y,x\rangle\in B_{n}$ if $\forall
z\in\mathrm{rng}(y)\ x\mathrel{\Gamma}z\lor x=z$ and for every pair
$O_{0},O_{1}$ of disjoint basic open subsets of $X$ such that $O_{0}\times
O_{1}\cap\Gamma=0$, either $x\notin O_{0}$ or $y\notin C_{O_{1}}$. This
presents $B_{n}$ as a Borel set. ∎

Now, since vertical sections of the set $B_{n}$ are $\Gamma$-cliques, they are
countable. By the Lusin–Novikov theorem, each set $B_{n}$ is a union of graphs
of countably many Borel functions. It is clear then that conditions are
exactly those $\Gamma$-colorings $p$ with countable domain such that the
domain is closed under all said Borel functions, and for each
$x\in\mathrm{dom}(p)$, $p(x)\subset X$ is a basic open neighborhood of $x$.
This shows that the set of conditions in $P_{\Gamma}$ is Borel.

The ordering on $P_{\Gamma}$ is obviously a Borel set. Proposition 4.3
provides a Borel characterization of compatibility of conditions in
$P_{\Gamma}$, completing the proof. ∎

######  Proposition 4.6.

$P_{\Gamma}$ forces the union of the generic filter to be a total
$\Gamma$-coloring.

###### Proof.

It is only necessary to show that for every condition $p\in P_{\Gamma}$ and
every $x\in X$ there is a condition $q\leq p$ such that $x\in\mathrm{dom}(q)$.
This follows from Proposition 4.3 applied to the set $a=\\{p\\}$. ∎

It is now time to prove the instrumental amalgamation property of the coloring
poset $P_{\Gamma}$. Recall [11] the following notions.

######  Definition 4.7.

  1. 1.

Let $\mathcal{T}$ be an analytic Noetherian topology on a $K_{\sigma}$ Polish
space $X$. If $M$ is a transitive model of ZFC containing the code for
$\mathcal{T}$ and $A\subset X$ is a set, the symbol $C(M,A)$ denotes the
smallest $\mathcal{T}$-closed set coded in $M$ which contains $A$ as a subset.

  2. 2.

Generic extensions $V[H_{0}],V[H_{1}]$ are _mutually Noetherian_ if for every
analytic Noetherian topology $\mathcal{T}$ on a $K_{\sigma}$ Polish space $X$
coded in the ground model $V$ and for every set $A_{1}\subset X$ in
$V[H_{1}]$, $C(V,A_{1})=C(V[H_{0}],A_{1})$ holds, and vice versa: for every
set $A_{0}\subset X$ in $V[H_{0}]$, $C(V,A_{0})=C(V[H_{1}],A_{0})$ holds.

For example, mutually generic extensions are mutually Noetherian.

######  Definition 4.8.

Let $P$ be a Suslin poset.

  1. 1.

A pair $\langle Q,\tau\rangle$ is _Noetherian balanced_ if $Q\Vdash\tau\in P$
and for every mutually Noetherian pair $V[H_{0}]$ $V[H_{1}]$ of generic
extensions, all filters $G_{0}\subset Q$ in $V[H_{0}]$ and $G_{1}\subset Q$ in
$V[H_{1}]$ generic over $V$, and conditions $p_{0}\leq\tau/G_{0}$ in
$V[H_{0}]$ and $p_{1}\leq\tau/G_{1}$ in $V[H_{1}]$, the conditions
$p_{0},p_{1}\in P$ have a common lower bound.

  2. 2.

The poset $P$ is Noetherian balanced if for every condition $p\in P$ there is
a Noetherian balanced pair $\langle Q,\tau\rangle$ such that
$Q\Vdash\tau\leq\check{p}$.

Thus, Noetherian balance is a strengthening of the usual balance of Suslin
posets [5, Chapter 5]. It is an amalgamation tool which for example rules out
nonprincipal ultrafilters on $\omega$ in $P$-extensions of the choiceless
Solovay model [11]. It is irrelevant for the main theorems of this paper, but
it will be used in future work.

######  Proposition 4.9.

The poset $P_{\Gamma}$ is Noetherian balanced.

###### Proof.

Let $p\in P_{\Gamma}$ be a condition. I will show that there is a total
$\Gamma$-coloring $c$ on $X$ such that $p\subset c$ and for every
$x\in\mathrm{dom}(c\setminus p)$, the value $c(x)$ is a basic open subset of
$X$ which contains no elements of $\mathrm{dom}(p)$ $\Gamma$-connected to $x$.
Then I will show that the pair
$\langle\mathrm{Coll}(\omega,\mathbb{R}),\check{c}\rangle$ is a Noetherian
balanced pair. This will prove the proposition.

To find $c$, first for every point $x\in X\setminus\mathrm{dom}(p)$ find an
open neighborhood $d(x)\subset X$ containing $x$ and no points of
$\mathrm{dom}(p)$ which are $\Gamma$-connected to $x$. This is possible by
Proposition 2.8. By the proof of Theorem 2.6, there is a total
$\Gamma$-coloring $e$ which to each point $x\in X$ assigns a basic open subset
$e(x)\subset d(x)$ containing $x$. Then define $c$ by $c(x)=p(x)$ if
$x\in\mathrm{dom}(p)$ and $c(x)=d(x)$ if $x\notin\mathrm{dom}(p)$; this
coloring $c$ is as required.

It is clear that
$\mathrm{Coll}(\omega,\mathbb{R})\Vdash\check{c}\leq\check{p}$. Suppose now
that $V[H_{0}],V[H_{1}]$ are mutually Noetherian extensions of $V$, each
containing respective condition $p_{0}\leq c$ and $p_{1}\leq c$; I must show
that $p_{0},p_{1}$ are compatible. This means that item (3) of Proposition 4.3
must be verified for $a=\\{p_{0},p_{1}\\}$. Suppose that
$x_{0}\in\mathrm{dom}(p_{0}\setminus c)$ and
$x_{1}\in\mathrm{dom}(p_{1}\setminus c)$ are $\Gamma$-connected points, and
towards a contradiction assume that (e.g.) $x_{1}\in p_{0}(x_{0})$. The set
$A_{1}=\\{y\in X\colon y=x_{0}\lor y\mathrel{\Gamma}x_{0}\\}$ is closed in the
$\Gamma$-topology, coded in $V[H_{0}]$, and contains $x_{1}$. By the
Noetherian assumption, the smallest closed in the $\Gamma$-topology set
$B_{1}$ coded in $V$ containing $x_{1}$ is a subset of $A_{1}$. By Mostowski
absoluteness between $V$ and $V[H_{1}]$, $B_{1}$ contains a ground model point
$y$ in the basic open set $p(x_{0})$. However, this contradicts the assumption
that $p_{0}\leq c$ holds. ∎

######  Corollary 4.10.

Let $\Gamma$ be a closed Noetherian graph on a $\sigma$-compact Polish space
without an uncountable clique. In the $P_{\Gamma}$-extension of the Solovay
model,

  1. 1.

there are no discontinuous homomorphisms between Polish groups;

  2. 2.

there is no nonprincipal ultrafilter on $\omega$;

  3. 3.

the Lebesgue null ideal is closed under well-ordered unions.

###### Proof.

Item (1) follows from the balance and the $3,2$-centeredness of the poset
$P_{\Gamma}$ as proved in [5, Theorem 13.2.1]. (2) follows from (1), since a
nonprincipal ultrafilter $U$ on $\omega$ yields a discontinuous homomorphism
from the Cantor group $2^{\omega}$ to $2$ assigning to any point $x\in
2^{\omega}$ its prevailing value. However, (2) also follows from the
Noetherian balance of the poset $P_{\Gamma}$ by [11]. (3) follows from the
Noetherian balance of $P_{\Gamma}$ again [11]. ∎

Properties of the $P_{\Gamma}$ extension of the Solovay model pertaining to
countable Borel equivalence relations must be checked by the methods of the
following sections.

##  5 The control poset

This section discussed the main technical tool used to control the generic
extension of the Solovay model by the balanced coloring poset $P_{\Gamma}$
obtained in Section 4.

######  Definition 5.1.

Let $\Gamma$ be a closed graph on a Polish space $X$. The _$\Gamma$ -control
poset_ $Q_{\Gamma}$ is the poset of all finite partial $\Gamma$-colorings
$q\colon X\to\omega$ ordered by reverse inclusion.

It is a well-known result of Todorcevic [8, Proposition 1] that the control
poset is c.c.c. if and only if the graph $\Gamma$ does not contain a perfect
clique. I need to precisely quantify the nature of c.c.c. of the control
posets in case that the graph $\Gamma$ is closed, Noetherian, and contains no
infinite cliques. The following common parlance will be useful throughout.

######  Definition 5.2.

Let $\Gamma$ be a closed graph on a Polish space $X$.

  1. 1.

A _location_ is a pair $\langle a,f\rangle$ where $a$ is a finite collection
of pairwise disjoint basic open subsets of $X$ and $f\colon a\to\omega$ is a
function such that for any two distinct open sets $O_{0},O_{1}\in a$, either
$(O_{0}\times O_{1})\cap\Gamma=0$ or $f(O_{0})\neq f(O_{1})$ holds;

  2. 2.

a function $q$ such that $\mathrm{dom}(q)$ is a selector in $a$ and for every
$x\in\mathrm{dom}(q)$ $q(x)=f(O)$ for the unique point $O\in a$ containing $x$
is _at location_ $\langle a,f\rangle$;

  3. 3.

if a location $\langle a,f\rangle$ is given, for any condition $q$ at this
location and any $O\in a$ the symbol $q(O)$ denotes the unique point in the
domain of $q$ which belongs to $O$.

Note that every function as in (2) is a condition in the control poset
$Q_{\Gamma}$. The first theorem evaluates the descriptive complexity of the
control poset.

######  Definition 5.3.

A c.c.c. poset $Q$ is _very Suslin_ if

  1. 1.

$Q$ is Suslin. That is, in an ambient Polish space the set $Q$ is analytic,
and the relations of ordering and incompatibility are analytic as well;

  2. 2.

the set $\\{d\in Q^{\omega}\colon\mathrm{rng}(d)\subset Q$ is a predense
set$\\}$ is analytic.

Very Suslin c.c.c. forcings do not add dominating reals [7], and their
complexity is preserved under finite support iterations of countable length.

######  Theorem 5.4.

If $\Gamma$ is a closed Noetherian graph on a Polish $\sigma$-compact space
$X$ without an infinite clique, then the poset $Q_{\Gamma}$ is very Suslin.

###### Proof.

Suslinness of $Q_{\Gamma}$ follows immediately from the definitions. To start,
use Kuratowski–Ryll-Nardzewski theorem [2, Theorem 12.13] to find Borel
functions $f_{n}\colon F(X)\to X$ for $n\in\omega$ such that for every
nonempty closed set $C\subset X$, the set $\\{f_{n}(C)\colon n\in\omega\\}$ is
a dense subset of $C$. Now, let $d\in\mathbb{Q}_{\Gamma}^{\omega}$ be a
sequence of conditions. Write $b=\bigcup\\{\mathrm{dom}(q)\colon
q\in\mathrm{rng}(d)\\}$ and $c=b\cup\bigcup\\{f_{n}(\Gamma(a))\colon
n\in\omega,a\in[b]^{<\aleph_{0}}\\}$. I claim that $\mathrm{rng}(d)\subset
Q_{\Gamma}$ is predense if and only if every condition whose domain is a
subset of $c$ is compatible with some element of $\mathrm{rng}(d)$.

First, note that this will show that the set $\\{d\in
Q^{\omega}\colon\mathrm{rng}(d)\subset Q$ is a predense set$\\}$ is analytic.
The universal quantifier on the right side of the equivalence is restricted to
a countable subset of $Q_{\Gamma}$ which is obtained in a Borel way from $d$.

Now, the left-to-right implication is immediate. The right-to-left implication
is proved in the contrapositive. Suppose that the set $\mathrm{rng}(d)$ is not
predense and work to find a condition which is incompatible to all elements of
$\mathrm{rng}(d)$, whose domain is a subset of $c$. Let $q\in Q_{\Gamma}$ be
any condition incompatible with all elements of $\mathrm{rng}(d)$. For each
point $x\in\mathrm{dom}(q)\setminus b$, let $b^{\prime}\subset b$ be a finite
set of points $\Gamma$-connected to $x$ and such that the set
$C_{x}=\Gamma(b^{\prime})$ is as small as possible. Such a set is possible to
find by the Noetherian assumption and Theorem 2.2.

Now, let $\langle a,f\rangle$ be any location of the condition $q$. Define a
condition $r$ at the same location using the following description.

  * •

if $O\in a$ is such that $q(O)\in b$ then let $r(O)=q(O)$;

  * •

if $O\in a$ is such that $x=q(O)\notin b$ and there is a point $y\in C_{x}\cap
O\cap b$ which is $\Gamma$-disconnected from $x$, then let $r(O)=y$;

  * •

finally, suppose that $O\in a$ is such that $x=q(O)\notin b$ and all points of
$C_{x}\cap O\cap b$ are $\Gamma$-connected to $x$. In such a case, $C_{x}\cap
O\cap b$ is a $\Gamma$-clique by the minimal choice of $C_{x}$. By the initial
assumptions on the graph $\Gamma$, this clique is finite. Note that $x\in
C_{x}$ holds and $x$ does not belong to the finite set $C_{x}\cap O\cap b$,
simply because $x\notin b$ holds. Since the set $c\cap C_{x}$ is dense in
$C_{x}$, there is a point $y\in c\cap C_{x}\cap O$ which does not contain any
elements of $C_{x}\cap O\cap b$. Let $r(O)=y$.

To complete the proof, argue that $r$ is incompatible with all conditions in
$\mathrm{rng}(d)$. To do that, suppose that $s\in\mathrm{rng}(d)$ is a
condition. Then $s,q$ are incompatible, and there must be points
$x\in\mathrm{dom}(q)$ and $z\in\mathrm{dom}(s)$ such that either $x=z$ and
$q(x)\neq s(z)$, or $x\mathrel{\Gamma}z$ and $q(x)=s(z)$. The discussion now
splits into cases.

If $x\in b$ then $s,r$ are incompatible by virtue of the same points $x,z$
since $q\restriction b\subseteq r\restriction b$ by the first item above. If
$x\notin b$, then let $O\in a$ be the unique open set which contains it, and
let $y=r(O)$. No matter whether the second or third item above occurred, the
minimality of $C_{x}$, the fact that $y\in C_{x}$, and the fact that $z\in b$
guarantee that $z=y$ or $z\mathrel{\Gamma}y$ holds. It will be enough to rule
out the possibility that $z=y$ holds, since then $s,r$ are incompatible by
virtue of the points $y,z$. Now, if the second item above occurred for $O$,
$z=y$ is impossible since $y\mathrel{\Gamma}x$ fails in that case while
$z\mathrel{\Gamma}x$ holds. If the third item above occurred for $O$, then
$y\notin b$ and $y$ must again be distinct from $z$ since $z\in b$ holds. The
proof is complete. ∎

Perhaps more importantly, the Noetherian property of the graph $\Gamma$ has
implications for the centeredness properties of the control poset
$Q_{\Gamma}$. Fine distinctions are important here, and we restate the
definitions of [5, Chapter 11]:

######  Definition 5.5.

Let $Q$ be a poset.

  1. 1.

A set $A\subset Q$ is _liminf-centered_ if for every infinite set $a\subset A$
there is a condition $q\in Q$ which forces the generic filter to contain
infinitely many elements of $a$.

  2. 2.

If $Q$ is a Suslin poset, it is _Suslin- $\sigma$-liminf-centered_ if there
are analytic liminf-centered sets $A_{n}\subset Q$ for $n\in\omega$ such that
$Q=\bigcup_{n}A_{n}$.

Note that a liminf centered set cannot contain an infinite antichain, so
$\sigma$-liminf centeredness implies c.c.c.

######  Theorem 5.6.

Suppose that $\Gamma$ is a closed Noetherian graph on a Polish space $X$,
without an infinite clique. Then the control poset $Q_{\Gamma}$ is
Suslin-$\sigma$-liminf centered.

###### Proof.

Let $\langle a,f\rangle$ be a location. It is enough to show that the set $A$
of all conditions at that location is liminf-centered. To this end, the
following abstract claim will be useful.

######  Claim 5.7.

Let $b\subset X$ be an infinite set. There is an infinite set $c\subset b$
such that each element of $X$ is either $\Gamma$-connected with only finitely
many elements of $c$ or with all elements of $c$.

###### Proof.

First use the Ramsey theorem to shrink the set $b$ if necessary to a
$\Gamma$-anticlique. Use Theorem 2.2 to find an inclusion-minimal set
$C\subset X$ in the $\Gamma$-graph topology such that $c=C\cap b$ is infinite.
I claim that the set $c$ works.

Indeed, suppose that $x\in X$ is a point. If $x\in c$, then $x$ is
$\Gamma$-disconnected from all other elements of $c$ since $c$ is a
$\Gamma$-anticlique. If $x\notin c$ and $x$ is $\Gamma$-connected to
infinitely many elements of $c$, then $C=C\cap\Gamma(x)$ by the minimal choice
of $C$ and therefore $x$ is $\Gamma$-connected to all elements of $c$. The
claim follows. ∎

Now, let $A=\\{q_{n}\colon n\in\omega\\}$ be an infinite collection of
conditions at location $\langle a,f\rangle$. Shrinking the collection if
necessary, it is possible to find a partition $a=a_{0}\cup a_{1}$ such that
for every $O\in a_{0}$ the points $q_{n}(O)$ for $n\in\omega$ are all the
same, while for every set $O\in a_{1}$ the points $q_{n}(O)$ for $n\in\omega$
are pairwise distinct. Using the claim repeatedly, it is possible to further
shrink the set $A$ so that for every $O\in a_{1}$, every point in $X$ is
$\Gamma$-connected to only finitely many points among $\\{q_{n}(O)\colon
n\in\omega\\}$ or to all of them. It will be enough to show that $q_{0}$
forces that the generic filter contains infinitely many conditions in the set
$A$.

To see this, suppose that $r\leq q_{0}$ is a condition; it will be enough to
show that $r$ is compatible with all but finitely many conditions in $A$.
Indeed, suppose that $n\in\omega$ is large enough so that for every point
$x\in\mathrm{dom}(r)$ and every $O\in a_{1}$, $q_{n}(O)\neq x$ and if $x$ is
$\Gamma$-connected to only finitely many elements of $q_{n}(O)$, then it is
not $\Gamma$-connected to $q_{n}(O)$. It will be enough to show that $r$ is
compatible with $q_{n}$. For this, note that $q_{n}\cup r$ is a function by
the choice of the number $n$. To show that $q_{n}\cup r$ is a
$\Gamma$-coloring, suppose that $x\in\mathrm{dom}(r)$ and $O\in a_{1}$ is a
set and write $y=q_{n}(O)$. I must show that $x\mathrel{\Gamma}y$ implies
$r(x)\neq q_{n}(y)$. To see this, note that $x\mathrel{\Gamma}y$ implies that
$x$ is $\Gamma$-connected with all points in the set $\\{q_{i}(O)\colon
i\in\omega\\}$ by the choice of the number $n$. In particular, $x$ is
$\Gamma$-connected to $z=q_{0}(O)$, and since $r\leq q_{0}$ holds, $r(x)\neq
q_{0}(z)$. Now, the conditions $q_{0}$ and $q_{n}$ are at the same location
and therefore $q_{0}(z)=q_{n}(y)$. It follows that the values $r(x)$ and
$q_{n}(y)$ are distinct as required. ∎

######  Definition 5.8.

Let $Q$ be a poset.

  1. 1.

A set $A\subset Q$ is _Ramsey centered_ if for every $m\in\omega$ there is
$n\in\omega$ such that every collection of $n$ many elements of $A$ contains a
subcollection of cardinality $m$ which has a common lower bound.

  2. 2.

If $Q$ is a Suslin poset, it is _Suslin- $\sigma$-Ramsey-centered_ if there
are analytic Ramsey-centered sets $A_{n}\subset Q$ for $n\in\omega$ such that
$Q=\bigcup_{n}A_{n}$.

Note that a Ramsey-centered set cannot contain an infinite antichain, so
$\sigma$-Ramsey centeredness implies c.c.c. again.

######  Theorem 5.9.

Suppose that $m\in\omega$ is a number and $\Gamma$ is a closed graph on a
Polish space $X$, containing no cliques of cardinality $m$. Then the control
poset $Q_{\Gamma}$ is Suslin-$\sigma$-Ramsey centered.

Note that this theorem does not refer to any Noetherian assumption; indeed,
its proof is much easier than that of Theorem 5.6.

###### Proof.

Let $\langle a,f\rangle$ be a location. It is enough to show that the set $A$
of all conditions at that location is Ramsey-centered. To this end, let
$m\in\omega$ be a number; increasing $m$ if necessary assume that $\Gamma$
contains no cliques of cardinality $m$. Writing $s$ for the cardinality of the
set $A$, any natural number $k$ such that $k\to(m)^{2}_{s+1}$ witnesses Ramsey
centeredness of the set $A$ for the number $m$. To see this, let $q_{i}\colon
i\in k\rangle$ be a collection of conditions in $A$. Define a map $c$ with
domain $[k]^{2}$ by setting $c(i,j)=O$ if the conditions $q_{i},q_{j}$ are
incompatible and this fact is witnessed by the open set $O\in a$ in the sense
that the unique elements $x_{i},x_{j}$ in $\mathrm{dom}(q_{i})\cap O$ and
$\mathrm{dom}(q_{j})\cap O$ are $\Gamma$-connected. Define $c(i,j)=!$ if the
conditions $q_{i},q_{j}$ are compatible.

By the choice of the number $k$ there is a set $b\subset k$ of cardinality $m$
homogeneous for the partition $c$. The homogeneous color cannot be a set $O\in
a$, since then the unique points in $\mathrm{dom}(q_{i})\cap O$ for $i\in b$
would form a $\Gamma$-clique of cardinality $m$, contradicting the initial
choice of $m$. Thus, the homogeneous color is $!$ and the set $\\{q_{i}\colon
i\in b\\}$ consists of pairwise compatible conditions. Then $\bigcup_{i\in
b}q_{i}$ is a common lower bound of this set, confirming Ramsey-centeredness
of the set $A$. ∎

##  6 Wrapping up

The theorems in the introduction are now obtained via the technologies of [5,
Chapter 11].

######  Definition 6.1.

Let $P$ be a Suslin poset. Say that $P$ has _liminf control_ if provably in
ZFC, there is a definable map which assigns to each condition $p\in P$ objects
$R,\pi,Q,\tau$ so that

  1. 1.

$R$ is a forcing and $Q,\tau$ are $R$-names;

  2. 2.

$\pi\colon R\to\mathrm{Ord}$ is a function such that preimages of singletons
are liminf-centered;

  3. 3.

$R\Vdash\langle Q,\tau\rangle$ is a balanced pair in $P$ and
$Q\Vdash\tau\leq\check{p}$.

In other words, there may not be a definable balanced pair for $P$, but there
is a definable and suitably centered way of forcing such a pair. The following
is a complementary concept from descriptive set theory.

######  Definition 6.2.

[5, Definition 11.1.5] An analytic graph on a Polish space $X$ has Borel
$\sigma$-finite clique number if there are Borel sets $B_{n}\subset X$ for
$n\in\omega$ such that $\bigcup_{n}B_{n}=X$ and no set $B_{n}$ contains an
infinite clique.

A good example of a Borel graph with uncountable Borel $\sigma$-finite clique
number is the Hamming graph $\mathbb{H}_{\omega}$ of infinite breadth from
Definition 1.3. The following is proved in [5, Theorem 11.7.5].

######  Fact 6.3.

Suppose that $P$ is balanced and has liminf control. Suppose that $\Delta$ is
an analytic graph with uncountable Borel $\sigma$-finite clique number. Let
$\kappa$ be an inaccessible cardinal and $W$ be the derived choiceless Solovay
model. In the $P$-extension of $W$, $\Delta$ has uncountable chromatic number.

######  Proposition 6.4.

Let $\Gamma$ be a closed Noetherian graph on a $\sigma$-compact Polish space
$X$ without infinite cliques. Then the coloring poset $P_{\Gamma}$ has liminf
control.

###### Proof.

Let $p\in P_{\Gamma}$ be a condition. Let $R$ be the finite support iteration
of the control poset $Q_{\Gamma}$ of Definition 5.1 of length $\omega_{1}$.
Since the control poset is Suslin-$\sigma$-liminf-centered by Theorem 5.6, the
iteration $R$ is definable and definably liminf-centered as in Definition 6.1
as proved in [5, Proposition 11.7.3] I will produce a definition of an
$R$-name for a total coloring of $X$ stronger than $p$. This will prove the
proposition, since by the (proof of) Proposition 4.9 such a coloring defines a
balanced pair.

First, note that the iteration $R$ produces a transfinite sequence $\langle
M_{\alpha}\colon\alpha\in\omega_{1}\rangle$ of forcing extensions, where we
put $M_{0}$ to be the ground model. By a c.c.c. argument, the space $X$ in the
$R$-extension is a subset of the union $\bigcup_{\alpha}M_{\alpha}$. The
iteration $R$ also produces a transfinite sequence $\langle
c_{\alpha}\colon\alpha\in\omega_{1}\rangle$ of partial $\Gamma$-colorings.
Namely, each coloring $c_{\alpha}$ is the union of the generic filter on the
$\alpha$-th iterand of $R$, and as such its domain is exactly $X\cap
M_{\alpha}$. The colorings do not cohere in any way. It is necessary to stitch
them together in a definable way to produce a total coloring of the space $X$
in the $R$-extension.

Let $B$ be a basis of the space $X$, and let $B=\bigcup_{n}B_{n}$ be a
partition of $B$ into countably many subbases. Define the coloring $c$ by the
following description. If $x\in\mathrm{dom}(p)$ then $c(x)=p(x)$. If
$x\notin\mathrm{dom}(p)$, then let $\alpha\in\omega_{1}$ be the smallest
ordinal such that $x\in M_{\alpha}$ holds, and let $c(x)$ be the first (in
some fixed enumeration) element of the basis $B_{c_{\alpha}(x)}$ which
contains no points in the set
$\mathrm{dom}(p)\cup\bigcup_{\beta\in\alpha}M_{\beta}$ which are
$\Gamma$-connected to $x$. Such a set exists by Proposition 2.8. It is
important to check the assumptions of that proposition, i.e. the set
$C_{\alpha}=X\cap(\mathrm{dom}(p)\cup\bigcup_{\beta\in\alpha}M_{\beta})$
should be $\Gamma$-good. To see this, if $\alpha=0$ it follows from the fact
that $\mathrm{dom}(p)$ is $\Gamma$-good. If $\alpha$ is a successor of some
ordinal $\beta$, then it follows from a Mostowski absoluteness argument for
the model $M_{\beta}$. Finally, if the ordinal $\alpha$ is limit then
$C_{\alpha}$ is the increasing union of $\Gamma$-good sets $C_{\beta}$ for
$\beta\in\alpha$ and therefore $\Gamma$-good as well.

Now, work to verify that the map $c$ is a $\Gamma$-coloring. To see that,
suppose first that $x\neq y$ are $\Gamma$-connected points in the domain of
$c$, and work to show that they receive different colors. Let
$\alpha_{x},\alpha_{y}$ be the smallest ordinals such that $x\in
M_{\alpha_{x}}$ and $y\in M_{\alpha_{y}}$. If the two ordinals are distinct
(say $\alpha_{y}\in\alpha_{x}$) then the color $c(y)$ is an open set
containing $y$, while the color $c(x)$ is an open set containing no elements
of the model $M_{\alpha_{y}}$ connected to $x$, in particular $y\notin c(x)$
and $c(x)\neq c(y)$. If the two ordinals $\alpha_{x},\alpha_{y}$ are equal to
some $\alpha$ then $c_{\alpha}(x)\neq c_{\alpha}(y)$ and therefore $c(x)\neq
c(y)$. As a special case, if $\alpha=0$ and one of the points (say $y$)
belongs to $\mathrm{dom}(p)$, then either $x\in\mathrm{dom}(p)$ and
$c(x)=p(x)\neq p(y)=c(y)$, or $x\notin\mathrm{dom}(p)$ and then $c(x)$ is an
open set containing no elements of $\mathrm{dom}(p)$ connected to $x$, in
particular $y\notin c(x)$ and $c(x)\neq c(y)$ again.

Finally, it is clear that the collapse of the continuum forces $c\leq p$ by
the definition of the map $c$. The proof of the proposition is complete. ∎

The story is entirely parallel in the case of Ramsey-$\sigma$-centered posets,
except the eventual conclusion is stronger.

######  Definition 6.5.

Let $P$ be a Suslin poset. Say that $P$ has _Ramsey control_ if provably in
ZFC, there is a definable map which assigns to each condition $p\in P$ objects
$R,\pi,Q,\tau$ so that

  1. 1.

$R$ is a forcing and $Q,\tau$ are $R$-names;

  2. 2.

$\pi\colon R\to\mathrm{Ord}$ is a function such that preimages of singletons
are Ramsey-centered;

  3. 3.

$R\Vdash\langle Q,\tau\rangle$ is a balanced pair in $P$ and
$Q\Vdash\tau\leq\check{p}$.

In other words, there may not be a definable balanced pair for $P$, but there
is a definable and suitably centered way of forcing such a pair. The following
is a complementary concept from descriptive set theory.

######  Definition 6.6.

An analytic graph $\Delta$ on a Polish space $X$ has _countable Borel
$\sigma$-bounded chromatic number_ if there are Borel sets $B_{n}\subset X$
for $n\in\omega$ such that $\bigcup_{n}B_{n}=X$ and $\Delta$ restricted to
every finite subset of $B_{n}$ has chromatic number at most $n+2$.

A good example of a Borel graph with uncountable Borel $\sigma$-bounded
chromatic number is the diagonal Hamming graph $\mathbb{H}_{<\omega}$ of
Definition 1.3. The following is proved in [5, Theorem 11.6.5]:

######  Fact 6.7.

Suppose that $P$ has Ramsey control. Let $\Delta$ be an analytic graph on a
Polish space with uncountable Borel $\sigma$-bounded chromatic number. Let
$\kappa$ be an inaccessible cardinal and $W$ be the derived choiceless Solovay
model. In the $P$-extension of $W$, $\Delta$ has uncountable chromatic number.

######  Proposition 6.8.

Let $\Gamma$ be a closed Noetherian graph on a $\sigma$-compact Polish space
$X$. Suppose that there is a number $m$ such that $\Gamma$ contains no cliques
of cardinality $m$. Then the coloring poset $P_{\Gamma}$ has Ramsey control.

The proof is a verbatim repetition of the proof of Proposition 6.4 with
references to Theorem 5.6 and [5, Proposition 11.7.3] replaced with Theorem
5.9 and [5, Proposition 11.6.3]. It should be noted that while the
Suslin-$\sigma$-Ramsey-centeredness of the control poset in this case does not
need the Noetherian assumption, the proof of Proposition 6.8 does need it at
the place where the transfinite sequence of colorings is stitched into a
single one.

Finally, it is possible to state the proofs of the main theorems of the
introduction in their entirety. For Theorem 1.4(1), let $\Gamma$ be a closed
Noetherian graph on a $\sigma$-compact Polish space. Let $\kappa$ be an
inaccessible cardinal, let $W$ be the choiceless Solovay model associated with
$\kappa$, and let $W[G]$ be a generic extension of $W$ obtained by the
coloring poset $P_{\Gamma}$ of Definition 4.1. The poset is balanced and it
has liminf-centered control by Proposition 6.4. By Fact 6.3, in the model
$W[G]$, the chromatic number of the Hamming graph $\mathbb{H}_{\omega}$ of
infinite breadth is uncountable, and Theorem 1.4(1) follows. If there is a
finite bound on the size of $\Gamma$-cliques, then the coloring poset
$P_{\Gamma}$ has Ramsey control by Proposition 6.8. By Fact 6.7, in the model
$W[G]$, the chromatic number of the diagonal Hamming graph
$\mathbb{H}_{<\omega}$ of infinite breadth is uncountable, proving Theorem
1.4(2).

## References

  * [1] Thomas Jech.  Set Theory.  Springer Verlag, New York, 2002.
  * [2] Alexander S. Kechris.  Classical Descriptive Set Theory.  Springer Verlag, New York, 1994.
  * [3] Péter Komjáth.  A decomposition theorem for $\mathbb{R}^{n}$.  Proc. Amer. Math. Soc., 120:921–927, 1994.
  * [4] Péter Komjáth.  The list-chromatic number of infinite graphs defined on Euclidean spaces.  Discrete Comput. Geom., 45:497–502, 2011.
  * [5] Paul Larson and Jindřich Zapletal.  Geometric set theory.  AMS Surveys and Monographs. American Mathematical Society, Providence, 2020.
  * [6] James H. Schmerl.  Avoidable algebraic subsets of Euclidean space.  Trans. Amer. Math. Soc., 352:2479–2489, 1999.
  * [7] Saharon Shelah.  On nicely definable forcing notions.  Journal of Applied Analysis, 11, No.1:1–17, 2005.  arxiv:math.LO/0303293.
  * [8] Stevo Todorcevic.  Two examples of Borel partially ordered sets with the countable chain condition.  Proceedings of the American Mathematical Society, 112:1125–1128, 1991.
  * [9] Lou van den Dries.  Tame topology and o-minimal structures.  Cambridge University Press, New York, 1998.  London Mathematical Society Lecture Note Series 248.
  * [10] Jindrich Zapletal.  Coloring the distance graphs.  2021\.  arXiv:2201.00275.
  * [11] Jindrich Zapletal.  Noetherian spaces in choiceless set theory.  2021\.  arXiv:2101.03434.


A Study of Using Multimodal LLMs for Non-Crash Functional Bug Detection in Android Apps

Bangyan Ju1,
Jin Yang1,
Tingting Yu2,
Tamerlan Abdullayev1,
Yuanyuan Wu1,
Dingbang Wang2,
Yu Zhao1
1University of Cincinnati, USA;

2University of Connecticut, USA;

<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
Numerous approaches employing various strategies have been developed to test the graphical user interfaces (GUIs) of mobile apps. However, traditional GUI testing techniques, such as random and model-based testing, primarily focus on generating test sequences that excel in achieving high code coverage but often fail to act as effective test oracles for non-crash functional (NCF) bug detection. To tackle these limitations, this study empirically investigates the capability of leveraging large language models (LLMs) to be test oracles to detect NCF bugs in Android apps. Our intuition is that the training corpora of LLMs, encompassing extensive mobile app usage and bug report descriptions, enable them with the domain knowledge relevant to NCF bug detection. We conducted a comprehensive empirical study to explore the effectiveness of LLMs as test oracles for detecting NCF bugs in Android apps on 71 well-documented NCF bugs. The results demonstrated that LLMs achieve a 49% bug detection rate, outperforming existing tools for detecting NCF bugs in Android apps. Additionally, by leveraging LLMs to be test oracles, we successfully detected 24 previously unknown NCF bugs in 64 Android apps, with four of these bugs being confirmed or fixed. However, we also identified limitations of LLMs, primarily related to performance degradation, inherent randomness, and false positives. Our study highlights the potential of leveraging LLMs as test oracles for Android NCF bug detection and suggests directions for future research.

Mobile Testing, Large Language Model, Testing Oracle, Non-Crash Functional Bug

[1]
“Google Play Data,” <https://www.statista.com/statistics/266210/number-of-available-applications-in-the-google-play-store>, 2020.

[2]
“APPLAUSE,” <https://www.applause.com/blog/app-abandonment-bug-testing>, 2020.

[3]
“Ui/application exerciser monkey,” <https://developer.android.com/studio/test/monkey.html>, 2022.

[4]
A. Machiry, R. Tahiliani, and M. Naik, “Dynodroid: An input generation system for android apps,” in Proc. of the Joint Meeting on Foundations of Software Engineering, 2013, pp. 224–234.

[5]
D. Amalfitano, A. R. Fasolino, P. Tramontana, S. De Carmine, and A. M. Memon, “Using gui ripping for automated testing of android applications,” in Proc. of the International Conference on Automated Software Engineering, 2012, pp. 258–261.

[6]
D. Amalfitano, A. R. Fasolino, P. Tramontana, B. D. Ta, and A. M. Memon, “Mobiguitar: Automated model-based testing of mobile apps,” IEEE software, vol. 32, no. 5, pp. 53–59, 2015.

[7]
T. Azim and I. Neamtiu, “Targeted and depth-first exploration for systematic testing of android apps,” in Acm Sigplan Notices, 2013, pp. 641–660.

[8]
Y. Koroglu, A. Sen, O. Muslu, Y. Mete, C. Ulker, T. Tanriverdi, and Y. Donmez, “QBE: Qlearning-based exploration of android applications,” in Proc. of the International Conference on Software Testing, Verification and Validation (ICST), 2018, pp. 105–115.

[9]
M. Pan, A. Huang, G. Wang, T. Zhang, and X. Li, “Reinforcement learning based curiosity-driven testing of android applications,” in Proc. of the International Symposium on Software Testing and Analysis, 2020, pp. 153–164.

[10]
Y. Li, Z. Yang, Y. Guo, and X. Chen, “Humanoid: a deep learning-based approach to automated black-box android app testing,” in Proc. of the International Conference on Automated Software Engineering (ASE), 2019, pp. 1070–1073.

[11]
C. Degott, N. P. Borges Jr, and A. Zeller, “Learning user interface element interactions,” in Proc. of the International Symposium on Software Testing and Analysis, 2019, pp. 296–306.

[12]
Y.-D. Lin, J. F. Rojas, E. T.-H. Chu, and Y.-C. Lai, “On the accuracy, efficiency, and reusability of automated test oracles for android devices,” IEEE Transactions on Software Engineering, vol. 40, no. 10, pp. 957–970, 2014.

[13]
M. Linares-Vásquez, K. Moran, and D. Poshyvanyk, “Continuous, evolutionary and large-scale: A new perspective for automated mobile app testing,” in Proc. of 2017 IEEE International Conference on Software Maintenance and Evolution (ICSME).1em plus 0.5em minus 0.4emIEEE, 2017, pp. 399–410.

[14]
M. Fazzini and A. Orso, “Automated cross-platform inconsistency detection for mobile apps,” in Proc. of 2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE).1em plus 0.5em minus 0.4emIEEE, 2017, pp. 308–318.

[15]
W. Guo, Z. Dong, L. Shen, W. Tian, T. Su, and X. Peng, “ifixdataloss: a tool for detecting and fixing data loss issues in android apps,” in Proc. of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis, 2022, pp. 785–788.

[16]
J. Sun, “Setdroid: detecting user-configurable setting issues of android apps via metamorphic fuzzing,” in Proc. of the 43rd International Conference on Software Engineering: Companion Proceedings.1em plus 0.5em minus 0.4emIEEE, 2021, pp. 108–110.

[17]
T. Petsios, A. Tang, S. Stolfo, A. D. Keromytis, and S. Jana, “Nezha: Efficient domain-independent differential testing,” in Proc. of the 2017 IEEE Symposium on security and privacy (SP).1em plus 0.5em minus 0.4emIEEE, 2017, pp. 615–632.

[18]
Y. Xiong, M. Xu, T. Su, J. Sun, J. Wang, H. Wen, G. Pu, J. He, and Z. Su, “An empirical study of functional bugs in android apps,” in Proc. of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis, 2023, pp. 1319–1331.

[19]
“Github,” <https://github.com>, 2012.

[20]
T. Su, Y. Yan, J. Wang, J. Sun, Y. Xiong, G. Pu, K. Wang, and Z. Su, “Fully automated functional fuzzing of android apps for detecting non-crashing logic bugs,” Proceedings of the ACM on Programming Languages, vol. 5, no. OOPSLA, pp. 1–31, 2021.

[21]
J. Wang, Y. Jiang, T. Su, S. Li, C. Xu, J. Lu, and Z. Su, “Detecting non-crashing functional bugs in android apps via deep-state differential analysis,” in Proc. of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, 2022, pp. 434–446.

[22]
C. Escobar-Velásquez, M. Osorio-Riaño, J. Dominguez-Osorio, M. Arevalo, and M. Linares-Vásquez, “An empirical study of i18n collateral changes and bugs in guis of android apps,” in Proc. of 2020 IEEE international conference on software maintenance and evolution (ICSME).1em plus 0.5em minus 0.4emIEEE, 2020, pp. 581–592.

[23]
Z. Liu, C. Chen, J. Wang, Y. Huang, J. Hu, and Q. Wang, “Owl eyes: Spotting ui display issues via visual understanding,” in 35th IEEE/ACM International Conference on Automated Software Engineering (ASE), 2020, pp. 398–409.

[24]
A. Chowdhery, S. Narang, J. Devlin, M. Bosma, G. Mishra, A. Roberts, P. Barham, H. W. Chung, C. Sutton, S. Gehrmann et al., “Palm: Scaling language modeling with pathways,” Journal of Machine Learning Research, vol. 24, no. 240, pp. 1–113, 2023.

[25]
S. Ozdemir, Quick Start Guide to Large Language Models: Strategies and Best Practices for Using ChatGPT and Other LLMs.1em plus 0.5em minus 0.4emAddison-Wesley Professional, 2023.

[26]
“Gpt-4o,” <https://openai.com/index/hello-gpt-4o/>, 2024.

[27]
P. Liu, W. Yuan, J. Fu, Z. Jiang, H. Hayashi, and G. Neubig, “Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing,” ACM Computing Surveys, vol. 55, no. 9, pp. 1–35, 2023.

[28]
“Ollm,” https://github.com/randomNameless/OLLM, 2024.

[29]
“Amaze-2113,” <https://github.com/TeamAmaze/AmazeFileManager/issues/2113>, 2024.

[30]
J. Sun, T. Su, J. Li, Z. Dong, G. Pu, T. Xie, and Z. Su, “Understanding and finding system setting-related defects in android apps,” in Proc. of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis, 2021, pp. 204–215.

[31]
X. Zhou, T. Zhang, and D. Lo, “Large language model for vulnerability detection: Emerging results and future directions,” in Proceedings of the 2024 ACM/IEEE 44th International Conference on Software Engineering: New Ideas and Emerging Results, 2024, pp. 47–51.

[32]
D. Wang, Y. Zhao, S. Feng, Z. Zhang, W. G. Halfond, C. Chen, X. Sun, J. Shi, and T. Yu, “Feedback-driven automated whole bug report reproduction for android apps,” arXiv preprint arXiv:2407.05165, 2024.

[33]
Z. Liu, C. Chen, J. Wang, M. Chen, B. Wu, X. Che, D. Wang, and Q. Wang, “Make llm a testing expert: Bringing human-like interaction to mobile gui testing via functionality-aware decisions,” in Proceedings of the IEEE/ACM 46th International Conference on Software Engineering, 2024, pp. 1–13.

[34]
“Uiautomator,” <https://developer.android.com/training/testing/other-components/ui-automator>, 2024.

[35]
T. Khot, H. Trivedi, M. Finlayson, Y. Fu, K. Richardson, P. Clark, and A. Sabharwal, “Decomposed prompting: A modular approach for solving complex tasks,” International Conference on Learning Representations, 2023.

[36]
“Mirrored,” <https://github.com/homac/Mirrored/>, 2024.

[37]
“Ankidroid-7232,” <https://github.com/ankidroid/Anki-Android/issues/7232>, 2024.

[38]
S. Deng, W. Xu, H. Sun, W. Liu, T. Tan, J. Liu, A. Li, J. Luan, B. Wang, R. Yan et al., “Mobile-bench: An evaluation benchmark for llm-based mobile agents,” arXiv preprint arXiv:2407.00993, 2024.

[39]
“Wordpress-15026,” <https://github.com/wordpress-mobile/WordPress-Android/issues/15026>, 2024.

[40]
K. Mao, M. Harman, and Y. Jia, “Sapienz: Multi-objective automated testing for android applications,” in Proc. of the International Symposium on Software Testing and Analysis, 2016, pp. 94–105.

[41]
T. Su, G. Meng, Y. Chen, K. Wu, W. Yang, Y. Yao, G. Pu, Y. Liu, and Z. Su, “Guided, stochastic model-based gui testing of android apps,” in Proc. of the Joint Meeting on Foundations of Software Engineering, 2017, pp. 245–256.

[42]
S. R. Choudhary, A. Gorla, and A. Orso, “Automated test input generation for android: Are we there yet? (e),” in Proc. of the 30th IEEE/ACM International Conference on Automated Software Engineering (ASE), 2015, pp. 429–440.

[43]
“Gpt-4,” https://openai.com/index/gpt-4/, 2024.

[44]
“Gemini,” <https://gemini.google.com/>, 2024.

[45]
“ChatGLM-4,” <https://chatglm.cn/>, 2024.

[46]
T. A. T. Vuong and S. Takada, “A reinforcement learning based approach to automated testing of android applications,” in Proc. of the International Workshop on Automating TEST Case Design, Selection, and Evaluation, 2018, pp. 31–37.

[47]
Y. Zhao, B. Harrison, and T. Yu, “Dinodroid: Testing android apps using deep q-networks,” ACM Transactions on Software Engineering and Methodology, 2022.

[48]
C. Callison-Burch, M. Osborne, and P. Koehn, “Re-evaluating the role of bleu in machine translation research,” in 11th conference of the european chapter of the association for computational linguistics, 2006, pp. 249–256.

[49]
T. Gu, C. Sun, X. Ma, C. Cao, C. Xu, Y. Yao, Q. Zhang, J. Lu, and Z. Su, “Practical gui testing of android applications via model abstraction and refinement,” in Proc. of the 41st IEEE/ACM International Conference on Software Engineering (ICSE).1em plus 0.5em minus 0.4emIEEE, 2019, pp. 269–280.

[50]
Y.-M. Baek and D.-H. Bae, “Automated model-based android gui testing using multi-level gui comparison criteria,” in Proc. of the 31st IEEE/ACM International Conference on Automated Software Engineering (ASE), 2016, pp. 238–249.

[51]
T. Gu, C. Cao, T. Liu, C. Sun, J. Deng, X. Ma, and J. Lü, “Aimdroid: Activity-insulated multi-level automated testing for android applications,” in Proc. of the International Conference on Software Maintenance and Evolution (ICSME), 2017, pp. 103–114.

[52]
J. Yan, L. Pan, Y. Li, J. Yan, and J. Zhang, “Land: a user-friendly and customizable test generation tool for android apps,” in Proc. of the International Symposium on Software Testing and Analysis, 2018, pp. 360–363.

[53]
J. Yan, T. Wu, J. Yan, and J. Zhang, “Widget-sensitive and back-stack-aware gui exploration for testing android apps,” in Proc. of the International Conference on Software Quality, Reliability and Security (QRS), 2017, pp. 42–53.

[54]
W. Yang, M. R. Prasad, and T. Xie, “A grey-box approach for automated gui-model generation of mobile applications,” in Proc. of the 16th International Conference on Fundamental Approaches to Software Engineering, 2013, pp. 250–265.

[55]
N. P. Borges, M. Gómez, and A. Zeller, “Guiding app testing with mined interaction models,” in Proc. of the International Conference on Mobile Software Engineering and Systems (MOBILESoft).1em plus 0.5em minus 0.4emIEEE, 2018, pp. 133–143.

[56]
J.-W. Lin, R. Jabbarvand, and S. Malek, “Test transfer across mobile apps through semantic mapping,” in Proc. of the International Conference on Automated Software Engineering (ASE), 2019, pp. 42–53.

[57]
G. Hu, L. Zhu, and J. Yang, “Appflow: using machine learning to synthesize robust, reusable ui tests,” in Proc. of the 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, 2018, pp. 269–282.

[58]
F. Behrang and A. Orso, “Test migration between mobile apps with similar functionality,” in Proc. of the 34th IEEE/ACM International Conference on Automated Software Engineering (ASE).1em plus 0.5em minus 0.4emIEEE, 2019, pp. 54–65.

[59]
L. Mariani, M. Pezzè, and D. Zuddas, “Augusto: Exploiting popular functionalities for the generation of semantic gui tests with oracles,” in Proc. of the 40th International Conference on Software Engineering, 2018, pp. 280–290.

[60]
Y. Koroglu and A. Sen, “Functional test generation from ui test scenarios using reinforcement learning for android applications,” Software Testing, Verification and Reliability, vol. 31, no. 3, p. e1752, 2021.

[61]
Z. Shan, T. Azim, and I. Neamtiu, “Finding resume and restart errors in android applications,” ACM SIGPLAN Notices, vol. 51, no. 10, pp. 864–880, 2016.

[62]
U. Farooq, Z. Zhao, M. Sridharan, and I. Neamtiu, “Livedroid: Identifying and preserving mobile app state in volatile runtime environments,” Proceedings of the ACM on Programming Languages, vol. 4, no. OOPSLA, pp. 1–30, 2020.

[63]
S. Feng and C. Chen, “Prompting is all you need: Automated android bug replay with large language models,” in Proc. of the 46th IEEE/ACM International Conference on Software Engineering, 2024, pp. 1–13.

[64]
S. Zhang, Z. Chen, Y. Shen, M. Ding, J. B. Tenenbaum, and C. Gan, “Planning with large language models for code generation,” arXiv preprint arXiv:2303.05510, 2023.