Foundations of mathematics asks what our objects mean, what we assume about them, and why an argument establishes its conclusion. Set theory gives a common language for collections and functions; mathematical logic makes the structure of statements and deductions precise. A mathematical definition fixes a meaning, an axiom supplies an assumption, and a mathematical proof explains what follows. Separating these roles makes results reusable: once the group axioms are enough for a conclusion, that conclusion applies to every group, regardless of how its members are represented.
The assumptions can change the answer to a familiar calculation. Over the real numbers, factors as , so is zero or one. The same reasoning holds in any integral domain, because a product can be zero only when a factor is zero. In the ring of integers modulo six, however, and : there are four solutions, represented by . The extra solutions are idempotents, and the failed step involves zero divisors. Writing the domain is part of explaining the answer.
This precision also reveals surprising possibilities. A two-dimensional grid of natural numbers is a countable set, while all infinite binary sequences form an uncountable set. The Cantor pairing function supplies a complete enumeration of the first; Cantor's diagonal argument defeats every proposed enumeration of the second. Both arguments are short, yet distinguish two sizes of infinity. The subject's appeal is this ability to turn a vague question into one whose assumptions, construction, and limits can all be inspected.
The initial table of content was limited to the first level because it is larger than 1000 articles. There are 3639 articles in total. Expand a branch to load its children.
Mathematical logic studies formal languages, formal proofs, model theory, computability theory, and the foundations of mathematics. It makes the rules of reasoning explicit enough that reasoning itself becomes an object of mathematics. Proof theory studies deductions; model theory studies interpretations in which statements hold.
Three questions organize the subject: is an expression a well-formed first-order formula, is it true in a specified first-order structure, and does it have a formal proof from specified axioms? These questions are distinct. For example, is a first-order sentence in an appropriate first-order language; it is false in the natural numbers but true in the rational numbers, with .
The beauty of mathematical logic is that the same logical connectives and rules of universal quantification and existential quantification organize arguments across mathematics. Classical propositional logic uses two truth values; Intuitionistic propositional logic interprets logical implication through constructions on proofs, without unrestricted law of excluded middle. This proof-based framework is developed in Frank Pfenning, Natural Deduction, sections 1–3.
A three-valued logic uses three truth values together with specified logical connectives and a rule for which values count as designated truth. The truth-value set alone does not determine the logic. A third value can represent incomplete information, but its intended interpretation and inference rules must also be supplied.
For a concrete strong-Kleene semantics, take , , and define negation by , conjunction by and disjunction by . Then and , while . If only is designated, the law of excluded middle is not valid for every valuation in this semantics.
Another three-valued semantics can use implication . It makes , whereas defining implication as would give . This explicit difference shows why one cannot reason from the number of values without specifying the connective tables and designated values.
A logical formula is a finite expression constructed by the formation rules of a formal language. Propositional formulas combine propositional variables by logical connectives. First-order formulas additionally contain terms, atomic relations and quantifiers. A logical formula is a syntactic object; its truth is determined only after specifying a suitable interpretation and values for its free variables.
A logical formula or a collection of formulas is unsatisfiable when no permitted interpretation makes all of it true. The permitted interpretations come from the chosen semantics: Boolean valuations for propositional logic, or structures and variable assignments for first-order logic. Unsatisfiability is therefore a semantic property; a refutation is a syntactic proof of that property.
For example, is unsatisfiable because neither truth value of makes both parts true. The logical formula is satisfiable, although it is false in the valuation assigning false to both letters. Thus being false in one interpretation does not establish unsatisfiability. In classical propositional logic, is valid exactly when is unsatisfiable. Likewise, exactly when is unsatisfiable. This turns entailment questions into searches for countermodels or contradiction certificates.
A logical variable is a symbol whose value is supplied by the semantics of a logical language. A propositional variable receives a truth value under a Boolean valuation. An individual variable of first-order logic receives an element of a structure under an assignment. These are different kinds of variable and should not be identified.
A logical fixed point is a formula or sentence equivalent to the result of applying a specified formula operation to itself. In arithmetic, self-reference is mediated by a Gödel number and the diagonal lemma, yielding a first-order sentence with a provable equivalence . In modal logic, a modal formula satisfies modulo the chosen logic. A merely true semantic equivalence is weaker than a specified provable or canonical construction, so its hypotheses must be kept distinct.
A modal logic extends propositional connectives by operators such as and its dual . An interpretation determines their meaning: necessity, knowledge and formal provability lead to different axiom systems. In a relational semantics, holds at a world when holds at every accessible world. Provability logic interprets the box through arithmetically coded proofs.
Uniform substitution in modal logic replaces each occurrence of a propositional variable by the same modal formula. Normal modal formal proof systems with axiom schemes are closed under this operation: substituted axioms remain instances, modus ponens is preserved, and necessitation commutes with substitution. Fresh auxiliary letters permit substituting a derived fixed point into fixed-point uniqueness theorems without changing other parameters.
Modal logic K4 extends the normal modal distribution axiom and necessitation rule by positive introspection . Its Kripke semantics uses transitive accessibility relations. The fixed point satisfies in this logic.
The normal distribution axiom says that a boxed implication and its boxed antecedent give the boxed consequent. Together with the necessitation rule, it permits boxed versions of propositional deductions. Under an arithmetic interpretation it is the internal modus-ponens condition among the Hilbert-Bernays-Löb derivability conditions. It does not permit dropping a box to assert the enclosed sentence.
A modal formula is built from propositional variables and logical constants using Boolean connectives and modal operators, such as the box operator. In provability logic, arithmetic realization replaces propositional letters by arithmetic sentences and interprets a box as the corresponding arithmetic provability assertion. Modal validity, theoremhood and truth under a particular arithmetic realization are distinct notions.
An occurrence of a propositional variable in a modal formula is modalized if it lies within the scope of a box operator. A variable occurs modalized in a formula when all its occurrences do. For example is modalized in , while is not. Fixed-point and uniqueness theorems for Gödel-Löb logic impose this syntactic condition on the variable being solved for.
Positive introspection says that a boxed assertion can itself be boxed. For an arithmetical provability predicate it is the third of the Hilbert-Bernays-Löb derivability conditions: provability of implies provability of the assertion that is provable. It follows from formalized Sigma-1 completeness when provability assertions are Sigma-1. It is not the reflection principle .
The necessitation rule permits boxing a theorem in a modal proof system. It does not permit boxing an arbitrary temporary assumption. Under an arithmetic interpretation, it uses the external first of the derivability conditions: an actual proof of supplies a proof that has a proof. This distinction matters when proving the Internal form of Löb's theorem.
Provability logic studies modal principles valid when is interpreted by an arithmetical provability predicate. The distribution axiom corresponds to formalized modus ponens rule, necessitation corresponds to verification of actual proofs, and the Löb axiom is the Internal form of Löb's theorem. The standard system capturing these principles is Gödel-Löb logic.
The Gödel-Löb logic has propositional tautologies, and as axiom schemes. Its rules are modus ponens rule and the necessitation rule; uniform propositional substitution is built into the schemes. Under an arithmetic realization, each axiom and each rule preserves provability in a theory with the Hilbert-Bernays-Löb derivability conditions and diagonalization. This proves arithmetic soundness by induction on derivations; it is distinct from claiming that every true arithmetic sentence is provable.
The Löb axiom over normal modal logic already implies . Put . Distribution gives , hence . Necessitation and distribution give ; the Löb axiom gives , which implies .
A formula provably equivalent to a boxed formula satisfies in GL. The displayed fixed point then gives both and under , hence . Boxed explosion proves the reverse implication. Under arithmetic realization this is a formal inconsistency statement; Sigma-1 soundness excludes its provability, while second incompleteness excludes provability of its negation.
If every occurrence of in lies under a box, Gödel-Löb logic has a formula without , using only the other letters of , satisfying the displayed equivalence. Write using the outermost boxes that contain , so has no . Solve by simultaneous boxed fixed-point elimination in GL. If the solutions are , then works by replacement of provably equivalent formulas.
In Gödel-Löb logic, the one-variable identity solves a boxed equation with a formula omitting its unknown letter. A finite simultaneous system can be solved by elimination. First solve its last equation with the other unknowns treated as parameters, substitute that formula into the preceding equations, and apply induction. Substituting the resulting solutions back into the last formula completes the system. This construction introduces no new parameter letters.
Let and . Boxed replacement gives , and positive introspection gives . For the reverse implication rewrite it as , necessitate, use , and apply the Löb axiom to obtain . This explicit one-variable construction needs no reflection axiom.
The Löb axiom gives . The tautology , necessitated and distributed, gives . Thus , and replacing the antecedent in gives exactly . Setting produces a negative-provability fixed point, provably equivalent to .
Map propositional letters to arithmetic sentences, map falsity to a refutable sentence, commute with implication and interpret by an arithmetical provability predicate. Propositional axioms remain theorems. The K axiom uses the second of the derivability conditions, and the Löb axiom uses the Internal form of Löb's theorem. Modus ponens rule is preserved directly, and the necessitation rule uses the first derivability condition. Induction on a GL proof therefore proves the displayed soundness implication for Peano arithmetic with the stipulated provability predicate.
A modal operator forms a new formula from a formula, such as . In provability logic, it represents an assertion that a proof of exists, rather than an assertion that is true. A box is not interchangeable with an unboxed formula.
A description logic describes classes of individuals, called concepts, and binary relationships, called roles. Its constructors are restricted so that logical reasoning tasks can be studied precisely. A TBox specifies general concept constraints, while an ABox records assertions about particular individuals.
For example, describes people related by to some person. A reasoning task may ask whether a concept can be nonempty or whether one concept is included in another. Different choices of constructors change expressiveness and computational complexity theory. These logics provide a mathematical basis for ontology languages and knowledge representation.
The assumption that distinct individual names denote distinct domain elements. Standard ALC semantics does not impose it; Herbrand interpretations do treat distinct ground terms as distinct elements.
A description logic concept is satisfiable with respect to a TBox if some model of that TBox interprets the concept as a nonempty set.
A rule-oriented description logic fragment designed for translation to function-free Horn rules, allowing constraints but excluding existential witness generation in rule conclusions. In an equivalence, each direction must meet the relevant restrictions. [ref]
The description logic generated by atomic concepts, , conjunction and existential restrictions. Some conventions also allow ; that extension is distinguished here as EL with bottom. Without , every concept is satisfiable with respect to every EL TBox.
EL extended with , allowing disjointness and unsatisfiable concepts. Concept satisfiability with respect to general TBoxes is P-complete.
The description logic with atomic concepts, top and bottom, Boolean concept constructors, and existential and universal restrictions on description logic roles.
A concept satisfiability procedure that expands concept labels into a graph, branches on disjunctions, creates witnesses for existential restrictions, propagates universal restrictions along existing edges, and tests for a tableau clash. General TBoxes require global constraints and a termination device such as direct blocking in description logic.
A test that stops further witness generation at a node when an appropriate earlier ancestor already represents its required pattern of labels. The exact test depends on the logic and tableau calculus. An isolated root has no ancestor and is not directly blocked.
An explicit contradiction in a node label, such as both and , or . Opposite universal restrictions alone cause no clash when there are no successors.
A collection of assertions about individuals, such as and , interpreted together with a TBox.
A collection of terminological axioms, including general concept inclusions, constraining the meanings of description logic concepts and description logic roles.
Rewriting suitable general axioms into definitions or primitive inclusions that can be processed when an atomic label is encountered. For example, can be absorbed as .
Substitution of acyclic concept definitions into expressions to be tested. Primitive inclusions require care: can be represented using a fresh name by , but is not equivalent to .
An axiom requiring every instance of the description logic concept to be an instance of . It holds throughout the domain, not just at named individuals.
A binary relation on individuals used by description logic restrictions such as and .
A unary description interpreted as a subset of the domain. Atomic names can be combined using the constructors of the chosen description logic.
Two sentences or theories are equisatisfiable when one has a model if and only if the other has a model. They need not be true in the same interpretations or even use the same signature.
Temporal logic extends ordinary mathematical logic with assertions about successive states or times. Temporal operators express properties such as eventually holding, always holding, or holding until another condition occurs.
In linear temporal logic, says that every request is eventually answered along a trace. A safety property rules out a bad finite behavior; a liveness property requires future progress. Computation tree logic additionally distinguishes possible execution paths. The choice of linear or branching time determines exactly which system behaviors a formula quantifies over.
A branching temporal logic whose operators quantify over paths in a transition system from a state. In particular, , also written , holds at when every infinite path in a transition system from satisfies at every position, including its initial position.
A temporal logic interpreted along infinite paths in a transition system. At position , requires at , requires it at some , and requires it at every . Strong until and weak until express conditions that hold up to a later event. A system satisfies a specification when all relevant initial paths in a transition system satisfy it.
A temporal operator states how a proposition behaves across time in a temporal logic. In linear temporal logic, means that holds at the next position, that it holds eventually, and that it holds at every later position, including the current one.
The binary strong until operator requires a future position where holds and requires at all earlier positions. Thus expresses that every request eventually gets a response. The temporal operators distinguish such behavior from an ordinary Boolean condition evaluated at one instant. Branching-time logics additionally quantify over possible execution paths.
In linear temporal logic, means . Thus it permits the left operand to hold forever without the right operand ever becoming true, unlike strong until.
In linear temporal logic, holds at position exactly when some satisfies and every position with satisfies . The witness must exist. The case imposes no condition on .
The linear temporal logic operator , true at position of a path in a transition system exactly when is true at position . Thus tests two positions ahead.
An inference rule licenses a conclusion from specified premises, possibly with side conditions. A derived inference rule is justified by a logical derivation using the primitive inference rules; using it subsequently abbreviates that logical derivation.
A derived inference rule abbreviates a logical derivation from the primitive inference rules. Its use retains the assumptions and side conditions required by that logical derivation; proving the abbreviation once allows subsequent proofs to use the rule without expanding every intermediate line.
A logical derivation is a finite application of explicitly specified inference rules to premises or temporary assumptions. In natural deduction, which assumptions remain open is part of the logical derivation: a conclusion reached inside a temporary subproof cannot simply be used outside it.
A sequent records that the formula is derivable with undischarged assumptions drawn from . In natural deduction, a temporary assumption contributes to only until an appropriate discharge rule closes its scope.
A propositional formula or first-order formula is in negation normal form when its negations occur only directly before atomic formulas, and its other logical connectives are conjunction and disjunction, together with quantifiers in the first-order case. Remove implications using , then push negations inward using De Morgan's laws, double-negation cancellation, and
In particular, negating an implication gives , so its antecedent retains its original sign after the outer negation has been pushed through.
A choice of a domain and meanings for the symbols of a formal language, used to evaluate its sentences. The same sentence can have different truth values under different interpretations, unless it is valid under every admitted interpretation.
Reasoning in which the conclusion follows from the premises by valid inference. A valid argument need not have true premises; soundness additionally requires their truth.
A solution exists when at least one object satisfies all the stated conditions. In first-order logic, this is expressed by existential quantification. Uniqueness additionally requires that any two solutions are equal.
A solution is unique when any two objects satisfying the stated conditions are equal. This is an at-most-one assertion; existence is a separate requirement. A common proof assumes two solutions, subtracts their equations, and proves that their difference vanishes. For a linear differential equation this turns the task into a homogeneous problem with zero boundary or initial data.
Proof theory studies formal proofs and the deductive systems that produce them. It examines which conclusions follow from axioms, how proofs can be transformed, and what those transformations reveal about the chosen logic. Natural deduction organizes a proof through introduction and elimination rules for logical connectives and quantifiers.
A refutation of a collection of logical assumptions is a derivation of a contradiction from them. To prove a logical formula by refutation in classical propositional logic, add its negation to the assumptions and derive falsity. The correctness of this inference follows from the rules of the chosen proof system.
For example, the clauses , and have a resolution refutation: the first two resolve to , and with yields the empty clause. No truth assignment satisfies the three original clauses. This distinguishes the semantic claim of unsatisfiability from a syntactic certificate establishing it. In automated proving, producing a refutation is useful because another program can check the individual inference steps without repeating the search.
A Hilbert proof system specifies axiom schemes and inference rules, commonly including modus ponens. A formal proof is a finite sequence of axiom instances, permitted assumptions and conclusions obtained from preceding lines by those rules. Soundness and completeness compare this syntactic derivability with semantic validity or semantic entailment. These properties concern the particular chosen axioms and rules.
One presentation of classical propositional logic uses the schemes , , and , together with modus ponens rule and the case rule from and to . Its deduction theorem for propositional logic follows by induction on logical derivations: conditional modus ponens handles a modus ponens rule line, and the second scheme handles a case-rule line.
Take precisely the propositional tautologies as axioms and supply no inference rules. A one-line proof then establishes exactly the valid propositional formulas, so this calculus is sound and complete for theoremhood. Its axiom set is decidable by finite truth tables. This construction does not by itself give strong completeness for consequence from arbitrary assumptions.
An inference rule deriving a clause from two clauses containing complementary literals. In propositional logic the displayed rule eliminates the atom . For first-order clauses, complementary atoms can first be made identical by a suitable first-order substitution.
A rule that combines first-order clauses by unifying complementary first-order literals and retaining the other literals under the resulting first-order substitution. Completeness requires the appropriate calculus and search conditions.
A family of resolution calculi for first-order Horn clauses. A selection function chooses either the positive head atom alone or a nonempty set of body atoms. Permitted inferences respect those choices; fair saturation is refutationally complete. Function symbols need not be excluded, so completeness does not by itself guarantee termination. [ref]
The use of resolution on ground clauses. A finite refutation ends in the empty ground clause and establishes unsatisfiability of the chosen ground instances. Herbrand's theorem explains the completeness of searching for such refutations for universal equality-free first-order clauses.
An axiom is a sentence admitted as a starting assumption of a formal theory. An axiom schema specifies a collection of such sentences, usually one for each formula of an allowed form. A model of a first-order theory satisfies all its axioms; a relative consistency construction can show that the other axioms do not imply a particular omitted one.
An axiom set is the collection of formulas available as axioms in a specified formal proof system. It may be finite or infinite, or specified by an axiom scheme.
For an independent axiom set, semantic entailment of any one axiom from the remaining axioms fails. By the completeness theorem, this is equivalent to no member being formally derivable from the others in a complete calculus. To establish independence it suffices to give, for each axiom, a first-order structure satisfying all the other axioms and failing that one.
The usual associative, identity, two-sided inverse and commutativity axioms form an independent axiom set. A three-element commutative unital operation with self-inverses can fail associativity; a constant-zero operation can satisfy the other three axioms while failing the identity condition; natural-number addition fails the inverse condition; and a noncommutative group fails commutativity. Each example must be checked against all three retained axioms.
A mathematical definition fixes the meaning of a term or symbol using previously specified concepts. A definition by a universal property can still require a mathematical proof that an object with that property exists. For example, the definition of a product in a category specifies its mapping behavior, while existence is a further question about that category.
Second-order logic extends first-order logic by allowing existential quantification and universal quantification over second-order relation variables, as well as over individual objects. In the relational presentation used here, an individual variable ranges over a domain , while a second-order relation variable of arity denotes a subset of . Unary second-order relation variables denote subsets of ; binary ones denote binary relations. Presentations with function variables can instead describe their graphs by second-order relation variables, with first-order formulas requiring a unique output for every input.
For a graph with vertices and fixed graph adjacency , the first-order sentence says that every vertex has a neighbour. It selects individual vertices while retains its given interpretation. By contrast,
selects an entire subset and says that it is a nonempty independent set. Here is a unary second-order relation variable, rather than a symbol in the input first-order signature. This particular property also has a simple first-order sentence on simple graphs; the example illustrates the change in what can be selected, rather than proving a separation in expressive power.
The usefulness of second-order logic is that one can describe a whole proposed solution, such as a graph coloring, and then impose local constraints on it. Syntax alone does not specify which proposed relations are available: full semantics for second-order logic permits all external subsets of , whereas Henkin semantics supplies designated ranges. The second-order encoding of three-colorability makes this distinction concrete.
A second-order relation variable of arity can be assigned a subset of the -fold Cartesian product ; its application is true exactly when the tuple belongs to that subset. Arity is the number of arguments, so a unary second-order relation variable is a predicate on individual objects. For a finite set of cardinality , there are possible tuples and possible relations under full semantics for second-order logic. A relation is encoded by membership bits once the objects have been numbered; the number of possible witnesses can be exponential even when each witness has a short encoding.
An existential second-order logic sentence has the form
where each is a second-order relation variable of fixed finite arity and is a first-order sentence over the input first-order signature expanded by the . The first-order sentence may contain both universal quantification and existential quantification over individuals; only the outer quantification over second-order relation variables is required to be existential. Under full semantics for second-order logic, truth means that some expansion by witness relations satisfies .
For a fixed existential second-order logic sentence on a domain of cardinality , the witnesses need membership bits. The arities and the number of witnesses are constants because the sentence is fixed. After guessing those bits, a verifier evaluates the fixed first-order sentence by enumerating assignments to its finitely many individual variables, taking polynomial time. In the second-order encoding of three-colorability, the three witnesses require bits, and the edge constraints can be checked over at most ordered vertex pairs. This is the logical form of the NP principle that a positive answer has a short complexity certificate.
The fixed-sentence qualification matters: it is the input first-order structure that varies, rather than an arbitrarily large formula supplied with each input. Fagin's theorem states the converse as well: every isomorphism-invariant NP property of finite relational first-order structures has such a description. The coloring example uses only unary second-order relation variables; the general theorem allows any fixed finite arities.
Represent a finite simple graph by a domain of vertices and a symmetric, irreflexive binary relation for graph adjacency. Introduce three unary second-order relation variables , one for each fixed named colour. Define the following abbreviations for first-order formulas in this expanded first-order signature:
Then the existential second-order logic sentence
asserts that every vertex receives exactly one of the three colours and adjacent vertices receive different colours. The first clause gives coverage and pairwise disjointness of the three subsets; the second makes each subset an independent set. Empty colour classes are allowed, so expresses existence of a proper vertex coloring using at most three colours.
For the complete graph on the fixed vertices , one witness is , , . Each vertex satisfies exactly one predicate, and each of the three edges joins different predicates. Every valid witness assigns different colours to all three vertices; there are witness triples with these fixed vertex labels and fixed named colours. We are counting assignments, without identifying them under colour permutations or graph isomorphisms. For the complete graph , the pigeonhole principle forces two of its four vertices to share a colour, and those vertices are adjacent. Thus it has no witness triple. This calculation illustrates a complexity certificate without requiring the reader to reconstruct a machine computation.
Figure 1.
Six relation witnesses for the labeled complete graph K3, and why K4 has none
. Details.
Reproduce the diagram by running python ../second-order-coloring-witness.py from the repository's _media directory. The script checks all witness triples for these two complete graphs before drawing them.
Fix a finite relational first-order signature , and let be a class of finite nonempty -first-order structures closed under isomorphism. Fagin's theorem states that is definable by one existential second-order logic sentence under full semantics for second-order logic if and only if its language of standard finite encodings belongs to NP. A standard encoding numbers the domain and lists membership bits for each input relation, together with ; take an explicit encoding whose length is at least . The encoding language contains all numbered copies of members of , with malformed encodings rejected. The isomorphism condition makes membership a property of the structure rather than an arbitrary choice of labels. Changing between the usual explicit encodings preserves the NP characterization by polynomial time translations.
The forward direction is the witness-and-verifier calculation in existential second-order logic. For the reverse direction, the guiding idea is to encode an accepting nondeterministic computation using second-order relation variables: fixed-length tuples of domain elements index enough time steps and storage positions for a polynomial time computation. A first-order sentence checks the initial input, legal transitions, and acceptance. The number of tuples grows with the input, although the checking sentence stays fixed. No total order must be supplied as part of the input first-order signature: an auxiliary total order can itself be existentially guessed and constrained by a first-order sentence. Isomorphism invariance ensures that a change of this auxiliary numbering does not change membership in .
The second-order encoding of three-colorability is a small instance of the forward direction. The beauty of Fagin's theorem is the complete correspondence: the computational class NP can be characterized by the shape of a logical description, without mentioning a particular machine in the statement. The scope is finite relational first-order structures and fixed sentences; it is not a claim about deciding arbitrary second-order logic sentences or about arbitrary infinite domains.
Ronald Fagin published the result in Generalized First-Order Spectra and Polynomial-Time Recognizable Sets, SIAM-AMS Proceedings 7 (1974), pp. 43–73, Section 4. The original paper frames the correspondence using classes of finite expansions and their encodings. Fagin's author-maintained publication list explains that the abstract in the available copy was added in 2019; its modern summary should therefore not be mistaken for part of the 1974 printing.
In Henkin semantics, a domain is accompanied by designated ranges for second-order relation variables of each arity . A formula searches only , and checks only . These ranges can be proper subcollections of the external power set. Keeping and its input relations fixed therefore need not fix the truth of a second-order logic sentence.
As a toy illustration of restricted quantification, take and unary range . The sentence
is true under full semantics for second-order logic, but false with this selected range, because neither singleton is available. Likewise, on the complete graph , the unary range admits no witness for the second-order encoding of three-colorability, even though a usual proper vertex coloring exists. This toy range illustrates the truth definition only: it fails second-order comprehension for the formula , and is not a model of a system requiring that comprehension instance.
Admissible Henkin semantics for a specified deductive system must satisfy its axioms, including its chosen second-order comprehension requirements or analogous closure conditions for predicate abstraction. Closure is relative to the permitted formulas and parameters, rather than a blanket property of every selected family. In particular, on a finite domain, allowing logical equality, individual parameters, all finite logical disjunctions, and comprehension for those formulas forces every finite-arity relation to be available: enumerate its tuples and disjoin the formulas naming them. Thus a proper restricted finite range cannot satisfy that entire scheme.
Treating each as an additional sort, with an application relation between its members and individuals, translates this relational presentation into first-order logic with several sorts. Include axioms saying that predicates with the same members are equal, together with whatever second-order comprehension the system requires. This makes Henkin semantics useful for bringing first-order logic methods to reasoning about predicates; it does not license conclusions about all external relations.
Leon Henkin's Completeness in the Theory of Types, Journal of Symbolic Logic 15 (1950), pp. 81–91 develops general models and proves completeness for his typed deductive system. Its opening footnote 5 explicitly discusses closure under operations associated with formula formation. Henkin later described the discovery process in his [ref]; that later account is a historical recollection, distinct from the original publication.
Under full semantics for second-order logic, a second-order relation variable of arity ranges over exactly , the external power set of the appropriate Cartesian product. Thus
and universal quantification over checks every such subset. Here the power set is taken in the ambient mathematical universe, not merely among relations definable by formulas or represented by objects inside .
For , a unary second-order relation variable has eight possible values, including the three singletons needed by the second-order encoding of three-colorability. The three unary witnesses can range independently over those eight subsets, giving candidate triples before the first-order sentence is checked; only six triples pass for the complete graph . For , there are candidate triples and none passes. Distinguishing the range of candidates from the constraints on valid witnesses clarifies both full semantics for second-order logic and the verifier view of NP.
The appeal of full semantics for second-order logic is its literal reading of assertions about every subset or every relation. A first-order structure fixes the second-order ranges automatically, in contrast to Henkin semantics. That expressive force comes with a limitation: there is no effective, sound deductive system complete for all valid second-order logic sentences under full semantics for second-order logic. This limitation and the change of intended models motivating Henkin semantics are described at the start of [ref].
For a domain , an external functional graph with all its individual ordered pairs in is therefore available, even if the whole graph does not belong to . More generally, a binary second-order relation variable can denote any external subset of ; its ordered pairs need not themselves be elements of the individual domain. Having endpoints in the domain is what matters. This distinction between internal objects and externally available relations is essential when applying second-order logic to the cumulative hierarchy.
Second-order comprehension is a scheme asserting the existence of a second-order relation variable whose members are exactly the tuples satisfying a permitted formula:
Here is not free in , and the displayed individual and relation parameters are universally closed in each instance. Under full semantics for second-order logic, the selected external subset of is always available. Under Henkin semantics, the selected subset must lie in for every allowed assignment of parameters. Different systems permit different formula classes: for example, arithmetical comprehension theory restricts comprehension to formulas without bound set variables, while still permitting set parameters. Consequently, the exact formula and parameter policy must accompany any claim that a restricted range satisfies second-order comprehension.
Second-order arithmetic has variables for natural numbers and for sets of natural numbers. Subsystems restrict comprehension and induction; arithmetical transfinite recursion theory is one important subsystem stronger than the first-order system Peano arithmetic.
Arithmetical transfinite recursion theory permits arithmetic recursive definitions along coded countable well-orders, together with the usual arithmetic comprehension background. Friedman's finite form of Kruskal's theorem is not provable in this theory.
A formal proof is a finite sequence of formulae in which every line is an axiom, an assumption, or follows from earlier lines by a specified inference rule.
A conclusion is formally derivable from premises when a permitted formal proof exists with those premises as its undischarged assumptions. This is a syntactic relation, distinct from semantic entailment.
Theoremhood is formal derivability with no undischarged assumptions. A logical formula is a theorem of a calculus exactly when it has an assumption-free formal proof.
Infinitary logic permits infinitary syntactic operations, such as infinite conjunctions, together with an interpretation of its formulas. The infinitary language specifies the permitted conjunction and quantifier lengths.
The infinitary language permits conjunctions and disjunctions of fewer than formulas and simultaneous quantification over fewer than variables. Ordinary first-order logic is .
The logic extends first-order logic by countable logical conjunctions and logical disjunctions. Each formula has finitely many free variables, and quantifier strings are finite. In a countable first-order language, every countable structure has a Scott sentence in this logic that characterizes its isomorphism class among countable structures.
Every countable structure in a countable first-order language has a Scott sentence. Hence countable structures satisfying the same sentences of countable infinitary logic are isomorphic. The proof uses Scott formulas, stabilization on the countable set of finite tuples, and the back-and-forth method.
A Scott sentence for a countable structure is a sentence of countable infinitary logic satisfied, among countable structures in the same first-order language, exactly by its isomorphic copies. It may also have uncountable models. Scott formulas and stabilized back-and-forth method equivalences give its construction.
A Scott formula describes a finite tuple at a transfinite stage of the back-and-forth method. Stage zero specifies the complete atomic description; successor stages specify matching one-element extensions in both directions; limit stages conjoin the earlier descriptions. For a countable structure the equivalences on its finite tuples stabilize at a countable ordinal.
First-order logic builds assertions using variables, logical connectives, and quantifiers over elements of a structure. A chosen first-order language supplies constants, function symbols, and relation symbols. The quantifiers range over elements, rather than arbitrary subsets or predicates.
For example, says that an ordered domain has no greatest element. It is true in the integers but false in a nonempty finite total order. A formal proof manipulates formulas syntactically, while a model of a first-order theory supplies their meanings. Gödel's completeness theorem links these viewpoints: semantic consequence from a theory agrees with formal derivability.
A Hilbert-style calculus specifies axiom schemes and a small collection of inference rules, typically implication elimination and universal generalization. Equality and quantifier schemes include substitution and free-variable side conditions. Proofs are finite syntactic derivations; validity is separately defined using structures and assignments. A context-sensitive presentation restricts generalization by its actual undischarged assumptions.
The rule is valid when is not a free variable in any undischarged assumption. Under that condition, changing the value of preserves the assumptions, so a derivable conclusion holds at every value of . Without the condition, the invalid inference from the assumption to would be possible on a domain with more than one element.
In a fixed first-order structure, the satisfaction implication at a first-order variable assignment says that if all formulas of hold at , then holds at . Semantic consequence requires that implication in every relevant structure and assignment. The assignment's codomain belongs to its structure; different domains are not silently assigned one common map. When all formulas are first-order sentences, assignments do not affect any of their truth values.
For a first-order structure with domain , an assignment maps every individual variable to an element of . It extends recursively to first-order terms using the interpreted functions. To evaluate , vary only the value of over , holding the other values fixed. The truth value of a first-order formula depends only on its free variables; a first-order sentence is therefore independent of the assignment.
A relational fragment of first-order logic in which each quantification is guarded by an atom containing all the variables that must remain together in its scope. The usual fragment excludes nonconstant function symbols.
A function-free implication between conjunctions of positive atomic formulas, allowing existentially quantified witnesses in its conclusion. Standard tuple-generating dependencies do not have disjunctive heads or negative constraints.
The set of all ground terms over a first-order signature . Add a fresh constant if the first-order signature has none, so that this domain is nonempty. A constant and unary function give the Herbrand universe .
The set of all ground atoms formed using a Herbrand universe and the signature's predicates.
Articles were limited to the first 100 out of 3639 total.

Articles by others on the same topic (1)

Foundations of mathematics is a branch of mathematical logic that seeks to understand the fundamental concepts and principles that underpin mathematics as a whole. It explores the nature of mathematical objects, the validity of mathematical reasoning, and the scope and limitations of mathematical systems. The field addresses several key areas, including: 1. **Set Theory**: This is the study of sets, which are collections of objects.