Fact-checked by Grok 2 weeks ago

Higher-order logic

Higher-order logic (HOL) is a in that generalizes by permitting quantification not only over individual variables but also over predicates, functions, and higher-type entities such as properties of properties. This extension enables the expression of complex statements involving , abstraction, and relations between logical objects, making HOL more expressive than first-order logic for formalizing , metaphysics, and aspects of semantics. The foundations of higher-order logic trace back to Gottlob Frege's (1879), which introduced second-order quantification over concepts and relations, allowing predicates to be treated as objects within the logical system. Frege's innovation laid the groundwork for quantifying into non-subject positions, such as ∃F (Fa), where F ranges over predicates rather than individuals. This was further advanced by and in their (1910–1913), which employed a ramified theory of types—a higher-order framework—to resolve paradoxes like arising from , while deriving all of from logical axioms. In the 1930s, developed the as a foundation for higher-order computation and logic, providing mechanisms for (e.g., λx (x is furry)) that underpin modern type systems. Syntactically, HOL employs typed variables to distinguish orders: for instance, type e for entities, type t for truth values, and functional types like ⟨e,t⟩ for unary predicates. Semantically, it supports both predicative interpretations (where higher types are built from lower ones without ) and impredicative ones (allowing circular definitions), though the latter raises concerns about consistency. Unlike , which is compact and complete but limited in expressive power (e.g., unable to fully capture on natural numbers without axioms), HOL can axiomatize Peano arithmetic directly and model second-order concepts like "every property has an instance." These features have made HOL influential in , particularly in interactive theorem provers such as HOL Light and , where it facilitates verified software and hardware design by enabling precise specifications of computational behaviors.

Overview

Definition and motivation

Higher-order logic (HOL), also known as second-order or higher-order predicate logic, extends (FOL) by allowing quantifiers to bind not only individual variables but also variables representing predicates, relations, and functions. In FOL, quantification is restricted to individuals within a domain, limiting its expressive power to statements about objects and their properties via unary predicates or relations. HOL addresses this by introducing higher types, enabling direct reference to properties of properties or functions as arguments, which facilitates the formalization of abstract mathematical structures. The primary motivation for HOL arises from the need to capture concepts that FOL cannot express compactly or at all without auxiliary axioms, such as , , and higher-level abstractions in and . For instance, the completeness property of the real numbers—ensuring every nonempty bounded has a least upper bound—requires quantification over subsets (predicates), which is impossible in pure FOL due to results like the Löwenheim-Skolem theorem that permit non-standard models. Similarly, in , which arises from unrestricted comprehension allowing a set to contain itself as a member, demonstrated the paradoxes of untyped higher quantification and motivated the development of typed HOL to impose type restrictions and avoid such inconsistencies. A simple illustrative example is the HOL sentence \forall P \, \exists x \, P(x), which asserts that every has at least one instance in the domain; this cannot be directly stated in FOL, as it would require quantifying over all possible predicates, necessitating additional set-theoretic axioms.

Historical development

Higher-order logic traces its origins to the late 19th century, when introduced elements of second-order quantification in his 1879 work , a for predicate calculus that allowed quantification over predicates and relations, laying the groundwork for higher-order reasoning beyond predicates. This enabled more expressive formalizations of mathematical concepts, such as functions and sets, though Frege's initially lacked explicit to prevent paradoxes. Building on Frege's ideas, incorporated higher-order quantification in his 1889 axiomatization of arithmetic, using second-order logic to express induction over properties, which strengthened the foundational rigor of . Bertrand , confronting the paradoxes arising in , identified the famous paradox in 1903, prompting the development of in his collaboration with ; their 1910–1913 Principia Mathematica employed a ramified to stratify higher-order logic and avoid self-referential contradictions. Alonzo Church formalized simply typed lambda calculus in the 1930s and 1940s, providing a typed framework for higher-order functions that directly influenced the syntax and semantics of higher-order logic by treating functions as first-class citizens. In 1950, Leon Henkin established a completeness theorem for higher-order logic using a generalized notion of models (Henkin semantics), addressing limitations in standard semantics for full classical higher-order logic. Post-World War II developments shifted focus toward computational applications and . In the 1970s, Dana Scott's provided mathematical models for higher-order functions and , enabling rigorous for programming languages and influencing the interpretation of higher-order logics in computational contexts. The 1980s saw practical implementations in proof assistants, notably with the development of automated theorem provers like the Nqthm system by Robert Boyer and J Strother Moore, and John Harrison's HOL Light, which formalized higher-order logic in a minimal kernel for . More recently, from 2020 onwards, extensions of provers like to higher-order features have enhanced mathematical reasoning capabilities. Ongoing research explores applications in higher-order theorem proving.

