Principal formula of a type 2026-10-31
A principal formula of a type is a logical formula first-order consistent with the base first-order theory that, modulo that first-order theory, implies every logical formula of the partial type. For a complete type it isolates a single point of the type space. A realized finite-tuple partial type in a finite first-order structure has such a logical formula by conjoining one distinguishing logical formula for each competing tuple with a different partial type.
Quantifier Created 2026-10-14 Updated 2026-10-25
A quantifier binds a free variable in a first-order formula and specifies how its truth depends on elements of a first-order structure: universal quantification requires every element, while existential quantification requires at least one.
Quantifier-free formula 2026-10-05
A quantifier-free first-order formula is built from atomic formulas using logical connectives, with no quantifiers. An embedding of first-order structures preserves and reflects its truth, by mathematical induction on the first-order formula. Both positive and negated atomic information are needed for this conclusion in a relational language.
Rank-n equivalence of structures 2026-10-06
Two first-order structures are rank-n equivalent if they agree on all sentences of quantifier rank at most . The tuple version compares formulas at fixed tuples. For finite relational vocabulary this is equivalent to a Duplicator winning strategy in the -round Ehrenfeucht-Fraïssé game.
Reduced product 2026-10-06
Given nonempty first-order structures and a proper filter on a set , a reduced product identifies product functions when . Operations are interpreted coordinatewise, and relations hold when their coordinate truth sets belong to . For an ultrafilter this is an ultraproduct. Primitive positive formulas transfer through an arbitrary proper filter, whereas logical disjunction and logical negation can fail to transfer.
Satisfaction for a set structure 2026-10-05
The satisfaction relation says that the finite code of a first-order formula is true in a set-sized first-order structure at assignment . It is defined uniformly in set theory by recursion on the finite syntax tree: evaluate atomic relations, Boolean operations and quantifiers over the given domain. A code includes only finitely many subformulas, and their truth relations are sets. This does not define a truth predicate for the ambient universe, whose domain is not a set. Finite relation closure for set-theoretic coding gives an explicit closure criterion ensuring that these truth relations are computed correctly in a transitive set.
Saturated elementary extension theorem 2026-10-14
For every infinite regular cardinal , every first-order structure has a -saturated elementary extension. At one stage use the compactness theorem with the elementary diagram to realize all complete types over subsets of the stage having size less than . There is a set of such types; finite subsets of the enlarged theory are satisfiable because their finitely many witnesses are independent. Iterate for stages, taking elementary unions at limits. Regularity puts any parameter set of size less than inside one stage, and its type is realized at the next one. Passing to a larger regular cardinal covers singular requested degrees of saturation as well.
Semantic consequence under an assignment 2026-10-31
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.
Structure (mathematical logic) 2026-10-14
A structure consists of a domain together with interpretations of the symbols of a formal language. In the usual finitary setting it interprets constant, function, and relation symbols of their declared arities. A first-order structure is such an interpretation for first-order logic.
In a first-order structure, an interpretation assigns a relation of the specified arity to each predicate symbol, a total function of the specified arity to each function symbol, and an element to each constant symbol. Evaluation of first-order terms and truth of logical formulas are then defined recursively. This specifies how symbols acquire their meanings on the underlying set.
Term valuation Created 2026-10-31 Updated 2026-11-05
A first-order structure and an assignment determine the value of every term recursively: a variable has its assigned value, a constant has its interpreted value, and a compound function term is evaluated by applying the interpreted function to the recursively evaluated arguments. This operation supplies the input values for the satisfaction clauses of atomic formulas.
Fix a tuple in a finite first-order structure. For every tuple of a different complete type, choose a logical formula true at the first tuple and false at the competitor. The finite conjunction selects only tuples of the desired partial type inside the first-order structure. Every implication from that conjunction to a member of the partial type is true in the first-order structure and hence belongs to its complete theory. Thus the conjunction isolates the partial type, even in an infinite first-order language.
Ultrapower embedding Created 2026-09-24 Updated 2026-11-05
For an ultrafilter on and a first-order structure , the diagonal mapsends an element to the equivalence class of its constant function. The Łoś theorem makes it an elementary embedding. The target is an ultrapower; it need not be well-founded. A Mostowski collapse is available only after well-foundedness and extensionality have been established.
For an uncountable cardinal , a -complete nonprincipal ultrafilter on gives a well-founded set-theoretic ultrapower of the universe, whose transitive collapse has critical point of an elementary embedding . Completeness makes every function from to an ordinal below constant on an ultrafilter-large set. Nonprincipality and completeness make the identity function's class lie above every constant ordinal below , forcing .
The uncountability qualification is essential. A nonprincipal ultrafilter on is only finitely complete and gives an externally ill-founded ultrapower of the natural numbers; it cannot produce a transitive elementary embedding with critical point .
Expand an infinite first-order structure by Skolem functions, choose distinct elements , and fix a nonprincipal ultrafilter on . For each finite subset of the required index order, form the ultrapower over using the ordered Fubini product of ultrafilters. Pullback along coordinate projections gives coherent elementary maps by the Łoś theorem. In their directed limit of elementary embeddings, the classes of the coordinate functions are distinct and form an order-indiscernible sequence; every first-order formula on increasing coordinates has the same nested ultrafilter test. Their Skolem hull gives an Ehrenfeucht-Mostowski model. An index-order automorphism sends a term in the generators to the same term in the transported generators; indiscernibility makes this well defined. Uniqueness is in the specified Skolem expansion, not necessarily in its reduct. If generators must respect a definable infinite order, first produce an increasing sequence by an ultrapower of finite increasing chains.
Unary predicate type 2026-10-25
For a fixed finite list of unary predicates, a unary predicate type specifies whether each predicate holds of an element. With predicates there are possible truth value patterns; a first-order structure may realize any subset of them. The notation , makes each pattern a quantifier-free formula.
Universal formula 2026-10-31
A universal formula has a block of universal quantifiers followed by a quantifier-free formula. Empty blocks are usually permitted. Truth transfers from a first-order structure to a substructure of a first-order structure for parameters in that substructure: every tuple in the smaller domain is available in the larger domain, and quantifier-free truth is preserved and reflected by the inclusion. This is the dual preservation direction to the forward preservation of an existential formula under a structure embedding.
Universal quantification Created 2026-10-05 Updated 2026-10-31
Universal quantification forms . In a first-order structure, it is true at an assignment to when every domain element assigned to makes the instance true. Its introduction rule requires that the generalized variable not occur freely in undischarged assumptions.
Over the natural numbers, reversing the preceding existential quantification and universal quantification gives a true first-order sentence:Choose . The computed witnesses for are . The choice may depend on the previously given . The formula states that every natural number has a larger natural number; the reversed formula demands one larger than all of them.
Universal quantification followed by existential quantification permits a different witness for each input
. Details. The diagram displays a finite window, while the rules and settle the two statements for every natural number. This dependence is why quantifier order matters in precise specifications. Choosing one that works for every would also provide a witness for each ; the reverse inference fails here.
To introduce universal quantification in natural deduction, reason with an arbitrary input, without assuming a special property of it. The construction does exactly this and also gives a proof in intuitionistic first-order logic. The introduction and elimination rules for both quantifiers are developed in Frank Pfenning, First-Order Logic and Type Theory, section 4.1.
Universal sentence 2026-10-05
A universal sentence has the form with quantifier-free formula , including an empty quantifier block. Its truth passes from a first-order structure to every substructure of a first-order structure: tuples from the smaller domain are also tuples of the larger domain, and quantifier-free truth agrees. Therefore a first-order theory of universal sentences has a first-order model class closed under substructures of a first-order structure.
Quantifier-free logical formulas have the same truth value in a substructure and its ambient first-order structure on tuples from the smaller carrier. First-order term evaluation agrees; atomic relations agree by restriction; Boolean connectives preserve agreement. A universally quantified quantifier-free matrix true on all ambient tuples is therefore true on all substructure tuples.
