Łoś–Tarski preservation theorem explained
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. The theorem was discovered by Jerzy Łoś and Alfred Tarski.
Statement
Let
be a theory in a
first-order logic language
and
a set of formulas of
.(The sequence of variables
need not befinite.) Then the following are equivalent:
- If
and
are models of
,
,
is a sequence of elements of
. If
B\modelswedge\Phi(\bar{a})
, then
A\modelswedge\Phi(\bar{a})
.
(
is preserved in substructures for models of
)
is equivalent modulo
to a set
of
formulas of
.
A formula is
if and only if it is of the form
\forall\bar{x}[\psi(\bar{x})]
where
is quantifier-free.
In more common terms, this states thatevery 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.
[1] Note that this property fails for finite models.
References
- Book: 1568812620 . Peter G. . Hinman . Fundamentals of Mathematical Logic . A K Peters . 2005 . 255 .
Notes and References
- Benjamin . Rossman . Benjamin Rossman. Homomorphism Preservation Theorems . . 55 . 3 . 10.1145/1379759.1379763.