Syntax

Type system

In higher-order logic (HOL), the provides a hierarchical classification of terms to ensure and avoid paradoxes arising from unrestricted . This structure, originally formalized in Alonzo Church's simple theory of types, distinguishes HOL from untyped logics by assigning types to variables, functions, and predicates, thereby enabling higher-order quantification over functions and relations while maintaining logical consistency. The base types in HOL consist of the type \iota for individuals (representing objects or entities) and the type o for truth values (propositions). These serve as the foundational atoms from which all other types are constructed, with \iota denoting the domain of basic elements and o the domain of boolean-like values that can be true or false. Common notations include \iota and o (as in original formulation), or e and t in linguistic and computational contexts. Function types are formed using arrow notation \sigma \to \tau, where \sigma is the type and \tau is the type, allowing representation of mappings from elements of type \sigma to elements of type \tau. Higher-order function types extend this recursively; for instance, \iota \to o denotes unary predicates over individuals, while (\iota \to o) \to o represents second-order predicates that take first-order predicates as arguments. This enables the expression of complex relations, such as quantification over properties of properties. HOL typically employs in the Church style, where types are constructed from type variables, base types, and arrows via formation rules: any base type or type variable is a type, and if \sigma and \tau are types, then so is \sigma \to \tau. This yields a rigid hierarchy without polymorphism in the basic system. Polymorphic variants, such as those in , introduce over types (e.g., \forall \alpha. \alpha \to \alpha) to allow generic functions, as developed by Jean-Yves Girard. Typing rules assign types to terms systematically: variables are assigned atomic types (e.g., x : \iota), and lambda abstractions \lambda x^\sigma . M receive type \sigma \to \tau if M : \tau under the assumption x : \sigma. For example, if P : \iota \to o, then \lambda x^\iota . P(x) : \iota \to o, ensuring that applications like P(a) are well-typed only when a : \iota. These rules propagate types through abstraction and application, guaranteeing type preservation under substitution. The type system resolves paradoxes like Russell's by imposing strict stratification, disallowing self-referential constructions such as a type-level predicate applying to itself without type-level distinction. In untyped settings, Russell's paradox arises from assuming a set of all sets not containing themselves; in HOL, types prevent such uniform self-application (e.g., no single type \rho satisfies \rho \to o and o \to o simultaneously for the same \rho), as functions must map to higher or distinct levels.

Terms and formulas

