S2S (mathematics)

In mathematics, S2S is the monadic second-order theory with two successors.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 7 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics, S2S is the monadic second-order theory with two successors. Its first-order objects are finite binary strings. It is one of the most expressive natural decidable theories known, with many decidable theories interpretable in S2S. Its decidability was proved by Rabin in 1969.

Equality is primitive, or it can be defined as s = t ⇔ ∀S (S(s) ⇔ S(t)) and S = T ⇔ ∀s (S(s) ⇔ T(s)). In place of strings, one can use (for example) natural numbers with n↦2n+1 and n↦2n+2 but no other operations. The set of all binary strings is denoted by {0,1} * , using Kleene star.

Arbitrary subsets of {0,1} * are sometimes identified with trees, specifically as a {0,1}-labeled tree {0,1} * ; {0,1} * forms a complete infinite binary tree. For formula complexity, the prefix relation on strings is typically treated as first order. Without it, not all formulas would be equivalent to \Delta^1_2 formulas.

For properties expressible in S2S (viewing the set of all binary strings as a tree), for each node, only O(1) bits can be communicated between the left subtree and the right subtree and the rest (see communication complexity). For a fixed k, a function from strings to k (i.e. natural numbers below k) can be encoded by a single set.

Moreover, s,t ⇒ s01t where t doubles every character of t is injective, and s ⇒ {s01t : t∈{0,1} * } is S2S definable. By contrast, by a communication complexity argument, in S1S (below) a pair of sets is not encodable by a single set. Weakenings of S2S: Weak S2S (WS2S) requires all sets to be finite (note that finiteness is expressible in S2S using Kőnig's lemma).

S1S can be obtained by requiring that '1' does not appear in strings, and WS1S also requires finiteness. Even WS1S can interpret Presburger arithmetic with a predicate for powers of 2, as sets can be used to represent unbounded binary numbers with definable addition.

Decision complexity S2S is decidable, and each of S2S, S1S, WS2S, WS1S has a nonelementary decision complexity corresponding to a linearly growing stack of exponentials. For the lower bound, it suffices to consider {\Sigma}^1_1 WS1S sentences.

A single second-order quantifier can be used to propose an arithmetic (or other) computation, which can be verified using first-order quantifiers if we can test which numbers are equal. For this, if we appropriately encode numbers 1..m, we can encode a number with binary representation i 1 i 2 ...i m as i 1 1 i 2 2 ... i m m, preceded by a guard.

By merging testing of guards and reusing variable names, the number of bits is linear in the number of exponentials. For the upper bound, using the decision procedure (below), sentences with k-fold quantifier alternation can be decided in time corresponding to k+O(1)-fold exponentiation of the sentence length (with uniform constants).

Axiomatization WS2S can be axiomatized through certain basic properties plus induction schema. S2S can be partially axiomatized by: (1) ∃!s ∀t ( t0≠s ∧ t1≠s) (empty string, denoted by ε; ∃!s means "there is unique s") (2) ∀s,t ∀i∈{0,1} ∀j∈{0,1} (si=tj ⇒ s=t ∧ i=j) (the use of i and j is an abbreviation; for i=j, 0 does not equal 1) (3) ∀S (S(ε) ∧ ∀s (S(s) ⇒ S(s0) ∧ S(s1))⇒ ∀s S(s)) (induction) (4) ∃S ∀s (S(s) ⇔ φ(s)) (S not free in φ) (4) is the comprehension schema over formulas φ, which always holds for second-order logic.

As usual, if φ has free variables not shown, we take the universal closure of the axiom. If equality is primitive for predicates, one also adds extensionality S=T ⇔ ∀s (S(s) ⇔ T(s)). Since we have comprehension, induction can be a single statement rather than a schema. The analogous axiomatization of S1S is complete.

However, for S2S, completeness is open (as of 2021). While S1S has uniformization, there is no S2S definable (even allowing parameters) choice function that given a non-empty set S returns an element of S, and comprehension schemas are commonly augmented with various forms of the axiom of choice.

However, (1)-(4) is complete when extended with a determinacy schema for certain parity games. S2S can also be axiomatized by Π 1 3 sentences (using the prefix relation on strings as a primitive).

However, it is not finitely axiomatizable, nor can it be axiomatized by Σ 1 3 sentences even if we add induction schema and a finite set of other sentences (this follows from its connection to Π 1 2 -CA 0 ). Combining a monadic theory with a first-order theory: Feferman–Vaught theorem extends/applies as follows.

If M is an MSO model and N is a first-order model, then M remains decidable relative to a (Theory(M), Theory(N)) oracle even if M is augmented with all functions M→N where M is identified with its first objects, and for each s∈M we use a disjoint copy of N, with the language modified accordingly. For example, if N is ( \mathbb{R} ,0,+,⋅), we can state ∀(function f) ∀s ∃r∈N s f(s) + N s r = 0 N s . If M is S2S (or more generally, the tree counterpart of some monadic model), the automata can now use N-formulas, and thereby convert f:M→N k into a tuple of M sets.

Disjointness is necessary as otherwise for every infinite N with equality, the extended S2S or just WS1S is undecidable. Also, for a (possibly incomplete) theory T, the theory T M of M-products of T is decidable relative to a (Theory(M), T) oracle, where a model of T M uses an arbitrary disjoint model N s of T for each s∈M (as above, M is an MSO model; Theory(N s ) may depend on s). The proof is by induction on formula complexity.

Let v s be the list of free N s variables, including f(s) if function f is free. By induction, one shows that v s is only used through a finite set of N-formulas with |v s | free variables.

Thus, we can quantify over all possible outcomes by using N (or T) to answer what is possible, and given a list possibilities (or constraints), formulate a corresponding sentence in M. Coding into extensions of S2S: Every decidable predicate on strings can be encoded (with linear time encoding and decoding) for decidability of S2S (even with the extensions above) together with the encoded predicate. Proof: Given a nondeterministic infinite tree automaton, we can partition the set of finite binary labeled trees (having labels over which the automaton can operate) into finitely many classes such that if a complete infinite binary tree can be composed of same-class trees, acceptance depends only on the class and the initial state (i.e. state the automaton enters the tree).

(Note a rough similarity with the pumping lemma.) For example (for a parity automaton), assign trees to the same class if they have the same predicate that given initial_state and set Q of (state, highest_priority_reached) pairs returns whether player 1 (i.e. nondeterminism) can simultaneously force all branches to correspond to elements of Q. Now, for each k, pick a finite set of trees (suitable for coding) that belong to the same class for automata 1-k, with the choice of class consistent across k. To encode a predicate, encode some bits using k=1, then more bits using k=2, and so on.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1359919666 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001359919666 · captured 2026-06-18 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “S2S (mathematics)”, snapshot enwiki-001359919666. https://encyclopegia.org/a/s2s-mathematics

Sources cited in this revision

14 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.