The Łoś–Tarski theorem is a theorem in model theory, a branch of mathematics, that states that the set of formulas preserved under taking substructures is exactly the set of universal formulas. [1] The theorem was discovered by Jerzy Łoś and Alfred Tarski.
Let be a theory in a first-order logic language and a set of formulas of . (The sequence of variables need not be finite.) Then the following are equivalent:
A formula is if and only if it is of the form where is quantifier-free.
In more common terms, this states that every first-order formula is preserved under induced substructures if and only if it is , i.e. logically equivalent to a first-order universal formula. As substructures and embeddings are dual notions, this theorem is sometimes stated in its dual form: every first-order formula is preserved under embeddings on all structures if and only if it is , i.e. logically equivalent to a first-order existential formula. [2]
Note that this property fails for finite models.
The Łoś–Tarski theorem is a theorem in model theory, a branch of mathematics, that states that the set of formulas preserved under taking substructures is exactly the set of universal formulas. [1] The theorem was discovered by Jerzy Łoś and Alfred Tarski.
Let be a theory in a first-order logic language and a set of formulas of . (The sequence of variables need not be finite.) Then the following are equivalent:
A formula is if and only if it is of the form where is quantifier-free.
In more common terms, this states that every first-order formula is preserved under induced substructures if and only if it is , i.e. logically equivalent to a first-order universal formula. As substructures and embeddings are dual notions, this theorem is sometimes stated in its dual form: every first-order formula is preserved under embeddings on all structures if and only if it is , i.e. logically equivalent to a first-order existential formula. [2]
Note that this property fails for finite models.