First-Order Logic with Equicardinality in Random Graphs

Haber, Simi; Hershko, Tal; Mirabi, Mostafa; Shelah, Saharon

doi:10.4230/LIPIcs.CSL.2025.12

First-Order Logic with Equicardinality in Random Graphs

Simi Haber

Bar-Ilan University, Ramat Gan, Israel Tal Hershko

California Institute of Technology, Pasadena, CA, USA Mostafa Mirabi

Taft School, Watertown, CT, USA Saharon Shelah

Hebrew University of Jerusalem, Israel

Abstract

We answer a question of Blass and Harary about the validity of the zero-one law in random graphs for extensions of first-order logic (FOL). For a given graph property $P$ , the Lindström extension of FOL by $P$ is defined as the minimal (regular) extension of FOL able to express $P$ . For several graph properties $P$ (e.g. Hamiltonicity), it is known that the Lindström extension by $P$ is also able to interpret a segment of arithmetic, and thus strongly disobeys the zero-one law. Common to all these properties is the ability to express the Härtig quantifier, a natural extension of FOL testing if two definable sets are of the same size. We prove that the Härtig quantifier is sufficient for the interpretation of arithmetic, thus providing a general result which implies all known cases of Lindström extensions which are able to interpret a segment of arithmetic.

Keywords and phrases:

finite model theory, first-order logic, monadic second-order logic, random graphs, zero-one laws, generalized quantifiers, equicardinality

Funding:

Saharon Shelah: Research partially supported by the grant “Independent Theories” NSF-BSF, (BSF 3013005232) and by NSF grant no: DMS 1833363. Paper 1250 on Shelah’s publication list.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Finite Model Theory ; Mathematics of computing

\rightarrow

Random graphs

DOI:

10.4230/LIPIcs.CSL.2025.12

Event:

33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)

Editors:

Jörg Endrullis and Sylvain Schmitz

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

In this paper we study the Erdös-Rényi binomial random graph model $G(n,p)$ . Recall that $G(n,p)$ is defined as a probability distribution over the set of all labeled (simple) graphs with the vertex set $[n]:=\left\{1,2,\dots,n\right\}$ , by requiring that each of the $\binom{n}{2}$ potential edges appears with probability $p$ and independently of all other edges. Note that $G\left(n,\frac{1}{2}\right)$ is the uniform distribution over the set of $2^{\binom{n}{2}}$ labeled graphs with vertex set $[n]$ .

In what follows, we use $\mathbb{P}(\cdot)$ to denote probabilities and $\mathbb{E}(\cdot)$ to denote expected values.

1.1 Background and Previous Results

The study of random graphs was pioneered by Erdös and Rényi in the 1960s, originating from two seminal papers [9, 10]. One of the earliest phenomena recognized in their work is the fact that many natural graph properties – including connectivity, Hamiltonicity, planarity, $k$ -colorability for a fixed $k$ and containing $H$ as a subgraph for a fixed graph $H$ – hold either in almost all graphs, or in almost none of them. Formally, let $P$ be a graph property and fix $p\in(0,1)$ . We say that $P$ holds asymptotically almost surely (a.a.s. for short) in $G(n,p)$ if

\lim_{n\rightarrow\infty}\mathbb{P}\left(G(n,p)\ \mathrm{satisfies}\ P\right)=1

and that $P$ holds asymptotically almost never (a.a.n. for short) in $G(n,p)$ if

\lim_{n\rightarrow\infty}\mathbb{P}\left(G(n,p)\ \mathrm{satisfies}\ P\right)=0.

Then, for example, for every fixed $p\in(0,1)$ ,

$\blacksquare$

Connectivity holds a.a.s. in $G(n,p)$ .
$\blacksquare$

Hamiltonicity holds a.a.s. in $G(n,p)$ .
$\blacksquare$

Planarity holds a.a.n. in $G(n,p)$ .
$\blacksquare$

For every fixed $k\in\mathbb{N}$ , $k$ -colorability holds a.a.n. in $G(n,p)$ .
$\blacksquare$

For every fixed finite graph $H$ , the property of containing $H$ as a subgraph holds a.a.s. in $G(n,p)$ .

As a reference, see any introductory text in random graphs, e.g. [19].

The observation that many natural graph properties hold either a.a.s. or a.a.n. in $G(n,p)$ motivates the following definition.

Definition 1.

Let $\mathcal{A}$ be a set of graph properties. We say that $\mathcal{A}$ obeys the zero-one law in $G(n,p)$ if for every property $P\in\mathcal{A}$ ,

\lim_{n\rightarrow\infty}\mathbb{P}\left(G(n,p)\ \mathrm{satisfies}\ P\right)% \in\left\{0,1\right\}.

With this definition, we may formulate the following informal observation: if $\mathcal{A}$ is a set of natural graph properties then $\mathcal{A}$ obeys the zero-one law. This is not a formal statement, due to the lack of a formal definition of a “natural graph property”.

From a logician’s point of view, a natural class of graph properties is the class $\mathcal{FO}$ of first-order properties. These are properties which can be expressed as a sentence in the first-order language of graphs, whose signature consists of a single binary relation $\sim$ representing adjacency.¹¹1We shall often identify logical sentences with the properties they describe. Indeed, a classic result, proven independently by Glebskii et al. [13] and Fagin [11], states that $\mathcal{FO}$ obeys the zero-one law in $G(n,p)$ .

Theorem 2 (GKLT-Fagin).

Fix $p\in(0,1)$ . Then the set of first-order graph properties $\mathcal{FO}$ obeys the zero-one law in $G(n,p)$ .

The GKLT-Fagin zero-one law pioneered the study of random graphs with tools of mathematical logic. This point of view has proved to be doubly beneficial, teaching us about the properties of the underlying random graph, and also about the expressive power of logical languages. It is therefore considered an important part of finite model theory.

The GKLT-Fagin zero-one law deals with first-order properties. However, many graph properties which are considered natural – including connectivity, Hamiltonicity and $k$ -colorability – are not first-order. On the other extreme, the class $\mathcal{SO}$ of second-order graph properties contains all the properties listed above, but fails to obey the zero-one law. For example, as noted by Fagin [11, p. 55], the property of having an even number of vertices is second-order, but clearly has no limiting probability.

It is therefore natural to ask for extensions of first-order logic which have a stronger expressive power on the one hand, but still obey the zero-one law on the other hand. This question was posed by Blass and Harary [2, Section 5]. In their discussion, they suggest several guiding questions:

1.

Is there an extension of first order logic which is strong enough to express Hamiltonicity and rigidity (asymmetry), but still obeys the zero-one law?
2.

What about monadic second-order logic? It cannot express Hamiltonicity, but it is still an important extension of first-order logic – does it obey the zero-one law?
3.

Can something be done with “more exotic languages”, for example with equicardinality quantifiers?

These questions have been studied in many papers. We dedicate the following sections to explain the precise meaning of these questions in more detail and review previous results. Our review is not exhaustive; for a broader survey of results in this field, we refer the reader to [4] and [29]. For a more focused discussion of results directly related to our work, see [6] and [16].

Lindström Extensions

Suppose we are interested in an extension of $\mathcal{FO}$ which includes a certain graph property $P$ . One option is to simply take the union $\mathcal{FO}\cup\left\{P\right\}$ . However, this set of properties clearly lacks a basic notion of closure. To avoid such trivialities, we focus on regular extensions. A regular logic is a logic that is closed under negation, conjunction, existential quantification, relativization and substitution (see [7] for more details). We then have the following definition.

Definition 3.

Let $P$ be a graph property. The Lindström extension of $\mathcal{FO}$ by $P$ , denoted $\mathcal{FO}[P]$ , is the minimal regular extension of $\mathcal{FO}$ that includes $P$ .

The term Lindström extension comes from the fact that $\mathcal{FO}[P]$ can be constructed by adjoining the Lindström quantifier of $P$ , denoted $Q_{P}$ and defined as follows [26, 27, 7].

Definition 4.

Let $P$ be a graph property. Its Lindström quantifier $Q_{P}$ is defined as follows.

$\blacksquare$

Syntactically, given a formula $\varphi_{V}(x,\vec{z})$ with $x,\vec{z}$ as free variables and a formula $\varphi_{E}(x,y,\vec{z})$ with $x,y,\vec{z}$ as free variables, it returns the formula $Q_{P}x,y\left(\varphi_{V}(x,\vec{z}),\varphi_{E}(x,y,\vec{z})\right)$ in which $x, y$ are quantified and $\vec{z}$ are free.
$\blacksquare$

Semantically, the truth value of this formula is defined as follows. Let $G=(V,E)$ be a graph and let $\vec{a}$ be a vector of vertices, of the same length as $\vec{z}$ . Let $V_{0}=\left\{v\in V:G\models\varphi_{V}(v,\vec{a})\right\}$ and let $E_{0}$ be the set of pairs $\left\{u,v\right\}$ with $u,v\in V_{0}$ such that $G\models\varphi(u,v,\vec{a})$ or $G\models\varphi(v,u,\vec{a})$ . Then

$G\models_{\vec{z}=\vec{a}}Q_{P}x,y\left(\varphi_{V}(x,\vec{z}),\varphi_{E}(x,y% ,\vec{z})\right)\iff G_{0}=(V_{0},E_{0})\;{\rm satisfies}\;P.$

It can be shown that $\mathcal{FO}[P]$ is the same as the closure of $\mathcal{FO}$ under quantification with $Q_{P}$ (see [8] for more details).

We can now suggest a more precise formulation of the first question of Blass and Harary: do the Lindström extensions of $\mathcal{FO}$ by Hamiltonicity and by rigidity obey the zero-one law? The answer was given by Dawar and Grädel ([6], also in [5]).

Theorem 5 (Dawar-Grädel).

Fix $p\in(0,1)$ .

1.

The Lindström extension $\mathcal{FO}[\mathrm{Rigidity}]$ obeys the zero-one law in $G(n,p)$ .
2.

The Lindström extension $\mathcal{FO}[\mathrm{Hamiltonicity}]$ does not obey the zero-one law in $G(n,p)$ .

The latter part of the theorem was demonstrated by encoding Parity – the property of having an even number of vertices. It is worth noting, however, that Parity still allows for the possibility of a modular limit law, as shown by Kolaitis and Kopparty [25]. A far more extreme violation of the zero-one law occurs through the interpretation of a segment of arithmetic, a concept we will elucidate in the subsequent section.

Arithmetization

The second question of Blass and Harary, regarding monadic second order logic $\mathcal{MSO}$ , was answered much earlier than the first. The answer was given by Kaufmann and Shelah [23], who proved that $\mathcal{MSO}$ disobeys the zero-one law in a very strong sense. Their main result is that $\mathcal{MSO}$ can interpret arithmetic in $G(n,p)$ , which roughly means that there are sentences in $\mathcal{MSO}$ that define an arithmetic structure on (a subset of) the vertex set. If a language $\mathcal{L}$ can interpret a segment of arithmetic then it is, in a sense, the farthest possible from obeying the zero-one law. Indeed, in such a case, it is possible to construct sentences $\varphi\in\mathcal{L}$ whose probability sequence $\left\{\mathbb{P}\left(G(n,p)\models\varphi\right)\right\}_{n=1}^{\infty}$ exhibits different kinds of complex behaviors. We shall demonstrate this fact shortly by constructing a sentence $\varphi\in\mathcal{L}$ whose probability sequence alternates between near-zero values and near-one values, and hence has no limit.

