The Tarski–Vaught test
ProvedFamousTheorems.tarski_vaught_testThe Tarski–Vaught test. Let be an embedding of -structures. Suppose that for every formula and every tuple from , whenever for some , there is already some with . Then is elementary: for every formula and every tuple from ,
This is the standard criterion for recognising elementary substructures. It is the key step in the downward Löwenheim–Skolem theorem, where one closes a subset under witnesses for existential formulas.
Formalization note. Mathlib's FirstOrder.Language.Embedding.isElementary_of_exists. Formulas with free variables are encoded as L.BoundedFormula Empty (n + 1), and the tuple is Fin.snoc (f ∘ x) b. The conclusion is exactly the definition of an elementary embedding, spelled out.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem tarski_vaught_test {L : FirstOrder.Language} {M N : Type*} [L.Structure M] [L.Structure N] (f : L.Embedding M N)
(htv : ∀ (n : ℕ) (φ : L.BoundedFormula Empty (n + 1)) (x : Fin n → M) (a : N),
φ.Realize default (Fin.snoc (f ∘ x) a : _ → N) →
∃ b : M, φ.Realize default (Fin.snoc (f ∘ x) (f b) : _ → N)) :
∀ {n : ℕ} (φ : L.Formula (Fin n)) (x : Fin n → M), φ.Realize (f ∘ x) ↔ φ.Realize x := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `FirstOrder.Language.Embedding.isElementary_of_exists`. Proof here reduces to that Mathlib result.