Testable and Untestable Classes of First-Order FormulaeCharles Jordana,1,∗, Thomas Zeugmanna,2a Division of Computer Science, Hokkaido University, N-14, W-9, Sapporo 060-0814, Japan

Abstract
In property testing, the goal is to distinguish structures that have some desired property
from those that are far from having the property, based on only a small, random sampleof the structure. We focus on the classification of first-order sentences according to theirtestability. This classification was initiated by Alon et al. [2], who showed that graphproperties expressible with prefix ∃∗ ∀∗ are testable but that there is an untestable graphproperty expressible with quantifier prefix ∀∗ ∃∗ . The main results of the present paper
are as follows. We prove that all (relational) properties expressible with quantifier prefix∃∗ ∀∃∗ (Ackermann’s class with equality) are testable and also extend the positive resultof Alon et al. [2] to relational structures using a recent result by Austin and Tao [8].
Finally, we simplify the untestable property of Alon et al. [2] and show that prefixes ∀3 ∃,∀2 ∃∀, ∀∃∀2 and ∀∃∀∃ can express untestable graph properties when equality is allowed.
Keywords: Property testing, logic, randomized algorithms, Ackermann’s class,Ramsey’s class

1. Introduction
In property testing, we take a small random sample of a large structure and wish
to determine if the structure has some desired property or if it is far from having thedesired property. The hope is that we can gain efficiency in return for not deciding the
problem exactly. We focus on the classification problem for testability, where the goal is
to determine exactly which prefix-vocabulary fragments of first-order logic are testable
and which are not. This problem was first considered by Alon et al. [2], who focused on
quantifier alternations (as opposed to quantifiers) and undirected, loop-free graphs.
More concretely, we would like to know the minimum number of universal quantifiers,
as well as of existential quantifiers, required to express an untestable property. In addition, we would like to know the minimum total number of quantifiers needed to express
an untestable property, as it is not prima facie necessary that one can achieve these two∗ Corresponding author

Email addresses: skip@ist.hokudai.ac.jp (Charles Jordan), thomas@ist.hokudai.ac.jp (Thomas
Zeugmann)
1 Supported by a Grant-in-Aid for JSPS Fellows under Grant No. 2100195209.
2 Supported by MEXT Grant-in-Aid for Scientific Research on Priority Areas under Grant No.
21013001.
Preprint submitted to Elsevier

March 21, 2012

minima simultaneously. Previous work by Alon et al. [2] implies upper bounds of twelve
universal, five existential and seventeen total quantifiers, and it is natural to ask if thesebounds can be improved. The following is an informal summary of our results addressing
this question.
The minimum numbers of quantifiers sufficient to express an untestable property ina first-order relational language are
1. Two universal quantifiers;
2. One existential quantifier;3. Three3 quantifiers in total.
In addition, the first two minima can be achieved in the vocabulary of directed graphs(i.e., one binary relation).
If we consider the pattern of quantifiers instead of focusing exclusively on counting
them, our results show that one can express an untestable (graph) property with prefixes∀3 ∃, ∀2 ∃∀, ∀∃∀2 , and ∀∃∀∃. It is trivial to show the testability of formulae with only
existential quantifiers, but it is natural to consider the remaining prefixes of length four.
In Subsection 4.1, we show that all formulae containing at most one universal quantifier are testable, even without a restriction to graph properties or four quantifiers. This
class is well-known as Ackermann’s class with equality, and covers four of the remaining
prefixes of length four. In Subsection 4.2, we extend the result of Alon et al. [2] fromgraphs to relational structures and show that all formulae of the form ∃∗ ∀∗ are testable.
This covers three additional prefixes of length four.
We have recently shown that one can express untestable graph properties with prefix∀∃∀ (improving on prefixes ∀2 ∃∀, ∀∃∀2 , and ∀∃∀∃ from this paper), see Jordan and
Zeugmann [27]. This prefix was first studied by Kahr, Moore and Wang [28].
The testability of the remaining prefixes, i.e., ∃∀2 ∃ and ∀2 ∃2 , remains open. These
prefixes are variations of the Gödel class (prefixes containing at least ∀2 ∃).
The paper is structured as follows. In Subsection 1.1, we outline the history of testing,focusing on results that influence our approach. We state the main results of this paperin Subsection 1.3. Definitions and notation are in Section 2. In Section 3, we proveseveral basic results that are needed in later sections. The main results are in Section 4(testable classes) and Section 5 (untestable classes).
1.1. History of Testing
We begin with a brief history and overview of property testing. There is a recent
introduction to graph property testing by Goldreich [21], and two recent surveys byRon, one focusing on connections with learning theory [43] and one focusing on thealgorithmic techniques [44] used in testability. There are also earlier surveys, including
those by Fischer [15] and Ron [42].
Property testing is a form of approximation where we trade accuracy for efficiency.
Probabilistic machines seem to have been first formalized by de Leeuw et al. [32], whoshowed that such machines cannot compute uncomputable properties under reasonableassumptions. However, they mention the possibility that probabilistic machines could
3 In the present paper, we only prove that the minimum is either three or four. During the reviewing
process, we found an untestable property with prefix ∀∃∀, see Jordan and Zeugmann [27].

2be more efficient than deterministic machines, a topic which was then investigated by
Gill [19]. An early example of such a result is Freivalds’ [18] matrix multiplication checker.
The study of property testing itself began in program verification (see Blum et al. [10]as well as Rubinfeld and Sudan [45]). Goldreich et al. [22] first considered the testabilityof graph properties and showed the existence of testable NP-complete properties. An
approach using incidence lists to represent bounded-degree graphs was introduced byGoldreich and Ron [20]. Parnas and Ron [37] generalized this approach and attempted
to move away from the functional representation of structures. There has been a great
deal of recent work on graph property testing, see the survey by Alon and Shapira [5].
For other types of structures, Alon et al. [4] showed that the regular languages aretestable and that there exist untestable context-free languages. Chockler and Kupferman [13] extended the positive result to the ω-regular languages.
There is also recent work on testing properties of (usually uniform) hypergraphs.
Fischer et al. [17] defined a general model that is roughly equivalent to one of our models,
namely Tr based on Definition 10 below, and showed that hypergraph partition problems
are testable in this framework. Very recently, Austin and Tao [8] have shown that all
hereditary properties4 of colored, directed hypergraphs are testable in a model that isroughly equivalent to another of our models, Tmr based on Definition 13 below.
Szemerédi’s regularity lemma (see, e.g., the survey by Rödl and Schacht [41]) has
been extremely influential in (dense) graph property testing and there has been a great
deal of work on recent extensions (see, e.g., [23, 40, 49]) of this lemma to hypergraphs.
However, as Alon et al. [2] noted, proofs of testability that avoid the regularity lemma
often result in better query complexity. We therefore prove testability directly when weknow how to.
Alon et al. [2] began a logical characterization of the testable (graph) properties, see
Subsection 1.2. Alon and Shapira [6] gave a characterization of a natural subclass of thegraph properties testable with one-sided error, which Rödl and Schacht [39] generalized
to hypergraphs. Alon et al. [3] showed a combinatorial characterization of the graphproperties testable with a constant number of queries. It would be particularly interesting
to consider extensions of this last result to hypergraphs or relational structures.
1.2. Previous Work on the Classification
We briefly outline prior work on the classification for testability before stating ourmain results. We begin with monadic first-order logic. Löwenheim [34] proved thatsatisfiability is decidable5 for monadic first-order logic, and McNaughton and Papert [35]showed that it (with ordering and some arithmetic) characterizes the star-free regular
languages. The testability of this class is then implied by a result of Alon et al. [4].
Using instead Büchi’s [12] result that monadic second-order logic characterizes the regular
languages, we get a parallel with Skolem’s [47] extension of Löwenheim’s result to secondorder logic. Of course, we are focused on the testability of classes of first-order formulae.
Below, we use the classification notation that will be introduced formally in Definition 8. Informally, we represent classes with a triple [Π, p]e , where Π denotes the pattern
4 A hereditary property is one that is closed under taking induced substructures.
5 A class is said to be decidable (for satisfiability) if, given an arbitrary formula from the class, one

can decide if there exists a (possibly infinite) model satisfying the formula.

3

of quantifiers allowed, the infinite sequence p denotes the maximum number of permitted
predicate symbols for each arity (we omit trailing zeros and all means that any numberof predicate symbols with any arities are permitted), and e denotes whether = is allowed.
Skolem [48] also showed that [∀∗ ∃∗ , all ] is a reduction class6 . An untestable graphproperty (essentially an encoding of graph isomorphism) was found by Alon et al. [2].
This property is expressible in [∀∗ ∃∗ , (0, 1)]= , and an examination of the proof reveals
that a prefix of ∀12 ∃5 suffices.
The class [∃∗ ∀∗ , all ]= was first studied in a seminal paper by Ramsey [38], who showedthat it is decidable as part of a stronger result characterizing its spectrum. Alon et al. [2]showed that the restriction of Ramsey’s class to undirected loop-free graphs (a restrictionof [∃∗ ∀∗ , (0, 1)]= ) is testable.
In Jordan and Zeugmann [27], we improved on some of the prefixes of this paper andshowed that [∀∃∀, (0, 1)]= is untestable.
1.3. Statement of Results
Our main results are as follows. First, we develop a framework for relational property testing including variations corresponding to the different models considered in theliterature for non-uniform hypergraph7 testing. We use this framework to prove thefollowing.
1. All (relational) properties expressible by formulae in Ackermann’s class with equality ([∃∗ ∀∃∗ , all ]= ) are testable in all of our models.
2. All (relational) properties expressible in Ramsey’s class ([∃∗ ∀∗ , all ]= ) are testablein all of our models. This extends the result by Alon et al. [2] to the full class.
3. There exist graph properties expressible in the classes [∀3 ∃, (0, 1)]= , [∀2 ∃∀, (0, 1)]= ,[∀∃∀2 , (0, 1)]= and [∀∃∀∃, (0, 1)]= which are untestable in all of our models. This
sharpens the untestable class of Alon et al. [2].
The latter two results improve the results of Alon et al. [2], and the second result relies
on an application of a strong result by Austin and Tao [8]. In the notation introducedas Definition 8 below, the current classification for testability is as follows.
• Testable classes:
1. Monadic first-order logic: [all , (ω)]= .
2. Ackermann’s class with equality: [∃∗ ∀∃∗ , all ]= .
3. Ramsey’s class: [∃∗ ∀∗ , all ]= .
• Untestable classes:
1. [∀3 ∃, (0, 1)]= .
2. [∀∃∀, (0, 1)]= .
6 A class is a reduction class if the satisfiability problem for first-order logic can be reduced to thesatisfiability problem for the class. These classes are therefore undecidable (for satisfiability).
7 A hypergraph is uniform if all edges have the same arity, and non-uniform if edges may have different
arities.

4

2. Preliminaries
Instead of restricting our attention exclusively to graphs, we focus on property testingin a more general setting. We begin by defining vocabularies.
Definition 1. A vocabulary τ is a tuple of distinct predicate symbols Ri together with
their arities ai ,
τ := (R1a1 , . . . , Rsas ) .
Two examples (unique up to renaming) of vocabularies are τG := (E 2 ), the vocabularyof directed graphs and τS := (S 1 ), the vocabulary of binary strings. We generally use
vocabulary τ (i.e., s predicate symbols Ri with arities ai ) in proofs that do not dependon the vocabulary.
Definition 2. A structure A of type τ is an (s + 1)-tupleA
A := (U, RA
1 , . . . , Rs ) ,ai
is a predicate corresponding to thewhere U is a finite universe and each RAi ⊆ U
predicate symbol Ri of τ .

We identify U with the non-negative integers {0, . . . , n − 1} and use n = #(A) for thesize of the universe of a structure A. We often omit the explicit mention of A and use n
to refer to the size of structures whose identity is clear from context. The universe U ofa binary string is the set of bit positions, which we will identify as {0, . . . , n − 1} fromleft to right. For i ∈ U , we interpret i ∈ S as “bit i of the string is 1.” We generally
omit the superscript A from the relations and include it only when we wish to explicitly
distinguish the same relation in different structures.
n
The set of all structures of type τ and universe size(τ ) and the set
S n is STRUCnof all (finite) structures of type τ is STRUC (τ ) := n≥0 STRUC (τ ). A property P
of structures with vocabulary τ is any subset of STRUC (τ ). For a structure A withvocabulary τ , we say A has P if A ∈ P .
We use language to refer to string properties, P to denote properties and B\C for
set difference. We refer to members of STRUC (τG ) as graphs, and note that our graphs
are directed and may contain loops.
A simple example of a graph property is the property of being a complete
S graph. This
property is the set of all graphs which have full edge relations, i.e., PK := n≥0 {(Un , E G ) |Un = {0, . . . , n − 1}, E G = Un × Un }.
2.1. Property Testing Definitions
We wish to distinguish, with high probability, between inputs that have a desired
property and inputs that are far from having the property. We begin by defining a
distance measure between structures. Changing the definition of distance results in adifferent model for relational testing. The symbol ⊕ denotes exclusive-or.
Definition 3. Let A, B ∈ STRUC (τ ) be any structures such that #(A) = #(B) = n.
The distance between structures A and B isPs
B|{x | x ∈ U ai and RA
i (x) ⊕ Ri (x)}|Ps.
dist(A, B) := i=1
a
i
i=1 n
5