The definition of interpreting arithmetic given below is somewhat weaker than what Kaufmann and Shelah prove for $\mathcal{MSO}$ , but describes a more general and more common type of arithmetization results (see review below). In particular, it includes the main result of this paper, Theorem 14).

Recall that for $n\in\mathbb{N}$ we denote $[n]=\left\{1,2,\dots,n\right\}$ . We begin by defining the language $\mathcal{SO}[\mathrm{Arith}]$ as the second-order language of arithmetic, where:

$\blacksquare$

Addition $+$ and multiplication $\times$ are defined as ternary relations (so, for example, we write $+(a,b,c)$ instead of $a+b=c$ ). This is a convenient choice when working with finite models such as $[n]$ , where addition and multiplication are restricted.
$\blacksquare$

Second order quantification is done only over unary and binary relations.

Example 6.

We can construct a formula in $\mathcal{SO}[\mathrm{Arith}]$ with free variables $x, y$ expressing the property $y=2^{x}$ by the following steps.

$\blacksquare$

Begin by asserting the existence of a binary relation: $\exists\mathrm{Exp}^{2}$ .
$\blacksquare$

Require that it is single-valued:

$\forall a\forall b\forall b^{\prime}\left({\rm Exp}(a,b)\wedge{\rm Exp}(a,b^{% \prime})\rightarrow b=b^{\prime}\right).$
$\blacksquare$

Define the relation inductively:

$\mathrm{Exp}(0,1)\wedge\forall a\forall b\forall a^{\prime}\forall b^{\prime}% \left(\mathrm{Exp}(a,b)\wedge+(a,1,a^{\prime})\wedge\times(b,2,b^{\prime})% \rightarrow\mathrm{Exp}(a^{\prime},b^{\prime})\right).$
$\blacksquare$

Finally, require $\mathrm{Exp}(x,y)$ .

For every $n\in\mathbb{N}$ , the set $[n]$ admits an arithmetic structure with the standard addition and multiplication (restricted to $[n]$ ). Given an interval $[a,b]\subseteq\mathbb{R}$ and a sentence $\varphi\in\mathcal{SO}[\mathrm{Arith}]$ , we say that:

1.

$\varphi$ holds in $[a,b]$ if $[n]\models\varphi$ for every $n\in[a,b]\cap\mathbb{N}$ .
2.

$\varphi$ is constant on $[a,b]$ if $\varphi$ holds in $[a,b]$ or $\neg\varphi$ holds in $[a,b]$ .

Finally, let us say that a function $f\colon\mathbb{N}\rightarrow\mathbb{N}$ is finite-to-one if for every $m\in\mathbb{N}$ , the inverse image $f^{-1}(m)$ is a non-empty finite set. Note that if $f$ is finite-to-one then $f$ is onto and $\lim_{n\rightarrow\infty}f(n)=\infty$ . Examples include $f(n)=\left\lfloor\sqrt{n}\right\rfloor$ and $f(n)=\left\lfloor\log\log n\right\rfloor$ .

Definition 7 (Arithmetization).

Let $\mathcal{L}$ be a logical language whose signature includes the binary relation symbol $\sim$ , representing adjacency. Fix a parameter $p\in(0,1)$ , constants $0<c_{1}\leq c_{2}$ and a finite-to-one function $f\colon\mathbb{N}\rightarrow\mathbb{N}$ . We say that $\mathcal{L}$ can interpret a segment of arithmetic in $G(n,p)$ with constants $c_{1},c_{2}$ and a scaling function $f(n)$ if the following holds. For every sentence $\varphi\in\mathcal{SO}[\mathrm{Arith}]$ there exists a sentence $\varphi^{*}\in\mathcal{L}$ such that, given a sequence $\left\{n_{k}\right\}_{k=1}^{\infty}$ with $\lim_{k\rightarrow\infty}n_{k}=\infty$ such that $\varphi$ is constant on $[c_{1}f(n_{k}),c_{2}f(n_{k})]$ for every $k$ , we have

\lim_{k\rightarrow\infty}\mathbb{P}\left(G(n_{k},p)\models\varphi^{*}\iff% \varphi\;{\rm holds}\;{\rm in}\;\left[c_{1}f(n_{k}),c_{2}f(n_{k})\right]\right% )=1.

To motivate the definition, we remark that it reflects a general strategy of encoding arithmetic in random graphs, which can be roughly summarized as follows:

$\blacksquare$

Restrict to a certain ${\cal L}$ -definable subset $S\subseteq[n]$ of size $\left|S\right|\in\left[c_{1}f(n),c_{2}f(n)\right]$ .
$\blacksquare$

Use the structure of the random graph to encode unary and binary relations and an arithmetic structure on $S$ .
$\blacksquare$

Given a sentence $\varphi\in\mathcal{SO}[\mathrm{Arith}]$ , use the encoded structure to convert it into a sentence $\varphi^{*}\in\mathcal{L}$ asserting that $\varphi$ is satisfied in $S$ .

Proposition 8.

Let ${\cal L}$ be a language that can interpret a segment of arithmetic in $G(n,p)$ . Then there exists a sentence $\psi\in{\cal L}$ such that the limit $\lim_{n\rightarrow\infty}\mathbb{P}\left(G(n,p)\models\psi\right)$ does not exist. In particular, ${\cal L}$ disobeys the zero-one law.

Proof.

Let $0<c_{1}\leq c_{2}$ and $f(n)$ be the constants and the scaling function for ${\cal L}$ , as in Definition 7. Let $N=\left\lceil\max\left\{\left|\log_{2}c_{1}\right|,\left|\log_{2}c_{2}\right|% \right\}\right\rceil+1$ . It is straightforward to construct a sentence $\varphi\in\mathcal{SO}[\mathrm{Arith}]$ such that for every $m\in\mathbb{N}$ , $[m]\models\varphi$ if and only if

\left\lfloor\log_{2}m\right\rfloor\equiv k\mod 8N\;\;\;\mathrm{for}\;k\in\left% \{-N,-N+1,\dots,N-1,N\right\}.

Let $\left\{n_{k}\right\}_{k=1}^{\infty}$ be a sequence satisfying $f(n_{k})=2^{4Nk}$ for every $k$ . Such a sequence exists and approaches $\infty$ , because $f$ is finite-to-one. We claim that $\varphi$ is constant on each interval $[c_{1}f(n_{k}),c_{2}f(n_{k})]$ . Indeed, for every $m\in\left[c_{1}f(n_{k}),c_{2}f(n_{k})\right]\cap\mathbb{N}$ we have

	$\displaystyle\log_{2}m$	$\displaystyle\in$	$\displaystyle\left[\log_{2}c_{1}+4Nk,\log_{2}c_{2}+4Nk\right],$
	$\displaystyle\left\lfloor\log_{2}m\right\rfloor$	$\displaystyle\in$	$\displaystyle\left[4Nk-N,4Nk+N\right]$		(1)

where (1) follows from our choice of $N$ . When $k$ is even, (1) implies $[m]\models\varphi$ . When $k$ is odd, (1) implies $[m]\not\models\varphi$ .

Now let $\varphi^{*}\in{\cal L}$ as in Definition 7. Then the probabilities sequence $\left\{\mathbb{P}\left(G(n_{k},p)\models\varphi^{*}\right)\right\}_{k=1}^{\infty}$ converges to $1$ on even values of $k$ and converges to $0$ on odd values of $k$ . This implies that the limit $\lim_{n\rightarrow\infty}\mathbb{P}\left(G(n,p)\models\varphi^{*}\right)$ does not exist. $\hfill\blacktriangleleft$

Going back to Kaufmann and Shelah, we can now formulate the following consequence of [23] (which follows from Theorem 1 and the closing remark).

Theorem 9 (Kaufmann-Shelah).

Fix $p\in(0,1)$ . Then $\mathcal{MSO}$ can interpret a segment of arithmetic in $G(n,p)$ (with constants $c_{1}=c_{2}=1$ and scaling function $f(n)=\left\lfloor\sqrt{n}\right\rfloor$ ).

As explained, this result provides a strongly negative answer to the second question of Blass and Harary.

In [16], Haber and Shelah prove an arithmetization result for the Lindström extension of Hamiltonicity, thus strengthening Part 2 of Theorem 5.

Theorem 10 (Haber-Shelah).

Fix $p\in(0,1)$ . Then $\mathcal{FO}[\mathrm{Hamiltonicity}]$ can interpret a segment of arithmetic in $G(n,p)$ (with scaling function $f(n)=\Omega(\log\log\log n)$ ).

As for other graph properties, Haber and Shelah also proved in [16] that the zero-one law holds for the Lindström extensions $\mathcal{FO}[\mathrm{Connectivity}]$ and $\mathcal{FO}[k\mathrm{-colorability}]$ for every fixed $k$ . These results also follow from a more general theorem by Dawar and Grädel [6], which also implies that the zero-one law holds for $\mathcal{FO}[\mathrm{Planarity}]$ . On the other hand, there are additional graph properties $P$ for which it is known that $\mathcal{FO}[P]$ can interpret a segment of arithmetic. These include regularity, the existence of a perfect matching [15] and the existence of a $C_{4}$ -factor [14]. It is noteworthy that Haber and Shelah [16] employed a strategy to encode the Rescher plurality quantifier [28], resulting in a more expressive logic. In contrast, our finding that equicardinality alone suffices to interpret a segment of arithmetic is unexpected and significantly stronger.

Equicardinality Quantifiers

Common to all the Lindström extensions of $\mathcal{FO}$ which are known to be able to interpret a segment of arithmetic is the ability to express the equicardinality quantifier, also known as the Härtig quantifier [17], which we denote by $Q_{=}$ . This quantifier allows for testing if two definable sets are of the same size.

Definition 11.

The Härtig quantifier $Q_{=}$ is defined as follows.

$\blacksquare$

Syntactically, given formulas $\varphi(x,\vec{z})$ and $\psi(x,\vec{z})$ with free variables $x,\vec{z}$ , it returns a formula $Q_{=}x\left(\varphi(x,\vec{z}),\psi(x,\vec{z})\right)$ in which $x$ is quantified and $\vec{z}$ are free.
$\blacksquare$

Semantically, the truth value of this formula is defined as follows. Let $G=(V,E)$ be a finite graph and let $\vec{a}$ be a vector of vertices, of the same length as $\vec{z}$ . Then

$G\models_{\vec{z}=\vec{a}}Q_{=}x\left(\varphi(x,\vec{z}),\psi(x,\vec{z})\right% )\iff\left|\left\{v\in V:G\models\varphi(v,\vec{a})\right\}\right|=\left|\left% \{v\in V:G\models\psi(v,\vec{a})\right\}\right|.$

The following proposition shows that $Q_{=}$ is indeed expressible in $\mathcal{FO}[{\mathrm{Hamiltonicity}}]$ . Similar arguments show that $Q_{=}$ is also expressible in the other Lindström extensions of $\mathcal{FO}$ listed above that are known to be able to interpret a segment of arithmetic.

Proposition 12.

Let $\varphi(x,\vec{z})$ and $\psi(x,\vec{z})$ be formulas in $\mathcal{FO}[{\mathrm{Hamiltonicity}}]$ with free variables $x,\vec{z}$ . Then the formula $Q_{=}x\left(\varphi(x,\vec{z}),\psi(x,\vec{z})\right)$ is also expressible in $\mathcal{FO}[{\mathrm{Hamiltonicity}}]$ .

