Second-order logic

Second-order logic extends first-order logic by allowing quantifiers over properties, relations, or sets as well as individual objects.

First-order logic: A formal logic whose quantifiers range only over individual objects in a domain. It provides the baseline that second-order quantifiers extend.
Full semantics: Second-order semantics in which predicate variables range over every suitable relation on the domain. This interpretation gives second-order logic its characteristic expressive strength.
Löwenheim–Skolem theorem: A theorem describing the sizes of models first-order theories can have. Full second-order logic avoids key first-order model-size limitations.
Peano axioms: Axioms specifying the natural numbers through zero, successor, and induction. Second-order induction yields a categorical characterization of the natural numbers.
Monadic second-order logic: A fragment of second-order logic that quantifies over individual objects and unary predicates. Restricting relation variables yields a more manageable expressive fragment.
Predicate logic: A family of formal systems that represent objects, predicates, and quantified statements. Second-order logic is an extension within this broader logical framework.
Henkin semantics: Second-order semantics in which predicate variables range over selected collections of relations. Its restricted ranges restore a complete proof system for validities.
Compactness theorem: A theorem stating that a set of first-order sentences has a model if every finite subset does. Compactness fails for full second-order consequence.
Principle of mathematical induction: A principle stating that a property holding at a base case and preserved by succession holds throughout the natural numbers. Second-order formulations quantify over properties to state induction in one axiom.
Higher-order logic: A family of logics permitting quantification over entities of types beyond individual objects. Second-order logic is one level in this broader hierarchy.

Linked from 13 pages