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

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