Proof.

Fix a graph $G=(V,E)$ and a vector $\vec{a}$ of vertices. Let $A=\left\{x\in V:G\models\varphi(x,\vec{a})\right\}$ and $B=\left\{x\in V:G\models\psi(x,\vec{a})\right\}$ . Also let $\varphi^{\prime}(x,\vec{z})=\varphi(x,\vec{z})\wedge\neg\psi(x,\vec{z})$ (which defines the set $A\setminus B$ ) and $\psi^{\prime}(x,\vec{z})=\psi(x,\vec{z})\wedge\neg\varphi(x,\vec{z})$ (which defines the set $B\setminus A$ ). Define $\varphi_{V}(x,\vec{z})=\varphi^{\prime}(x,\vec{z})\vee\psi^{\prime}(x,\vec{z})$ and $\varphi_{E}(x,y,\vec{z})=\varphi^{\prime}(x,\vec{z})\wedge\psi^{\prime}(y,\vec% {z})$ . Consider the graph $G_{0}=(V_{0},E_{0})$ defined by these formulas, as in Definition 4. Note that $G_{0}$ is the complete bipartite graph with sides $A\setminus B$ and $B\setminus A$ . Recall that a complete bipartite graph is Hamiltonian if and only if its sides are of the same size. Therefore

G\models_{\vec{z}=\vec{a}}Q_{\mathrm{Ham}}x,y\left(\varphi_{V}(x,\vec{z}),% \varphi_{E}(x,y,\vec{z})\right)\iff\left|A\setminus B\right|=\left|B\setminus A% \right|\\ \iff\left|A\right|=\left|B\right|\iff G\models_{\vec{z}=\vec{a}}Q_{=}x\left(% \varphi(x,\vec{z}),\psi(x,\vec{z})\right).

$\hfill\blacktriangleleft$

Let $\mathcal{FO}[Q_{=}]$ denote the closure of $\mathcal{FO}$ under quantification with $Q_{=}$ . This is a natural extension of first-order logic which has been studied quite extensively. For a survey on equicardinality quantifiers in the context of general model theory and abstract logic, see [18]. Equicardinality quantifiers have also been studied in the context of zero-one laws and convergence laws. In [12], Fayolle, Grumbach and Tollu studied zero-one laws for first-order logic enriched by generalized quantifiers, including Härtig quantifiers (equicardinality quantifiers) and Rescher quantifiers (expressing inequalities of cardinalities). Their results show that the zero-one law does hold for $\mathcal{FO}^{*}[Q_{=}]$ , defined in the same way as $\mathcal{FO}[Q_{=}]$ but with the restriction that free variables are not allowed in the scope of $Q_{=}$ -quantification.

$\blacktriangleright$ Remark 13.

A simple argument, also mentioned in [12], proves that $\mathcal{FO}[Q_{=}]$ can express parity in the special case of $G\left(n,\frac{1}{2}\right)$ . Indeed, consider the sentence $\exists zQ_{=}x\left(x\sim z,\neg(x\sim z)\right)$ , asserting the existence of a vertex with the same number of neighbors as non-neighbors. This sentence holds in $G\left(n,\frac{1}{2}\right)$ with probability $0$ when $n$ is even, and with probability approaching $1$ when $n$ is odd. In particular, $\mathcal{FO}[Q_{=}]$ does not satisfy the zero-one law in $G\left(n,\frac{1}{2}\right)$ . As we shall soon see, much more can be said: $\mathcal{FO}[Q_{=}]$ can express not only parity, but a segment of arithmetic, and for every $p\in(0,1)$ (Theorem 14).

Finally, we mention that in addition to Lindström quantifiers and equicardinality quantifiers, other generalized quantifiers have also been studied in the context of zero-one laws and convergence laws. In a sequence of three papers [20, 21, 22], Kalia studied almost sure quantifier elimination, providing a method for proving convergence laws for logics with generalized quantifiers. In [24], Keisler and Lotfallah proved almost sure quantifier elimination logics with probability quantifiers.

1.2 Our Results

The main result of the paper is the following theorem.

Theorem 14 (Main Theorem).

Fix $p\in(0,1)$ . Then $\mathcal{FO}[Q_{=}]$ can interpret a segment of arithmetic in $G(n,p)$ (with scaling function $f(n)=\left\lfloor\sqrt{\ln n}\right\rfloor$ ).

In particular, from Proposition 8 we get the following corollary.

Corollary 15.

Fix $p\in(0,1)$ . Then there exists a sentence $\psi\in\mathcal{FO}[Q_{=}]$ such that the limit $\lim_{n\rightarrow\infty}\mathbb{P}\left(G(n,p)\models\psi\right)$ does not exist.

This answers the third question of Blass and Harary [2, Section 5], and provides a general result which immediately implies all known cases of Lindström extensions of $\mathcal{FO}$ which are able to express arithmetic. As mentioned above, these include the Lindström quantifier of Hamiltonicity, regularity, the existence of a perfect matching and the existence of a $C_{4}$ -factor.

The rest of the paper is dedicated to the proof of Theorem 14. The proof strategy is roughly as follows. Given a sentence $\varphi\in\mathcal{SO}[\mathrm{Arith}]$ , first apply Theorem 9 to convert it into a sentence $\varphi^{*}\in\mathcal{MSO}$ which expresses $\varphi$ on a set of size $\lfloor\sqrt{n}\rfloor$ . Then, the crux of the proof is to convert a sentence $\varphi^{*}\in\mathcal{MSO}$ into a sentence $\psi\in\mathcal{FO}[Q_{=}]$ which expresses $\varphi^{*}$ on a set of size $\Theta(\ln n)$ . To do that, we need to show that $\mathcal{FO}[Q_{=}]$ can define subsets of logarithmic size, and can also interpret monadic second-order logic on such sets. The proof is divided between Sections 2 and 3. In Section 2 we develop the necessary probabilistic tools, and in Section 3 we put them together in order to complete the proof.

Notation and Conventions

We denote $\mathcal{FO}_{=}:=\mathcal{FO}[Q_{=}]$ for short. Given a list of variable symbols $x_{1},\dots,x_{n}$ , let $\mathcal{FO}(x_{1},\dots,x_{n})$ denote the set of first-order formulas (in the language of graphs) with $x_{1},\dots,x_{n}$ as free variables. Similarly define $\mathcal{FO}_{=}(x_{1},\dots,x_{n})$ and $\mathcal{MSO}(x_{1},\dots,x_{n})$ .

Throughout the text we maintain the convention of denoting random variables with a boldface font.

For $n\in\mathbb{N}$ and $p\in(0,1)$ , we write ${\bf G}_{n}\sim G(n,p)$ to indicate that ${\bf G}_{n}$ is a random graph with distribution $G(n,p)$ . For two vertices $u,v\in[n]$ , let $u\sim v$ denote that they are adjacent in ${\bf G}_{n}$ . For a subset $S\subseteq[n]$ , let ${\bf G}_{n}[S]$ denote the subgraph of ${\bf G}_{n}$ induced by $S$ .

We shall use the following notions of asymptotic probabilities. Let $\left({E}_{n}\right)_{n=1}^{\infty}$ be a sequence of events, taken from a sequence of probability spaces.

1.

We say that $E_{n}$ holds with high probability (as $n\rightarrow\infty$ ) if

$\mathbb{P}\left(E_{n}\right)=1-o(1).$
2.

We say that $E_{n}$ holds with exponentially high probability (as $n\rightarrow\infty$ ) if

$\mathbb{P}\left(E_{n}\right)=1-\exp\left(-n^{\Omega(1)}\right).$

In addition, let $\left({\bf X}_{n}\right)_{n=1}^{\infty}$ , $\left({\bf Y}_{n}\right)_{n=1}^{\infty}$ be two sequences of positive random variables. We say that ${\bf X}_{n}=\left(1+o(1)\right){\bf Y}_{n}$ with (exponentially) high probability if there exists a sequence $\varepsilon_{n}=o(1)$ such that the event $\left|{\bf X}_{n}/{\bf Y}_{n}-1\right|\leq\varepsilon_{n}$ holds with (exponentially) high probability.

For notational convenience, we sometimes omit dependency on $n$ from our notation. The underlying assumption throughout the text is that all quantities implicitly depend on $n$ (unless it is explicitly stated that they are constant or fixed) and $n\rightarrow\infty$ . We explicitly refer to the dependency on $n$ in cases where this convention may cause ambiguity.

Finally, recall the following tail bounds on binomial and Poisson variables, following from Chernoff’s inequality (e.g. see [1, Appendix A]).

$\blacksquare$

Let $\mathbf{X}\sim{\rm Bin}(n,p)$ and $\mu=\mathbb{E}\mathbf{X}$ . Then for every $0<\delta<1$ ,

$\mathbb{P}\left(\left|\mathbf{X}-\mu\right|\geq\delta\mu\right)\leq 2\exp\left% (-\frac{\delta^{2}}{3}\mu\right).$ (2)
$\blacksquare$

Let $\mathbf{X}\sim{\rm Pois}(\lambda)$ and $\mu=\mathbb{E}\mathbf{X}$ . Then for every $0<\delta<1$ ,

$\mathbb{P}\left(\left|\mathbf{X}-\mu\right|\geq\delta\mu\right)\leq 2\exp\left% (-\frac{\delta^{2}}{4}\mu\right).$ (3)

2 Some Probabilistic Results

From now fix a constant $p\in(0,1)$ and consider a binomially distributed random graph ${\bf G}_{n}\sim G(n,p)$ .

We begin by fixing, for every $n$ , two arbitrary vertices $u_{1},u_{2}\in[n]$ . Let $V^{\prime}=[n]\setminus\{u_{1},u_{2}\}$ . Define the following (random) vertex sets:

$\displaystyle{\bf A}$	$\displaystyle=$	$\displaystyle\left\{v\in V^{\prime}:v\sim u_{1}\wedge v\sim u_{2}\right\},$
$\displaystyle{\bf B}$	$\displaystyle=$	$\displaystyle\left\{v\in V^{\prime}:v\sim u_{1}\wedge v\not\sim u_{2}\right\},$
$\displaystyle{\bf C}$	$\displaystyle=$	$\displaystyle\left\{v\in V^{\prime}:v\not\sim u_{1}\wedge v\sim u_{2}\right\}.$

Note that the statements $v\in{\bf A},v\in{\bf B},v\in{\bf C}$ are all expressible as formulas in ${\mathcal{FO}}(u_{1},u_{2},v)$ .

From (2), with exponentially high probability we have

	$\displaystyle\left\|{\bf A}\right\|$	$\displaystyle=$	$\displaystyle(1+o(1))p^{2}n,$
	$\displaystyle\left\|{\bf B}\right\|,\left\|{\bf C}\right\|$	$\displaystyle=$	$\displaystyle(1+o(1))p(1-p)n.$

That is, there exists a sequence $\delta_{n}=o(1)$ such that the event (which we denote by $\mathcal{Q}$ )

\frac{|{\bf A}|}{p^{2}n},\frac{|{\bf B}|}{p(1-p)n},\frac{|{\bf C}|}{p(1-p)n}% \in[1-\delta_{n},1+\delta_{n}]

(4)