The dist distance is the fraction of assignments on which the two structures disagree.
It is equivalent to the definition that would result from mapping relational structures tobinary strings and using the usual definitions for testing strings. We note that Definition 3
is common in the literature on graph property testing, but that it is generally not used in
testing properties of non-uniform hypergraphs (for reasons discussed before Definition 10
below). However, as we will see in Theorem 5, it results in the weakest notion of testability
that we consider and so we will use it when proving untestability results.
We now give the remaining definitions for testing, and will then give alternatives toDefinition 3 (cf. Definitions 10 and 13 below). When proving results, we always state
explicitly which models the results hold in.
Definition 4. Let P be a property of structures with vocabulary τ and let A be such astructure with a universe of size n. Then,dist(A, P ) :=min

A0 ∈P ∩STRUC n (τ )dist(A, A0 ) .

Definition 5. An ε-tester for property P is a randomized algorithm given an oracle
which answers queries for the universe size and truth values of relations on desired tuples
in a structure A. The tester must accept A with probability at least 2/3 if A has P andmust reject A with probability at least 2/3 if dist(A, P ) ≥ ε.
Testers are called oblivious (see Alon and Shapira [6]) if they are not allowed to makedecisions based on the size of the universe. More concretely, a tester in their setting
is only allowed to give the oracle a natural Q, and the oracle then uniformly randomly
selects Q elements of the universe of A and returns the resulting induced substructure.
However, if A is of size smaller than Q, then the entire structure is returned. This is more
restricted than our model, but our positive results hold even in the oblivious setting.
Some of our results hold even when the testers are restricted to one-sided error, where
the following definition applies.
Definition 6. An ε-tester for P has one-sided error if it accepts with probability 1 if A
has P and rejects with probability at least 2/3 if dist(A, P ) ≥ ε.
Definition 7. Property P is testable if for every ε > 0 there is an ε-tester making a
number of queries which is upper-bounded by a function depending only on ε.
We say that a property P is testable with one-sided error if the ε-testers satisfy theadditional restriction of having one-sided error. Note that we allow the ε-testers to bedifferent for each ε > 0. This results in uniform (where the ε-testers are computablegiven ε, or equivalently, where there is a single tester that also takes ε as input) and nonuniform versions of testability. Although testable properties in the literature are usually
uniformly testable, see Alon and Shapira [7] for a property that is testable only with
uncomputable c(ε) and therefore only non-uniformly. Our results hold in both cases8
and so we will not distinguish between them.
8 That is, our negative results hold for non-uniform testing and positive results for uniform testing.
In the uniform case, we must restrict Lemma 10 in Section 3 to decidable properties. All properties
considered in the present paper are clearly decidable.

62.2. Logical Definitions
We use a predicate logic with equality that does not contain function symbols. There
are no ordering symbols such as ≤ or arithmetic relations such as PLUS. The first-orderlogic of vocabulary τ is built from the atomic formulae xi = xj and Ri (x1 , . . . , xai ) for
variable symbols xj and predicate symbols Ri ∈ τ by using the Boolean connectives andquantifiers ∃ and ∀ in the usual way.
Formula ϕ of vocabulary τ is interpreted as usual and defines property P := {A |A ∈ STRUC (τ ) and A |= ϕ}. Lower-case Greek letters ϕ, ψ and γ refer to first-orderformulae and x, y, and z to first-order variables. Our classification definitions are fromBörger et al. [11] except that we omit function symbols. Essentially, we classify firstorder sentences according to their pattern of quantifiers and vocabulary. The following
is for completeness, where N = {0, 1, . . .} denotes the set of natural numbers.
Definition 8. A prefix vocabulary class is specified as [Π, p]e , where Π is a string overthe four-character alphabet {∃, ∀, ∃∗ , ∀∗ }, p is a sequence over N and the first infinite
ordinal ω, and e is ‘=’ or the empty string.
We often use all as an abbreviation for the sequence (ω, ω, ω, . . .). Now that we havedefined the syntactic specification of a prefix vocabulary class, we define the class specified
by a triple [Π, p]e . Recall that a first-order sentence ϕ is in prenex normal form if it is in
the form ϕ := π1 x1 π2 x2 . . . πr xr : ψ, with quantifiers πi , 1 ≤ i ≤ r, and quantifier-free ψ.
Such a ϕ is a member of the prefix vocabulary class given by [Π, (p1 , p2 , . . .)]e , wherepi ∈ N ∪ {ω} if
1. The string π1 π2 . . . πr is contained in the language specified by Π when Π is interpreted as a regular expression.
2. If p is not all, at most pi distinct predicate symbols of arity i appear in ψ.
3. Equality (=) appears in ψ only if e is ‘=’.
Here, Π is the pattern of quantifiers, p is the maximum number of predicate symbols
of each arity and e determines whether or not the equality symbol is permitted.
We use the following conventions to avoid unwieldy language.
Definition 9.
1. A sentence is (un)testable if the property it defines is (un)testable.
2. A prefix class is testable if every sentence in it expresses a testable property forevery vocabulary in which it is evaluable.
3. A prefix class is untestable if it contains an untestable sentence.
An extension of a vocabulary τ is any vocabulary formed by adding a new, distinct
predicate symbol to τ . The following simple lemma justifies the intuition that we canfocus on the minimal vocabulary needed in a formula and ignore vocabularies that include
extraneous predicate symbols.
Lemma 1. Let ϕ be a formula in the first-order logic of vocabulary τ and let τ 0 be any
extension of τ . If ϕ defines a property that is testable in the context of τ , then theproperty of type τ 0 defined by ϕ is also testable.

7

Proof. Let ϕ define property P of type τ and property P 0 of type τ 0 . Assume the“new” predicate symbol in τ 0 is N of arity a. Let Tετ be an ε-tester for P . We will showthat it is also an ε-tester for P 0 . Assume A0 ∈ STRUC (τ 0 ) has property P 0 . Removing
the N predicate, the corresponding A ∈ STRUC (τ ) has property P and so Tετ accepts
with probability at least 2/3, as desired.
Assume that dist(A0 , P 0 ) ≥ ε and again let A be the structure of type τ formed byremoving the N predicate from A0 . By the definition of distance,Ps
B|{x | x ∈ U ai and RA
i (x) ⊕ Ri (x)}|Ps≥
dist(A, P ) = min i=1
ai
B∈P
i=1 n
Ps
0
B
|{x | x ∈ U ai and RA
i (x) ⊕ Ri (x)}|P
min i=1= dist(A0 , P 0 ) ≥ ε .
s
a
a
B∈P
n + i=1 n i
The tester rejects such an A0 with probability at least 2/3, as desired.



Testable properties remain testable when the vocabulary is extended. So it suffices toconsider the minimal relevant vocabulary. Simple modifications of the proof of Lemma 1
give the corresponding results for the variations considered in the next subsection.
2.3. Variations of Relational Property Testing
We now consider alternatives to Definition 3, which was presented first due to its
simplicity. In Definition 3, any difference in low-arity relations is asymptotically dominated by the number of high-arity tuples. However, there are situations where this is not
ideal. Consider (not necessarily admissible9 , vertex) 3-colored graphs with the vocabulary τC := (E 2 , R1 , G1 , B 1 ), where we use the binary predicate E to represent edges andthe monadic predicates to represent colors. We might wish to test if the given coloringis admissible. In large graphs, this is equivalent to testing if the graph is 3-colorable andignores the given coloring. We need a different model for our task.
Here we give two alternative definitions for the distance between structures. In testing
we wish to distinguish structures that have a desired property and those that are far fromthe property, and so modifying the definition of distance changes the task of testing. As
in Definition 3, the symbol ⊕ denotes exclusive-or.
Definition 10. Let A, B ∈ STRUC n (τ ) be structures. Then, the r-distance is
B|{x | x ∈ U ai and RA
i (x) ⊕ Ri (x)}|
.
1≤i≤s
nai

rdist(A, B) := max

While Definition 3 gave equal weight to each tuple regardless of its arity, the above
gives equal weight to each relation. Definition 10 is essentially equivalent to the model
used by Fischer et al. [17].
However, loops (i.e., self-edges (x, x)) in graphs and other subrelations of relations
are similar to low-arity relations. In Definition 10, these are still dominated by the“non-degenerate” tuples. Definition 13 will resolve this issue and result in a model of
testability essentially equivalent to that implicit in Austin and Tao [8]. We begin bydefining the syntactic notion of subtype before proceeding to subrelations.
9 An admissible vertex-coloring is one that assigns distinct colors to adjacent vertices.

8Definition 11. A subtype S of a predicate symbol with arity a is any partition of theset {1, . . . , a}.
For example, graphs have a single, binary predicate symbol E 2 which has two subtypes: {{1, 2}} and {{1}, {2}}, corresponding to loops and non-loops respectively. Let
SUB(R) denote the set of subtypes of predicate symbol R.
Definition 12. Let A ∈ STRUC (τ ) be a structure with vocabulary τ and universe U ,and let S be a subtype of predicate symbol Ra ∈ τ . We define the following.
• sU (S), the tuples that belong to S, is the set of (x1 , . . . , xa ) ∈ U a satisfying thefollowing condition. For every 1 ≤ j, k ≤ a, xj = xk iff j and k are contained in
the same element of S.
• The subrelation sA (S) of A corresponding to S is sA (S) := sU (S) ∩ RA .
Returning to our example of graphs, the sets of loops and non-loops are the subrelations of the edge relation E corresponding to the subtypes {{1, 2}} and {{1}, {2}} of E 2 ,respectively.
We denote the symmetric difference of sets U and V by U 4 V , i.e.,
U 4 V := (U \V ) ∪ (V \U ) .
Definition 13. Let A, B ∈ STRUC n (τ ) be structures with vocabulary τ and universe
size n. The mr-distance between A and B is|sA (S) 4 sB (S)|.
R∈τ S∈SUB(R)n!/(n − |S|)!

mrdist(A, B) := maxmax

The distance between structures is the fraction of assignments that differ in the mostdifferent subtype. As before, the distance between a structure and a property is the
distance to the closest structure with the property. We let T be the set of testableproperties using the dist definition, Tr be the set of testable properties using the rdist
definition and Tmr be the set of testable properties using the mrdist definition.
3. Basic Results
We begin by relating the three models for testability that we defined in Section 2.
Theorem 5 below is quite simple, however, it justifies our focus on T for untestable classes
and on Tmr for testable classes. First, the distances are related in the following simple
way.
Lemma 2. Let τ be a vocabulary and A, B ∈ STRUC n (τ ). Then,dist(A, B) ≤ rdist(A, B) ≤ mrdist(A, B).
Proof. We first show dist(A, B) ≤ rdist(A, B). If an ε-fraction of all assignments
differs and we partition the assignments, there must be a partition such that at least an9

