Editing Second-order logic (section)

==Syntax and fragments==
{{anchor|fragments}}
The syntax of second-order logic tells which expressions are well formed [[formula (mathematical logic)|formulas]]. In addition to the [[First-order logic#Formation rules|syntax of first-order logic]], second-order logic includes many new ''sorts'' (sometimes called ''types'') of variables. These are:
* A sort of variables that range over sets of individuals. If ''S'' is a variable of this sort and ''t'' is a first-order term then the expression ''t'' ∈ ''S'' (also written ''S''(''t''), or ''St'' to save parentheses) is an [[atomic formula]]. Sets of individuals can also be viewed as [[Finitary relation|unary relation]]s on the domain.
* For each natural number ''k'' there is a sort of variables that ranges over all ''k''-ary relations on the individuals. If ''R'' is such a ''k''-ary relation variable and ''t''<sub>1</sub>,...,''t''<sub>''k''</sub> are first-order terms then the expression ''R''(''t''<sub>1</sub>,...,''t''<sub>''k''</sub>) is an atomic formula.
* For each natural number ''k'' there is a sort of variables that ranges over all functions taking ''k'' elements of the domain and returning a single element of the domain. If ''f'' is such a ''k''-ary function variable and ''t''<sub>1</sub>,...,''t''<sub>''k''</sub> are first-order terms then the expression ''f''(''t''<sub>1</sub>,...,''t''<sub>''k''</sub>) is a first-order term.
Each of the variables just defined may be universally and/or existentially quantified over, to build up formulas. Thus there are many kinds of quantifiers, two for each sort of variables. A ''sentence'' in second-order logic, as in first-order logic, is a well-formed formula with no free variables (of any sort).

It's possible to forgo the introduction of function variables in the definition given above (and some authors do this) because an ''n''-ary function variable can be represented by a relation variable of arity ''n''+1 and an appropriate formula for the uniqueness of the "result" in the ''n''+1 argument of the relation. (Shapiro 2000, p.&nbsp;63)

'''[[Monadic second-order logic]]''' (MSO) is a restriction of second-order logic in which only quantification over unary relations (i.e. sets) is allowed. Quantification over functions, owing to the equivalence to relations as described above, is thus also not allowed. The second-order logic without these restrictions is sometimes called ''full second-order logic'' to distinguish it from the monadic version. Monadic second-order logic is particularly used in the context of [[Courcelle's theorem]], an algorithmic meta-theorem in [[graph theory]].  The MSO theory of the complete infinite binary tree ([[S2S (mathematics)|S2S]]) is decidable.  By contrast, full second order logic over any infinite set (or MSO logic over for example (<math>\mathbb{N}</math>,+)) can interpret the true [[second-order arithmetic]].

Just as in first-order logic, second-order logic may include [[non-logical symbol]]s in a particular second-order language. These are restricted, however, in that all terms that they form must be either first-order terms (which can be substituted for a first-order variable) or second-order terms (which can be substituted for a second-order variable of an appropriate sort).

A formula in second-order logic is said to be of first-order (and sometimes denoted <math>\Sigma^1_0</math> or <math>\Pi^1_0</math>) if its quantifiers (which may be universal or existential) range only over variables of first order, although it may have free variables of second order. A <math>\Sigma^1_1</math> (existential second-order) formula is one additionally having some existential quantifiers over second order variables, i.e. <math>\exists R_0\ldots\exists R_m \phi</math>, where <math>\phi</math> is a first-order formula. The fragment of second-order logic consisting only of existential second-order formulas is called '''existential second-order logic''' and abbreviated as ESO, as <math>\Sigma^1_1</math>, or even as ∃SO. The fragment of <math>\Pi^1_1</math> formulas is defined dually, it is called universal second-order logic. More expressive fragments are defined for any ''k'' > 0 by mutual recursion: <math>\Sigma^1_{k+1}</math> has the form <math>\exists R_0\ldots\exists R_m \phi</math>, where <math>\phi</math> is a <math>\Pi^1_k</math> formula, and similar, <math>\Pi^1_{k+1}</math> has the form <math>\forall R_0\ldots\forall R_m \phi</math>, where <math>\phi</math> is a <math>\Sigma^1_k</math> formula. (See [[analytical hierarchy]] for the analogous construction of [[second-order arithmetic]].)