holds with exponentially high probability. It will be convenient to condition on the values of the variables ${\bf A},{\bf B},{\bf C}$ ; that is, to condition on an event of the form $Q_{A,B,C}=\left\{{\bf A}=A,{\bf B}=B,{\bf C}=C\right\}$ where $A, B, C$ are possible values of ${\bf A},{\bf B},{\bf C}$ . Note that conditioning on $Q_{A,B,C}$ does not affect the distribution of ${\bf G}_{n}[V^{\prime}]$ .

The rest of the section is as follows. In Section 2.1 we show how to define sets $S\subseteq[n]$ of logarithmic size in $\mathcal{FO}[Q_{=}]$ . In Section 2.2 we show how to express unary relations (subsets) on such sets $S$ in $\mathcal{FO}[Q_{=}]$ . In both sections, all the probabilities and expected values are assumed to be conditioned on $Q_{A,B,C}$ , where we assume that $A, B, C$ satisfy Equation (4) (that is, we assume $Q_{A,B,C}\subseteq\mathcal{Q}$ ). Finally, in Section 2.3 we apply the law of total probability to obtain non-conditioned results.

2.1 Defining Sets of Logarithmic Size

Recall that $A$ , $B$ are the fixed values of the random sets $\mathbf{A}$ , $\mathbf{B}$ defined above. We construct subsets of $A$ in terms of the edges between $A$ and $B$ .

Definition 16.

1.

For every vertex $x\in A$ , let ${\bf d}_{B}(x)$ denote the $B$ -degree of $x$ , which is the number of edges between $x$ and $B$ .
2.

For every $0\leq k\leq\left|B\right|$ , let ${\bf S}_{k}=\left\{v\in A:{\bf d}_{B}(v)=k\right\}$ . That is, $\mathbf{S}_{k}$ is the set of vertices from $A$ with $B$ -degree $k$ .
3.

For every $x\in A$ , let ${\bf S}[x]={\bf S}_{{\bf d}_{B}(x)}=\left\{v\in A:{\bf d}_{B}(v)={\bf d}_{B}(x% )\right\}.$ That is, $\mathbf{S}[x]$ is the set of vertices from $A$ with the same $B$ -degree as $x$ .

$\blacktriangleright$ Remark 17.

Given a vertex $x\in A$ , the statement $v\in{\bf S}[x]$ is expressible as a formula in $\mathcal{FO}_{=}\left(u_{1},u_{2},x,v\right)$ :

v\in A\wedge Q_{=}y\left(y\in B\wedge y\sim v,y\in B\wedge y\sim x\right)

where $x\in A$ means $x\sim u_{1}\wedge x\sim u_{2}$ and $y\in B$ means $y\sim u_{1}\wedge\neg(y\sim u_{2})$ .

Importantly, note that the $B$ -degrees $\left({\bf d}_{B}(x)\right)_{x\in A}$ are i.i.d. with distribution $\mathrm{Bin}\left(\left|B\right|,p\right)$ .

Theorem 18.

Let $c>0$ be a constant. Then, with exponentially high probability, there exists $k=k(n)$ such that $0\leq k\leq\left|B\right|$ and $\left|{\bf S}_{k}\right|=(1+o(1))c\ln n$ .

We can reformulate the statement of theorem more explicitly by recalling the definition of exponentially high probability (see Notation and conventions above). Given a positive constant $c$ , the statement is that there exists a sequence $(\varepsilon_{n})_{n=1}^{\infty}$ such that, as $n\rightarrow\infty$ , we have $\varepsilon_{n}=o(1)$ and

\mathbb{P}\left(\exists 0\leq k\leq\left|B\right|:\;\left|\frac{\left|{\bf S}_% {k}\right|}{c\ln n}-1\right|\geq\varepsilon_{n}\right)=\exp\left(-n^{\Omega(1)% }\right).

For the proof of Theorem 18 we use the following normal approximations of binomial probabilities (see [3, Theorems 1.2 and 1.5]).

Claim 19.

Let $p\in(0,1)$ and $n\in\mathbb{N}$ . Let $\mu=np$ and $\sigma=\sqrt{p(1-p)n}$ be the mean and standard deviation of the binomial distribution $\mathrm{Bin}(n,p)$ . Let $0\leq k\leq n$ be an integer and let $b(k;n,p)=\mathbb{P}\left({\rm Bin}\left(n,p\right)=k\right)$ . Write $k=\mu+h$ .

1.

Assume $\mu\geq 1$ and $\frac{h(1-p)n}{3}\geq 1$ . Then

$b(k;n,p)\leq\frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{h^{2}}{2\sigma^{2}}+% \frac{h}{(1-p)n}+\frac{h^{3}}{p^{2}n^{2}}\right).$
2.

Assume $\mu\geq 1$ , $h>0$ and $k<n$ . Then

$b(k;n,p)\geq\frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{h^{2}}{2\sigma^{2}}-% \frac{h^{3}}{2(1-p)^{2}n^{2}}-\frac{h^{4}}{3p^{3}n^{3}}-\frac{h}{2pn}-\frac{1}% {12k}-\frac{1}{12(n-k)}\right).$

In the proof of Theorem 18 we shall use the following notation:

1.

$n_{A}=\left|A\right|$ and $n_{B}=\left|B\right|$ .
2.

$\mu=pn_{B}$ and $\sigma=\sqrt{p(1-p)n_{B}}$ .
3.

$p_{k}=\mathbb{P}\left({\rm Bin}\left(n_{B},p\right)=k\right)$ for every $0\leq k\leq n_{B}$ .

Lemma 20.

Let $c>0$ be a constant. For every $n\in\mathbb{N}$ let $t_{0}\in\mathbb{R}$ be the unique positive solution of

\frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{t_{0}^{2}}{2}\right)=\frac{c\ln n}% {n}

and let $k_{0}=\mu+t_{0}\sigma$ . Then, for every integer $k\in\left[k_{0}-n^{\nicefrac{{1}}{{4}}},k_{0}+n^{\nicefrac{{1}}{{4}}}\right]$ we have $p_{k}=\left(1+o(1)\right)\frac{c\ln n}{n}$ (where the asymptotic term $o(1)$ is uniform with respect to $k$ ).

Proof of Lemma 20.

First note that $n_{B}=\Theta(n)$ , $\mu=\Theta(n)$ , $\sigma=\Theta\left(n^{\nicefrac{{1}}{{2}}}\right)$ and $t_{0}=(1+o(1))\sqrt{\ln n}$ . For a given integer $k\in\left[k_{0}-n^{\nicefrac{{1}}{{4}}},k_{0}+n^{\nicefrac{{1}}{{4}}}\right]$ , we can write $k=\mu+t\sigma$ for $t=t_{0}+O(n^{-\nicefrac{{1}}{{4}}})$ . Applying Part 1 of Claim 19 (with $h=t\sigma$ and $n=n_{B}$ ),

$\displaystyle p_{k}$	$\displaystyle\leq$	$\displaystyle\frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{t^{2}}{2}\right)\cdot% \exp\left(\frac{t\sigma}{(1-p)n_{B}}+\frac{t^{3}\sigma^{3}}{p^{2}n_{B}^{2}}\right)$
	$\displaystyle=$	$\displaystyle\frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{t_{0}^{2}}{2}\right)% \cdot\exp\left(O(t_{0}n^{-\nicefrac{{1}}{{4}}})\right)\cdot\exp\left(O(t_{0}n^% {-\nicefrac{{1}}{{2}}})\right)$
	$\displaystyle=$	$\displaystyle(1+o(1))\frac{c\ln n}{n}.$

Applying Part 2 of Claim 19 (with $h=t\sigma$ and $n=n_{B}$ ),

$\displaystyle p_{k}$	$\displaystyle\geq$	$\displaystyle\frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{t^{2}}{2}\right)$
		$\displaystyle\cdot\exp\left(-\frac{t^{3}\sigma^{3}}{2(1-p)^{2}b^{2}}-\frac{t^{% 4}\sigma^{4}}{3p^{3}b^{3}}-\frac{t\sigma}{2pb}-\frac{1}{12k}-\frac{1}{12(n-k)}\right)$
	$\displaystyle=$	$\displaystyle\frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{t_{0}^{2}}{2}\right)% \cdot\exp\left(O(t_{0}n^{-\nicefrac{{1}}{{4}}})\right)\cdot\exp\left(O(t_{0}n^% {-\nicefrac{{1}}{{2}}})\right)$
	$\displaystyle=$	$\displaystyle(1+o(1))c\frac{\ln n}{n}.$

Overall we have $p_{k}=(1+o(1))c\frac{\ln n}{n}$ , where the $o(1)$ term can be taken to be $O\left((\ln n)^{\nicefrac{{1}}{{2}}}n^{-\nicefrac{{1}}{{4}}}\right)$ and uniform with respect to $k$ . $\hfill\blacktriangleleft$

Proof of Theorem 18.

Note that ${\bf s}_{k}:=\left|{\bf S}_{k}\right|\sim{\rm Bin}\left(n_{A},p_{k}\right)$ for every $0\leq k\leq n_{B}$ . The variables $\left\{{\bf s}_{k}\right\}_{k=0}^{n_{B}}$ are not independent, since $\sum_{k=0}^{n_{B}}{\bf s}_{k}=n_{A}$ . However, we can replace them with independent variables by introducing a Poisson process.

Let $\left\{{\bf d}_{i}\right\}_{i=1}^{\infty}$ be i.i.d. variables with distribution ${\rm Bin}\left(n_{B},p\right)$ and let ${\bf N}\sim{\rm Pois}(n_{A})$ be independent of $\left\{{\bf d}_{i}\right\}_{i=1}^{\infty}$ . These variables define the Poisson process ${\bf d}_{1},{\bf d}_{2},\dots,{\bf d}_{{\bf N}}$ . For every $0\leq k\leq n_{B}$ let $\tilde{{\bf s}}_{k}$ count the number of times the value $k$ appears in the process; that is, $\tilde{{\bf s}}_{k}=\left|\left\{0\leq i\leq{\bf N}:{\bf d}_{i}=k\right\}\right|$ . Then the variables $\left\{\tilde{{\bf s}}_{k}\right\}_{k=0}^{n_{B}}$ satisfy the following two properties:

1.

The distribution of $\left\{\tilde{{\bf s}}_{k}\right\}_{k=0}^{n_{B}}$ given ${\bf N}=n_{A}$ is identical to the distribution of $\left\{{\bf s}_{k}\right\}_{k=0}^{n_{B}}$ .
2.

$\left\{\tilde{{\bf s}}_{k}\right\}_{k=0}^{n_{B}}$ are independent and $\tilde{{\bf s}}_{k}\sim{\rm Pois}(n_{A}p_{k})$ for every $k$ .

We now apply Lemma 20 with $\frac{c}{p^{2}}$ as the constant. For every integer $k\in\left[k_{0}-n^{\nicefrac{{1}}{{4}}},k_{0}+n^{\nicefrac{{1}}{{4}}}\right]$ we then have

\mathbb{E}\left(\tilde{{\bf s}}_{k}\right)=n_{A}p_{k}=(1+o(1))p^{2}n\cdot\frac% {c}{p^{2}}\ln n=(1+o(1))c\ln n.

From Equation (3) we deduce that there exists a sequence $\varepsilon_{n}=o(1)$ such that for every integer $k\in\left[k_{0}-n^{\nicefrac{{1}}{{4}}},k_{0}+n^{\nicefrac{{1}}{{4}}}\right]$ ,

