APPLICATION OF LOGIC TO COMBINATORIAL SEQUENCES 3
The way we defined combinatorial interpretations does not require uniformity.
In the ordered case K could be patched together arbitrarily, in the pure case we
only have to require that it is closed under isomorphisms. Uniformity can be for-
mulated in terms of some device (a Turing machine, a logical formula) or closure
conditions (closed under substructures, products, disjoint unions). In this article
we are mostly concerned with classes defined by logical formulas. Intuitively speak-
ing, a combinatorial interpretation K of a(n) is a logical interpretation of a(n) if K
is definable by a formula in some logic formalism, say full Second Order Logic.
Definition 1.2 (Logical interpretation and Specker sequences).
(i) A combinatorial interpretation K of a(n) is an SOL-interpretation (MSOL-
interpretation) of a(n), if K is definable in SOL(τord) (MSOL(τord)).
(ii) Pure SOL-interpretations ( MSOL-interpretation) of a(n) are defined
analogously.
(iii) We call a sequence a(n) which has a logical interpretation in some frag-
ment L of SOL an L-Specker sequence, or just a Specker sequence if the
fragment is
SOL2.
Remark 1.1. In the sequel of this article we will encounter sequences a(n)
which are the normalized difference
a1(n)−a2(n)
f(n)
of two sequences a1(n),a2(n), which
both have a logical interpretation, and f(n) is a normalizing function depending on
a(n). As this is not a logical interpretation of a(n) we speak here of a logical
characterization of a(n).
The following two propositions are straightforward.
Proposition 1.1.
(i) If a(n) has a combinatorial interpretation then for all n N we have
a(n) 0.
(ii) If a(n) has a combinatorial interpretation then for all n N we have
a(n)
2nd(τ)
, where d(τ) is a constant depending on the vocabulary τ.
(iii) There are uncountably many sequences a(n) which have a combinatorial
interpretation.
Proof. We only prove (iii). Let K0 be the class of structures with one unary
predicate, where the structures have the form [n], ∅. Let K1 be the class of
structures with one unary predicate, where the structures have the form [n], P ,
with no restriction on P . We have dK0 (n) = 1 and dK1 (n) =
2n.
Now let A N
and define
KA = {[n], : n A} {[n],P : n A}
Clearly, for each A N, the class KA gives a pure combinatorial interpretation for
the sequence
dKA (n) =
1 n A
2n n A
Proposition 1.2.
(i) There are only countably many Specker sequences.
2
E. Specker was to the best of our knowledge the first to introduce MSOL-definability as a
tool in analyzing combinatorial interpretations of sequences of non-negative integers.
3
Previous Page Next Page