ε-fraction of the assignments differs in the partition. Let dist(A, B) = ε and let αi be
the fraction of Ri -assignments that differ between the structures,
αi :=|{x | x ∈ U ai and RiA (x) ⊕ RiB (x)}|.
naiThen, rdist(A, B) = maxi αi and we can write dist(A, B) in terms of the αi ,P
αi naidist(A, B) = Pi ai = ε .
inPPThis implies that i αi nai = ε i nai , and so there must be an αi ≥ ε.
Next, we show that rdist(A, B) ≤ mrdist(A, B). The proof is nearly identical to theabove. If rdist(A, B) = ε then there is an Ri such that an ε-fraction of the Ri -assignments
differs between the structures. If we partition the Ri -assignments into the subtypes of Ri(which are disjoint), then there must be some partition such that at least an ε-fractionof the assignments in that partition differ.
Assume a tester distinguishes between structures A having some property P and
those for which mrdist(A, P ) ≥ ε. Lemma 2 trivially implies that it also distinguishes
between structures A that have P and those for which rdist(A, P ) ≥ ε. The case withrdist and dist is analogous, which proves the following.
Corollary 3. Tmr ⊆ Tr ⊆ T .
Of course it is always desirable to show that such containments are strict. We show←
the separations by encoding the following language of binary strings, where u denotes
the usual reversal of string u. It is also possible to use, e.g., the untestable property thatwill be seen in Section 5 to prove the separations with a first-order expressible property
that is closed under isomorphisms.
← ←Theorem 4 (Alon et al. [4]). The language L = {uuv v | u, v are strings over {0, 1}}
is not testable.
In some vocabularies, e.g., binary strings, all three definitions are equivalent. However, we will show the following.
Theorem 5. Tmr ⊂ Tr ⊂ T .
Proof. The inclusions are by Corollary 3 and so only the separations remain. We
first show that T \Tr is not empty. It suffices to give a vocabulary τ and a property
with vocabulary τ that is T -testable but not Tr -testable. We use the vocabulary τC :=(E 2 , S 1 ).
We will show P1 ∈ T \Tr , where P1 ⊆ STRUC (τC ) is the set of structures where theS assignments encode the language L of Theorem 4 above. Recall that n denotes the sizeof the universe and our convention is that S(i) is interpreted as “bit i of the string is 1”.
Therefore, A has P1 if there is some 0 ≤ k ≤ n/2 such that for all 0 ≤ i < k, S(i) is true
iff S(2k − 1 − i) is true and for all 0 ≤ j < (n − 2k)/2, S(2k + j) is true iff S(n − 1 − j)is true. The property uses only the low-arity relation S; the E relation is for “padding”
to make P1 testable under the dist definition for distance.
10

We first show that P1 is in T . A structure with a universe of odd size cannot have P1 .
A tester can begin by checking the parity of n and rejecting if it is odd and so we assume
in the following that the size of the universe is even.
Lemma 6. Property P1 is testable under the dist definition for distance.
← ←Proof. For any (even) n, 1n is of the form uuv v. Changing all S(i) assignments totrue in any given A results in the string 1n . This involves at most n modifications andso dist(A, P1 ) ≤ dist(A, A0 ) = O(n)/Θ(n2 ) < ε, where the final inequality holds for
sufficiently large n. Let N (ε) be the smallest value of n for which it holds. The following
is an ε-tester for P1 , where the input has universe size n.
1. If n < N (ε), query all assignments and output whether the input has P1 .
2. Otherwise, accept.
If A has P1 , we accept with zero error. If dist(A, P1 ) ≥ ε, then n < N (ε). In thiscase we query all assignments and reject with zero error.
 Lemma 6
It remains to show that P1 is not testable when using the rdist definition for distance.
We do this by showing that it would contradict Theorem 4 above.
Lemma 7. Property P1 is not testable under the rdist definition for distance.
Proof. Suppose there exist Tr -type ε-testers T ε for all ε > 0. The following is a T -typeε-tester for the language L of Theorem 4. Let the input be w, a binary string of length n.
1. Run T ε and intercept all queries.
2. When a query is made for S(i), return the value of S(i) in w.
3. When a query is made for E(i, j), return 0.
4. Output the decision of T ε .
We run T ε on the A ∈ STRUC n (τC ) that agrees with w on S and where all E
assignments are false. If w ∈ L, then any such A has property P1 and so our tester
accepts with probability at least 2/3.
Assume dist(w, L) ≥ ε. Then, rdist(A, P1 ) = dist(w, L) ≥ ε and so our tester rejects
with probability at least 2/3. These are testers for the untestable language of Theorem 4,
 Lemma 7
and so P1 is untestable under the rdist definition.
Lemmata 6 and 7, together with Corollary 3 show Tr ⊂ T . The separation Tmr ⊂ Tr
is shown in a similar way, using a property with sufficient “padding” to make Tr testing
simple but Tmr testing would contradict Theorem 4.
For example, one can use the property P2 of graphs in which the “loops” E(i, i) encode
the language from Theorem 4. That is, a graph has P2 if there is some 0 ≤ k ≤ n/2
such that for all 0 ≤ i < k, E(i, i) is true iff E(2k − 1 − i, 2k − 1 − i) is true and for all
0 ≤ j < (n − 2k)/2, E(2k + j, 2k + j) is true iff E(n − 1 − j, n − 1 − j) is true. The
non-loops are used as padding to ensure Tr testability while Tmr testability would allow
us to violate Theorem 4.
 Theorem 5
11

There exist properties that are testable in the rdist sense but not in the mrdist sense.
However, the definition of subtypes and Tmr testability allows for a simple mapping
between vocabularies such that rdist-testability of certain classes of properties implies
mrdist-testability of the same classes. For these classes, proving testability in the rdist
sense is equivalent to proving it in the mrdist sense, and so it suffices to use whichever
definition is more convenient.
Lemma 8 below is stated in the context of the classification problem for first-orderlogic but it is not difficult to prove similar results in other contexts. We use only equality
and that the class is closed under adding additional predicate symbols. The main resultin Subsection 4.1 will be the testability of Ackermann’s class with equality, which is of
the form required by the lemma.
Lemma 8. Let C := [Π, all ]= be a prefix vocabulary class. Then, C is testable in therdist sense iff it is testable in the mrdist sense.
Proof. Recalling Theorem 5, Tmr testability implies Tr testability. We prove Tr testability of such prefix classes implies Tmr testability using Lemma 9. In the following,
S(n, k) is the Stirling number of the second kind.
Lemma
P 9. Let C = [Π, (p1 , p2 , . . .)]= be a prefix vocabulary class and, furthermore, let
qj = i≥j pi S(i, j). If C 0 = [Π, (q1 , q2 , . . .)]= is Tr testable, then C is Tmr testable.
Proof. Let ϕ ∈ C be arbitrarily fixed and assume that the predicate symbols of ϕare {R11 , R21 , . . . , Rp11 , R12 , . . .}, where the arity of Rji is i. We construct a ϕ0 ∈ C 0 andshow that Tr testability of ϕ0 implies Tmr testability of ϕ. In ϕ0 we will use a distinct
predicate symbol for each subtype of each Rji in ϕ. A subtype S of Rji such that |S| = k
is a partition of the integers {1, . . . , i} into k non-empty sets and so there are S(i, k)such subtypes. We therefore require a total of qk distinct predicate symbols of arity k.
For example, we will map the “loops” in a binary predicate E to a new monadic
predicate and the non-loops to a separate binary predicate. Formally, recall that sU
maps the subtypes of a predicate to the sets of tuples comprising the subtypes. For our
example of a binary predicate, (0, 1) ∈ sU ({{1}, {2}}) and (0, 0) ∈ sU ({{1, 2}}). Next,
we let r be a bijection from the subtypes of predicates to their new names, the predicate
symbols that we will use in ϕ0 .
We create ϕ0 by modifying ϕ. Replace all occurrences of Rji (x1 , . . . , xi ) with


_



(x1 , . . . , xi ) ∈ sU (S) ∧ r(S, Rji )(y)  .
S∈SUB(Rji )Note that (x1 , . . . , xi ) ∈ sU (S) is an abbreviation for a simple conjunction, e.g., x1 6=
x2 ∧ x1 6= x3 ∧ · · · . Likewise, y is an |S|-ary tuple, formed by removing the duplicatecomponents of (x1 , . . . , xi ). The implicit mapping from (x1 , . . . , xi ) is invertible given S.
To continue our example of a binary predicate E, we would replace all occurrences ofE(x, y) in ϕ with([x = y ∧ E1 (x)] ∨ [x 6= y ∧ E2 (x, y)]) .
We assume that ϕ0 is Tr testable, and so there exists an ε-tester T ε for it. We run
this tester and intercept all queries. For a query to r(S, Rji )(y), we return the value of12Rji (x1 , . . . , xi ). This is possible because r is a bijection, and so we can retrieve S and Rji
using its inverse. Then, we can reconstruct the full i-ary tuple (x1 , . . . , xi ) from y and S.
The tester implicitly defines a map10 from structures A which we wish to test for ϕ to
structures A0 (with the same universe as A) which we can test for ϕ0 . Given an A |= ϕ,the corresponding A0 |= ϕ0 and so T ε will accept with probability at least 2/3.
We map each subtype S to a distinct predicate symbol with arity |S|. Therefore, forany structures A, B, the implicit mapping to A0 , B 0 is such that
mrdist(A, B) = rdist(A0 , B 0 ).
For convenience, let P := {B | B |= ϕ} and P 0 := {B 0 | B 0 |= ϕ0 }. For an A such that
mrdist(A, P ) ≥ ε, we simulate T ε on an A0 such that rdist(A0 , P 0 ) ≥ ε. The tester T ε
rejects with probability at least 2/3, as desired.
 Lemma 9
Proving Tr testability for [Π, all ]= implies proving it for all (q1 , . . .) that are “images” ofsome (p1 , . . .) and so Lemma 9 is stronger than required.
 Lemma 8
The proofs in Subsection 4.2 and Section 5 will follow the proofs by Alon et al. [2], andin particular rely on a generalization of their notion of indistinguishability to relational
structures, which we define as follows.
Definition 14. Let P1 , P2 ⊆ STRUC (τ ) be properties with vocabulary τ that are closed
under isomorphisms. We say that P1 and P2 are indistinguishable if for every ε > 0 there
exists an N := N (ε) ∈ N such that the following holds for all n > N . For every
A ∈ STRUC n (τ ), if A has property P1 , then mrdist(A, P2 ) < ε and if A has P2 , thenmrdist(A, P1 ) < ε.
Alon et al. [2] introduced the concept of indistinguishability and showed that it preserves testability of graph properties. This is true even after the above extension torelational properties.
Lemma 10. Let P1 , P2 ⊆ STRUC (τ ) be indistinguishable properties with vocabulary τ .
Property P1 is testable iff P2 is testable.
The proof by Alon et al. [2] extends without difficulty.
4. Testable Classes
Next, we show that two well-known classes of first-order logic are testable. We begin
with Ackermann’s class with equality, the set of first-order sentences that have at mostone universal quantifier (and any number of existential quantifiers), before proceeding toRamsey’s class in Subsection 4.2.
10 Explicitly, map A to an A0 with the same universe size, where y ∈ r(S, Ri ) in A0 if (x , . . . , x ) ∈ Ri
1ijj
in A. Note that we have not yet defined the assignments of tuples y with duplicate components. By
construction, the assignments of these tuples do not affect ϕ0 and so any reasonable convention will
do. For example, for any predicate symbol Q of ϕ0 and any tuple z that has at least one duplicatecomponent, we define z 6∈ Q. The resulting map is injective but not necessarily surjective.

13

4.1. Ackermann’s Class with Equality
In this subsection we show that Ackermann’s class with equality ([∃∗ ∀∃∗ , all ]= ) is
testable. We begin by reviewing the history of this class, which has a number of niceproperties.
Ackermann’s class was first considered (without equality) by Ackermann [1], whoshowed that the satisfiability problem for the class is decidable and that it has thefinite model property11 . Kolaitis and Vardi [30] showed the satisfiability problem for
Ackermann’s class with equality is complete for NEXPTIME and that a 0-1 law holds
for existential second-order logic12 where the first-order part belongs to [∃∗ ∀∃∗ , all ]= .
Lewis [33] proved that satisfiability for Ackermann’s class without equality is completefor (deterministic) EXPTIME. Grädel [24] showed that satisfiability for Ackermann’sclass without equality is complete for EXPTIME even with the addition of arbitrarilymany function symbols.
If we allow equality and a unary function symbol, the result is Shelah’s class, which
Shelah [46] proved decidable. Shelah’s class is a decidable class that does not have thefinite model property, and it would be interesting to determine if it is testable. This
would require extending relational testing to allow function symbols.
Ackermann’s class with equality has been studied in other settings as well. For
example, Fermüller and Salzer [14] used an extension of resolution to decide an extensionof Ackermann’s class with equality using automated theorem provers.
The main goal of this subsection is Theorem 11 below. Recalling Theorem 5, this also
implies that such properties are testable in the dist and rdist senses. If the vocabulary
consists of a single relation, the rdist and dist definitions are equivalent to the dense hypergraph model. We therefore obtain the corresponding results in the dense hypergraphand dense graph models as special cases.
We denote the set of monadic predicate symbols in a vocabulary τ by M := {Ri |Ri ∈ τ and ai = 1}. The set of assignments of the symbols in M for an element in auniverse is called the color of the element and there are 2|M | possible colors. We define
Col(A, c) to be the set of colors that occur at least c times in A.
Theorem 11. All formulae in [∃∗ ∀∃∗ , all ]= define properties that are in Tmr with onesided error.
Proof. Recall that Ackermann’s class with equality is [∃∗ ∀∃∗ , all ]= and, therefore, itsuffices to show the testability of property P of type τ = (R1a1 , . . . , Rsas ) defined byformula ϕ := ∃x1 . . . ∃xa ∀y∃z1 . . . ∃zb : ψ, where ψ is quantifier-free. Note that a isthe number of leading existential quantifiers and b is the number of trailing existential
quantifiers. We can trivially test any ϕ that has only finitely-many models with a constantnumber of queries and zero error, and so it suffices to assume that ϕ has infinitely-manymodels.
11 A class is said to have the finite model property if every satisfiable formula in the class has a finite
model. Classes without this property have infinity axioms, i.e., sentences with only infinite models.
12 A class C of first-order logic has an associated 0-1 law if all existential second-order sentences
ϕ := ∃C1 . . . Ca ψ, where ψ is a first-order sentence in C, have the property that the limit as n → ∞of the probability that a random structure of size n satisfies ϕ exists and is either 0 or 1. Recall thatthe focus is on existential second-order because all of first-order admits a 0-1 law, see the references in
Kolaitis and Vardi [31].

