# Second-order logic

**second-ordersecond order logicexistential second-order logicsecond ordersecond-order theory2nd-orderHenkin semanticssecond order predicate calculussecond-order beliefssecond-order predicate calculus**

In logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic.wikipedia

162 Related Articles

### Monadic second-order logic

**monadic second-ordermonadic second order logicmonadic second order theory**

Monadic second-order logic (MSO) is a restriction of second-order logic in which only quantification over unary relations (i.e.: sets) are allowed.

In mathematical logic, monadic second order logic (MSO) is the fragment of second-order logic where the second-order quantification is limited to quantification over sets.

### Higher-order logic

**higher order logichigher-orderHigher Order**

Second-order logic is in turn extended by higher-order logic and type theory.

First-order logic quantifies only variables that range over individuals; second-order logic, in addition, also quantifies over sets; third-order logic also quantifies over sets of sets, and so on.

### Logic

**logicianlogicallogics**

In logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic.

Predicate logic is the generic term for symbolic formal systems such as first-order logic, second-order logic, many-sorted logic, and infinitary logic.

### Second-order arithmetic

**second order arithmeticarithmetical comprehensionΠ 1 1 comprehension**

(See analytical hierarchy for the analogous construction of second-order arithmetic.)

If second-order arithmetic is studied using the full semantics of second-order logic then the set quantifiers range over all subsets of the range of the number variables.

### Independence-friendly logic

**Independence-Friendlyindependence-friendly (IF) logicIndependent-Friendly Logic**

ESO also enjoys translation equivalence with some extensions of first-order logic which allow non-linear ordering of quantifier dependencies, like first-order logic extended with Henkin quantifiers, Hintikka and Sandu's independence-friendly logic, and Väänänen's dependence logic.

This greater level of generality leads to an actual increase in expressive power; the set of IF sentences can characterize the same classes of structures as existential second-order logic (\Sigma^1_1).

### Propositional calculus

**propositional logicpropositionalsentential logic**

In logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic.

Second-order logic and other higher-order logics are formal extensions of first-order logic.

### Löwenheim–Skolem theorem

**(downward) Löwenheim–Skolem propertydownward Löwenheim–Skolem theoremLöwenheim-Skolem theorem**

It follows from the compactness theorem and the upward Löwenheim–Skolem theorem that it is not possible to characterize finiteness or countability, respectively, in first-order logic.

In general, the Löwenheim–Skolem theorem does not hold in stronger logics such as second-order logic.

### Natural deduction

**Deductionelimination ruleintroduction rule**

The weakest deductive system that can be used consists of a standard deductive system for first-order logic (such as natural deduction) augmented with substitution rules for second-order terms.

His 1965 monograph Natural deduction: a proof-theoretical study was to become a reference work on natural deduction, and included applications for modal and second-order logic.

### Branching quantifier

**branching quantifier logic**

ESO also enjoys translation equivalence with some extensions of first-order logic which allow non-linear ordering of quantifier dependencies, like first-order logic extended with Henkin quantifiers, Hintikka and Sandu's independence-friendly logic, and Väänänen's dependence logic.

Several things follow from this, including the nonaxiomatizability of first-order logic with Q_H (first observed by Ehrenfeucht), and its equivalence to the \Sigma_1^1-fragment of second-order logic (existential second-order logic)—the latter result published independently in 1970 by Herbert Enderton and W. Walkoe.

### First-order logic

**predicate logicfirst-orderpredicate calculus**

In logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic.

Axiom systems that do fully describe these two structures (that is, categorical axiom systems) can be obtained in stronger logics such as second-order logic.

### Gödel's completeness theorem

**completeness theoremcompletenesscomplete**

Leon Henkin (1950) defined these semantics and proved that Gödel's completeness theorem and compactness theorem, which hold for first-order logic, carry over to second-order logic with Henkin semantics.

Second-order logic, for example, does not have a completeness theorem for its standard semantics (but does have the completeness property for Henkin semantics), and the set of logically-valid formulas in second-order logic is not recursively enumerable.

### Decidability (logic)

**decidabledecidabilityundecidable**

(Effectiveness) There is a proof-checking algorithm that can correctly decide whether a given sequence of symbols is a proof or not.