\mathbb{P}\left(\tilde{{\bf s}}_{k}\not\in\left[(1-\varepsilon_{n})c\ln n,(1+% \varepsilon_{n})c\ln n\right]\right)\leq\frac{1}{2}.

Write

	$\displaystyle I$	$\displaystyle=$	$\displaystyle\left[(1-\varepsilon_{n})c\ln n,(1+\varepsilon_{n})c\ln n\right],$
	$\displaystyle K$	$\displaystyle=$	$\displaystyle\left[k_{0}-n^{\nicefrac{{1}}{{4}}},k_{0}+n^{\nicefrac{{1}}{{4}}}% \right]\cap\mathbb{Z}$

for short. Then, from independence,

\mathbb{P}\left(\tilde{{\bf s}}_{k}\not\in I\;\forall k\in K\right)\leq\left(% \frac{1}{2}\right)^{\left|K\right|}=\exp\left(-\Theta(n^{\nicefrac{{1}}{{4}}})% \right).

Therefore there exists $k$ such that $\tilde{{\bf s}}_{k}\in I$ with exponentially high probability.

Finally, we condition on the event ${\bf N}=n_{A}$ . By Stirling’s approximation, $\mathbb{P}\left({\bf N}=n_{A}\right)=\Theta\left(n_{A}^{-\nicefrac{{1}}{{2}}}% \right)=\Theta\left(n^{-\nicefrac{{1}}{{2}}}\right)$ . Overall

\mathbb{P}\left({\bf s}_{k}\not\in I\;\forall k\in K\right)\leq\frac{\mathbb{P% }\left(\tilde{{\bf s}}_{k}\not\in I\;\forall k\in K\right)}{\mathbb{P}\left({% \bf N}=n_{A}\right)}=\frac{\exp\left(-\Theta(n^{\nicefrac{{1}}{{4}}})\right)}{% \Theta\left(n^{-\nicefrac{{1}}{{2}}}\right)}=\exp\left(-\Theta(n^{\nicefrac{{1% }}{{4}}})\right).

We conclude that, with exponentially high probability, there exists $k$ such that ${\bf s}_{k}\in I$ , and so ${\bf s}_{k}=(1+o(1))c\ln n$ as we wanted. $\hfill\blacktriangleleft$

Corollary 21.

Let $c>0$ be a constant. Then, with exponentially high probability, there exists $x\in A$ such that $\left|{\bf S}[x]\right|=(1+o(1))c\ln n$ .

Proof.

Given $k$ such that $\left|{\bf S}_{k}\right|=(1+o(1))c\ln n$ , pick any $x\in{\bf S}_{k}$ and then ${\bf S}_{k}={\bf S}[x]$ . $\hfill\blacktriangleleft$

2.2 Expressing Unary Relations

To express subsets of a given set $S\subseteq A$ , we use the edges between $S$ and $C$ .

Definition 22.

For a set $S\subseteq A$ and a vertex $z\in C$ let $S_{z}=\left\{s\in S:s\sim z\right\}$ . We say that $S_{z}$ is the subset of $S$ defined by $z$ .

Proposition 23.

There exists a positive constant $c_{1}<\frac{1}{2}$ such that the following holds with exponentially high probability. For every $x\in A$ , if $\left|\mathbf{S}[x]\right|\leq 2c_{1}\ln n$ then for every subset $T\subseteq\mathbf{S}[x]$ there exists $z\in C$ such that $T=\mathbf{S}[x]_{z}$ .

The purpose of the condition $c_{1}<\frac{1}{2}$ will become apparent in Section 3 (see Lemma 30).

Proof.

Let $p_{1}=\min\left\{p,1-p\right\}$ and choose $c_{1}$ to be a sufficiently small constant such that $c_{1}<\frac{1}{2}$ and $\gamma_{1}:=-2c_{1}\ln p_{1}<1$ . For this proof only, let us say that a subset $S\subseteq A$ is good if for every subset $T\subseteq S$ there exists $z\in C$ such that $T=S_{z}$ .

First, fix $S\subseteq A$ of size $\left|S\right|\leq 2c_{1}\ln n$ and a subset $T\subseteq S$ . For every $z\in C$ ,

\mathbb{P}\left(T=S_{z}\right)=p^{\left|T\right|}(1-p)^{\left|S\right|-\left|T% \right|}\geq p_{1}^{\left|S\right|}\geq p_{1}^{2c_{1}\ln n}=n^{-\gamma_{1}}.

Crucially, the subsets of $S$ defined by different vertices $z\in C$ are independently distributed. Thus

\mathbb{P}\left(\forall z\in C.\ T\neq S_{z}\right)=\left(1-p^{\left|T\right|}% (1-p)^{\left|S\right|-\left|T\right|}\right)^{\left|C\right|}\leq\left(1-n^{-% \gamma}\right)^{\left|C\right|}=\exp\left(-\Theta(n^{1-\gamma_{1}})\right).

Taking a union bound over $2^{|S|}=2^{\Theta\left(\ln n\right)}$ possible choices of the subset $T$ , we deduce $\mathbb{P}\left(S\;{\rm is}\;{\rm not}\;{\rm good}\right)=\exp\left(-n^{\Omega% (1)}\right)$ .

Finally, for every $x\in A$ we can apply the law of total probability with respect to the possible values of $\mathbf{S}[x]$ , and deduce that, with exponentially high probability, $\left|\mathbf{S}[x]\right|\leq 2c_{1}\ln n$ implies that $\mathbf{S}[x]$ is good. Taking a union bound over $\Theta(n)$ possible choices of $x$ , we get the desired result. $\hfill\blacktriangleleft$

We will also need the following analogous proposition, which will be used to control the upper bound on the size of the definable sets.

Proposition 24.

There exists a positive constant $c_{2}$ such that $c_{2}\geq 2c_{1}$ and the following holds with probability $1-o\left(n^{-2}\right)$ . For every $x\in A$ , if $\left|{\bf S}[x]\right|\geq c_{2}\log_{2}n$ then for every $z_{1},z_{2}\in C$ , if $z_{1}\neq z_{2}$ then $\mathbf{S}[x]_{z_{1}}\neq\mathbf{S}[x]_{z_{2}}$ .

Again, the purpose of the condition $c_{2}\geq 2c_{1}$ will become apparent in Section 3.

Proof.

Let $p_{2}=\max\left\{p,1-p\right\}$ and choose $c_{2}$ to be a sufficiently large constant such that $c_{2}\geq 2c_{1}$ and $\gamma_{2}:=-c_{2}\ln p_{1}>5$ . For this proof only, let us say that a subset $S\subseteq A$ is good if for every $z_{1},z_{2}\in C$ , if $z_{1}\neq z_{2}$ then $S_{z_{1}}\neq S_{z_{2}}$ .

First, fix $S\subseteq A$ of size $\left|S\right|\geq c_{2}\ln n$ . For every pair of distinct vertices $z_{1},z_{2}\in C$ ,

\mathbb{P}\left(S_{z_{1}}=S_{z_{2}}\right)\leq p_{2}^{\left|S\right|}\leq p_{2% }^{c_{2}\ln n}=n^{c_{2}\ln p_{2}}=n^{-\gamma_{2}}.

Taking a union bound over $\Theta(n^{2})$ choices of $z_{1}\neq z_{2}$ , we get

\mathbb{P}\left(S\;{\rm is}\;{\rm not}\;{\rm good}\right)=O(n^{2-\gamma_{2}}).

Finally, for every $x\in A$ we can apply the law of total probability with respect to the possible values of $\mathbf{S}[x]$ and deduce that, with probability $1-O(n^{2-\gamma_{2}})$ , $\left|\mathbf{S}[x]\right|\geq c_{2}\ln n$ implies that $\mathbf{S}[x]$ is good. Taking a union bound over $\Theta(n)$ possible choices of $x$ , and recalling that $n^{3-\gamma_{2}}=o(n^{-2})$ by definition, we get the desired result. $\hfill\blacktriangleleft$

2.3 Non-Conditioned Results

Finally, we lose the conditioning on the events $Q_{A,B,C}$ which fix the values of ${\bf A},{\bf B},{\bf C}$ . Note that we still have dependency on the choice of $u_{1},u_{2}$ ; we will quantify over $u_{1},u_{2}$ in the next section. The following theorem summarizes all the probabilistic results proved in this section.

Theorem 25.

There exist positive constants $c_{1},c_{2}$ with $c_{1}<\frac{1}{2}$ and $c_{2}\geq 2c_{1}$ and sequences $\delta_{n}=o(1)$ and $\varepsilon_{n}=o(1)$ such that $\mathbb{P}(\Gamma(u_{1},u_{2}))=1-o(n^{-2}),$ where $\Gamma(u_{1},u_{2})$ is the event that:

1.

$\displaystyle\frac{|{\bf A}|}{p^{2}n},\frac{|{\bf B}|}{p(1-p)n},\frac{|{\bf C}% |}{p(1-p)n}\in[1-\delta_{n},1+\delta_{n}]$ (we denote this event by $\mathcal{Q}$ );
2.

There exists $x\in{\bf A}$ such that

$\left|{\bf S}[x]\right|\in\left[(1-\varepsilon_{n})\frac{3}{2}c_{1}\ln n,(1+% \varepsilon_{n})\frac{3}{2}c_{1}\ln n\right];$
3.

For every $x\in\mathbf{A}$ , if $\left|\mathbf{S}[x]\right|\leq 2c_{1}\ln n$ then for every $T\subseteq\mathbf{S}[x]$ there exists $z\in\mathbf{C}$ such that $T=\mathbf{S}[x]_{z}$ ; and
4.

For every $x\in\mathbf{A}$ , if $\left|\mathbf{S}[x]\right|\geq c_{2}\ln n$ then for every $z_{1},z_{2}\in\mathbf{C}$ , if $z_{1}\neq z_{2}$ then $\mathbf{S}[x]_{z_{1}}\neq\mathbf{S}[x]_{z_{2}}$ .

Proof.

Let $\delta_{n}=o(1)$ be the sequence from Equation (4). In the previous sections, we conditioned all probabilities on $Q_{A,B,C}$ where $Q_{A,B,C}\subseteq\mathcal{Q}$ . However, note that the proofs of Theorem 18 and Propositions 23, 24 do not depend on the specific values $A, B, C$ , but only on the fact that they satisfy Equation (4). Therefore, they also hold when the conditioning is on the event $\mathcal{Q}$ .

Now, let $c_{1},c_{2}$ be the constants from Propositions 23 and 24 (respectively) and let $\left(\varepsilon_{n}\right)_{n=1}^{\infty}$ be the sequence from Theorem 18 for $c=\frac{3}{2}c_{1}$ . Define $\Gamma(u_{1},u_{2})$ as above. Then

	$\displaystyle\mathbb{P}\left(\Gamma(u_{1},u_{2})\right)$	$\displaystyle=\mathbb{P}\left(\Gamma(u_{1},u_{2})\bigm{\|}\mathcal{Q}\right)% \mathbb{P}\left(\mathcal{Q}\right)$
	$\displaystyle\geq$	$\displaystyle\left(1-o(n^{-2})\right)\left(1-\exp\left(-n^{\Omega(1)}\right)% \right)=1-o(n^{-2}).$

That concludes the proof. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 26.