14The class [∃∗ ∀∃∗ , all ]= is of the form required by Lemma 8 above, and so it is mrdisttestable iff it is rdist-testable. It therefore suffices to show that P is testable in therdist sense. We will show that the following is an ε-tester in the rdist sense for P
on input A ∈ STRUC n (τ ). Here, k := k(τ, ε) is the number of elements queried andN := N (ϕ, τ, ε) is a constant, both of which are determined below. Note the actual
number of queries in Step 2 is not exactly k, but rather a constant multiple of it dependingon τ . Finally, we explicitly give κ := κ(ϕ, τ ) below.
1. If n < N , query all of A and decide exactly whether A has P .
2. Uniformly and independently choose k members of the universe of A and query
all monadic predicates on the members in this sample. Let B be the observed
substructure.
3. Search over all A0 ∈ STRUC κ (τ ). Accept if an A0 is found such that A0 |= ϕ andCol(B, a + 1) ⊆ Col(A0 , a + 1).
4. Otherwise, reject.
We will show that the tester accepts (with probability 1) if A |= ϕ and rejects withprobability 2/3 if rdist(A, P ) > ε. We first show that if A |= ϕ, then the tester isguaranteed to accept. Then, we will show in Lemma 13 that with probability at least
2/3, we get a “good” sample in Step 2. A sample is “good” if it contains at least (a + 1)many distinct representatives of each color that occurs on at least an ε/(2 · 2|M | ) fractionof the elements of A. We then show that the tester is correct if it obtains a good sample,
and therefore rejects with probability at least 2/3 if rdist(A, P ) > ε.
We will now show that if A |= ϕ, the tester will accept with probability 1. We begin
with Lemma 12.
Lemma 12. Let A be a model of ϕ such that #(A) > N and let
P s P aiaiai −jκ := a + 3b a + 2 i=1 j=1 ( j )a
+ 2|M | (a + 1).
Then, there is an A0 |= ϕ such that #(A0 ) = κ and Col(A, a + 1) ⊆ Col(A0 , a + 1).
Proof. Assume that N > κ. The structure A is a model of ϕ, and so there exists atleast one tuple of a elements (u1 , . . . , ua ) such that ϕ is satisfied when the existential
quantifiers bind ui to xi . We consider the xi and the substructure induced by them tobe fixed, and refer to this substructure
as Ax .
P s P ai(aji )aai −j many distinct structures constructed
i=1
j=1
There are at most κ2 := a + 2
by adding an element labeled y to Ax when we include the structures where the label yis simply placed on one of the xi . We let v ≤ κ2 be the number of such structures that
occur in A and assume there is an enumeration of them.
For each of these v substructures there exist b elements, w1 , . . . , wb , such that when
we label wi with zi , the structure induced by (x1 , . . . , xa , y, z1 , . . . , zb ) models ψ. We
construct Ai,j for 1 ≤ i ≤ 3 and 1 ≤ j ≤ v such that Ai,j is a copy of the w1 , . . . , wb used
for the j-th structure. We connect each Ai,j to Ax in the same way as in A, modifying
assignments on tuples (Ax ∪ Ai,j )ak .
For each wh in Ai,j , we consider the case where y is bound to wh . By construction thesubstructure induced by (x1 , . . . , xa , y) occurs in A. We assume it is the g-th structure15

and use the elements of Ai+1 mod 3,g to construct a structure satisfying ψ. We modify theassignments of tuples as needed to create a structure identical to that in A satisfying ψ.
Note that by construction all of these assignments are of tuples that contain wh andat least one element from Ai+1 mod 3,g . The resulting structure, which we call A1 , isa model of ϕ. Before this step we have not modified any assignments “spanning” the“rows” Ai,j of A1 and so there are no assignments that we modify more than once.
However, there may be some color from Col(A, a+1) that does not appear a+1 times
in A1 . We therefore add a new block, denoted Ae , of at most 2|M | (a + 1) elements which
consists of a + 1 copies of each color from Col(A, a + 1). Each of these colors occurred atleast a + 1 times in A, and so for each such color C, there is an element q in A with color
C such that q is not part of Ax . If the substructure induced by (Ax , q) in A is the j-thstructure in our enumeration, then we do the following for each member p of Ae that has
the same color as q. First, we make the substructure induced by (Ax , p) identical to thatinduced by (Ax , q) in A. Next, we make the substructure induced by (p, A1,j ) identicalto that induced by q and the corresponding zi in A. All of these modifications are ontuples containing a p ∈ Ae and so we do not modify any tuples more than once. We callthis structure A2 .
Finally, so far we only have an upper bound on the size of A2 while the lemma states
it to be exactly of size κ. We therefore pad in the following simple way13 . We know thatN > κ > 2|M | a and so there is a color that occurs at least a+1 times in A. If #(A2 ) < κ,
we simply make an additional κ − #(A2 ) many copies of this color in Ae and modify theassignments of tuples containing these new elements in the same manner as above. The
resulting A0 has size κ and satisfies the requirements of the lemma.
 Lemma 12
For any sample B of A, it is true that Col(B, a + 1) ⊆ Col(A, a + 1). If A |= ϕ, thenLemma 12 implies that our tester will find an A0 satisfying the conditions of Step 3 andwill therefore accept. This holds for any sample B and so the tester will accept such A
with probability 1.
Next, assume that rdist(A, P ) ≥ ε. In this case we must show that the tester rejects
with probability at least 2/3. First, we show that the tester obtains a “good” sample
with probability at least 2/3.
Lemma 13. There are constants k and N such that, with probability at least 2/3, thetester obtains a sample that contains at least (a+1)-many distinct representatives of eachcolor in Col(A, εn/(2 · 2|M | )).
Proof. The probability that any particular query misses a fixed color that occurs on atleast an ε/(2 · 2|M | ) fraction of A is at most (1 − ε/(2 · 2|M | )). Moreover, the probability
that we miss such a fixed color after k1 independent queries is at most (1 − ε/(2 · 2|M | ))k1 .
There are at most 2|M | such colors, and so the probability that a sample of k1 elements
fails to contain at least one representative of all such colors is at most

k
ε/2 1
|M |
p1 := 2
1 − |M |.
2
The |M | is a constant, and we choose k1 such that (a + 1)p1 is at most 1/6.
13 One could instead change the tester to search structures with size at most κ.

16Let k := (a + 1)k1 . We will make k independent queries, and consider the total
sample as (a + 1) separate samples of size k1 . All of these smaller samples will containat least one representative of every color in Col(A, εn/(2 · 2|M | )) with probability at least
1 − (a + 1)p1 ≥ 5/6. However, there is the possibility that some of these smaller samples
contain elements in common. We will choose N such that for n > N , the probability
that any particular element in the universe of A is chosen more than once is at most 1/6.
In particular, if #(A) = n and we define xy := x(x − 1) · · · (x − (y − 1)) = x!/(x − y)!,then the probability that some element is queried more than once is
p2 := 1 −n!
n(a+1)k1=1−.
n(a+1)k1 (n − (a + 1)k1 )!
n(a+1)k1

The sample size (a + 1)k1 is a constant, and so we can choose N such that p2 ≤ 1/6 forn > N.
The probability that the tester obtains a sample that contains at least (a + 1)-many
distinct representatives of each color in Col(A, εn/(2 · 2|M | )) is at least
1 − (a + 1)p1 − p2 ≥ 2/3.
 Lemma 13
