Atomic formula 2026-10-05
An atomic first-order formula is a relation applied to terms, or a logical equality of two terms when logical equality is included in the logic. It contains no logical connective or quantifier. Its truth is preserved and reflected by an embedding of first-order structures.
An equivalence-relation first-order structure with exactly two infinite classes, one countable and one uncountable, is atomic but lacks finite-tuple homogeneity. Its first-order theory has quantifier elimination: a new point is either assigned a previously used class or an available unused class, and can avoid finitely many forbidden points in that infinite class. Finite equality-and-equivalence patterns therefore isolate all tuple partial types. All elements have the same complete one-type, but no automorphism exchanges the two differently sized classes.
A-type over a structure Created 2026-10-06 Updated 2026-10-14
For , an A-type over first-order structure is a set of formulas in a fixed finite tuple of variables, with parameters in , consistent with the complete theory of expanded by constants for . Every finite subset is realized in . A complete type decides all formulas in its variables over those parameters.
Classical first-order logic 2026-10-05
Classical first-order logic has the quantifier and logical equality rules of natural deduction together with unrestricted double-negation elimination, or equivalently the law of excluded middle. It is interpreted in ordinary two-valued first-order structures.
Closed term 2026-10-31
A closed term contains no variables, so its value in a first-order structure does not depend on an assignment. In a language containing only relations and the constant zero, zero is the only closed term. A term-generated model has every element denoted by such a term.
Constant symbol 2026-10-31
A constant symbol is a zero-ary function symbol. Its interpretation in a first-order structure names one fixed domain element, and the symbol is a closed term. A language can contain no constant symbols unless a construction explicitly adds them.
Definable power set Created 2026-09-24 Updated 2026-10-05
The definable power set consists of the subsets of definable over the first-order structure by a first-order formula with parameters from . Satisfaction for a set structure makes this a definable operation in ZF. Iterating it produces the constructible hierarchy and the relative constructible hierarchy; their unions are the constructible universe and the relative constructible universe.
Definable set 2026-10-31
A definable set in a first-order structure is the set of tuples satisfying one first-order formula, possibly with a specified finite tuple of parameters from the structure. A set definable over uses parameters from . Parameter-free definability uses no extra named elements. The distinction matters: any singleton becomes definable if its own element is allowed as a parameter, while many singletons are not definable without parameters. Finite Boolean combinations of definable sets are definable, using logical conjunction, logical disjunction and logical negation.
Dense-extension filter semantics 2026-10-05
For a family of first-order structures, take free filters on the index set as worlds, ordered by inclusion, and product sequences as parameters. Force an atom when its coordinate truth set belongs to the filter. Conjunction is local, implication and negation quantify over filter extensions, and a disjunction is forced when every extension has a further extension forcing one disjunct. Existence is witnessed by a product sequence and universality holds for all sequences at all extensions. With the axiom of choice, induction on formulas identifies forcing with membership of the classical coordinate truth set. Equivalently, every ultrafilter extension satisfies the formula in its ultraproduct. Thus the semantics validates classical logic. A local disjunction rule would fail this identification: a set and its complement can both be absent from a free filter, while their union is the whole index set.
Diagram embedding criterion for universal theories Created 2026-10-06 Updated 2026-10-31
A first-order structure embeds into a model of exactly when . For the nontrivial direction apply the compactness theorem to . If a finite diagram conjunction were inconsistent with , its universal negation after replacing the new constants by variables would belong to and contradict its truth in .
Directed limit of elementary embeddings 2026-10-05
A directed system of first-order structures and coherent elementary embeddings has a direct limit into which every member embeds elementarily. Represent an element by a pair consisting of a stage and an element at that stage; identify two representatives when their images agree at a common later stage. Interpret functions and relations at a common stage. Mathematical induction on first-order formulas proves elementarity: for an existential first-order formula true at the limit, its witness and parameters occur at a common stage, and elementarity pulls truth back to the stage containing the original parameters. This generalizes the elementary chain theorem beyond linearly ordered diagrams.
Domain of a first-order structure 2026-10-31
The underlying set of elements over which the quantifiers of a first-order structure range. Relation symbols are interpreted as finitary relations on this set, and function symbols as functions on it.
Ehrenfeucht-Mostowski theorem Created 2026-09-28 Updated 2026-10-05
Let be an infinite first-order structure and a total order. After choosing a Skolem expansion of , an elementary extension contains distinct elements forming an order-indiscernible sequence in that expanded language. Their Skolem hull is an elementary substructure in the expanded language, and its reduct is a first-order model of . Every order automorphism of extends uniquely to a structure automorphism of the hull preserving the chosen Skolem expansion, by transporting terms in the generators.
Uniqueness need not hold among all structure automorphisms of the reduct. For an infinite structure in the pure logical equality language, take two distinct nullary Skolem function values in the hull. For an infinite order-indiscernible sequence, neither can equal a generator: the expanded formula would otherwise hold at every generator, contradicting their distinctness. Swapping fixes every generator and preserves the pure logical equality reduct, while failing to preserve the Skolem expansion. Thus the identity order automorphism already has two extensions in that reduct.
Elementary embedding Created 2026-09-24 Updated 2026-11-05
An elementary embedding between first-order structures preserves and reflects every first-order formula with parameters: for every finite tuple from ,In particular it is injective, by applying the condition to equality, and its image is an elementary substructure of . An elementary inclusion is the defining map of an elementary extension.
For example, the rational order is an elementary substructure of the real order in the language containing only , by quantifier elimination for dense linear orders without endpoints. Elementarity is stronger than preserving just the atomic relations. For embeddings between suitable transitive models of set theory, one can additionally ask which ordinals are moved; the least moved ordinal, when there is one, is the critical point of an elementary embedding. This ordinal notion is not part of the definition for arbitrary structures.
Elementary equivalence 2026-10-06
Two first-order structures are elementarily equivalent when they satisfy the same first-order sentences. They need not be isomorphic or embed into one another. Every elementary embedding implies elementary equivalence of its source and target.
Existential embedding 2026-10-14
An embedding of first-order structures is existential when every existential formula with parameters from the source has the same truth value in the source and target. Forward preservation follows from being a structure embedding; reflection is the additional requirement. Applying compactness theorem to the target's diagram of a structure and the source's elementary diagram places the target inside an elementary extension of the source.
Existential quantification Created 2026-10-05 Updated 2026-10-31
Existential quantification forms . In a first-order structure, it is true at an assignment to when some domain element makes the instance true. In natural deduction, elimination uses a fresh variable for the hypothetical witness; that variable may not escape into the conclusion or the remaining undischarged assumptions.
Existence requires at least one witness, not exactly one. Over the natural numbers , is true: works, as do . In intuitionistic first-order logic, a direct proof supplies a witness together with a proof of the corresponding instance; merely rejecting nonexistence is generally weaker.
Placing existential quantification before universal quantification requires a single witness that works throughout:This first-order sentence is false. For any proposed , choose : the required inequality becomes . For example, works for but fails at . No finite list of successful checks establishes universal quantification over the natural numbers.
Existential second-order logic 2026-10-14
An existential second-order logic sentence has the formwhere 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.
Existential sentence 2026-10-14
An existential sentence has a block of existential quantifiers followed by a quantifier-free formula. Empty blocks are allowed. These sentences are preserved when a first-order structure embeds into another structure.
Fagin's theorem 2026-10-14
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.