Note that, due to symmetry considerations, $\mathbb{P}\left(\Gamma(u_{1},u_{2})\right)$ does not depend on the choice of $u_{1},u_{2}$ .

3 Proof of the Main Theorem

In this section we complete the proof of Theorem 14. We begin with a sequence of short lemmas, which build upon our previous results. Once again, we fix a constant $p\in(0,1)$ and consider a binomial random graph ${\bf G}_{n}\sim G(n,p)$ . Probabilities are now non-conditioned.

We begin with a refinement of Theorem 9.

Lemma 27 (Kaufmann-Shelah).

There exists a sentence $\mathrm{Encode}^{*}\in\mathcal{MSO}$ such that:

1.

$\lim_{n\rightarrow\infty}\mathbb{P}\left(\mathbf{G}_{n}\models\mathrm{Encode}^% {*}\right)=1$ .
2.

For every sentence $\varphi\in\mathcal{SO}[\mathrm{Arith}]$ there exists a sentence $\varphi^{*}\in\mathcal{MSO}$ such that, for every $n\in\mathbb{N}$ and graph $G=([n],E)$ with $G\models\mathrm{Encode}^{*}$ , we have $G\models\varphi^{*}\iff\left[\sqrt{n}\right]\models\varphi$ .

Proof.

This follows from Theorem 1 and the closing remark of [23]. $\hfill\blacktriangleleft$ Intuitively, the sentence $\mathrm{Encode}^{*}$ asserts the existence of $\mathcal{MSO}$ -formulas expressing a structure of addition and multiplication on the vertices, a necessary ingredient for converting any $\varphi\in\mathcal{SO}[\mathrm{Arith}]$ into $\varphi^{*}\in\mathcal{MSO}$ . The basic structure of the sentence $\mathrm{Encode}^{*}$ is given in Theorem 1 of [23].

Lemma 28.

For every sentence $\varphi^{*}\in\mathcal{MSO}$ there exists a formula $\varphi^{**}(u_{1},u_{2},x)\in\mathcal{FO}_{=}\left(u_{1},u_{2},x\right)$ such that the following holds. Given the event $\Gamma(u_{1},u_{2})$ , for every $x\in{\bf A}$ with $\left|{\bf S}[x]\right|\leq 2c_{1}\ln n$ we have

{\bf G}_{n}\models\varphi^{**}(u_{1},u_{2},x)\iff{\bf G}_{n}[{\bf S}[x]]% \models\varphi^{*}.

Proof.

Given $\varphi^{*}$ , define $\varphi^{**}(u_{1},u_{2},x)$ as follows:

$\blacksquare$

Restrict quantification to ${\bf S}[x]$ : replace every $\forall v\left(\theta\right)$ with $\forall v\left(v\in{\bf S}[x]\rightarrow\theta\right)$ and every $\exists v\left(\theta\right)$ with $\exists v\left(v\in{\bf S}[x]\wedge\theta\right)$ . Recall that the statement $v\in{\bf S}[x]$ is expressible as a formula in $\mathcal{FO}_{=}\left(u_{1},u_{2},x,v\right)$ (see Remark 17).
$\blacksquare$

Convert unary relations: for every unary relation $R$ introduced by $\psi$ , replace $\exists R\left(\theta\right)$ with $\exists z_{R}(z_{R}\in{\bf C}\wedge\theta)$ where $z_{R}$ is a new variable symbol, and also replace every $R(v)$ with $v\sim z_{R}$ . Similarly handle $\forall R\left(\theta\right)$ . Recall that the statement $z\in{\bf C}$ is expressible the formula $z\not\sim u_{1}\wedge z\sim u_{2}$ , which is in $\mathcal{FO}(u_{1},u_{2},z)$

Given the event $\Gamma(u_{1},u_{2})$ , for every $x\in{\bf A}$ with $\left|{\bf S}[x]\right|\leq 2c_{1}\ln n$ , we know that every subset of ${\bf S}[x]$ is defined by some $z\in{\bf C}$ (see Part 3 of Theorem 25). Therefore

{\bf G}_{n}\models\varphi^{**}(u_{1},u_{2},x)\iff{\bf G}_{n}[{\bf S}[x]]% \models\varphi^{*}

as we wanted. $\hfill\blacktriangleleft$ Next, we introduce a formula for upper-bounding the size of definable sets.

Definition 29.

Given a choice of $u_{1},u_{2}\in[n]$ and $x\in\mathbf{A}$ , we say that $\mathbf{S}[x]$ is pseudo-logarithmic if there exist $z_{1},z_{2}\in\mathbf{C}$ such that $z_{1}\neq z_{2}$ but $\mathbf{S}[x]_{z_{1}}=\mathbf{S}[x]_{z_{2}}$ .

Note that this property is expressible as a formula in $\mathcal{FO}_{=}(u_{1},u_{2},x)$ , given by

\exists z_{1}\exists z_{2}\left(z_{1}\in\mathbf{C}\wedge z_{2}\in\mathbf{C}% \wedge z_{1}\neq z_{2}\wedge\mathbf{S}[x]_{z_{1}}={\bf S}[x]_{z_{2}}\right),

where $\mathbf{S}[x]_{z_{1}}={\bf S}[x]_{z_{2}}$ is the formula $\forall y\left(y\in\mathbf{S}[x]\rightarrow\left(y\sim z_{1}\leftrightarrow y% \sim z_{2}\right)\right)$ .

Lemma 30.

Given the event $\Gamma(u_{1},u_{2})$ , for every $x\in{\bf A}$ ,

1.

If $\mathbf{S}[x]$ is pseudo-logarithmic then $|\mathbf{S}[x]|\leq c_{2}\ln n$ .
2.

If $|\mathbf{S}[x]|\leq 2c_{1}\ln n$ then $\mathbf{S}[x]$ is pseudo-logarithmic.

Proof.

Part 1 follows directly from the definition of $\Gamma(u_{1},u_{2})$ (see part 4 of Theorem 25 ). Part 2 follows from the pigeonhole principle. Indeed, let $S=\mathbf{S}[x]$ and assume $|S|\leq 2c_{1}\ln n$ . Then the number of subsets of $S$ is $2^{|S|}\leq 2^{2c_{1}\ln n}=n^{2c_{1}\ln 2}$ . Recall that $c_{1}<\frac{1}{2}$ , so $2^{|S|}\leq n^{\ln 2}=o(n)$ . However, given $\Gamma(u_{1},u_{2})$ we have $|\mathbf{C}|=\Theta(n)$ . From the pigeonhole principle there must exist $z_{1},z_{2}\in\mathbf{C}$ such that $z_{1}\neq z_{2}$ but $S_{z_{1}}=S_{z_{2}}$ , hence $S$ is pseudo-logarithmic. $\hfill\blacktriangleleft$ Finally, we introduce a formula for comparing sizes of definable sets.

Definition 31.

Given a choice of $u_{1},u_{2}\in[n]$ and two vertices $x,x^{\prime}\in\mathbf{A}$ , we say that $\mathbf{S}[x]$ is pseudo-smaller than $\mathbf{S}[x^{\prime}]$ if there exists $z\in{\bf C}$ such that $|\mathbf{S}[x^{\prime}]_{z}|=|\mathbf{S}[x]|$ .

Note that this property is expressible as a formula in ${FO}_{=}(u_{1},u_{2},x,x^{\prime})$ , since belonging to $\mathbf{S}[x]$ and to $\mathbf{S}[x^{\prime}]_{z}$ and the equicardinality condition $|\mathbf{S}[x^{\prime}]_{z}|=|\mathbf{S}[x]|$ are all expressible in $\mathcal{FO}_{=}$ .

Lemma 32.

Given the event $\Gamma(u_{1},u_{2})$ , for every $x,x^{\prime}\in{\bf A}$ ,

1.

If $\mathbf{S}[x]$ is pseudo-smaller than $\mathbf{S}[x^{\prime}]$ then $|\mathbf{S}[x]|\leq|\mathbf{S}[x^{\prime}]|$ .
2.

If $|\mathbf{S}[x]|\leq|\mathbf{S}[x^{\prime}]|\leq 2c_{1}\ln n$ then $\mathbf{S}[x]$ is pseudo-smaller than $\mathbf{S}[x^{\prime}]$ .

Proof.

Part 1 follows from the definition of pseudo-smaller (in fact, it is true deterministically). Part 2 follows from the definition of $\Gamma(u_{1},u_{2})$ (see Part 3 of Theorem 25 ). $\hfill\blacktriangleleft$

We are now ready to prove the main theorem. In the proof, we use the notation $\mathbf{E}(X,Y)$ for the set of edges in $\mathbf{G}_{n}$ between two disjoint sets of vertices $X,Y\subseteq[n]$ .

Proof of Theorem 14.

We prove that $\mathcal{FO}_{=}$ can interpret a segment of arithmetic with constants $\sqrt{c_{1}},\sqrt{c_{2}}$ and scaling function $f(n)=\left\lfloor\sqrt{\ln n}\right\rfloor$ , where $c_{1},c_{2}$ are the constants from Theorem 25. That is, for every sentence $\varphi\in\mathcal{SO}[\mathrm{Arith}]$ we construct a sentence $\psi\in\mathcal{FO}_{=}$ such that the following holds. Given a sequence $\left\{n_{k}\right\}_{k=1}^{\infty}$ with $\lim_{k\rightarrow\infty}n_{k}=\infty$ such that $\varphi$ is constant on $\left[\sqrt{c_{1}\ln n_{k}},\sqrt{c_{2}\ln n_{k}}\right]$ for every $k$ , we have

\lim_{k\rightarrow\infty}\mathbb{P}\left(G(n_{k},p)\models\psi\iff\varphi\;{% \rm holds}\;{\rm in}\;\left[\sqrt{c_{1}\ln n_{k}},\sqrt{c_{2}\ln n_{k}}\right]% \right)=1.

(5)

From now on we fix a sentence $\varphi\in\mathcal{SO}[\mathrm{Arith}]$ . First, we apply Lemma 27 to obtain a sentence $\varphi^{*}\in\mathcal{MSO}$ such that, for every graph $G=([n],E)$ with $G\models\mathrm{Encode}^{*}$ , we have $G\models\varphi^{*}\iff\left[\sqrt{n}\right]\models\varphi$ . Second, we apply Lemma 28 to the $\mathcal{MSO}$ -sentences $\varphi^{*}$ and $\mathrm{Encode}^{*}$ (from Lemma 27) to obtain formulas $\varphi^{**}(u_{1},u_{2},x),\mathrm{Encode}^{**}(u_{1},u_{2},x)\in\mathcal{FO}% _{=}\left(u_{1},u_{2},x\right)$ such that, given the event $\Gamma(u_{1},u_{2})$ , for every $x\in{\bf A}$ with $\left|{\bf S}[x]\right|\leq 2c_{1}\ln n$ we have

	$\displaystyle\mathbf{G}_{n}\models\varphi^{**}\left(u_{1},u_{2},x\right)$	$\displaystyle\iff$	$\displaystyle\mathbf{G}_{n}\left[\mathbf{S}[x]\right]\models\varphi^{*},$		(6)
	$\displaystyle\mathbf{G}_{n}\models\mathrm{Encode}^{**}\left(u_{1},u_{2},x\right)$	$\displaystyle\iff$	$\displaystyle\mathbf{G}_{n}\left[\mathbf{S}[x]\right]\models\mathrm{Encode}^{*}.$		(7)