Our goal is to show that if rdist(A, P ) ≥ ε, then we reject with probability at least 2/3.
It is easier to show the contrapositive: if the tester accepts with probability strictly
greater than 1/3, then rdist(A, P ) < ε.
If we accept a structure A with probability strictly greater than 1/3, then we must
accept it when we obtain a good sample. We construct a B such that B |= ϕ andrdist(A, B) < ε from the A0 that the tester must find to accept. We begin with Lemma 14,
which we will use to “grow” smaller models.
Lemma 14. Let ϕ := ∃x1 . . . ∃xa ∀y∃z1 . . . ∃zb : ψ be a formula with vocabulary τ ,where ψ is quantifier-free and A ∈ STRUC (τ ) be such that A |= ϕ. Additionally, let
B ∈ STRUC (τ ) be any structure containing A as an induced substructure such that#(B) = #(A) + 1. If the additional element of B has a color that occurs at least a + 1
times in A, then we can construct a B 0 |= ϕ by modifying at most a constant number of
non-monadic assignments in B.
Proof. Structure B contains an induced copy of A and one additional element, which
we will denote by q. By assumption, A is a model of ϕ and therefore contains an a-tuple(u1 , . . . , ua ) such that the formula is satisfied when xi is bound to ui . In addition, there
are at least a + 1 elements in A that have the same color as q. Therefore, there is at least
one such element p that is not one of the ui . We will make q equivalent to p without
modifying any monadic assignments.
We begin by modifying the assignments as needed to make the structure inducedby, . . . , xa ,q) identical to that induced by (x1 , . . . , xa , p). This requires at mostPs (x1Pai
ai ai −j= O(1) modifications, all of which are non-monadic. There must
j=1 j ai=1
be (v1 , . . . , vb ) in A such that ψ is satisfied when zi is bound to vi and y to p. We
modify the assignments needed to make the structure induced by (q, v1 , . . . , vb ) identical17

Ps Pai ai  ai −jto that induced by (p, v1 , . . . , vb )14 . This requires at most i=1 j=1= O(1)
j b
modifications, all of which are non-monadic. The result has #(A) + 1 elements, models
ϕ and was constructed from B by making a constant number of modifications to nonmonadic assignments.
 Lemma 14
Let A be the structure that the tester is running on and A0 be the structure found in
Step 3 of the tester. As mentioned above, we will construct a B |= ϕ from A0 such that
B |= ϕ and rdist(A, B) < ε.
Note that there must exist at least one color in Col(A, εn/(2 · 2|M | )) and assume that
N is large enough that εn/(2 · 2|M | ) ≥ a + 1. We first make a constant sized portion of
A identical to A0 . This requires at most O(1)-many modifications to each relation. All
colors in Col(A, εn/(2 · 2|M | )) occur at least a + 1 times in A0 , allowing us to recursively
apply Lemma 14 and add the elements of A that have colors in Col(A, εn/(2·2|M | )). Thisentails making O(1)-many modifications to non-monadic relations (and none to monadic
relations) at each step, for a total of O(n) modifications to the non-monadic relations.
Finally, we consider the elements of A that have colors occurring at most εn/(2 · 2|M | )times. There are at most 2|M | such colors and at most εn/2 elements with these colors.
We change the monadic assignments on such elements as required to give them colors
contained in Col(A, εn/(2 · 2|M | )). This requires at most εn/2 modifications to each of
the monadic assignments. We again recursively apply Lemma 14 to A, making O(1)modifications to non-monadic assignments at each step. The resulting structure is B
and is such that B |= ϕ.
Finally, we show that rdist(A, B) < ε. If Ri is a monadic relation, then the i-th termof the maximum in the definition of rdist (cf. Definition 10 above) is at most ε/2 + o(1).
If Ri has arity at least two, then the i-th term of the maximum is O(n)/Ω(n2 ) = o(1).
All o(1) terms can be made arbitrarily small by choosing N (ϕ, τ, ε) appropriately and so
we can assume that all terms are strictly less than ε. The maximum is then strictly lessthan ε and so rdist(A, B) < ε as desired.
 Theorem 11
4.2. Ramsey’s ClassIn this subsection we revisit a result of Alon et al. [2] in the light of recent work by
Austin and Tao [8]. The main result is the testability of the full Ramsey’s class (i.e.,removing the restriction to undirected loop-free graphs). As we did for Ackermann’sclass with equality in Subsection 4.1, we begin by reviewing the history and propertiesof the class, denoted [∃∗ ∀∗ , all ]= .
Ramsey’s class is also known as the Bernays-Schönfinkel-Ramsey class. Bernays andSchönfinkel [9] proved the finite model property and that satisfiability is decidable for theclass without equality. Ramsey [38] extended these results to the class with equality as
part of a stronger result. Lewis [33] showed that satisfiability is NEXPTIME-complete
for Ramsey’s class and Kolaitis and Vardi [29] proved that a 0-1 law holds for existential second-order logic where the first-order part belongs to [∃∗ ∀∗ , all ]= . Omodeo andPolicriti [36] have recently shown that the class is semidecidable for set theory.
The main goal of this subsection is Theorem 15 below. Recalling Theorem 5, this also
implies testability in the T and Tr senses. The proof of Theorem 15 follows the proof by
Alon et al. [2], and relies on a reduction to a strong result by Austin and Tao [8].
14 The case where v

i = p can be handled by replacing vi with q in (q, v1 , . . . , vb ).

18

An outline of the proof is as follows. First, we show that all sentences in [∃∗ ∀∗ , all ]=define properties which are indistinguishable from instances of a generalized colorability
problem. Next, we note that all such problems are hereditary and therefore testable
when mapped to the setting defined by Austin and Tao [8]. Finally, we show that this
implies testability under our definitions, giving the following.
Theorem 15. All sentences in [∃∗ ∀∗ , all ]= define properties in Tmr .
We begin the proof of Theorem 15 by defining a generalized colorability problem, as
did Alon et al. [2].
For any fixed set F of structures with vocabulary τ , some positive number of colors c,
and functions that assign a color between 1 and c to each element of each structure
in F , we define the F -colorability problem as follows. A structure A ∈ STRUC (τ ) is
F -colorable if there exists some (not necessarily proper) c-coloring of A such that A does
not contain any induced substructures isomorphic to a member of F . We let PF be theset of structures that are F -colorable.
For example, we can consider the case of graphs and let F contain c copies of K2 . We
enumerate these copies in some fashion from 1 to c, and for copy i, color both vertices
with i. The resulting problem is of course the usual (k- or equivalently) c-colorability.
The following is a straightforward generalization of the proof by Alon et al. [2].
Lemma 16. Let ϕ be any first-order sentence in the class [∃∗ ∀∗ , all ]= . There exists
an instance of the F -colorability problem that is indistinguishable from P , the property
defined by ϕ.
Proof. Let ε > 0 be arbitrary and ϕ := ∃x1 . . . ∃xt ∀y1 . . . ∀yu : ψ be any first-orderformula with quantifier-free ψ and vocabulary τ . We note, as did Alon et al. [2], that
we can restrict our attention to formulae ψ, where it is sufficient to consider only cases
where the variables are bound to distinct elements. This is because, given any ψ 0 , we canconstruct a ψ satisfying this restriction that is equivalent on structures with at least t + uelements, and the smaller structures do not matter in the context of indistinguishability.
Let P = {A | A ∈ STRUC (τ ), A |= ϕ} be the property defined by ϕ. We now define
an instance of F -colorability that we will show to be indistinguishable from P . We denoteour c colors by the elements of{(0, 0)} ∪ {(a, b) | 1 ≤ a ≤ π1 , 1 ≤ b ≤ π2 , a, b ∈ N} .
Here, πP
1 is the number of distinct structures of vocabulary τ with exactly t elements,sai
π1 := 2 i=1 t . Similarly, we denote by π2 the number of ways it is possible to “connect”
or “add” a single element to some existing, fixed t-element structure of vocabulary τ , i.e.,
Ps Pai −1 ai a −ji
π2 := 2 i=1 j=1 ( j )t
. We will use fixed enumerations of these π1 structures with telements and π2 ways of connecting an additional element to a fixed t element structure.
We impose on the coloring of the structure the following restrictions. Each can be
expressed by prohibiting finite sets of colored induced substructures.
(1) The color (0, 0) may be used at most t times. Therefore, we prohibit all (t + 1)element structures that are colored completely with (0, 0).15
15 Note that introducing a constraint guaranteeing the existence of t such elements cannot be done byforbidding finite sets of structures, and would result in a non-hereditary property.

19

(2) The graph must be colored using only {(0, 0)} ∪ {(a, b) | 1 ≤ b ≤ π2 } for somefixed a ∈ {1, . . . , π1 }. Therefore, we prohibit all two-element structures colored((a, b), (a0 , b0 )) with a 6= a0 .
(3) We now consider some fixed coloring of a u-element structure V , whose universe
we identify with {v1 , . . . , vu }. We assume that this coloring satisfies the previous
restriction and that color (0, 0) does not appear. We must decide whether toprohibit this structure. In order to do so, we first take the fixed a guaranteed by
the previous restriction, and consider the t-element structure E, whose universe we
identify with {e1 , . . . , et }, that is the a-th structure in our enumeration of t element
structures. We connect each vi to E in the following way. If vi is colored (a, b),
we use the b-th way of connecting an additional element to a t-element structure
in our enumeration. We denote the resulting (t + u)-element structure as M andallow (do not prohibit) V iff M is a model of ψ when we replace xi with ui and yj
with vj .
We now show that the resulting F -colorability problem is indistinguishable from P .
Recall the definition of indistinguishability (Definition 14) and assume that we are given
an A |= ϕ. Color the t vertices existentially bound to the xi with (0, 0). Then, we
can color all remaining vertices vi with (a, b), where a corresponds to the substructure
induced by {x1 , . . . , xt } in our enumeration of t-element structures, and b corresponds tothe connection between vi and {x1 , . . . , xt }. It is easy to see that this coloring satisfies
the restrictions of our F -colorability problem. We have not made any modifications tothe structure and so mrdist(A, PF ) = 0 (i.e., A ∈ PF ).
Next, we assume that we are given a structure with a coloring that satisfies ourrestrictions. We will show that we can obtain a model of ϕ by making only a small numberof modifications. First, if there are less than t elements colored (0, 0), we arbitrarilychoose additional elements to color (0, 0) so that there are exactly t such elements. We
will denote these t elements with {e1 , . . . , et }. Restriction (2) guarantees that all colors
which are not (0, 0) share the same first component. Let a be this shared component.
We make the structure induced by {e1 , . . . , et } identical
Psto the a-th structure in our
enumeration of t-element structures, requiring at most i=1 tai = O(1) modifications.
Next, for each element vi that is colored (a, b) with a, b 6= 0, we modify the connections
between vi and {e1 , . . . , et } in order to make these connections identical to the b-th wayof making such connections in our enumeration. This requires at most(n − t)r aXi −1 
Xai
i=1 j=1

j

t

ai −j


= O(n)

additional modifications, all of which are to non-monadic subrelations. Binding xi to ei ,the resulting structure is a model of ϕ. We made at most O(1) modifications to monadic
subrelations and O(n) modifications to non-monadic subrelations, and so mrdist(A, P ) ≤max{O(1)/n, O(n)/Ω(n2 )} = o(1) < ε, where the inequality holds for sufficiently large n.
Therefore, all such properties P are indistinguishable from instances of F -colorability,
as desired.

Recall that a hereditary property of relational structures is one which is closed undertaking induced substructures. F -colorability is clearly a hereditary property; if A is20

F -colorable, then so are its induced substructures. However, the definitions of Austin
and Tao [8] are significantly different from ours and so we explicitly reduce the following
translation in our setting to their result.
Theorem 17 (Translation of Austin and Tao). Let P be a hereditary property ofrelational structures which is closed under isomorphisms. Then, property P is testablein the sense of Tmr with one-sided error.
Theorem 17 can be viewed as the latest in a series of generalizations of Alon etal. [2] Corollary 6.3, i.e., the testability of colorability problems for undirected loopfree graphs. The first such generalization was by Fischer [16], who extended the result
to more general colorability problems with counting restrictions. This was followed byAlon and Shapira [6] who extended it to hereditary graph properties. Ishigami [25]extended the testability result to hereditary partite uniform hypergraph properties, andRödl and Schacht [39] extended it to hereditary uniform hypergraph properties. These
generalizations are closely related to extensions of Szemerédi’s Regularity Lemma andthe Removal Lemma, see the references in Subsection 1.1.
Before reducing Theorem 17 to its statement in [8], we first briefly introduce theirdefinitions. All of the definitions in Subsection 4.2.1 are from Austin and Tao [8], although
we omit definitions which are not necessary for our purposes.
4.2.1. Framework of Austin and Tao
We begin by introducing their analogue of vocabularies: finite palettes.
Definition 15. A finite palette K is a sequence K := (Kj )∞j=0 of finite sets, of which
all but finitely-many are singletons. The singletons are called points and denoted pt. A
point is called trailing if it occurs after all non-points.
We will write K = (K0 , . . . , Kk ), omitting trailing points and call k the order of K.
We use the elements of Kj to color the j-ary edges in hypergraphs.
Definition 16. A vertex set V is any set which is at most countable. If V, W are vertex
sets, then a morphism f from W to V is any injective map f : W → V and the set ofsuch morphisms is denoted Inj(W, V ). For N ∈ N, we denote the set {1, . . . , N } by [N ].
Of course, [N ] is a vertex set. Our structures are finite so we are mostly interested
in finite vertex sets. Next, we define the analogue of relational structures.
Definition 17. Let V be a vertex set and K be a finite palette. A K-colored hypergraphG on V is a sequence G := (G)∞j=0 , where each Gj : Inj([j], V ) → Kj is a function. Let
K (V ) be the set of K-colored hypergraphs on V .
Only finitely-many of the Kj are not points, and so only finitely-many Gj are nontrivial. The Gj assign colors from Kj to the morphisms in Inj([j], V ). In our relationalsetting, this set of morphisms corresponds to the set of j-ary tuples (x1 , . . . , xj ) withpairwise distinct components.
Before defining hereditary K-properties, we need one last technical definition.
21

Definition 18. Let V, W be vertex sets and f ∈ Inj(W, V ) be a morphism from W to V .
The pullback map K (f ) : K (V ) → K (W ) is
K (f ) (G) (g) := Gj (f ◦ g) ,j

(V )for all G = (Gj )∞, j ≥ 0 and g ∈ Inj([j], W )). If W ⊆ V and f ∈ Inj(W, V ) is
j=0 ∈ K
the identity map on W , we abbreviate

G W := K (f ) .
Abusing notation, the pullback map K (f ) maps K-colored hypergraphs on V to thoseon W , by assigning the color of f ◦ g to g, for all tuples g. Note that G W is equivalent
to the induced subhypergraph on W . For notational clarity, we reserve P for propertiesof relational structures and use P to denote properties of hypergraphs.
Definition 19. Let K = (Kj )∞j=0 be a finite palette. A hereditary K-property P is an
assignment P : V 7→ P (V ) of a collection P (V ) ⊆ K (V ) of K-colored hypergraphs forevery finite vertex set V such that
K (f ) (P (V ) ) ⊆ P (W )for every morphism f ∈ Inj(W, V ) between finite vertex sets.
Finally, we state the definition of (one-sided error) testability
used by Austin andTao [8]. Here, for a vertex set V and c ∈ N, we write Vc := {V 0 | V 0 ⊆ V, |V 0 | = c} todenote the set of subsets of V with exactly c elements.
Definition 20. Let K be a finite palette with order k ≥ 0 and P be a hereditary Kproperty. Property P is testable with one-sided error if for every ε > 0, there exists N ≥ 1and δ > 0 satisfying the following. For all vertex sets V with |V | ≥ N , if G ∈ K (V )satisfies

 

V
1
(W )
, G W ∈ P≥ 1−δ,(1)
W |W ∈V
N
N

then there exists a G0 ∈ P (V ) satisfying

 

1
V
0
≤ ε.
, G W 6= G W
W |W ∈

V
k

(2)

k