In higher-order logic, terms are the basic building blocks of expressions, constructed inductively according to the to ensure type correctness. A term of a given type \sigma can be a x^\sigma, which ranges over objects of type \sigma, or a constant c^\sigma, interpreted as a fixed of the domain of type \sigma. Additionally, if f is a term of type \sigma \to \tau and t is a term of type \sigma, then the application f(t) is a term of type \tau. Finally, if t is a term of type \tau possibly containing free occurrences of a x^\sigma, then the lambda abstraction \lambda x^\sigma . t is a term of type \sigma \to \tau. Formulas, which represent propositions, are simply terms of the base type o (truth values). formulas are formed by applying a or P of type \sigma_1 \to \cdots \to \sigma_n \to o to terms t_1 : \sigma_1, \dots, t_n : \sigma_n, yielding P(t_1, \dots, t_n) of type o. Compound formulas are built from simpler formulas \phi and \psi (both of type o) using logical connectives, treated as constants of appropriate functional types: \neg \phi via \neg_o : o \to o; conjunction \phi \wedge \psi via \wedge_{oo} : o \to o \to o; disjunction \phi \vee \psi via \vee_{oo} : o \to o \to o; \phi \to \psi via \to_{oo} : o \to o \to o; and equivalence \phi \leftrightarrow \psi via \leftrightarrow_{oo} : o \to o \to o. Quantified formulas are formed using universal or existential quantifiers over any type \sigma: if \phi (of type o) contains free occurrences of x^\sigma, then \forall x^\sigma . \phi and \exists x^\sigma . \phi are formulas of type o, where the quantifiers are constants \forall^\sigma : (\sigma \to o) \to o and \exists^\sigma : (\sigma \to o) \to o, respectively. The formation of terms and formulas follows an inductive definition that enforces type correctness at each step: variables and constants are base terms of their assigned types; applications require the function term's output type to match the argument's type; lambda abstractions bind a variable in a body term to produce a functional type; atomic formulas arise from predicate applications yielding type o; connectives combine type-o terms into new type-o terms; and quantifiers apply only to type-o expressions, binding variables of arbitrary type \sigma (including higher-order types). This ensures all well-formed expressions are typed properly, preventing paradoxes like Russell's through the type discipline. In terms and formulas, variables can be free or bound. A variable occurrence is free if it lies outside the scope of any binding operator (lambda abstraction or quantifier); otherwise, it is bound by the nearest enclosing binder. The scope of a quantifier \forall x^\sigma . \phi or \exists x^\sigma . \phi (or lambda \lambda x^\sigma . t) extends to all occurrences of x^\sigma in \phi (or t) not shadowed by inner binders. Two formulas are considered identical up to alpha-equivalence if one can be obtained from the other by consistently renaming bound variables, preserving the structure and bindings; for example, \forall x^\iota . P(x) is alpha-equivalent to \forall y^\iota . P(y). This equivalence accounts for the arbitrariness in choice of bound variable names. A representative example of a higher-order formula is one expressing that every unary predicate is satisfied by exactly one individual: \forall P^{\iota \to o} . \exists x^\iota . P(x) \wedge \forall y^\iota . P(y) \to y = x Here, P is a bound predicate variable of type \iota \to o, the inner universal quantifier binds y^\iota, and the equality = is a constant of type \iota \to \iota \to o. This formula is well-formed as a term of type o, quantifying over unary predicates to assert existence and uniqueness for each.

Semantics

Interpretations and models

In higher-order logic, an , also known as a , provides the semantic for evaluating typed terms and formulas by assigning to each type in the . A M is defined by a collection of non-empty \{D_\sigma \mid \sigma is a type\}, where the domain for the base type of individuals, denoted \iota, is an arbitrary non-empty set D_\iota. For the base type of propositions, often denoted o, the domain D_o is the set of truth values, typically \{0, 1\} or \{\top, \bot\}. Higher-order domains are constructed recursively for complex types. For a function type \sigma \to \tau, the domain D_{\sigma \to \tau} consists of all functions from D_\sigma to D_\tau in the standard semantics, ensuring that higher-order objects like predicates and operators are interpreted as complete function spaces. Specifically, for unary predicates of type \iota \to o, the domain D_{\iota \to o} is the power set \mathcal{P}(D_\iota), identifying subsets of individuals with characteristic functions to truth values. This recursive construction extends to all types, such as D_{(\iota \to o) \to o} as the set of all functions from \mathcal{P}(D_\iota) to D_o, capturing quantification over predicates and higher abstractions. A assignment v in a M is a that maps each typed x^\sigma to an of the corresponding D_\sigma. are updated homomorphically for terms: for a v[f/x^\sigma], where f \in D_\sigma, the new assignment agrees with v except at x^\sigma, which now maps to f; this extends inductively to interpret all closed and open terms via application and abstraction in the domains. A model M = (D, I) for higher-order logic combines the domains D = \{D_\sigma\} with an interpretation function I that assigns to each constant symbol c^\sigma in the signature an element I(c) \in D_\sigma. In full higher-order models, following Church's standard semantics, the domains for higher types are the complete function spaces, leading to models where quantification over predicates ranges over all possible subsets or functions. However, Henkin models employ a more general semantics, where domains for predicate types D_{\sigma \to o} (with \sigma non-propositional) are arbitrary non-empty collections of functions from D_\sigma to D_o, rather than the full power set or function space; this accommodates partial interpretations and ensures completeness properties. Such general models, often called Henkin semantics, interpret higher-order quantifiers over these chosen collections, avoiding the extensional collapse of full models in certain contexts. For example, consider the formula \forall P^{\iota \to o} \exists x^\iota \, P(x) in a model M. In standard semantics, P ranges over all subsets of D_\iota (via characteristic functions), including the empty set, so the formula does not hold, as for the empty predicate there exists no x such that P(x). In a Henkin model, P instead ranges over a selected collection of subsets, and the formula holds if and only if that collection excludes the empty set.