Now define $\psi$ as the sentence claiming the existence of two vertices $u_{1},u_{2}$ and a vertex $x\in\mathbf{A}$ such that:

1.

$\mathbf{S}[x]$ is pseudo-logarithmic and ${\bf G}_{n}[{\bf S}[x]]\models\mathrm{Encode}^{*}$ .
2.

If $x^{\prime}\in\mathbf{A}$ is another vertex such that $\mathbf{S}[x^{\prime}]$ is pseudo-logarithmic and ${\bf G}_{n}[{\bf S}[x]]\models\mathrm{Encode}^{*}$ , then $\mathbf{S}[x]$ is not pseudo-smaller than $\mathbf{S}[x^{\prime}]$ .
3.

${\bf G}_{n}[{\bf S}[x]]\models\varphi^{*}$ .

From Lemmas 30, 32 and (6), (7) above, $\psi$ is indeed expressible as a sentence in $\mathcal{FO}_{=}$ . It remains to verify (5).

Let $\left\{n_{k}\right\}_{k=1}^{\infty}$ with $\lim_{k\rightarrow\infty}n_{k}=\infty$ such that $\varphi$ is constant on $\left[\sqrt{c_{1}\ln n_{k}},\sqrt{c_{2}\ln n_{k}}\right]$ for every $k$ . There are two cases to consider.

Case 1: $\varphi$ holds in $\left[\sqrt{c_{1}\ln n_{k}},\sqrt{c_{2}\ln n_{k}}\right]$ .

Fix two vertices $u_{1},u_{2}$ arbitrarily. We show that, with high probability, there exists a vertex $x\in{\bf A}$ which satisfies the three parts of $\psi$ (along with $u_{1},u_{2}$ ).

First, we know that $\mathbb{P}\left(\Gamma(u_{1},u_{2})\right)=1-o(1)$ , so from now on we may assume that $\Gamma(u_{1},u_{2})$ holds. Recall that the event $\Gamma(u_{1},u_{2})$ guarantees a vertex $x^{\prime}\in{\bf A}$ such that

\left|\mathbf{S}[x^{\prime}]\right|\in\left[(1-\varepsilon_{n})\frac{3}{2}c_{1% }\ln n_{k},(1+\varepsilon_{n})\frac{3}{2}c_{1}\ln n_{k}\right].

Fix such a vertex $x^{\prime}$ . Since $c_{2}\geq 2c_{1}\geq(1+\varepsilon_{n})\frac{3}{2}c_{1}$ , Lemma 32 implies that ${\bf S}[x^{\prime}]$ is pseudo-logarithmic. Let us show that ${\bf G}_{n_{k}}\left[\mathbf{S}[x^{\prime}]\right]\models\mathrm{Encode}^{*}$ with high probability.

Condition on the values $A, B, C$ of the sets ${\bf A},{\bf B},{\bf C}$ and on the edge sets ${\bf E}(A,B)$ and ${\bf E}(A,C)$ . These values determine the value $S$ of the set ${\bf S}[x^{\prime}]$ . Crucially, the induced subgraph ${\bf G}_{n_{k}}\left[S\right]$ depends only on the edge set ${\bf E}(A)$ , and so, given the last conditioning, ${\bf G}_{n_{k}}\left[S\right]$ is still binomially distributed with vertex set $S$ and edge probability $p$ . From Lemma 27 we get that, given the last conditioning, ${\bf G}_{n_{k}}\left[S\right]\models{\rm Encode}^{*}$ with high probability. Now apply the law of total probability over the possible values of ${\bf A},{\bf B},{\bf C},{\bf E}(A,B),{\bf E}(A,C)$ to conclude that ${\bf G}_{n_{k}}\left[{\bf S}[x]\right]\models\varphi^{*}$ with high probability.

Next, among all vertices $x\in{\bf A}$ such that ${\bf S}[x]$ is pseudo-logarithmic and ${\bf G}_{n_{k}}\left[\mathbf{S}[x]\right]\models\mathrm{Encode}^{*}$ , pick $x$ such that $\left|{\bf S}[x]\right|$ is maximal. By definition, $x$ satisfies Part 1 and Part 2 of $\psi$ . We show that it also satisfies Part 3. Since ${\bf S}[x]$ is pseudo-logarithmic, Lemma 30 implies $\left|{\bf S}[x]\right|\leq c_{2}\ln n_{k}$ . We also know that

\left|{\bf S}[x]\right|\geq\left|{\bf S}[x^{\prime}]\right|\geq(1-\varepsilon_% {n})\frac{3}{2}c_{1}\ln n_{k}\geq c_{1}\ln n_{k}+1.

Letting ${\bf s}=\left|{\bf S}[x]\right|$ , we deduce $\left\lfloor\sqrt{{\bf s}}\right\rfloor\in\left[\sqrt{c_{1}\ln n_{k}},\sqrt{c_% {2}\ln n_{k}}\right]$ . From the assumption of Case 1, $\left[\left\lfloor\sqrt{{\bf s}}\right\rfloor\right]\models\varphi$ . Since ${\bf G}_{n_{k}}\left[\mathbf{S}[x^{\prime}]\right]\models\mathrm{Encode}^{*}$ , Lemma 27 implies ${\bf G}_{n_{k}}\left[\mathbf{S}[x^{\prime}]\right]\models\varphi^{*}$ as we wanted.

Case 2: $\neg\varphi$ holds in $\left[\sqrt{c_{1}\ln n_{k}},\sqrt{c_{2}\ln n_{k}}\right]$ .

We need to prove that with high probability, for every $u_{1},u_{2}$ , there is no vertex $x$ that satisfies all three parts of $\psi$ . Let $\Gamma=\bigcap_{u_{1},u_{2}}\Gamma(u_{1},u_{2})$ . Theorem 25 shows that $\mathbb{P}\left(\Gamma(u_{1},u_{2})\right)=1-o(n^{-2})$ for every $u_{1},u_{2}$ . Taking a union bound the over $\Theta(n^{2})$ pairs $u_{1},u_{2}$ we get $\mathbb{P}\left(\Gamma\right)=1-o(1)$ . So from now on we may assume that $\Gamma$ holds.

Assume that $u_{1},u_{2},x$ are vertices such that Part 1 and Part 2 of $\psi$ hold and let us show that Part 3 does not hold. Again, $\Gamma$ guarantees a vertex $x^{\prime}\in{\bf A}$ such that

\left|\mathbf{S}[x^{\prime}]\right|\in\left[(1-\varepsilon_{n})\frac{3}{2}c_{1% }\ln n_{k},(1+\varepsilon_{n})\frac{3}{2}c_{1}\ln n_{k}\right].

We prove $\left|{\bf S}[x]\right|\geq\left|{\bf S}[x^{\prime}]\right|$ by contradiction. Indeed, otherwise we have

\left|{\bf S}[x]\right|\leq\left|{\bf S}[x^{\prime}]\right|\leq(1+\varepsilon_% {n})\frac{3}{2}c_{1}\ln n_{k}\leq 2c_{1}\ln n_{k},

and from Lemma 30 we get that ${\bf S}[x]$ is pseudo-smaller than ${\bf S}[x^{\prime}]$ . But that contradicts Part 2 of $\psi$ . Therefore

\left|{\bf S}[x]\right|\geq\left|{\bf S}[x^{\prime}]\right|\geq(1-\varepsilon_% {n})\frac{3}{2}c_{1}\ln n_{k}\geq c_{1}\ln n_{k}+1.

Moreover, ${\bf S}[x]$ is pseudo-logarithmic, so Lemma 30 implies $\left|{\bf S}[x]\right|\leq c_{2}\ln n$ . As before, letting ${\bf s}=\left|{\bf S}[x]\right|$ , we get $\left\lfloor\sqrt{{\bf s}}\right\rfloor\in\left[\sqrt{c_{1}\ln n_{k}},\sqrt{c_% {2}\ln n_{k}}\right]$ . From the assumption of Case 2, $\left[\left\lfloor\sqrt{{\bf s}}\right\rfloor\right]\not\models\varphi$ . Since ${\bf G}_{n_{k}}\left[\mathbf{S}[x^{\prime}]\right]\models\mathrm{Encode}^{*}$ , Lemma 27 implies ${\bf G}_{n_{k}}\left[\mathbf{S}[x^{\prime}]\right]\not\models\varphi^{*}$ , as we wanted. $\hfill\blacktriangleleft$

References

[1] Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley Publishing, 4th edition, 2016.
[2] Andreas Blass and Frank Harary. Properties of almost all graphs and complexes. Journal of Graph Theory, 3(3):225–240, 1979. doi:10.1002/JGT.3190030305.
[3] Béla Bollobás. Random Graphs. Cambridge University Press, 2001.
[4] Kevin J. Compton. 0-1 laws in logic and combinatorics. In Rival Ivan, editor, Algorithms and Order, volume 255 of Advanced Study Institute Series C: Mathematical and Physical Sciences, pages 353–383. Kluwer Academic Publishers, Dordrecht, 1989.
[5] Anuj Dawar and Erich Grädel. Generalized quantifiers and 0-1 laws. In Proceedings of the Tenth Annual IEEE Symposium on Logic in Computer Science (LICS 1995), pages 54–64. IEEE Computer Society Press, June 1995. doi:10.1109/LICS.1995.523244.
[6] Anuj Dawar and Erich Grädel. Properties of almost all graphs and generalized quantifiers. Fundam. Inform., 98(4):351–372, 2010. doi:10.3233/FI-2010-232.
[7] Heinz-Dieter Ebbinghaus. Extended logics: The general framework. In Jon Barwise and Solomon Feferman, editors, Model-Theoretic Logics, chapter II, pages 25–76. Association for Symbolic Logic, September 1985.
[8] Heinz-Dieter Ebbinghaus and Jörg Flum. Finite Model Theory. Springer Berlin, Heidelberg, second edition, 2006.
[9] Paul Erdős and Alfréd Rényi. On random graphs, I. Publicationes Mathematicae, 6:290–297, 1959.
[10] Paul Erdős and Alfréd Rényi. On the evolution of random graphs. In Publication of the Mathematical Institute of the Hungarian Academy of Sciences, number 5 in Acta Math. Acad. Sci. Hungar., pages 17–61, 1960.
[11] Ronald Fagin. Probabilities on finite models. The Journal of Symbolic Logic, 41(1):50–58, March 1976. doi:10.1017/S0022481200051756.
[12] Guy Fayolle, Stéphane Grumbach, and Christophe Tollu. Asymptotic probabilities of languages with generalized quantifiers. In Proceedings Eighth Annual IEEE Symposium on Logic in Computer Science, pages 199–207, 1993. doi:10.1109/LICS.1993.287587.
[13] Yu. V. Glebskiĭ, D. I. Kogan, M. I. Liogon’kiĭ, and V. A. Talanov. Range and degree of realizability of formulas in the restricted predicate calculus. Cybernetics and Systems Analysis, 5(2):142–154, March 1969. (Russian original: Kibernetika 5(2):17–27, March-April 1969).
[14] Simi Haber. Generalized quantifiers for simple graph properties in random graphs. , Preprint.
[15] Simi Haber. Arithmetization for first order logic augmented with perfect matching. , Submitted.
[16] Simi Haber and Saharon Shelah. Random graphs and Lindström quantifiers for natural graph properties. Accepted, Annales Univ. Sci. Budapest., Sect. Math, 2024+. HbSh:986 in Shelah’s archive.
[17] Klaus Härtig. Über einen quantifikator mit zwei wirk ungsbereichen. In Laszlo Kalmar, editor, Colloquium on the Foundations of Mathematics, Mathematical Machines and their Applications, pages 31–36. Akademiai Kiado, Budapest, September 1962.
[18] Heinrich Herre, Michał Krynicki, Alexandr Pinus, and Jouko Väänänen. The Härtig quantifier: a survey. Journal of Symbolic Logic, 56(4):1153–1183, December 1991. doi:10.2307/2275466.
[19] Svante Janson, Tomasz Łuczak, and Andrzej Ruciński. Random Graphs. John Wiley & Sons, 2000.
[20] Risto Kaila. On probabilistic elimination of generalized quantifiers. Random Struct. Algorithms, 19(1):1–36, 2001. doi:10.1002/RSA.1016.
[21] Risto Kaila. Convergence laws for very sparse random structures with generalized quantifiers. Math. Log. Q., 48(2):301–320, 2002. doi:10.1002/1521-3870(200202)48:2\%3C301::AID-MALQ301\%3E3.0.CO;2-Z.
[22] Risto Kaila. On almost sure elimination of numerical quantifiers. J. Log. Comput., 13(2):273–285, 2003. doi:10.1093/LOGCOM/13.2.273.
[23] Matt Kaufmann and Saharon Shelah. On random models of finite power and monadic logic. Discrete Mathematics, 54(3):285–293, 1985. doi:10.1016/0012-365X(85)90112-8.
[24] H. Jerome Keisler and Wafik Boulos Lotfallah. Almost everywhere elimination of probability quantifiers. Journal of Symbolic Logic, 74(4):1121–1142, 2009. doi:10.2178/JSL/1254748683.
[25] Phokion G. Kolaitis and Swastik Kopparty. Random graphs and the parity quantifier. Journal of the Association for Computing Machinery, 60(5):1–34, October 2013. doi:10.1145/2528402.
[26] Per Lindström. First order predicate logic with generalized quantifiers. Theoria, 32(3):186–195, 1966.
[27] Per Lindström. On extensions of elementary logic. Theoria, 35(1):1–11, 1969.
[28] M. H. Löb. Meeting of the association for symbolic logic, leeds 1962. The Journal of Symbolic Logic, 27(3):373–382, 1962. First abstract: Plurality-quantification by Nicholas Rescher. doi:10.1017/S0022481200118742.
[29] Peter Winkler. Random structures and zero-one laws. In Sauer N. W., Woodrow R. E., and Sands B., editors, Finite and Infinite Combinatorics in Sets and Logic, Advanced Science Institutes, pages 399–420. Kluwer Academic Publishers, Dordrecht, 1993.

