first order languages over graphs (and other discrete models)

Question

A lot of research has been devoted to the study of first order language of graphs (FO). Formulas in this language are constructed using variables $x, y,\dots$ ranging over the vertices of a graph, the usual quantifiers ∀, ∃, the usual logical connectives ¬, ∨, ∧, etc., parentheses and the binary relations =, ∼, where x ∼ y denotes that x and y are adjacent. . In FO one can for instance write “G is triangle-free” as ¬∃x, y, z : (x ∼ y) ∧ (x ∼ z) ∧ (y ∼ z).

In this context, a lot has been studied for 0-1 laws concerning sequences of graphs $\{G_i\}_{i\geq 1}$. For instance, a really strong result due to Shelah and Spencer says that that if $p = n^{−α}$ with $0 ≤ α ≤ 1$ fixed, then the FO-zero-one law holds if and only if α is an irrational number.

Possibly this is obvious for someone coming from logic (I am not from the area), but I would like to know if there are similar models not for graphs. In particular, I am interested on knowing if there (or if it has been studied or defined) FOs (or extensions of FOs) over

1.- on subsets of integers (roughly speaking, those are 1-uniform hypergraphs), here it is not clear to me how to define a binary relation. For instance, one would like to encode here that a certain set is $k$-AP free, or a sum-free set.

2.- more generally to $k$-uniform hypergraphs with $k>2$ (definitely we need more than a binary relation).

References would be greatly appreciated

Answer 1

To complement J.-E. Pin's answer, many other structures have been considered in the literature, like words [1], discrete metric spaces [2], maps [3] or simplicial complexes [4]. In [5] the relations between some of these results are investigated as instances of a more abstract theorem. The case of $k$-uniform hypergraphs has been treated in [6], and fairly unsurprisingly most results on graphs convert to similar results on hypergraphs in a straightforward (yet tedious) way. The general case of hypergraphs (non-uniform, with multiple edges allowed) has been treated in [7], using the encoding as bipartite graphs. Again, the results are fairly straightforward extensions from the graph case.

The convergence law of random graphs has three components, the structure, the language, and the probability distribution. Most of the previously mentioned results have a general likeness to each other, which suggests rather to explore stronger langages (extensions of FO, MSO) or more complex distributions. The difficulty is to find a balance, where you can still get something; there are a number of negative results for example for fragments of Second Order logic. If you are interested in these questions, you can start with the introduction of [8].

Two last interesting papers interesting results that are related but open up different horizons. In [9], the authors studies matroids in the framework of Nešetřil and de Mendez (full FO-convergence). In [10], the author uses analogues of the Rado graph to obtain set-theoretic results.

To conclude, there is no general survey of "FO on discrete structures"; the existing ones are more specific and/or a bit old. You can start with [11], which is nice and easy to read. This may be a bit messy since there are many things to cover, so don't hesitate to ask for details on some points!

[1] James Lynch, "Convergence laws for random words"

[2] Dhruv Mubayi, Caroline Terry, "Discrete metric spaces: structure, enumeration, and 0-1 laws"

[3] Bender, Compton, Richmond, "0-1 Laws for Maps"

[4] Andreas Blass, Frank Harary, "Properties of almost all graphs and complexes"

[5] Andreas Blass, Yuri Gurevich, "Zero-One Laws: Thesauri and Parametric Conditions"

[6] Nicolau C. Saldanha, Márcio Telles, "Some examples of asymptotic combinatorial behavior, zero-one and convergence results on random hypergraphs"

[7] Nans Lefebvre, "Convergence law for hyper-graphs with prescribed degree sequences"

[8] Peter Heinig, Tobias Muller, Marc Noy, Anusch Taraz, "Logical limit laws for minor-closed classes of graphs"

[9] Frantisek Kardos, Daniel Kral, Anita Liebenau, Lukas Mach, "First order convergence of matroids"

[10] Joel David Hamkins, "Every countable model of set theory embeds into its own constructible universe"

[11] P. Winkler, "Random structures and zero-one laws"

Answer 2

I am not sure whether this is the answer you expect, but the nice survey [1] might be of interest to you. In particular it contains the following result. Let $p$ be a prime number. A subset $S$ of $\mathbb{N}$ is said to be $p$-recognizable if there exists a finite automaton accepting the set $$ \{ a_0a_1 \dotsm a_k \in \{0,1,...,p−1\}^* \mid a_0p^k + a_1p^{k−1}+ \dots + a_kp^0 \in S\} $$ Theorem. Let $S$ be a subset of $\mathbb{N}$ and let $s_0 < s_1 < \dotsm$ be the ordered sequence of the elements of $S$. The following conditions are equivalent:

1. $S$ is $p$-recognizable,

2. $S$ is first order definable in the structure $⟨\mathbb{N},+,v_p⟩$, where $v_p(x)$ is the greatest power of $p$ dividing $x$ if $x \not= 0$ and $v_p(0) = 1$,

3. The series $\sum_{n \geqslant 0} s_nX^n$ is algebraic over $\mathbb{F}_p[X]$.

There is actually a fourth equivalent condition, which I omit. There is also an extension to $\mathbb{N}^k$.

[1] V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic and $p$-recognizable sets of integers. Journées Montoises (Mons, 1992). Bull. Belg. Math. Soc. Simon Stevin 1 (1994), no. 2, 191-238.

[2] V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Correction to: "Logic and $p$-recognizable sets of integers''. Bull. Belg. Math. Soc. Simon Stevin 1 (1994), no. 4, 577.