To see that this is a variant of testability, it is easiest to consider the contrapositive.
If there is a G0 satisfying (2), then G is not ε-far from P, using the implicit distancemeasure based on the fraction of differing induced subhypergraphs of size k. If there isno such G0 (i.e., G is ε-far from P) and P is testable, then (1) must not hold. That is,there are many induced subhypergraphs of size N that do not have P. The definition isfor hereditary P, and so if G has P, then so do all induced subhypergraphs. This allows
the construction of testers.
Finally, we can state one of the main results of Austin and Tao [8].
22Theorem 18 (Austin and Tao [8]). Let K be a finite palette and let P be a hereditary
K-property. Then, P is testable with one-sided error.
In the following subsection we will map our vocabularies, structures and properties
to this setting. We will then show that hereditary properties in our setting correspondto hereditary properties (in the sense of Definition 19 above) here, and that testability
in the sense of this section (Definition 20) implies testability of the original relational
properties. That is, we explicitly reduce our translation (Theorem 17) to Theorem 18.
4.2.2. Reducing Theorem 17 to Theorem 18
We begin by mapping vocabulary τ = {R1a1 , . . . , Rsas } to a finite palette Kτ = (Ki )∞i=0 .
We use the color of a “tuple” to represent the set of assignments on it. The difference
between the set of j-ary tuples over a finite universe U and Inj([j], U ) is that the latterdoes not permit repeated components. If S ∈ SUB(Riai ) has |S| < ai , then the corresponding subrelation consists of tuples with repeated components. We treat such S as
relations with arity |S| and no repeated components. Recall that S(n, k) is the Stirlingnumber of the second kind.
For a ≥ 1, let Pa := {Riai | Riai ∈ τ, ai = a} be the set hof predicate symbols
with
i
Pi

