Feferman–Vaught theorem

The Feferman–Vaught theorem in model theory is a theorem by Solomon Feferman and Robert Lawson Vaught that shows how to reduce, in an algorithmic way, the first-order theory of a product of structures to the first-order theory of elements…

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

The Feferman–Vaught theorem in model theory is a theorem by Solomon Feferman and Robert Lawson Vaught that shows how to reduce, in an algorithmic way, the first-order theory of a product of structures to the first-order theory of elements of the structure. The theorem is considered to be one of the standard results in model theory.

The theorem extends the previous result of Andrzej Mostowski on direct products of theories. It generalizes (to formulas with arbitrary quantifiers) the property in universal algebra that equalities (identities) carry over to direct products of algebraic structures (which is a consequence of one direction of Birkhoff's theorem). \mathbf{A} = \prod_{i \in I} \mathbf{A}_i , which is also an L-structure, with all functions and relations defined pointwise.

The definition generalizes the direct product in universal algebra to structures for languages that contain not only function symbols but also relation symbols. If r(a_1,\ldots,a_p) is a relation symbol with p arguments in L and a_1,\ldots,a_n \in \Pi_{i \in I}\mathbf{A}_i are elements of the cartesian product, we define the interpretation of r in \mathbf{A} by \mathbf{A} \models r(a_1,\ldots,a_p) \iff \forall i \in I,\ \mathbf{A}_i \models r(a_1(i),\ldots,a_p(i)) When r is a functional relation, this definition reduces to the definition of direct product in universal algebra. ||\phi(\bar a)|| = \{ i \mid \mathbf{A}_i \models \phi(\bar a(i)) \} Given a first-order formula with free variables \phi(\bar x) , there is an algorithm to compute its equivalent game normal form, which is a finite disjunction \bigvee_{i=1}^{k} \theta_i(\bar x) of mutually contradictory formulas.

The Feferman–Vaught theorem gives an algorithm that takes a first-order formula \phi(\bar x) and constructs a formula \phi^* that reduces the condition that \phi(\bar a) holds in the product to the condition that \phi^* holds in the interpretation of k+1 sets of indices: I, ||\theta_i(\bar a)||, \ldots, ||\theta_{k}(\bar a)|| The formula \phi^* is thus a formula with k+1 free set variables, for example, in the first-order theory of fields of sets. & \iff \{ i \mid \mathbf{A}_i \models \phi(\bar a(i)) \} = I \\ & \iff ||\phi(\bar a)|| = I \end{array} Consequently, we can take \phi^*(U,X_1) to be the equality U = X_1 in the language of fields of sets. Extending the condition to quantified formulas can be viewed as a form of quantifier elimination, where quantification over product elements \bar a in \phi is reduced to quantification over subsets of I . c(i) = \left\{\begin{array}{rl} a(i), & \mbox{ if } i \in X \\ b(i), & \mbox{ if } i \in (I \setminus X) \end{array}\right.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1352595288 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001352595288 · captured 1777945098.0 · version history

Cite this page as: encyclopegia.org, “Feferman–Vaught theorem”, snapshot enwiki-001352595288. https://encyclopegia.org/a/feferman-vaught-theorem

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.