[bib.bib1] [1] Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley Publishing, 4th edition, 2016.

[bib.bib2] [2] Andreas Blass and Frank Harary. Properties of almost all graphs and complexes. Journal of Graph Theory, 3(3):225–240, 1979. doi:10.1002/JGT.3190030305.

[bib.bib3] [3] Béla Bollobás. Random Graphs. Cambridge University Press, 2001.

[bib.bib4] [4] Kevin J. Compton. 0-1 laws in logic and combinatorics. In Rival Ivan, editor, Algorithms and Order, volume 255 of Advanced Study Institute Series C: Mathematical and Physical Sciences, pages 353–383. Kluwer Academic Publishers, Dordrecht, 1989.

[bib.bib5] [5] Anuj Dawar and Erich Grädel. Generalized quantifiers and 0-1 laws. In Proceedings of the Tenth Annual IEEE Symposium on Logic in Computer Science (LICS 1995), pages 54–64. IEEE Computer Society Press, June 1995. doi:10.1109/LICS.1995.523244.

[bib.bib6] [6] Anuj Dawar and Erich Grädel. Properties of almost all graphs and generalized quantifiers. Fundam. Inform., 98(4):351–372, 2010. doi:10.3233/FI-2010-232.

[bib.bib7] [7] Heinz-Dieter Ebbinghaus. Extended logics: The general framework. In Jon Barwise and Solomon Feferman, editors, Model-Theoretic Logics, chapter II, pages 25–76. Association for Symbolic Logic, September 1985.

[bib.bib8] [8] Heinz-Dieter Ebbinghaus and Jörg Flum. Finite Model Theory. Springer Berlin, Heidelberg, second edition, 2006.

[bib.bib9] [9] Paul Erdős and Alfréd Rényi. On random graphs, I. Publicationes Mathematicae, 6:290–297, 1959.

[bib.bib10] [10] Paul Erdős and Alfréd Rényi. On the evolution of random graphs. In Publication of the Mathematical Institute of the Hungarian Academy of Sciences, number 5 in Acta Math. Acad. Sci. Hungar., pages 17–61, 1960.

[bib.bib11] [11] Ronald Fagin. Probabilities on finite models. The Journal of Symbolic Logic, 41(1):50–58, March 1976. doi:10.1017/S0022481200051756.

[bib.bib12] [12] Guy Fayolle, Stéphane Grumbach, and Christophe Tollu. Asymptotic probabilities of languages with generalized quantifiers. In Proceedings Eighth Annual IEEE Symposium on Logic in Computer Science, pages 199–207, 1993. doi:10.1109/LICS.1993.287587.

[bib.bib13] [13] Yu. V. Glebskiĭ, D. I. Kogan, M. I. Liogon’kiĭ, and V. A. Talanov. Range and degree of realizability of formulas in the restricted predicate calculus. Cybernetics and Systems Analysis, 5(2):142–154, March 1969. (Russian original: Kibernetika 5(2):17–27, March-April 1969).

[bib.bib14] [14] Simi Haber. Generalized quantifiers for simple graph properties in random graphs. , Preprint.

[bib.bib15] [15] Simi Haber. Arithmetization for first order logic augmented with perfect matching. , Submitted.

[bib.bib16] [16] Simi Haber and Saharon Shelah. Random graphs and Lindström quantifiers for natural graph properties. Accepted, Annales Univ. Sci. Budapest., Sect. Math, 2024+. HbSh:986 in Shelah’s archive.

[bib.bib17] [17] Klaus Härtig. Über einen quantifikator mit zwei wirk ungsbereichen. In Laszlo Kalmar, editor, Colloquium on the Foundations of Mathematics, Mathematical Machines and their Applications, pages 31–36. Akademiai Kiado, Budapest, September 1962.

[bib.bib18] [18] Heinrich Herre, Michał Krynicki, Alexandr Pinus, and Jouko Väänänen. The Härtig quantifier: a survey. Journal of Symbolic Logic, 56(4):1153–1183, December 1991. doi:10.2307/2275466.

[bib.bib19] [19] Svante Janson, Tomasz Łuczak, and Andrzej Ruciński. Random Graphs. John Wiley & Sons, 2000.

[bib.bib20] [20] Risto Kaila. On probabilistic elimination of generalized quantifiers. Random Struct. Algorithms, 19(1):1–36, 2001. doi:10.1002/RSA.1016.

[bib.bib21] [21] Risto Kaila. Convergence laws for very sparse random structures with generalized quantifiers. Math. Log. Q., 48(2):301–320, 2002. doi:10.1002/1521-3870(200202)48:2\%3C301::AID-MALQ301\%3E3.0.CO;2-Z.

[bib.bib22] [22] Risto Kaila. On almost sure elimination of numerical quantifiers. J. Log. Comput., 13(2):273–285, 2003. doi:10.1093/LOGCOM/13.2.273.

[bib.bib23] [23] Matt Kaufmann and Saharon Shelah. On random models of finite power and monadic logic. Discrete Mathematics, 54(3):285–293, 1985. doi:10.1016/0012-365X(85)90112-8.

[bib.bib24] [24] H. Jerome Keisler and Wafik Boulos Lotfallah. Almost everywhere elimination of probability quantifiers. Journal of Symbolic Logic, 74(4):1121–1142, 2009. doi:10.2178/JSL/1254748683.

[bib.bib25] [25] Phokion G. Kolaitis and Swastik Kopparty. Random graphs and the parity quantifier. Journal of the Association for Computing Machinery, 60(5):1–34, October 2013. doi:10.1145/2528402.

[bib.bib26] [26] Per Lindström. First order predicate logic with generalized quantifiers. Theoria, 32(3):186–195, 1966.

[bib.bib27] [27] Per Lindström. On extensions of elementary logic. Theoria, 35(1):1–11, 1969.

[bib.bib28] [28] M. H. Löb. Meeting of the association for symbolic logic, leeds 1962. The Journal of Symbolic Logic, 27(3):373–382, 1962. First abstract: Plurality-quantification by Nicholas Rescher. doi:10.1017/S0022481200118742.

[bib.bib29] [29] Peter Winkler. Random structures and zero-one laws. In Sauer N. W., Woodrow R. E., and Sands B., editors, Finite and Infinite Combinatorics in Sets and Logic, Advanced Science Institutes, pages 399–420. Kluwer Academic Publishers, Dordrecht, 1993.

First-Order Logic with Equicardinality in Random Graphs

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Background and Previous Results

Definition 1.

Theorem 2 (GKLT-Fagin).

Lindström Extensions

Definition 3.

Definition 4.

Theorem 5 (Dawar-Grädel).

Arithmetization

Example 6.

Definition 7 (Arithmetization).

Proposition 8.

Proof.

Theorem 9 (Kaufmann-Shelah).

Theorem 10 (Haber-Shelah).

Equicardinality Quantifiers

Definition 11.

Proposition 12.

Proof.

▶ Remark 13.

1.2 Our Results

Theorem 14 (Main Theorem).

Corollary 15.

Notation and Conventions

2 Some Probabilistic Results

2.1 Defining Sets of Logarithmic Size

Definition 16.

▶ Remark 17.

Theorem 18.

Claim 19.

Lemma 20.

Proof of Lemma 20.

Proof of Theorem 18.

Corollary 21.

Proof.

2.2 Expressing Unary Relations

Definition 22.

Proposition 23.

Proof.

Proposition 24.

Proof.

2.3 Non-Conditioned Results

Theorem 25.

Proof.

▶ Remark 26.

3 Proof of the Main Theorem

Lemma 27 (Kaufmann-Shelah).

Proof.

Lemma 28.

Proof.

Definition 29.

Lemma 30.

Proof.

Definition 31.

Lemma 32.

Proof.

Proof of Theorem 14.

Case 1: 𝝋 holds in [𝒄𝟏⁢𝐥𝐧⁡𝒏𝒌,𝒄𝟐⁢𝐥𝐧⁡𝒏𝒌].

Case 2: ¬𝝋 holds in [𝒄𝟏⁢𝐥𝐧⁡𝒏𝒌,𝒄𝟐⁢𝐥𝐧⁡𝒏𝒌].

References

$\blacktriangleright$ Remark 13.

$\blacktriangleright$ Remark 17.

$\blacktriangleright$ Remark 26.

Case 1: $\varphi$ holds in $\left[\sqrt{c_{1}\ln n_{k}},\sqrt{c_{2}\ln n_{k}}\right]$ .

Case 2: $\neg\varphi$ holds in $\left[\sqrt{c_{1}\ln n_{k}},\sqrt{c_{2}\ln n_{k}}\right]$ .