Truth and satisfaction

In higher-order logic, truth is defined relative to a model and a assignment through the relation M, v \models \phi, where M is a model, v is a valuation assigning denotations to free variables, and \phi is a . This relation is defined inductively on the structure of \phi. For atomic formulas P(t_1, \dots, t_n), where P is an n-ary symbol and the t_i are terms, satisfaction holds if the of P in M maps the denotations of the t_i under v to true, i.e., I(P)([t_1]^v_M, \dots, [t_n]^v_M) = \top. The inductive clauses for Boolean connectives follow the standard Tarskian pattern: M, v \models \phi \land \psi if and only if M, v \models \phi and M, v \models \psi; M, v \models \neg \phi if and only if M, v \not\models \phi; and similarly for disjunction and implication, with truth-functional semantics. For quantifiers, M, v \models \forall x^\sigma . \phi if and only if for every element d in the domain D_\sigma of type \sigma in M, M, v[x^\sigma \mapsto d] \models \phi, where v[x^\sigma \mapsto d] is the assignment modified to map x^\sigma to d; the existential quantifier is defined dually. A distinctive feature of higher-order logic is that quantification can occur over higher types, such as function spaces. For a X^{\sigma \to \tau}, the universal quantifier \forall X^{\sigma \to \tau} . \phi requires of \phi under every possible from D_\sigma to D_\tau as the of X, while the existential requires at least one such . This contrasts with , as the domain for higher types consists of all (in full semantics) or definable (in Henkin semantics), enabling quantification over predicates and operators. A formula \phi is valid, denoted \models \phi, if it is satisfied in every model M under every assignment v; a set of formulas \Gamma entails \phi, denoted \Gamma \models \phi, if every model and assignment satisfying all formulas in \Gamma also satisfies \phi. Consider the formula \exists P^{\iota \to o} \forall x^\iota . P(x) in a model with domain D_\iota for individuals (type \iota) and truth values (type o). This asserts the existence of a predicate P that holds for all x \in D_\iota. In full semantics, satisfaction holds in any model with non-empty D_\iota, as the constant-true function (mapping every element to \top) belongs to the full D_{\iota \to o} = [D_\iota \to \{\top, \bot\}], and substituting it yields universal satisfaction. In Henkin semantics, however, the domain D_{\iota \to o} comprises only those functions definable from lower types via axioms, so satisfaction requires that the constant-true predicate is witnessed (e.g., as \lambda x . (x = x)), which holds in standard Henkin models but highlights the semantics' restriction to "nominal" higher-order objects compared to the full power-set construction.

Logical properties

Expressiveness compared to first-order logic