arity a. We now define palette K. Let K0 := pt and Ki := 2 j |Pj |S(j,i) . There are
finitely-many predicate symbols and so only finitely-many Ki 6= pt.
Let Sa := {Sai | Sai ∈ SUB(Riai ), |Sai | = a, 1 ≤ i ≤ s} be the set of subtypes withcardinality a for all a ≥ 1. Now, 2|Sa | = |Ka | and we have exactly enough colors to
encode the set of assignments of the a-ary subtypes on a-ary tuples.
We will now define a map h from relational structures A on universe U to hypergraphs
GA ∈ K (U ) . For any Sai ∈ Sa , there is a bijectionr(Sai ) : sU (Sai ) → {(x1 , . . . , xa ) | xi ∈ U, xi 6= xj for i 6= j}from sU (Sai ) to the a-ary tuples without duplicate components, formed by removing
the duplicate components. That is, r(Sai ) maps (x1 , . . . , xai ) to (xi1 , . . . , xia ) where1 ≤ i1 < i2 < . . . < ia ≤ ai . We can now define GA = h(A).
For j > 0, we define Gj : Inj([j], U ) → Kj as follows. Assign to f ∈ Inj([j], U ) thecolor encoding the set of assignments of the subtypes Sj on (f (1), . . . , f (j)), using theinverses (r(Sji ))−1 to get assignments for subtypes of high-arity relations. For j = 0,
Inj([j], U ) = ∅ and K0 = pt and we can use a trivial map.
Of course, we extend the map to properties in the obvious way. If P is a property ofrelational structures, we let P (U ) := {h(A) | A ∈ P }. Formally, we define P(U ) := P (U ) ,but there is a small technical point. We have identified finite universes with subsets of
the naturals, allowing us to call STRUC (τ ) a set. However, Definition 16 in this section
allows a vertex set to be any finite set and Definition 19 requires hereditary hypergraphproperties to be closed under bijections between vertex sets. To remedy this, for eachfinite vertex set W , we fix a16 bijection g W : W → {0, . . . , |W | − 1}. We then define
P := h(P ) formally as(
P (W ) ,if W = {0, 1, . . . , |W | − 1};
P(W ) :=
gW )({0,...,|W |−1})(KP, otherwise.
16 Our properties are closed under isomorphisms, so any fixed bijection is acceptable.

23

Hereditary relational properties are mapped to hereditary hypergraph properties,
which are testable in the sense of this section (Definition 20 above) by Theorem 18.
Lemma 19. If P is a hereditary property of relational structures, then h(P ) is a hereditary property of hypergraphs.
Proof. Let P be a hereditary property of relational structures with vocabulary τ . Assume that P := h(P ) is not a hereditary K-property. Then, by Definition 19 above,
there exist finite vertex sets V and W , and a morphism f 0 ∈ Inj(W, V ) such that
K (f ) (P (V ) ) 6⊆ P (W ) .

(3)

Since f 0 exists, Inj(W, V ) cannot be the empty set and so |V | ≥ |W |. Let UV :={0, . . . , |V | − 1} and UW := {0, . . . , |W | − 1}. By the definition of P, we can fix
Vbijections g V : V → UV and g W : W → UW such that P (V ) = K (g ) P (UV ) and
W
P (W ) = K (g ) P (UW ) . By the definition of P = h(P ), this implies





W
V
6⊆ K (g ) P (UW ) .
K (f ) K (g ) P (UV )Bijections are invertible, and so this implies
K

”
“
−1
g V ◦f ◦(g W )P (UV ) ⊆6 P (UW ) .

−1
and note f 0 ∈ Inj(UW , UV ). Let A0 ∈ P (UV ) be such that
Rename f 0 := g V ◦ f ◦ g W0(UW )(f 0 )K (A ) 6∈ P.
We defined P as h(P ) for a hereditary property P of relational structures. Property
P is closed under isomorphisms, and so there is an A := h−1 (A0 ) ∈ P ∩ STRUC |UV | (τ )such that the |UW |-element substructure induced by {a | a = f 0 (u) for some u ∈ Uw }does not have P . This contradicts the hereditariness of P and so P must be hereditary
in the sense of this section (Definition 19).

We mapped hereditary relational properties to hereditary hypergraph properties,
which are testable by Theorem 18. We will show this implies testability of the original properties.
Definition 21. Let A, B ∈ STRUC n (τ ) be structures with vocabulary τ and universe
U := {0, . . . , n−1} of size n, k := maxi ai be the maximum arity of the predicate symbols,
and h : STRUC n (τ ) → K (U ) be the map defined above. The h-distance between A and
B is

 

1
U
hdist(A, B) :=
W
|
W
∈
,
h(A)

=
6
h(B)

.
W
W

U
k
k

We now relate the two distances with the following simple lemma.
Lemma 20. Let A, B ∈ STRUC n (τ ) be relational structures with vocabulary τ and sizen. Then, hdist(A, B) ≥ mrdist(A, B).
24

Proof. Assume that mrdist(A, B) = ε. Then, there exists a predicate symbol Riai ∈ τand subtype S ∈ SUB(Riai ) such that sA (S) 4 sB (S) /(n!/(n − |S|)!) = ε. Let k :=maxi ai and let the universe of both structures be Un := {0, . . . , n − 1}.
Consider a random permutation of the universe (i.e., a bijection r : Un → Un ) chosen
uniformly from the set of such permutations. The probability that the substructuresinduced on {r(0), . . . , r(k − 1)} differ in A and B is hdist(A, B). The probability thatthe tuple of the first |S| elements, i.e. (r(0), . . . , r(|S| − 1)), differ in sA (S) and sB (S) is
ε and so hdist(A, B) ≥ ε.

Equality is obtained when |S| = k. It is possible to show that the two distances
differ by at most a constant factor, and so the corresponding notions of testability are
essentially equivalent. However, Lemma 20 suffices for our purposes.
Lemma 21. Let P ⊆ STRUC (τ ) be a property of relational structures which is mappedby h to a property of hypergraphs that is testable with one-sided error. Then, P is testablewith one-sided error.
Proof. Let P := h(P ) be the hypergraph property which P is mapped to. We show thatthe following is an ε-tester for P with one-sided error. Let N ≥ 1, δ > 0 be the constantsof Definition 20 above for ε. Assume that we are testing a structure A ∈ STRUC n (τ )and recall that U = {0, . . . , n − 1}.
1. If #(A) ≤ N , query the entire structure and decide exactly whether A ∈ P .
2. Otherwise, repeat the following q(δ) times.
(a) Uniformly select N elements and query the induced substructure.
(b) If it has P , continue. Otherwise, reject.
3. Accept if all of the induced substructures had P .
If A ∈ P , then all induced substructures have P because P is hereditary and thetester accepts with probability 1. Next, assume mrdist(A, P ) > ε. We use Definition 20
above to show the tester will find a witness for A 6∈ P with probability at least 2/3. By
Lemma 20, hdist(A, P ) ≥ mrdist(A, P ) > ε. We assumed h(P ) is hereditary, and so (byTheorem 18) it is testable in the sense of Definition 20. The probability that a uniformly
chosen N -element substructure does not have P is at least δ. We use q(δ) to amplify the
success probability from δ to 2/3.
This completes the proof of the testability of Ramsey’s class (Theorem 15). All properties expressible in Ramsey’s class are indistinguishable from instances of F -colorability.
Indistinguishability preserves testability and so it sufficed to show that these instances
are testable. All instances of F -colorability are hereditary relational properties, which
are testable by Theorem 17, which we reduced to the statement by Austin and Tao [8].
5. Untestable Classes
We now shift our attention to untestable classes. As mentioned in Subsection 1.2,
Alon et al. [2] proved that there exists an untestable property of undirected, loop-freegraphs expressible with quantifier prefix ∀12 ∃5 . We simplify their untestable example and thereby show that the classes [∀3 ∃, (0, 1)]= , [∀2 ∃∀, (0, 1)]= , [∀∃∀2 , (0, 1)]= and25[∀∃∀∃, (0, 1)]= are untestable. The focus on graphs is justified by recalling that monadic
first-order logic is testable. We begin by briefly reviewing other properties of these classes.
The class [∀3 ∃, (0, 1)] (usually without equality) is well-known in the literature. It
is trivial to prove that this class does not have the finite model property. In addition,
Kolaitis and Vardi [30] showed that a 0-1 law does not hold for second-order existential
logic when the first-order part is in this class (even without equality). However, it isan essentially finite class (i.e., it can only express a finite number of properties) andtherefore decidable.
The other classes of this section contain the well-known class [∀∃∀, (0, 1)], which isa subclass of the Kahr-Moore-Wang [28] class. We have recently shown that there areuntestable graph properties in this class, see Jordan and Zeugmann [27]. It is again trivial
to prove that [∀∃∀, (0, 1)] does not have the finite model property. Vedø [50] showed thata 0-1 law does not hold for second-order existential logic when the first-order part is in
this class (again, even without equality). However, as above, all classes in this section
are essentially finite and therefore decidable.
We will begin by defining property P , which is essentially the graph isomorphism
problem for undirected loop-free graphs encoded in directed graphs that may containloops. We will begin by showing in Lemma 23 that P is indistinguishable from property
Pf (cf. Definition 23 below) which is expressible in any of the prefix vocabulary classes
mentioned in Theorem 22 below. We will then show that P is not testable. Indistinguishability preserves testability and so this implies that Pf is also untestable, which will
suffice to show the following theorem.
Theorem 22. The following prefix classes are not testable:
1.
2.
3.
4.

[∀∃∀∃, (0, 1)]=[∀∃∀2 , (0, 1)]=[∀2 ∃∀, (0, 1)]=[∀3 ∃, (0, 1)]=

We define property P as follows. First, a graph that has property P must consistof an even number of vertices, of which exactly half have loops. The subgraph inducedby the vertices with loops must be isomorphic to that induced by the vertices without
loops, ignoring all loops, and there must be no edges connecting the vertices with loops
to those without loops. Finally, all edges must be undirected (i.e., an edge from x to y
implies an edge from y to x). We refer to such undirected edges as paired edges.
Definition 22. A graph G ∈ G n has P iff the following conditions are satisfied:
1. For some s, n = 2s.
2. There are exactly s vertices x satisfying E(x, x). We will refer to the set of suchvertices as H1 and to the remaining s vertices as H2 .
3. The substructure induced by H1 is isomorphic to that induced by H2 when all loops
are removed. That is, there is a bijection f from H1 to H2 such that for distinct
x, y ∈ H1 , it is true that G |= E(x, y) iff G |= E(f (x), f (y)).
4. There are no edges between H1 and H2 .
5. All edges are paired.
26

Graph isomorphism is not directly expressible in first-order logic, and so we use thefollowing encoding where the bijection f is made explicit by adding n edges between H1and H2 . This of course reduces the complexity from the level of finding an isomorphism
to the level of checking a given one, in order to achieve first-order expressivity. However,it maintains hardness for testability: essentially, our samples are too small to see any
part of the given isomorphism.
Definition 23. A graph G ∈ G n has Pf iff the following conditions are satisfied:
1. For every vertex x, if E(x, x) then there is an edge from x to exactly one y suchthat ¬E(y, y).
2. For every vertex x, if ¬E(x, x) then there is an edge from x to exactly one y suchthat E(y, y).
3. For all vertices x and y, E(x, y) iff E(y, x).
4. For all vertices x1 , x2 , x3 , x4 that are pairwise distinct, if E(x1 , x1 ), ¬E(x2 , x2 ),E(x3 , x3 ), ¬E(x4 , x4 ), E(x1 , x2 ) and E(x3 , x4 ), then E(x1 , x3 ) iff E(x2 , x4 ).
Expressing Conditions 1 and 2 as “there is at most one such y” and “there is at least
one such y,” Pf can be expressed in each of the classes [∀∃∀∃, (0, 1)]= , [∀∃∀2 , (0, 1)]= ,[∀2 ∃∀, (0, 1)]= and [∀3 ∃, (0, 1)]= .
For example, in the class [∀3 ∃, (0, 1)]= , we can express Pf byh∀x1 ∀x3 ∀x4 ∃x2 :
(E(x1 , x1 ) ↔ ¬E(x2 , x2 )) ∧ E(x1 , x2 ) ∧(E(x1 , x1 ) ↔ ¬E(x3 , x3 )) ∧ (E(x3 , x3 ) ↔ E(x4 , x4 )) ∧
E(x1 , x3 ) ∧ E(x1 , x4 ) → x3 = x4 ∧E(x1 , x3 ) → E(x3 , x1 ) ∧[E(x1 , x1 ) ∧ E(x3 , x3 ) ∧ x1 6= x3 ∧ ¬E(x4 , x4 ) ∧ E(x3 , x4 )] →i(¬E(x2 , x2 ) ∧ E(x1 , x2 ) ∧ (E(x1 , x3 ) ↔ E(x2 , x4 ))) .
To express Pf with prefixes ∀2 ∃∀ and ∀∃∀2 , it suffices to reorder the quantifiers (keeping x2 existential and x1 first). The prefix ∀∃∀∃ requires a few additional modifications.
The two properties P and Pf differ only in the edges which make the isomorphism
explicit in Pf but are forbidden in P . There are at most n such edges, none of which areloops. This suffices to prove the following.
Lemma 23. Properties P and Pf are indistinguishable.
Proof. Let ε > 0 be arbitrary and let Nε = ε−1 . Assume that G is a structure thathas property P and that #(G) > Nε . We will show that mrdist(G, Pf ) < ε.
Structure G has P and so there is a bijection f satisfying Condition 3 of Definition 22.
For all x ∈ H1 , we add the edges E(x, f (x)) and E(f (x), x) and call the result G0 .
Property Pf differs from P only in that the isomorphism is made explicit by the edges
connecting loops and non-loops, and so G0 has Pf . Indeed, it satisfies Conditions 1
and 2 of Definition 23 because G had no edges between loops and non-loops and we have27

connected each to exactly one of the other, following the bijection f . Next, G0 satisfies
Condition 3 of Definition 23 because G satisfied Condition 5 of Definition 22 and we added
only paired edges. Finally, G0 satisfies Condition 4 of Definition 23 because the edges
between loops and non-loops follow the isomorphism f from Condition 3 of Definition 22.
We have added exactly n (directed) edges, none of which are loops and so we havemrdist(G, P ) ≤ mrdist(G, G0 ) = 0 + n/n2 < ε, where the inequality holds for n > Nε .
The converse is analogous; given a G that has property Pf , we simply remove the n edges
between loops and non-loops after using them to construct the isomorphism f .
Properties P and Pf are indistinguishable. We saw in Section 3 that testability
is preserved by indistinguishability (cf. Theorem 10) and thus showing that P is not
testable suffices to prove that Pf is not testable (and therefore Theorem 22). The proof
closely follows that of Alon et al. [2]. The crucial lemma is the following, a combinationof Lemmata 7.3 and 7.4 from Alon et al. [2]. We use countH (T ) to refer to the number oftimes that a graph T occurs as an induced subgraph in H. A bipartite graph is a graphwhere we can partition the vertices into two sets H1 and H2 such that there are no edges“internal” to the partitions. That is, for all x1 , y1 ∈ H1 and x2 , y2 ∈ H2 , ¬E(x1 , y1 ) and¬E(x2 , y2 ). See Jordan and Zeugmann [26] for an explicit proof of the following, which
is somewhat technical and long.
Lemma 24 (Alon et al. [2]). There exists a constant ε0 > 0 such that for every D ∈N, there exist two undirected bipartite graphs H = H(D) and H 0 = H 0 (D), and a number t satisfying the following conditions.
1. Both H and H 0 have a bipartition into classes U1 and U2 , each of size t.
2. In both H and H 0 , for all subgraphs X with size t/3 ≤ #(X) ≤ t, there are morethan t2 /18 undirected edges between X and the remaining part of the graph.
3. The minimum degree of both H and H 0 is at least t/3.
4. dist(H, H 0 ) ≥ ε0 .
5. For all D-element graphs T , countH (T ) = countH 0 (T ).
It is worth noting that the above is for undirected, loop-free graphs. However, bipartite graphs never have loops and “undirected” in our setting results in paired edges. It iseasy to show that if two structures agree on the counts for all size D induced subgraphs,
they agree on the counts for all induced subgraphs of size at most D. This is done by
applying the following lemma inductively.
Lemma 25. Let H and H 0 be two graphs, both of size s, and let 2 < D ≤ s. If forevery graph T of size D, countH (T ) = countH 0 (T ), then for every graph T 0 of size D − 1,
countH (T 0 ) = countH 0 (T 0 ).
Proof. Assume H and H 0 satisfy the initial conditions of Lemma 25, but that there
exists a T 0 of size D − 1 such that countH (T 0 ) 6= countH 0 (T 0 ). Let C = {T | #(T ) =0
D and T contains
P T as an induced subgraph}.
00
P Note that T ∈C countH0(T ) countT (T ) = countH (T )(s − D0 + 1) and likewise for0
T ∈C countH (T ) countT (T ). We have assumed that H and H satisfy countH (T ) =countH 0 (T ) for T ∈ C, but countH (T 0 ) 6= countH 0 (T 0 ), giving a contradiction and thelemma follows.

28

Lemma 26. Property P is not testable.
Proof. Assume that P is testable. Then, there exists an ε-tester for
ε := min {ε0 /8, 1/144} ,where ε0 is the constant from Lemma 24 above. We can assume without loss of generalitythat the tester queries all edges in a random sample of D := D(ε) vertices.
Consider the graph G which contains two copies of the H = H(D) from Lemma 24,
where one of the copies is marked by loops on each vertex and there are no edges between
the copies. This graph has property P , and so the tester must accept it with probability
at least 2/3. Next, consider the graph G0 which contains one copy of H marked by loops
and one copy of H 0 , again where there are no edges between the two (induced) subgraphs.
Graph G0 is such that dist(G0 , P ) ≥ ε (cf. Lemma 27 below) and so it must be rejectedwith probability at least 2/3. Both G and G0 consist of two bipartite graphs, each ofwhich has a bipartition into two classes of size t, and so #(G) = #(G0 ) = 4t.
However, G and G0 both contain exactly the same number of each induced subgraphwith D vertices. This is because both have loops on exactly half of the vertices andthe two halves are not connected by any edges. Some of the D vertices must be in thefirst copy of H and the others in the second H (resp. H 0 ). By Lemma 25 above, H
and H 0 contain the same number of each induced subgraph with size at most D. The
tester therefore obtains any fixed sample with the same probability in G and G0 and isunable to distinguish between them. Hence, it is unable to accept G with probability 2/3
and also reject G0 with probability 2/3. This completes the proof, taking into accountLemma 27 below.

Recall that testing is easiest under the dist definition, and so Lemma 26 also implies
P is not testable under other definitions.
Lemma 27. The graph G0 is such that dist(G0 , P ) ≥ ε.
Proof. Suppose that dist(G0 , P ) < ε. Then, there is an M ∈ P such that dist(G0 , M ) <ε. Let M1 be the set of vertices with loops in M and let M2 be the set of vertices without
loops. We will refer to the subgraph induced by the vertices with loops in G0 as H andto that induced by those without loops as H 0 . Without loss of generality, assume that|M1 ∩ H| ≥ |M1 ∩ H 0 |. Then, |M1 ∩ H| ≥ t. We let α1 be the set M1 \H and α2 be
M2 \H 0 . Note that |α1 | = |α2 | and |α1 | ≤ t because |M1 ∩ H| ≥ t.
Informally, M is formed by moving the vertices α1 from H 0 to H and the vertices α2from H to H 0 , and then possibly making other changes. There are three cases, which wewill consider in order.
1. |α1 | = 0.
2. |α1 | ≥ t/3.
3. 0 < |α1 | < t/3.
If |α1 | = 0, then we can construct M from G0 without exchanging vertices between
H and H 0 , and in particular, construct H 0 from H (ignoring loops), by making less thanε(4t)2 modifications. However, dist(H, H 0 ) ≥ ε0 by Lemma 24 above and so this must29

require at least ε0 (2t)2 modifications. By definition, ε < ε0 /4 so ε(4t)2 < ε0 (2t)2 . The
first case is therefore not possible.
Recall that |α1 | ≤ t. If |α1 | ≥ t/3, then by Condition 2 of Lemma 24 there exist atleast t2 /18 undirected edges between α1 and H 0 \α1 and between α2 and H\α2 . All ofthese edges must be removed to satisfy P because each would connect a vertex with aloop to a vertex without a loop. Therefore,dist(G0 , M ) ≥4t2 /18= 1/72 .
(4t)2But, ε < 1/72 and so the second case is not possible.
Therefore, it must be that 0 < |α1 | < t/3. Here, we will show that it must be
the case that α1 and α2 are relatively far apart. If they are not far apart, then it ispossible to modify them instead of swapping them. This essentially results in the firstcase considered above. Condition 3 of Lemma 24 requires that each vertex has relatively
high degree. These edges can be either internal to α1 (resp. α2 ) or connecting α1 (α2 )with H 0 \α1 (H\α2 ). If α1 and α2 are relatively far apart, then we will see that thisforces too many edges “outside” of α1 (resp. α2 ), resulting in a similar situation to thesecond case considered above.
We have assumed that dist(G0 , M ) < ε and that we can construct M from G0 by
making less than ε(4t)2 modifications if we move α1 to H and α2 to H 0 . This entails thefollowing modifications.
1. Removing all edges connecting α1 to H 0 \α1 .
2. Removing all edges connecting α2 to H\α2 .
3. Adding any required edges between α1 and H\α2 .
4. Adding any required edges between α2 and H 0 \α1 .
5. Changing α1 , α2 , H\α2 and H 0 \α1 to their final forms.
We can assume that the total number of modifications is less than ε(4t)2 . It must
be that dist(α1 , α2 )|α1 |2 /(4t)2 + ε ≥ ε0 /4. If this does not hold, then we could firstmodify α1 to make it identical to α2 and then make H 0 identical to M2 . Next, M2 isidentical to M1 , which we could make identical to H. This would require less than ε0 (2t)2modifications, which would violate Lemma 24. Therefore,dist(α1 , α2 ) ≥16(ε0 /4 − ε)t2.
|α1 |2(4)

If both α1 and α2 are complete graphs then they cannot be far apart. Given that all
vertices in α1 (α2 is analogous) have degree at least t/3, then there must be at least|α1 |(t/3 − |α1 | + 1) + 2r
edges connecting α1 to H 0 \α1 , where r is the number of edges internal to α1 that must
be omitted to satisfy (4). The simple lower bound on r, the number of edges needed fortwo graphs with at most r edges to be dist(α1 , α2 )-far, that follows from dist(α1 , α2 ) ≤2r/|α1 |2 is sufficient. Finally, combining this with Inequality (4) yieldsr ≥ 8(ε0 /4 − ε)t2 .
30(5)The number of edges connecting α1 to H 0 \α1 is therefore, by (5), at least|α1 |(t/3 − |α1 | + 1) + 16(ε0 /4 − ε)t2 ≥ 16(ε0 /4 − ε)t2 .
All of these edges must be removed to move α1 (resp. α2 ), and sodist(G0 , M ) ≥ε016(ε0 /4 − ε)t2
=
− ε.
2
(4t)
4

We have defined ε ≤ ε0 /8 and so dist(G0 , M ) ≥ ε, a contradiction.
The cases are exhausted and so dist(G0 , P ) ≥ ε as desired.



6. Conclusions
We have focused on the testability of prefix-vocabulary classes of first-order logic,
extending work that was initiated by Alon et al. [2]. Alon et al. [2] showed that all
properties of undirected, loop-free graphs expressible in first-order sentences with quantifier pattern ∃∗ ∀∗ are testable, while there exists an untestable property expressible
with quantifier pattern ∀∗ ∃∗ . Their proof of the latter result implies upper bounds oftwelve, five and seventeen for the minimum number of universal, existential and total
quantifiers, respectively, sufficient to express an untestable property. One of our goals
was to optimize these bounds and find the minimum number of universal and existential
quantifiers, as well as quantifiers in total, sufficient to express an untestable property.
Our results imply that these minima are two universal, one existential and three total
quantifiers, respectively. In addition, we remove the restriction to undirected, loop-freegraphs and focus on relational structures.
Our main results are as follows. First, we proved that all properties expressible in
Ackermann’s class with equality ([∃∗ ∀∃∗ , all ]= ) are testable. Then, we extended thepositive result of Alon et al. [2] from undirected, loop-free graphs to relational structuresby using a result from Austin and Tao [8]. This answers a question of Fischer [16] on thetestability of hypergraph properties expressible with quantifier pattern ∃∗ ∀∗ , althoughmuch of the work for this case is by Austin and Tao [8]. Finally, we simplified theuntestable property of Alon et al. [2] and showed that there are untestable properties of
directed graphs expressible with quantifier prefixes ∀3 ∃, ∀2 ∃∀, ∀∃∀2 , and ∀∃∀∃. Recently,
we have shown in Jordan and Zeugmann [27] that there are untestable properties of
directed graphs expressible with prefix ∀∃∀, improving on three of these prefixes.
The current classification of prefix-vocabulary classes for testability is the following.
• Testable classes
1. Monadic first-order logic: [all , (ω)]= .
2. Ackermann’s class with equality: [∃∗ ∀∃∗ , all ]= .
3. Ramsey’s class: [∃∗ ∀∗ , all ]= .
• Untestable classes
1. [∀3 ∃, (0, 1)]= .
2. [∀∃∀, (0, 1)]= .
31

It is interesting to compare this classification for testability with known (complete)classifications for other properties. For example, the current classification for testability
is consistent with the classifications for the finite model property (see, e.g., Chapter 6 ofBörger et al. [11]), for docility17 (see Kolaitis and Vardi [31]) and for 0-1 laws for fragments of existential second-order logic (see Kolaitis and Vardi [31]). These classifications
may be helpful in providing guidance in the classification for testability.
This similarity between classifications may indicate a deeper connection between these
seemingly distinct properties. We would like to know which (if any) of the traditionalclassifications coincides with the classification for testability, and hope to understand theconnections between testability and other properties of prefix classes.
As concrete open problems, we are especially interested in the testability of [∀∃∀, (0, 1)]
and [∀3 ∃, (0, 1)] (without equality) and variants of the Gödel class (i.e., classes whose
prefix contain at least ∀2 ∃). Determining the testability of these classes may suffice tocomplete the classification for the special case of predicate logic with equality.
There are also many possible variations of the classification for testability. For example, one could be more interested in classes which are constructively testable, i.e., where
it is possible to compute an ε-tester given ε and a formula from the class. However,in the present paper we are fortunate that many of the possible classifications coincide.
Namely, all of our positive results are for constructive (and therefore uniform) testability
in the most-restricted model (Tmr ) that we consider, while all of the negative results holdeven for non-uniform testability in the least-restricted model (T ).
Acknowledgments
We would like to thank an anonymous referee from LATA for significantly improving
Theorem 22 in a preliminary version of this paper by eliminating one variable from eachprefix, adding ∀∃∀∃ and simplifying the example following Definition 23.
We also thank the anonymous referees for their careful reading and valuable comments.
References[1] Wilhelm Ackermann. Über die Erfüllbarkeit gewisser Zählausdrücke. Math. Annalen, 100:638–649,
1928.
[2] Noga Alon, Eldar Fischer, Michael Krivelevich, and Mario Szegedy. Efficient testing of large graphs.
Combinatorica, 20(4):451–476, 2000.
[3] Noga Alon, Eldar Fischer, Ilan Newman, and Asaf Shapira. A combinatorial characterization of thetestable graph properties: It’s all about regularity. In STOC ’06: Proceedings of the 38th Annual
ACM Symposium on Theory of Computing, pages 251–260, New York, NY, USA, 2006. ACM.
[4] Noga Alon, Michael Krivelevich, Ilan Newman, and Mario Szegedy. Regular languages are testablewith a constant number of queries. SIAM J. Comput., 30(6):1842–1862, 2001.
[5] Noga Alon and Asaf Shapira. Homomorphisms in graph property testing. In M. Klazar, J. Kratochvı́l, M. Loebl, J. Matoušek, R. Thomas, and P. Valtr, editors, Topics in Discrete Mathematics,
volume 26 of Algorithms and Combinatorics, pages 281–313. Springer, 2006.
[6] Noga Alon and Asaf Shapira. A characterization of the (natural) graph properties testable with
one-sided error. SIAM J. Comput., 37(6):1703–1727, 2008.

17 A class is said to be docile (or decidable for finite satisfiability) if given an arbitrary formula fromthe class, one can decide if there exists a finite model of the property.

32

[7] Noga Alon and Asaf Shapira. A separation theorem in property testing. Combinatorica, 28(3):261–
281, 2008.
[8] Tim Austin and Terence Tao. On the testability and repair of hereditary hypergraph properties.
Random Struct. Algorithms, 36(4):373–463, 2010.
[9] Paul Bernays and Moses Schönfinkel. Zum Entscheidungsproblem der mathematischen Logik. Math.
Annalen, 99(1):342–372, 1928.
[10] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications tonumerical problems. J. of Comput. Syst. Sci., 47(3):549–595, 1993.
[11] Egon Börger, Erich Grädel, and Yuri Gurevich. The Classical Decision Problem. Springer-Verlag,
1997.
[12] J. Richard Büchi. Weak second-order arithmetic and finite-automata. Z. Math. Logik Grundlagen
Math., 6:66–92, 1960.
[13] Hana Chockler and Orna Kupferman. ω-regular languages are testable with a constant number ofqueries. Theoret. Comput. Sci., 329(1-3):71–92, 2004.
[14] Christian Fermüller and Gernot Salzer. Ordered paramodulation and resolution as decision procedure. In Logic Programming and Automated Reasoning,4th International Conference, LPAR’93,
St. Petersburg, Russia, July 13-20, 1993, Proceedings, volume 698 of Lecture Notes in Computer
Science, pages 122–133. Springer, 1993.
[15] Eldar Fischer. The art of uninformed decisions. Bulletin of the European Association for TheoreticalComputer Science, 75:97–126, October 2001. Columns: Computational Complexity.
[16] Eldar Fischer. Testing graphs for colorability properties. Random Struct. Algorithms, 26(3):289–
309, 2005.
[17] Eldar Fischer, Arie Matsliah, and Asaf Shapira. Approximate hypergraph partitioning and applications. Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science,
FOCS 2007, pages 579–589, 2007.
[18] Rūsiņš Freivalds. Fast probabilistic algorithms. In Mathematical Foundations of Computer Science
1979, Proceedings, 8th Symposium, Olomouc, Czechoslovakia, September 3-7, 1979, volume 74 of
Lecture Notes in Computer Science, pages 57–69. Springer-Verlag, 1979.
[19] John Gill. Computational complexity of probabilistic Turing machines. SIAM J. Comput., 6(4):675–
695, 1977.
[20] O. Goldreich and D. Ron. Property testing in bounded degree graphs. Algorithmica, 32:302–343,
2002.
[21] Oded Goldreich. Introduction to testing graph properties. Technical Report TR10-082, Electronic
Colloquium on Computational Complexity (ECCC), May 2010.
[22] Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learningand approximation. J. ACM, 45(4):653–750, 1998.
[23] W. T. Gowers. Hypergraph regularity and the multidimensional Szemerédi theorem. Ann. of Math.
(2), 166(3):897–946, 2007.
[24] Erich Grädel. Satisfiability of formulae with one ∀ is decidable in exponential time. Arch. Math.
Logic, 29:256–276, 1990.
[25] Yoshiyasu Ishigami. Removal lemma for infinitely-many forbidden hypergraphs and property testing. Preprint, available on arXiv.org as arXiv:math/0612669v2, 2008.
[26] Charles Jordan and Thomas Zeugmann. Contributions to the classification for testability: Four
universal and one existential quantifier. Technical Report TCS-TR-A-09-39, Hokkaido University,
Division of Computer Science, November 2009.
[27] Charles Jordan and Thomas Zeugmann. Untestable properties in the Kahr-Moore-Wang class. In
Lev Beklemishev and Ruy de Queiroz, editors, Logic, Language, Information and Computation,
18th International Workshop, WoLLIC 2011, Philadelphia, USA, May 2011, Proceedings, volume6642 of Lecture Notes in Computer Science, pages 176–186. Springer, 2011.
[28] A. S. Kahr, Edward F. Moore, and Hao Wang. Entscheidungsproblem reduced to the ∀∃∀ case.
Proc. Nat. Acad. Sci. U.S.A., 48:365–377, 1962.
[29] P. Kolaitis and M. Vardi. The decision problem for the probabilities of higher-order properties.
In STOC ’87: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages
425–435, New York, NY, USA, 1987. ACM.
[30] Phokion G. Kolaitis and Moshe Y. Vardi. 0-1 laws and decision problems for fragments of secondorder logic. Inf. Comput., 87(1-2):302–338, 1990.
[31] Phokion G. Kolaitis and Moshe Y. Vardi. 0-1 laws for fragments of existential second-order logic: A
survey. In Mogens Nielsen and Branislav Rovan, editors, Mathematical Foundations of Computer
Science 2000, 25th International Symposium, MFCS 2000, Bratislava, Slovakia, August/September

33

2000, Proceedings, volume 1893 of Lecture Notes in Computer Science, pages 84–98. Springer, 2000.
[32] K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro. Computability by probabilistic machines.
In C.E. Shannon and J. McCarthy, editors, Automata Studies, pages 183–212. Princeton University
Press, Princeton, NJ, 1956.
[33] Harry R. Lewis. Complexity results for classes of quantificational formulas. J. Comput. Syst. Sci.,
21(3):317–353, 1980.
[34] Leopold Löwenheim. Über Möglichkeiten im Relativkalkül. Math. Annalen, 76:447–470, 1915.
[35] Robert McNaughton and Seymour Papert. Counter-Free Automata. M.I.T. Press, 1971.
[36] Eugenio Omodeo and Alberto Policriti. The Bernays-Schönfinkel-Ramsey class for set theory:
Semidecidability. J. Symbolic Logic, 75(2):459–480, June 2010.
[37] Michal Parnas and Dana Ron. Testing the diameter of graphs. Random Struct. Algorithms,
20(2):165–183, 2002.
[38] F. P. Ramsey. On a problem of formal logic. Proc. London Math. Soc. (2), 30:264–286, 1930.
[39] Vojtěch Rödl and Mathias Schacht. Generalizations of the removal lemma. Combinatorica,
29(4):467–501, 2009.
[40] Vojtěch Rödl and Mathias Schacht. Regular partitions of hypergraphs: Regularity lemmas. Combin.
Probab. Comput., 16:833–885, 2007.
[41] Vojtěch Rödl and Mathias Schacht. Regularity lemmas for graphs. Preprint, available at
http://www.math.uni-hamburg.de/home/schacht/preprints/reg survey.pdf, 2010.
[42] Dana Ron. Property testing. In Sanguthevar Rajasekaran, Panos M. Pardalos, John H. Reif, andJosé Rolim, editors, Handbook of Randomized Computing, volume II, chapter 15, pages 597–649.
Kluwer Academic Publishers, 2001.
[43] Dana Ron. Property testing: A learning theory perspective. Found. Trends Mach. Learn., 1(3):307–
402, 2008.
[44] Dana Ron. Algorithmic and analysis techniques in property testing. Found. Trends Theor. Comput.
Sci., 5(2):73–205, 2009.
[45] Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications toprogram testing. SIAM J. Comput., 25(2):252–271, 1996.
[46] Saharon Shelah. Decidability of a portion of the predicate calculus. Israel J. Math., 28(1-2):32–44,
1977.
[47] Th. Skolem. Untersuchungen über die Axiome des Klassenkalküls und über Produktations und Summationsprobleme, welche gewisse Klassen von Aussagen betreffen. Videnskapsselskapets skrifter, I.
Matematisk-naturvidenskabelig klasse, (3):37–71, 1919.
[48] Th. Skolem. Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit
mathematischer Sätze nebst einem Theorem über dichte Mengen. Videnskapsselskapets skrifter, I.
Matematisk-naturvidenskabelig klasse, (4):1–26, 1920.
[49] Terence Tao. A variant of the hypergraph removal lemma. J. Comb. Theory Ser. A, 113(7):1257–
1280, 2006.
[50] Anne Vedø. Asymptotic probabilities for second-order existential Kahr-Moore-Wang sentences. J.
Symbolic Logic, 62(1):304–319, March 1997.

34