Prenex normal form theorem
ProvedFamousTheorems.prenex_normal_form_7aPrenex normal form theorem. Let be a first-order language and a formula of with free variables indexed by and further bound-variable slots. There is a formula in prenex normal form, meaning a string of quantifiers followed by a quantifier-free formula, such that in every nonempty -structure and under every assignment, holds if and only if holds.
Prenex forms go back to Peirce and Skolem. Every formula can be put in prenex form by moving quantifiers outward. This is the first step of Skolemization and of the arithmetical and Lévy hierarchies, which classify formulas by their quantifier prefixes.
Formalization note. Mathlib's FirstOrder.Language.BoundedFormula.realize_toPrenex and toPrenex_isPrenex. Here is Mathlib's explicit transformation φ.toPrenex. BoundedFormula α n has free variables indexed by and de Bruijn-style variables, assigned by v and xs respectively. The structure is assumed nonempty, as is needed to move quantifiers across connectives.
import Mathlib
namespace FamousTheorems
theorem prenex_normal_form_7a {L : FirstOrder.Language} {M : Type*} [L.Structure M] {α : Type*} {n : ℕ} [Nonempty M]
(φ : L.BoundedFormula α n) {v : α → M} {xs : Fin n → M} :
φ.toPrenex.IsPrenex ∧ (φ.toPrenex.Realize v xs ↔ φ.Realize v xs) := by sorry
end FamousTheoremsConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.