Łoś–Tarski preservation theorem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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 (Hodges 1997). The theorem was discovered by Jerzy Łoś and Alfred Tarski.

Statement[edit]

Let be a theory in a first-order language and a set of formulas of . (The set of sequence of variables need not be finite.) Then the following are equivalent:

  1. If and are models of , , is a sequence of elements of . If , then .
    ( is preserved in substructures for models of )
  2. is equivalent modulo to a set of formulas of .

A formula is if and only if it is of the form where is quantifier-free.

Note that this property fails for finite models.

References[edit]

  • Peter G. Hinman (2005), Fundamentals of Mathematical Logic, A K Peters, ISBN 1568812620.
  • Hodges (1997), A Shorter Model Theory, Cambridge University Press, ISBN 0521587131.