First-order logic (FOL) is fundamentally limited in its expressive power because it permits quantification only over individual elements in the domain, without the ability to quantify over predicates, relations, or higher-type objects. This restriction prevents FOL from directly defining key mathematical concepts such as finiteness or . For instance, finiteness cannot be expressed as a property, as the implies that any consistent has models of every , allowing models to satisfy any purported "finiteness" set. Similarly, in the real numbers requires quantification over subsets or functions, which FOL cannot capture without an infinite axiomatization, as highlighted by the implications of the Löwenheim-Skolem theorems that generate non-standard models lacking such properties. Higher-order logic (HOL) overcomes these limitations by allowing quantification over predicates and higher-order entities, enabling the direct expression of second-order concepts that are inexpressible in FOL. For example, the can be formulated in second-order set theory as the statement that there is no set bijectable with the power set of the natural numbers but not with the natural numbers themselves, a notion reliant on quantifying over all subsets. Likewise, , which asserts the existence of infinite homogeneous sets in colorings of infinite structures, is naturally stated using second-order quantification over subsets. A concrete illustration is the HOL version of the , which posits the existence of an infinite inductive set: \forall S \, (\emptyset \in S \land \forall x (x \in S \to x \cup \{x\} \in S) \to \omega \in S), where S ranges over sets, directly capturing the existence of the natural numbers without needing FOL's infinite schema. One of HOL's key strengths is its ability to achieve categoricity, axiomatizing structures up to in ways impossible for FOL's non-categorical theories. For the natural numbers, second-order Peano arithmetic provides a categorical , ensuring all models are isomorphic to the \mathbb{N} with successor, , and , unlike FOL's Peano arithmetic, which admits non-standard models by the Löwenheim-Skolem theorem. This categorical power extends to the real numbers, where HOL axioms for a complete yield unique isomorphism types. However, HOL's enhanced expressiveness comes with trade-offs: in its full semantics, where higher-order variables range over all subsets or functions on the domain (akin to full power sets), the logic is not recursively axiomatizable, as its validity problem reduces to that of . Henkin semantics mitigates this by restricting higher-order domains to "standard" interpretations within a many-sorted framework, restoring relative to these models. Additionally, advanced results like the Mostowski collapse , which states that every well-founded extensional is isomorphic to a transitive set model under membership, are expressible in HOL due to its ability to quantify over relations and well-foundedness directly.

Decidability and completeness

Higher-order logic (HOL) is undecidable, meaning there is no that can determine the validity of arbitrary HOL formulas, even for simple fragments such as those without relation symbols. This undecidability follows from the embedding of (FOL) into HOL and Church's 1936 theorem establishing the undecidability of FOL with identity, as the validity problem for HOL reduces to that of FOL in this way. Furthermore, even restricted unification problems in third-order logic fragments are undecidable, highlighting the computational challenges inherent to higher-order quantification. Regarding completeness, classical HOL lacks a completeness theorem with respect to full semantics, where models interpret higher-order variables over all possible subsets and functions on the domain, due to the existence of non-standard models that fail to capture standard mathematical structures like the natural numbers. However, in Henkin semantics, which restricts interpretations to sets and functions definable within the language itself (effectively reducing HOL to a many-sorted FOL), a soundness and completeness theorem holds: a formula is provable if and only if it is true in all Henkin models. This result, established by Henkin in 1950, allows semantic entailment in Henkin models to correspond to syntactic provability. The complexity of HOL validity is Π₂-complete, reflecting quantifier elimination difficulties that prevent general decidability, though certain fragments exhibit better behavior. For instance, monadic second-order logic, which quantifies only over predicates, is decidable over structures like infinite binary trees, as shown by Rabin's 1969 theorem using automata-theoretic methods. In general, however, HOL fragments beyond monadic second-order remain undecidable. HOL is typically axiomatized using a Hilbert-style system that extends FOL axioms with higher-order quantifier rules and schemas, such as the comprehension axiom allowing quantification over definable sets and functions. Equality in HOL includes axioms for higher types, such as ∀f ∀g (∀x (f x = g x) → f = g) for functions, ensuring that equal functions agree on all inputs, along with rules for substitution in predicates and quantifiers. A key result illustrating HOL's enhanced power is that while FOL theories like Peano arithmetic are incomplete by Gödel's first incompleteness theorem (1931), HOL can formalize a of arithmetic by quantifying over all subsets, uniquely characterizing the standard natural numbers and proving all true arithmetic statements in that model. Thus, HOL proves all FOL theorems but extends their expressiveness to resolve limitations like incompleteness in formalizing basic mathematics.

Applications and extensions

In mathematics and philosophy

