Fact-checked by Grok 2 weeks ago

Second-order logic

Second-order logic is a formal logical system that extends by permitting quantification over predicates, relations, and functions in addition to individuals, thereby allowing the expression of second-level concepts such as properties of properties or relations among relations. This augmentation provides significantly greater expressive power than , enabling the formulation of theories that are categorical—meaning they have a unique model up to —for key mathematical structures like the natural numbers and the real numbers. Unlike , which is complete and enjoys the Löwenheim-Skolem theorem guaranteeing non-standard models, second-order logic under standard semantics is incomplete, lacking a recursive axiomatization that captures all validities, and it presupposes a richer akin to . The syntax of second-order logic builds directly on that of , incorporating variables for predicates (e.g., monadic P, binary R) and functions alongside individual variables, with quantifiers ranging over all possible subsets or relations on the domain in standard interpretations. For instance, the second-order axiom of infinity can express the existence of an , a undefinable in first-order terms. Semantically, two main approaches prevail: standard semantics, where higher-order quantifiers range over the full of the domain, yielding maximal expressive strength but undecidability; and Henkin semantics, which restricts the range to a predetermined collection of predicates, rendering the logic compact and complete but closer in behavior to with expanded vocabulary. These semantics highlight ongoing debates about whether second-order logic constitutes "logic proper" or an informal fragment of , as its validity requires assumptions about the or similar set-theoretic principles. In mathematics, second-order logic underpins foundational theories by providing categorical axiomatizations, such as the second-order Peano axioms, which uniquely characterize the standard model of natural numbers (\mathbb{N}, 0, S, +, \times), unlike the non-categorical first-order version that admits non-standard models. Similarly, second-order formulations of real analysis categorically define the complete ordered field of real numbers, capturing Dedekind completeness in a way unattainable first-order. This categoricity supports neologicist programs in the philosophy of mathematics, reviving Frege's logicism by interpreting second-order logic as a conservative extension capable of deriving arithmetic without impredicative set-theoretic commitments. Philosophically, it raises questions about ontological neutrality, with critics like Quine viewing its set-like quantifiers as embedding mathematics within logic, while defenders emphasize its role in structuralist accounts of mathematical objects. Overall, second-order logic bridges formal systems and mathematical practice, influencing model theory, proof theory, and the semantics of higher-order languages.

Fundamentals

Syntax