Logical systems extending first-order logic, such as second-order logic and type theory, are also undecidable.

### Gottlob Frege

**FregeFrege, GottlobFregean**

However, today most students of logic are more familiar with the works of Frege, who published his work several years prior to Peirce but whose works remained less known until Bertrand Russell and Alfred North Whitehead made them famous.

Frege's logic, now known as second-order logic, can be weakened to so-called predicative second-order logic. Predicative second-order logic plus Basic Law V is provably consistent by finitistic or constructive methods, but it can interpret only very weak fragments of arithmetic.

### Descriptive complexity theory

**descriptive complexitydescriptional complexitylogical characterization**

The field of descriptive complexity studies which computational complexity classes can be characterized by the power of the logic needed to express languages (sets of finite strings) in them.

For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of second-order logic.

### Nonfirstorderizability

**nonfirstorderizable**

Boolos furthermore points to the claimed nonfirstorderizability of sentences such as "Some critics admire only each other" and "Some of Fianchetto's men went into the warehouse unaccompanied by anyone else", which he argues can only be expressed by the full force of second-order quantification.

Boolos argued that such sentences call for second-order symbolization, which can be interpreted as plural quantification over the same domain as first-order quantifiers use, without postulation of distinct "second-order objects" (properties, sets, etc.).

### Fagin's theorem

**Fagin 1974**

NP is the set of languages definable by existential, second-order formulas (Fagin's theorem, 1974).

Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP.

### Skolem's paradox

**countable models of set theory**

This construction is closely related to Skolem's paradox.

Zermelo argued that his axioms should instead be studied in second-order logic, a setting in which Skolem's result does not apply.

### Regular language

**regularregular languagesREG**

REG (the set of regular languages) is definable by monadic, second-order formulas (Büchi's theorem, 1960)

8) it can be defined in monadic second-order logic (Büchi-Elgot-Trakhtenbrot theorem )

### George Boolos

**Boolos, GeorgeBoolosG. Boolos**

In recent years second-order logic has made something of a recovery, buoyed by George Boolos' interpretation of second-order quantification as plural quantification over the same domain of objects as first-order quantification (Boolos 1984).

Boolos argued that if one reads the second-order variables in monadic second-order logic plurally, then second-order logic can be interpreted as having no ontological commitment to entities other than those over which the first-order variables range.

### Set theory

**axiomatic set theoryset-theoreticset**

It was found that set theory could be formulated as an axiomatized system within the apparatus of first-order logic (at the cost of several kinds of completeness, but nothing so bad as Russell's paradox), and this was done (see Zermelo–Fraenkel set theory), as sets are vital for mathematics.

Since the publication of the first volume of Principia Mathematica, it has been claimed that most or even all mathematical theorems can be derived using an aptly designed set of axioms for set theory, augmented with many definitions, using first or second order logic.

### Plural quantification

**multigradeplural quantifierplurally**

In recent years second-order logic has made something of a recovery, buoyed by George Boolos' interpretation of second-order quantification as plural quantification over the same domain of objects as first-order quantification (Boolos 1984).

Boolos argued that 2nd-order monadic quantification may be systematically interpreted in terms of plural quantification, and that, therefore, 2nd-order monadic quantification is "ontologically innocent".

### NP (complexity)

**NPnondeterministic polynomial timeclass NP**

NP is the set of languages definable by existential, second-order formulas (Fagin's theorem, 1974).

In terms of descriptive complexity theory, NP corresponds precisely to the set of languages definable by existential second-order logic (Fagin's theorem).

### PH (complexity)

**PHpolynomial hierarchy PHpolynomial hierarchy**

PH is the set of languages definable by second-order formulas.

PH has a simple logical characterization: it is the set of languages expressible by second-order logic.

### Transitive closure

**extendtransitive closure first-order logictransitively-closed**

PSPACE is the set of languages definable by second-order formulas with an added transitive closure operator.

When transitive closure is added to second-order logic instead, we obtain PSPACE.

### PSPACE

**polynomial spaceAPhard**

PSPACE is the set of languages definable by second-order formulas with an added transitive closure operator.

A logical characterization of PSPACE from descriptive complexity theory is that it is the set of problems expressible in second-order logic with the addition of a transitive closure operator.