Higher-order logic (HOL) can be semantically interpreted within set theory such as Zermelo-Fraenkel set theory with choice (ZFC), where its higher-order quantifiers are modeled using sets, enabling the formalization of concepts involving power sets and hierarchies in a typed manner. This approach is relevant for discussing issues like the continuum hypothesis, whose truth in HOL models depends on the underlying set-theoretic universe, allowing the capture of infinite cardinalities. HOL also underpins type theory's with , where higher-order types model functors and natural transformations as predicates over morphisms and objects, providing a logical framework for abstract algebraic structures. For instance, in formalizing , HOL defines real numbers through Dedekind cuts, representing each real as a of into lower and upper sets satisfying specific order properties, thus constructing the complete of within a typed logical . This approach ensures rigorous proofs of and axioms directly in HOL, avoiding circularity in foundational developments. In philosophy, HOL has been central to the logicist program of and , which aimed to reduce to pure by defining numbers as equivalence classes of concepts—higher-order entities that quantify over extensions of predicates. and Russell's (1910–1913) exemplified this by developing a ramified within HOL to avoid paradoxes like Russell's, treating propositional functions as higher-order relations stratified by type to prevent impredicative . However, the system's ramified types were later critiqued for overly restricting expressive power, leading to simpler type-free alternatives in modern HOL. Philosophical debates on HOL versus first-order logic (FOL) often center on ontological commitments, as articulated in W.V.O. Quine's critique, which argues that HOL's quantification over predicates and relations commits theorists to abstract entities like sets or properties, unlike FOL's restriction to individuals, thereby inflating ontology beyond empirical necessity. HOL's strength in handling impredicative definitions further fuels these discussions; for example, the least upper bound of a bounded set of reals is defined as the unique element that is an upper bound and minimal among all such, quantifying over the collection itself in a way that FOL cannot express without additional axioms. In metaphysics, HOL formalizes and relations as higher-order entities, allowing quantification over them to analyze , , and ; for instance, a F can be treated as a second-order applicable to individuals or other , resolving puzzles like the property paradox by distinguishing levels of predication. This framework supports debates on whether are abundant (all denote ) or sparse (only fundamental ones exist), with HOL providing tools to regiment arguments without reductions. Recent work, such as Skiba (2024) on higher-order , applies HOL to metaphysical questions about facts as higher-order beings.

In computer science and theorem proving

Higher-order logic (HOL) forms the foundation for several prominent interactive theorem provers used in . Isabelle/HOL, developed by Lawrence Paulson in the early 1990s, is a generic that implements a polymorphic variant of Church's simple theory of types, enabling users to formalize and verify mathematical statements through tactics and structured proofs. HOL4, a successor to earlier HOL systems, provides an environment for specifying and proving theorems in classical higher-order logic, incorporating built-in decision procedures and support for external oracles like solvers to enhance . These systems rely on higher-order unification algorithms within their tactics to handle substitutions involving abstractions, allowing flexible proof search in the presence of bound variables. In programming language design, HOL underpins typed lambda calculi that serve as the core of functional languages such as and , where higher-order functions and polymorphic types enable expressive, type-safe constructions derived from Church's . Coq extends HOL principles through its dependent type theory based on the Calculus of Inductive Constructions, integrating higher-order logic with inductive definitions to support proof assistants that verify both programs and their correctness properties. HOL has been instrumental in formal verification of hardware and software systems. The seL4 microkernel's functional correctness was machine-checked in Isabelle/HOL in 2009, proving that its 8,700 lines of C code and 600 lines of assembly adhere to an abstract specification, preventing crashes and ensuring predictable behavior across all states. In industrial applications, ACL2, while primarily first-order, integrates with HOL via embeddings that allow its use as an oracle for verifying large-scale systems like microprocessors, leveraging HOL's expressiveness for higher-order aspects. Post-2020 advances have applied HOL to AI, particularly neural network verification; for instance, a 2023 framework embeds feedforward neural networks trained in TensorFlow into Isabelle/HOL, enabling proofs of robustness properties like accurate digit classification under perturbations. More recent work in 2025 has explored stable model semantics for higher-order logic programming using Approximation Fixpoint Theory. Extensions of HOL in computing include higher-order abstract syntax (HOAS), which represents object-language binders as meta-language functions to simplify handling of variable scoping and in theorem provers and language implementations. encodings further allow data types, such as booleans and naturals, to be defined purely as higher-order functions within HOL's typed framework, facilitating proofs without primitive constructors.