9Non‐expressibility of a class of finite graphs
Akito Tsuboi

Institite of Mathematics,University of Tsukuba
1Introduction

A graph is an R‐structure in which R is irreflexive and symmetric. In thisarticle, we will use a compactness argument to examine the expressibility ofa class of finite graphs. First let us explain a simple example as follows: Let
C be the class of all finite circles, i.e., all graphs H of the form:\bullet H=\{h_{1}, . . . , h_{n}\} ;\bulletR^{H}=\{h_{1}h_{2}, h_{2}h_{3}, . . . , h_{n-1}h_{n}, h_{n}h_{1}\} , where hk denotes (h, k), (k, h) .

Then C is not an elementary class, because finiteness cannot be represented
by a sentence or even by a set of sentences. Furthermore, there is no R‐
sentence \varphi such that, for any finite graphs G,

G\models\varphi\Leftrightarrow G\in C.
For showing this, we can use a compactness argument: Suppose that there
were such a sentence \varphi . Let T be the theory consisting of the following
sentences:

1. Graph axioms;
2. Every node has exactly two neighbors;

3. There is no (finite) cycles.

10Since every finite part of T is satisfied by a graph in C , by compactness, there
is a countable infinite graph G_{0}\models T\cup\{\varphi\} . By extending G_{0} , if necessary,
we can assume G_{0} is a disjoint union of countably many \mathb {Z} ‐chains. Noticethat every graph consisting of two circles does not belong to C . So, again bycompactness, there is a countable infinite graph G_{1}\models T\cup\{\neg\varphi\}. G_{1} is also
assumed to be a disjoint union of countably many \mathb {Z} ‐chains. So, we must
conclude G_{0}\cong G_{1} , a contradiction.
In this paper, concerning finite graphs, we consider a different type of(non‐) expressibility.
2Preliminaries

Let L=\{R(*, *)\} and L^{*}=L\cup\{X_{i}(*) : i<n\} , where R is a binary
predicate symbol, and X_{i} ’s are unary predicate symbols. Let T be a finite
set of L ‐sentences and\varphi(X_{0}, \ldots, X_{n-1}) an L^{*} ‐sentence.

PC_{fin}(\varphi, T) is the class of L ‐reducts of finite models of T\cup\{\varphi\} . If T is the axiom for graphs, we simply write PC_{fin}(\varphi) for PC_{fin}(\varphi, T) .

Definition 1.

PC stands for ‘pseudo elementary class.’

Example 2.
1. Let C be the class of all non‐connected finite graphs.
Then, there is a sentence \varphi such that PC_{fin}(\varphi)=C . Let \varphi be thesentence asserting that (i) both X_{0} and \neg X_{0} are non‐empty, and (ii)there is no edge between X_{0} and \neg X_{0} . Then clearly \varphi satisfies therequired condition.
2. Let C be the class of all finite graphs with a cycle. Then Then, there
is a sentence \varphi such that

PC_{fin}(\varphi)=C.

Now another important point will be explained below. In the structure
In other words, \mathb {N} can beconsidered as a model of finite set theory. So, we assume \mathbb{N}=(\mathbb{N}, 0,1, +, \cdot, <\in) , where \in is the membership relation. Finite graphs are objects in \mathbb{N}.
Let G be a finite graph with the code a_{G} , i.e. G=\{g\in \mathbb{N} : \mathbb{N}\models g\in a_{G}\}.
The connectedness of G can be expressed by a sentence in \mathb {N} as follows: G
is connected \Leftrightarrow there is a coded function f : [0, n]arrow G such that (i)\mathb {N} , by a coding method, finite sets are represented.

,ran (f)=G , and (ii) R(f(i), f(i+1))(\forall i<n) .
Let \mathbb{N}^{*}\succ \mathbb{N} be a recursively saturated countable model. In \mathbb{N}^{*} , a coded
set \{x\in \mathbb{N}^{*} : x\in a\} , where a\in \mathbb{N}^{*} , is not necessarily finite. Let con(x) be1111

the formula expressing (in \mathb {N} ) that the graph coded by x is connected, andlet a\in \mathbb{N}^{*} be an element with \mathbb{N}^{*}\models con(a) . The graph coded by a is notconnected in general, although it is connected in the sense of \mathbb{N}^{*}

3

Non‐expressibility

As an application of compactness argument to finite graphs, we show thefollowing proposition, which is due to Fagin [1].
Proposition 3. Let C be the class of all finite connected graphs. Then thereis no L^{*} ‐sentence\varphi=\varphi(X_{0}, \ldots, X_{n-1}) with C=PC_{fin}(\varphi) .

Sketch of Proof. A more detailed proof of a more general result be given in
our forthcoming paper. Suppose that there were a sentence \varphi(X_{0}, \ldots, X_{n-1})
with C=PC_{fin}(\varphi) . Let C_{n} be the circle graph with the universe [0, n-1]
and the edges R(i, i+1)(i<n-1) and R(n-1,0) . Now we work in \mathbb{N}^{*}
Let n^{*} be a nonstandard number, and let G=C_{n^{*}} . Since C_{n}\models\varphi for all n,
we have some coded sets D_{0} , . . . , D_{n-1} such that

G\models\varphi(D_{0}, \ldots, D_{n-1}) .

(1)

By the recursive saturation, there are two points a<b\in \mathbb{N}^{*} such thattp_{\mathbb{N}^{*}}(a/n^{*}, d_{0}, \ldots, d_{n-1})=tp_{\mathbb{N}^{*}} (b/n^{*}, d_{0}, \ldots, d_{n-1}) , where d_{i} is the code ofD_{i} . We define a new graph G' by:

1. The universe of G' is the same as G , hence |G'|=|G|=[0, n^{*}-1] ;2.

R^{G'}=R^{G}\backslash \{a(a+1), b(b+1)\}\cup\{a(b+1), b(a+1)\}

Each ofG

and G' is a disjoint union of \mathb {Z} ‐chains with coloring by X_{i}' s.

By our construction, G and G' are definable (and hence both are coded in\mathbb{N}^{*}) . Moreover, they are isomorphic as \{R, X_{0}, . . . , X_{n-1}\} ‐structures, since
they have the same \mathb {Z} ‐chains (counting multiplicity) with coloring. Hence wehave:

Claim A. G\cong\{R,X_{0},\ldots,X_{n-1}\}G' . This isomorphism, say \sigma , is not definablein \mathbb{N}^{*} But, each D_{i} is \sigma ‐invariant.

On the other hand, G' is not connected in the sense of \mathbb{N}^{*} (in fact, it is adisjoint union of two circles), hence we have:
Claim B. G'\models\neg\varphi(B_{0}, \ldots, B_{n-1}) , for all coded sets B_{i}' s.

The two claims above together with (1) yield a contradiction.

\square12References[1] Fagin, R. Monadic generalized spectra. Zeitschrif für Mathetatische Logik
und Grundlagen der Mathematik, 21 (1975), 123—134.
[2] Libkin, L. Elements of finite model theory. Berlin: Springer, (2015).

[3] Kaye, R. W. Models of peano arithmetic; Clarendon Press: Oxford, 2011.
[4] Our forthcoming paper.