Second-order logic extends the syntax of by incorporating variables that range over s and s, in addition to individual variables. The alphabet of a second-order L consists of logical symbols and non-logical symbols. Logical symbols include individual variables (typically lowercase letters like x, y, z), variables (uppercase letters like P, Q with specified n \geq 1), variables (uppercase letters like F, G with n \geq 1), the symbol =, logical connectives such as \neg, \land, disjunction \lor, \to, and biconditional \leftrightarrow, and quantifiers \forall and \exists that apply to both individual and higher-order variables. Non-logical symbols include symbols, symbols, and () symbols, each assigned a fixed . Terms in second-order logic are formed recursively, mirroring terms but extended to include applications of function variables. Specifically, every symbol and every individual variable is a . If t_1, \dots, t_n are terms and f is an n-ary symbol or an n-ary function variable, then f(t_1, \dots, t_n) is a . No other expressions qualify as terms. Formulas are built from atomic formulas using connectives and quantifiers. Atomic formulas include equations t = t' where t and t' are terms, as well as R(t_1, \dots, t_n) where R is an n-ary symbol and t_1, \dots, t_n are terms, or P(t_1, \dots, t_n) where P is an n-ary . If \phi and \psi are formulas, then \neg \phi, \phi \land \psi, \phi \lor \psi, \phi \to \psi, and \phi \leftrightarrow \psi are formulas. If \phi is a formula, x an individual , P a , or F a function , then \forall x \, \phi, \exists x \, \phi, \forall P \, \phi, \exists P \, \phi, \forall F \, \phi, and \exists F \, \phi are formulas. Equality can be defined syntactically using a second-order , such as \forall P \, (P(t) \leftrightarrow P(t')) for unary P. This syntax allows for quantification over predicates and functions, distinguishing second-order logic from . For example, the \exists P \, \forall x \, (P(x) \leftrightarrow x = x) illustrates predicate quantification, where P is a unary binding over a involving individual quantification. Another example is the syntactic definition of identity between relations: \forall x_1 \dots \forall x_n \, (P(x_1, \dots, x_n) \leftrightarrow Q(x_1, \dots, x_n)) for n-ary P and Q. Second-order logic admits various syntactic fragments based on the arities of higher-order variables. Full second-order logic permits and variables of arbitrary (polyadic form). The monadic fragment restricts variables to (i.e., properties of individuals) and typically excludes variables. These fragments share the core formation rules but limit the vocabulary accordingly.

Semantics

In second-order logic, the standard semantics, also known as full semantics, interprets formulas in structures that extend the Tarskian framework of to accommodate quantification over predicates and relations. A structure \mathcal{M} = (D, I) consists of a non-empty domain D of individuals and an interpretation function I that assigns to each non-logical constant an element of D, to each n-ary function symbol a function from D^n to D, and to each n-ary predicate symbol a subset of D^n. For second-order predicate variables, which are n-ary, their interpretations range over the full \mathcal{P}(D^n) of all possible n-ary relations on D. This ensures that second-order quantifiers capture all conceivable subsets or relations definable over the domain. The satisfaction relation \mathcal{M} \models \phi for a second-order formula \phi under an assignment s to the free variables is defined recursively, mirroring the Tarskian definition for but extended to second-order quantifiers. For predicate quantifiers, the clauses are as follows: \mathcal{M} \models \forall P \, \phi for every S \subseteq D^n, \mathcal{M}[S/P] \models \phi, where \mathcal{M}[S/P] denotes the \mathcal{M} with the variable P assigned to S; dually, \mathcal{M} \models \exists P \, \phi there exists a S \subseteq D^n such that \mathcal{M}[S/P] \models \phi. More generally, for an I of the non-logical symbols and an to predicate variables, \mathcal{M} \models \exists P \, \phi holds if there exists an extension I' of I such that the with I' satisfies \phi. This semantics validates principles like the second-order axiom of in models: the \forall X \, \bigl( [X(0) \land \forall y \, (X(y) \to X(y+1))] \to \forall y \, X(y) \bigr) is true in the of natural numbers, as the quantifier \forall X ranges over all subsets, capturing the full inductive sets. Henkin semantics provides a non-standard of second-order logic, treating it as a conservative extension of via many-sorted structures with partial for . In this framework, a model is a pair (\mathcal{M}, \mathcal{G}), where \mathcal{M} = (D, I) is as before, but \mathcal{G} is a fixed collection of subsets of D^n (not necessarily the full \mathcal{P}(D^n)) over which the n-ary predicate variables range; this \mathcal{G} forms an expanded domain of "higher-type" . The satisfaction relation adjusts accordingly: (\mathcal{M}, \mathcal{G}) \models \exists P \, \phi if and only if there exists S \in \mathcal{G} (with matching P) such that (\mathcal{M}, \mathcal{G})[S/P] \models \phi, and similarly for over elements of \mathcal{G}. Introduced by Leon Henkin in his proof for the theory of types, this semantics allows for models of varying cardinalities and ensures the theorem holds, unlike the standard semantics, though it permits non-standard models where, for instance, the induction axiom may require additional comprehension axioms to enforce full validity.

Variants and Fragments

Monadic second-order logic

Monadic second-order logic (MSO) is the fragment of second-order logic in which second-order quantification is restricted to predicate variables, excluding higher-arity relations and symbols. In its , formulas are built from variables (e.g., x, y), second-order variables (e.g., X, Y), constant and symbols from a , atomic formulas of the form X(t) where t is a term, and the usual logical connectives and quantifiers \forall, \exists, which can bind either or second-order variables. For instance, a simple MSO might assert \exists X \forall x (X(x) \lor \neg X(x)), quantifying over a X of the domain. Semantically, MSO is interpreted over structures with domain D, where first-order variables range over elements of D and unary second-order variables range over all subsets of D, i.e., the power set \mathcal{P}(D). This interpretation uses the full power set in standard semantics, allowing MSO to express properties involving arbitrary subsets, such as the existence of a spanning set or a partition into unary classes. MSO significantly extends the expressive power of , particularly on finite structures. For example, the property of graph connectivity—whether there exists a path between every pair of vertices—can be defined in MSO by quantifying over a subset X that includes one vertex and is closed under adjacency to reach all others, but this property is not definable in the existential fragment of monadic second-order logic. On finite structures, MSO captures many combinatorial properties beyond first-order logic, such as 3-colorability of graphs, by quantifying over subsets representing color classes that are independent sets and cover the vertices. Certain fragments of MSO enjoy decidability results, notably over structures like words or trees, where reduces to without delving into construction details. Specifically, the monadic second-order theory of one successor on natural numbers is decidable, as established via connections to finite . Similarly, MSO over infinite trees is decidable, linking to tree models. Regarding its relation to , MSO on finite structures is strictly more expressive, as it defines properties like well-quasi-orderings or of size that cannot. However, MSO inherits properties from , such as Gaifman , which states that every MSO sentence is equivalent to a local formula asserting properties within bounded distances around points, allowing reductions in some expressive cases on sparse or bounded-degree structures.

Henkin semantics

Henkin semantics provides an alternative interpretation of second-order logic, distinct from the full semantics where second-order quantifiers range over the complete of the and all possible functions thereon. In this framework, a Henkin model consists of a (A, V), where A is the of individuals and V assigns to each sort of second-order variable a collection of relations or functions on A, not necessarily exhaustive. This allows for a more flexible semantics that aligns second-order logic more closely with . The construction of Henkin semantics involves expanding the language of second-order logic into a many-sorted language. For each n \geq 1, new sorts are introduced: one for n-ary (relations) and one for n-ary . The original second-order variables are replaced by variables of the corresponding sorts, and second-order quantifiers \forall P or \exists P (for an n-ary P) become quantifiers over the of n-ary relations, which consists of subsets of A^n. Similarly, function variables are handled with appropriate sorts. Predication is interpreted via a new that checks membership in the assigned subsets. This expanded language is then interpreted in standard models, where the domains for and sorts are arbitrary collections closed under the model's operations but not required to be complete. Due to this reduction, satisfaction of a second-order formula in a Henkin model corresponds precisely to satisfaction of its translation in a first-order model of the expanded theory. Consequently, second-order logic under Henkin semantics inherits the compactness theorem—if every finite subset of a set of sentences has a model, then the entire set does—and the Löwenheim-Skolem theorems, which guarantee the existence of models of various cardinalities, including countable ones for any consistent theory. These properties fail in full semantics, where the completeness of the power set prevents such results. Philosophically, Henkin semantics enables second-order logic to mimic key features of first-order logic, such as semantic with respect to a natural deductive system, while preserving much of its expressive strength for mathematical applications. This makes it a practical framework for foundational studies, avoiding the set-theoretic commitments of full semantics that tie validity to the full axiom.

Expressive Power

Comparison to first-order logic

Second-order logic extends syntactically by introducing variables that range over predicates and functions, in addition to the individual variables of . While permits quantification only over individuals (e.g., ∀x φ(x)), second-order logic allows quantification over relations and functions (e.g., ∀P φ(P)), enabling the expression of properties about properties themselves. Semantically, second-order structures interpret second-order variables as ranging over all subsets or functions on the , rather than merely over elements as in . This full semantics, often requiring a set-theoretic , allows second-order logic to capture the complete of the , quantifying over all possible relations, whereas first-order interpretations are limited to designated predicates in the structure. The expressive power of second-order logic strictly surpasses that of , as no theory can fully capture the semantics of second-order logic due to results like the Löwenheim-Skolem theorem, which guarantees non-standard models for theories with infinite models. For instance, second-order logic can axiomatize rigid structures such as the real numbers as the unique complete up to , using a second-order completeness axiom that quantifies over all subsets to assert the existence of least upper bounds, a feat impossible in . A concrete illustration of this enhanced expressiveness is the treatment of . In , induction requires an , one instance for each formula, to ensure the principle holds for all definable properties. In contrast, second-order logic compresses this into a single axiom quantifying over all predicates: \forall P \left( P(0) \land \forall x \left( P(x) \to P(x+1) \right) \to \forall x \, P(x) \right) This axiom categorically characterizes the natural numbers up to , unlike the first-order , which admit non-standard models.

Definability results

One prominent definability result in second-order logic is its ability to characterize the standard model of arithmetic up to isomorphism. Specifically, second-order Peano arithmetic, which includes the second-order induction axiom, has a unique countable model, namely the structure of natural numbers (\mathbb{N}, 0, S, +, \cdot), distinguishing it from first-order Peano arithmetic, which admits non-standard models. This categoricity follows from the full comprehension schema in second-order logic, which allows quantification over all subsets of the domain, enabling the induction axiom to capture precisely the properties of the standard naturals. In set-theoretic contexts, second-order logic can express the continuum hypothesis (CH), stating that there is no cardinality strictly between that of the finite sets and the continuum. This is achieved through a second-order formula \theta_{\text{CH}} that quantifies over subsets of the universe to assert the non-existence of such intermediate sets, a definability not possible in first-order logic due to its limited expressive power over power sets. The truth of CH in second-order set theory depends on the underlying model, such as V_\kappa for inaccessible cardinals \kappa, but the logic itself provides a precise formulation. Second-order logic also defines principles of well-foundedness and well-ordering that exceed capabilities. For instance, the can be formulated as \forall X \, (\forall x \exists y \, X(x,y) \to \exists F \, \forall x \, X(x, F(x))), where X is a second-order over relations, ensuring the of functions for any collection of non-empty sets. This implies the , allowing every set to be well-ordered, and supports axioms of well-foundedness by quantifying over all possible order relations on the domain. Regarding extensions of Lindström's theorem, second-order logic illustrates a in abstract model theory: while it possesses greater expressive power than —enabling definitions like those above—it lacks the property, as shown by failures such as the inability to compactly approximate infinite conjunctions over subsets. This positions second-order logic as a maximal extension in terms of definability for certain semantic classes, such as categorical theories, but outside the scope of logics satisfying both Löwenheim-Skolem and compactness.

Proof and Model Theory

Deductive systems

Deductive systems for second-order logic extend those of to accommodate quantification over predicates and relations, typically through Hilbert-style axiomatic systems or sequent calculi. These systems ensure the derivation of valid second-order formulas while incorporating the additional expressive power of second-order variables. In Hilbert-style systems, the axioms include all standard axioms, such as those for propositional connectives and first-order quantifiers, augmented with second-order-specific axioms. A key axiom is the second-order universal instantiation schema: \forall X \, A \to A[X / F], where X is an n-ary predicate variable, F is an n-ary predicate term, and substitution replaces free occurrences of X in A with F. Another essential component is the quantifier distribution axiom: \forall P \, (\phi \to \psi) \to (\forall P \, \phi \to \forall P \, \psi), where P does not occur free in \psi. The comprehension further allows the existence of predicates defined by arbitrary formulas: \exists X \, \forall v_1 \dots \forall v_n (X v_1 \dots v_n \leftrightarrow A(v_1, \dots, v_n)), where X is an n-ary predicate variable not free in A, and A may contain other free variables treated as parameters. These axioms, first systematically presented in Hilbert and Ackermann's work, enable the formalization of second-order reasoning by ensuring predicates can be introduced and manipulated consistently. The primary inference rules are —from \phi and \phi \to \psi, infer \psi—and , extended to second-order variables: if \phi is a and P does not occur in the assumptions leading to \phi, then \forall P \, \phi is a . This applies uniformly to both individual and predicate variables, allowing the derivation of quantified statements from instances without restrictions beyond variable capture avoidance. Sequent calculi for second-order logic extend Gentzen's LK system for classical by adding rules for second-order quantifiers. The structural rules—such as weakening, , , and cut—remain unchanged, preserving the focus on sequents of the form \Gamma \vdash \Delta, where \Gamma and \Delta are multisets of formulas. For the second-order universal quantifier \forall X, the left rule is: from \Gamma, A[X := \lambda y_1 \dots y_n . B] \vdash \Delta, infer \Gamma, \forall X \, A \vdash \Delta, where the substitution instantiates X with a lambda abstraction defining a via B. The right rule is: from \Gamma \vdash A[X := F], \Delta, infer \Gamma \vdash \forall X \, A, \Delta, with F a fresh variable. Existential quantifier rules follow dually. These rules, without accompanying completeness theorems for full semantics, enable analytic proofs that decompose second-order formulas step-by-step, mirroring first-order derivations but accommodating higher-order s. Such extensions maintain the subformula property for cut-free proofs, facilitating in second-order contexts.

Metalogical properties

Second-order logic is undecidable, meaning there is no algorithm that can determine, for an arbitrary second-order sentence, whether it is valid. This result follows from a reduction to the or the undecidability of , establishing that the validity problem for second-order logic is at least as hard as these undecidable problems. Unlike , second-order logic fails to satisfy the . A classic illustration involves the second-order theory of dense linear orders without endpoints, augmented by a second-order expressing Dedekind completeness (every nonempty subset that is bounded above has a least upper bound). The full set of axioms has a unique model up to , the real numbers, but every finite subset is satisfiable in the rational numbers, which form a dense linear order without endpoints but lack completeness. Thus, no finite subset captures the completeness property, demonstrating non-compactness. Second-order logic is sound and complete with respect to Henkin semantics, where predicate quantifiers range over all subsets definable by first-order formulas in the expanded language; this allows embedding into an extended first-order logic, yielding a completeness theorem via the first-order result. However, under full semantics, where quantifiers range over all subsets of the domain, second-order logic lacks completeness, as there is no effective deductive system that captures all validities due to the non-absolute nature of truth in full models. Gödel's incompleteness theorems apply to recursively axiomatizable extensions of second-order logic but not directly to full second-order Peano arithmetic, which is categorical (all models are isomorphic to the standard natural numbers) and thus "complete" in the sense that every true arithmetic sentence holds in its unique model. The full induction schema in second-order Peano arithmetic is not recursively enumerable, evading the applicability of Gödel's theorems to produce undecidable sentences within the theory.

Applications and Connections

Relation to type theory

Second-order logic can be embedded as a fragment of simple , where the base types are \iota for individuals and o for truth values, with functional types such as \iota \to o representing unary predicates and (\iota \to o) \to o enabling quantification over such predicates. This embedding interprets second-order variables as terms of appropriate functional types within Church's simply typed \lambda-calculus, preserving the expressive of second-order quantification while avoiding paradoxes through strict . Under the Curry-Howard , proofs in second-order logic correspond directly to normalized terms in the second-order , where logical connectives map to type constructors and quantifiers to \lambda-abstractions over predicate types. For instance, a second-order universal quantifier \forall P \, \phi(P) translates to a polymorphic type \forall \alpha. \, \phi(\alpha), with proofs as \lambda-terms that inhabit these types, establishing a deep isomorphism between the proof theory of second-order logic and the term structure of typed functional programs. This relation extends to more advanced systems like , the polymorphic \lambda-calculus, where second-order logic's universal quantification over predicates aligns with type variables ranging over all types, introducing parametricity that guarantees relational properties for polymorphic functions. In , the correspondence via Curry-Howard yields second-order , allowing proofs of parametric theorems such as the inability to distinguish between different instantiations of a polymorphic without side effects. Parametricity in this context ensures that second-order specifications enforce uniform behavior across type instances, a key feature absent in plain second-order logic but inherited through the polymorphic extension. A example is simple theory of types, which axiomatizes second-order logic by incorporating type quantifiers such as \Lambda^{\alpha} M^{\alpha \beta} for over types, alongside primitive constants like the universal quantifier \Pi_o^{(\iota \to o) \to o} that binds second-order variables. This formulation treats second-order predicates as higher-type functions, with axioms ensuring and relative to standard models, thus providing a typed foundation for second-order reasoning.

Computational aspects

The problem for full second-order logic is undecidable. This undecidability is established by a many-one reduction from the problem of determining whether Diophantine equations have integer solutions, which is and known to be undecidable. Certain fragments of second-order logic admit more tractable decision procedures. For instance, the monadic second-order fragment over strings has model-checking complexity in and is decidable through translation to automata, such as Büchi automata in the case of infinite strings. This connection highlights how restricting quantification to predicates preserves decidability while capturing properties of strings. In the context of finite structures, second-order logic plays a central role in . Existential second-order logic, when interpreted over finite ordered structures, captures exactly the NP, as proven by Fagin's theorem: a property of finite structures is expressible in existential second-order logic if and only if it is recognizable in nondeterministic polynomial time. Consequently, for existential second-order formulas on finite structures is NP-complete in combined complexity. Practical implementations for handling second-order fragments include automated theorem provers that support higher-order techniques, enabling reasoning over restricted second-order formulas in domains like and . These tools often reduce second-order problems to or higher-order subsystems for decidable approximation.

Historical Development

Origins and key contributors

The origins of second-order logic trace back to the late , with Gottlob Frege's (1879) introducing key elements of higher-order quantification within his of predicate logic. Frege's notation employed a universal quantifier that ranged over both objects and s, enabling the expression of second-order concepts without explicit type distinctions, though later works like Grundgesetze der Arithmetik (1893–1903) formalized a of function levels to support second-order quantification. This innovation laid the groundwork for logics that could capture properties and relations more expressively than systems, amid growing concerns over paradoxes in . In the early 20th century, and advanced second-order logic through their (1910–1913), where they developed ramified as a foundational framework to reconstruct . This system extended by quantifying over propositional functions and classes, while imposing type restrictions to circumvent paradoxes such as , which had exposed inconsistencies in unrestricted comprehension principles of . The ramified hierarchy distinguished functions by their arguments and formation levels, allowing second-order expressivity while avoiding self-referential vicious circles, though it required the controversial to simplify higher-order definitions. David Hilbert and Wilhelm Ackermann provided a more systematic treatment in their Grundzüge der theoretischen Logik (1928), formally introducing second-order predicate logic—termed the "extended function calculus"—with a deductive system incorporating the Comprehension Axiom Schema and explicit axioms for second-order quantification. This work built on earlier efforts to formalize , emphasizing second-order logic's role in addressing foundational issues in mathematics, including the consistency of arithmetic axioms. Alonzo Church further refined these ideas in 1940 with his formulation of simple type theory, a higher-order system that encompassed second-order logic through , providing a clean alternative to ramified types while preserving expressive power for mathematical foundations. The mid-20th century saw Leon Henkin's seminal 1950 paper on in the theory of types, which introduced general models (now known as Henkin semantics) for second-order logic, proving a relative to these structures and distinguishing them from standard semantics that assume full second-order domains. This development marked a pivotal evolution, shifting second-order logic from its roots in paradox avoidance—particularly and related set-theoretic inconsistencies—toward rigorous model-theoretic foundations that influenced modern and semantics.

Philosophical debates

One central philosophical debate surrounding second-order logic concerns the choice between full semantics and Henkin semantics, particularly regarding their ontological commitments. In full semantics, second-order quantifiers range over all subsets and functions on the domain, which proponents argue provides a interpretation by committing to the of all possible properties and relations as genuine entities. Stewart defends this view, maintaining that such semantics aligns with a robust about mathematical structures, where the full power of second-order quantification reflects an objective of abstracta. In contrast, Henkin semantics restricts quantifiers to a specified collection of predicates, often those definable within a extension, thereby reducing ontological commitments and leaning toward by avoiding the positing of "too many" entities. This restriction enables a theorem but sacrifices the categoricity achieved in full semantics. The legacy of , as pursued by Frege and , further fuels debates about second-order logic's foundational status. Frege's system in the Grundgesetze der Arithmetik employed second-order quantification to derive the from purely logical principles, aiming to reduce to logic without set-theoretic assumptions. and extended this in using a ramified to formalize , though necessitated type restrictions that complicated the pure logicist reduction. Critics argue that these efforts ultimately devolved into set-theoretic foundations, as the impredicative comprehensions required for mirror axioms of , undermining the claim that second-order logic is "pure" logic rather than disguised . A prominent criticism comes from W.V.O. Quine, who contended that second-order logic is not a genuine extension of logic but "set theory in sheep's clothing," as its second-order quantifiers effectively range over sets or classes, importing mathematical assumptions under the guise of . Quine viewed this as blurring the boundary between logic and , rendering second-order systems theoretically unappealing compared to logic's austerity. This perspective has influenced nominalist and naturalist philosophies, emphasizing that second-order logic's expressive power comes at the cost of ontological parsimony. Defenders of second-order logic counter these criticisms by highlighting its role in structuralist , where it enables axiomatizations that characterize structures up to , achieving categoricity for key domains like the natural numbers. For instance, second-order Peano arithmetic categorically defines the standard model of , supporting a structuralist view that mathematics concerns invariant relations rather than individual objects. Shapiro and others argue that this categoricity justifies second-order logic's foundational use, as it provides determinate references to mathematical entities without relying on set-theoretic hierarchies, thus preserving a form of compatible with modern structuralism.

References

  1. [1]
    [PDF] A Defense of Second-Order Logic
    Jun 4, 2010 · In contrast with nth-order logics (n C 3), second- order logic is still relatively close to first-order logic, and thus its ontological.
  2. [2]
    [PDF] Journal of Philosophy, Inc. On Second-Order Logic Author(s)
    J SHALL discuss some of the relations between second-order logic, first-order logic, and set theory. I am interested in two quasi-terminological questions ...
  3. [3]
    [PDF] Reverse mathematics and Peano categoricity - Stephen G. Simpson
    Abstract. We investigate the reverse-mathematical status of several theorems to the effect that the natural number system is second-order categorical. One.
  4. [4]
    Second-order and Higher-order Logic
    Aug 1, 2019 · Second-order logic has a subtle role in the philosophy of mathematics. It is stronger than first order logic in that it incorporates “for all properties” into ...Model Theory of Second-Order... · Axioms of Second-Order Logic · CategoricityMissing: key | Show results with:key
  5. [5]
    [PDF] Second-order Logic
    In second-order logic, both the language and the definition of satisfac- tion are extended to include free and bound function and predicate variables, and ...Missing: formal | Show results with:formal
  6. [6]
    Leon Henkin. Completeness in the theory of types. The journal of ...
    Leon Henkin. Completeness in the theory of types. The ... As you have access to this content, a full PDF is available via the 'Save PDF' action button.
  7. [7]
    The monadic second-order logic of graphs. I. Recognizable sets of ...
    Every set of finite graphs, that is definable in monadic second-order logic is recognizable, but not vice versa. The monadic second-order theory of a context- ...Missing: finiteness | Show results with:finiteness
  8. [8]
    https://www.sciencedirect.com/science/article/pii/S0304397520301389
  9. [9]
    Bisimulation invariant monadic-second order logic in the finite
    Jul 2, 2020 · We consider bisimulation-invariant monadic second-order logic over various classes of finite transition systems.Missing: finiteness | Show results with:finiteness
  10. [10]
    Completeness in the theory of types1 | The Journal of Symbolic Logic
    Mar 12, 2014 · Completeness in the theory of types1. Published online by Cambridge University Press: 12 March 2014. Leon Henkin. Show author details. Leon ...
  11. [11]
    Internal Categoricity in Arithmetic and Set Theory - Project Euclid
    The aim of this paper is to synthesize completeness and categoricity in the second- order view. We work within the framework of Henkin second-order logic. We ...
  12. [12]
    https://plato.stanford.edu/entries/axiom-choice/
  13. [13]
    https://tedsider.org/teaching/higher_order_20/HO_CC_second_order_logic.pdf
  14. [14]
    [PDF] Crash Course: - Ted Sider
    Moral: it's hard-wired into the semantics for second-order logic that the second- order quantifier ∀F ranges over subsets of the domain, and that second-order.
  15. [15]
    [PDF] proof theory and meaning: on second order logic - Greg Restall
    Dec 4, 2007 · The second order quantifiers have natural and compelling inference rules, and they also have natural models. These do not match: the inference ...
  16. [16]
    [PDF] Simple Type Theory as Framework for Combining Logics
    Evidently, ST T has many prominent classical logic fragments, including propositional and first-order logic, the guarded fragment, second-order logic, monadic ...
  17. [17]
    [PDF] A Formulation of the Simple Theory of Types Alonzo Church The ...
    Apr 2, 2007 · Thus, e.g., OLL is the type of proposi- tional functions of two individual variables. We purposely refrain from making more definite the nature ...
  18. [18]
    [PDF] The Girard-Reynolds Isomorphism (second edition)
    Jean-Yves Girard and John Reynolds independently discovered the second-order polymorphic lambda calculus, F2. Girard additionally proved a Representation ...
  19. [19]
    [PDF] Undecidability, Incompleteness, and Completenessof Second-Order ...
    Jan 17, 2022 · This paper mechanizes results about second-order logic (SOL) in Coq, including undecidability, incompleteness, and completeness, and shows that ...
  20. [20]
    [PDF] The Complexity of First-Order and Monadic Second-Order Logic ...
    Theorem (Stockmeyer 1974, Vardi 1982) Model-checking for first-order logic FO and monadic second-order logic MSO is PSPACE complete.
  21. [21]
    [PDF] Monadic Second Order Logic and Automata on Infinite Words
    Dec 18, 2007 · 4Thomas suggests Finite Model Theory by Ebbinghaus and Flum for details on this result and other results of descriptive complexity theory ...Missing: finiteness | Show results with:finiteness
  22. [22]
    [PDF] Chapter 7 - Second-Order Logic and Fagin's Theorem
    Second-order logic consists of first-order logic plus new relation variables over which we may quantify. For example, the formula (∀Ar)ϕ means that for all.
  23. [23]
    [PDF] LEO-II - A Cooperative Automatic Theorem Prover for Classical ...
    LEO-II is a standalone, resolution-based higher-order theo- rem prover designed for effective cooperation with specialist provers for natural fragments of ...<|control11|><|separator|>
  24. [24]
    Frege's Logic - Stanford Encyclopedia of Philosophy
    Feb 7, 2023 · Friedrich Ludwig Gottlob Frege (b. 1848, d. 1925) is often credited with inventing modern quantificational logic in his Begriffsschrift.
  25. [25]
    Document Not Found
    **Summary:**
  26. [26]
    Principia Mathematica - Stanford Encyclopedia of Philosophy
    May 21, 1996 · Principia Mathematica, the landmark work in formal logic written by Alfred North Whitehead and Bertrand Russell, was first published in three volumes in 1910, ...
  27. [27]
    Church's type theory - Stanford Encyclopedia of Philosophy
    Aug 25, 2006 · Pattern unification, like first-order unification, is decidable and most general unifiers exist for solvable problems. This is why pattern ...
  28. [28]
    Frege's Theorem and Foundations for Arithmetic
    Jun 10, 1998 · Gottlob Frege formulated two logical systems in his attempts to define basic concepts of mathematics and to derive mathematical laws from the laws of logic.The Second-Order Predicate... · Frege's Theory of Extensions... · Frege's Theorem