# Blatter-Specker Theorem for ternary relations

 Importance: Medium ✭✭
 Author(s): Makowsky, Janos A.
 Subject: Logic » Finite Model Theory
 Keywords: Blatter-Specker Theorem FMT00-Luminy
 Posted by: dberwanger on: May 18th, 2012

Let be a class of finite relational structures. We denote by the number of structures in over the labeled set . For any class definable in monadic second-order logic with unary and binary relation symbols, Specker and Blatter showed that, for every , the function is ultimately periodic modulo .

Question   Does the Blatter-Specker Theorem hold for ternary relations.

Our exposition follows closely [BS84].

## Counting labeled structures modulo

Let be a class of finite structures for one binary relation symbol . We define for

#### Examples:

\item If consists of all -structures, . \item If consists of bijections, \item If is the class of all (undirected, simple) graphs, . \item If is the class of all equivalence relations, then , the {\em Bell Numbers}. \item If is the class of all equivalence relations with two classes only, of the same size, . Clearly, . \item If is the class of all trees, , {\em Caley}.

We observe the following:

And for each the functions, , , are ultimately periodic .

However, iff , hence is not periodic .

## Monadic second-order logic definable classes

The first four examples (all relations, all bijections, all graphs, all equivalence relations) are definable in First Order Logic . The trees are definable in Monadic Second Order Logic ..

is definable in Second Order Logic , but it is not -definable. If we expand to have the bijection between the classes we get structures with two binary relations. The class is now -definable. Let us denote the corresponding counting function . We have for large enough.

## Periodicity and linear recurrence relations

The periodicity of is usually established by exhibiting a linear recurrence relation:

There exists and integers such that for all

#### Examples.

\item In the case of we have \item In the case of we have for all In this case we say that trivializes.

## The Blatter-Specker Theorem

Theorem  (BS84)   Let be a binary vocabulary, i.e. all relation symbols are at most binary. If is a class of finite -structures which is -definable, then for all is ultimately periodic .

Moreover, there exists and integers such that for all i.e we have a linear recurrence relation.

In [F03] Fischer showed that the Specker-Blatter Theorem does not hold for quaternary relations.

The case of ternary relations remains open.