Basics on First-Order Semantics

This file defines the interpretations of first-order terms, formulas, sentences, and theories in a style inspired by the Flypitch project.

Main Definitions

• FirstOrder.Language.Term.realize is defined so that t.realize v is the term t evaluated at variables v.
• FirstOrder.Language.BoundedFormula.Realize is defined so that φ.Realize v xs is the bounded formula φ evaluated at tuples of variables v and xs.
• FirstOrder.Language.Formula.Realize is defined so that φ.Realize v is the formula φ evaluated at variables v.
• FirstOrder.Language.Sentence.Realize is defined so that φ.Realize M is the sentence φ evaluated in the structure M. Also denoted M ⊨ φ.
• FirstOrder.Language.Theory.Model is defined so that T.Model M is true if and only if every sentence of T is realized in M. Also denoted T ⊨ φ.

Main Results

• FirstOrder.Language.BoundedFormula.realize_toPrenex shows that the prenex normal form of a formula has the same realization as the original formula.
• Several results in this file show that syntactic constructions such as relabel, castLE, liftAt, subst, and the actions of language maps commute with realization of terms, formulas, sentences, and theories.

Implementation Notes

• Formulas use a modified version of de Bruijn variables. Specifically, a L.BoundedFormula α n is a formula with some variables indexed by a type α, which cannot be quantified over, and some indexed by Fin n, which can. For any φ : L.BoundedFormula α (n + 1), we define the formula ∀' φ : L.BoundedFormula α n by universally quantifying over the variable indexed by n : Fin (n + 1).

References

For the Flypitch project:

• [J. Han, F. van Doorn, A formal proof of the independence of the continuum hypothesis] [flypitch_cpp]
• [J. Han, F. van Doorn, A formalization of forcing and the unprovability of the continuum hypothesis][flypitch_itp]

def FirstOrder.Language.Term.realize {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} (v : α → M) (_t : FirstOrder.Language.Term L α) : M

A term t with variables indexed by α can be evaluated by giving a value to each variable.

Equations

• FirstOrder.Language.Term.realize v (FirstOrder.Language.var k) = v k
• FirstOrder.Language.Term.realize v (FirstOrder.Language.func f ts) = FirstOrder.Language.Structure.funMap f fun (i : Fin l) => FirstOrder.Language.Term.realize v (ts i)

@[simp]

theorem FirstOrder.Language.Term.realize_var {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} (v : α → M) (k : α) : FirstOrder.Language.Term.realize v (FirstOrder.Language.var k) = v k

@[simp]

theorem FirstOrder.Language.Term.realize_func {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} (v : α → M) {n : ℕ} (f : L.Functions n) (ts : Fin n → FirstOrder.Language.Term L α) : FirstOrder.Language.Term.realize v (FirstOrder.Language.func f ts) = FirstOrder.Language.Structure.funMap f fun (i : Fin n) => FirstOrder.Language.Term.realize v (ts i)

@[simp]

theorem FirstOrder.Language.Term.realize_relabel {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} {t : FirstOrder.Language.Term L α} {g : α → β} {v : β → M} : FirstOrder.Language.Term.realize v (FirstOrder.Language.Term.relabel g t) = FirstOrder.Language.Term.realize (v ∘ g) t

@[simp]

theorem FirstOrder.Language.Term.realize_liftAt {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {n : ℕ} {n' : ℕ} {m : ℕ} {t : FirstOrder.Language.Term L (α ⊕ Fin n)} {v : α ⊕ Fin (n + n') → M} : FirstOrder.Language.Term.realize v (FirstOrder.Language.Term.liftAt n' m t) = FirstOrder.Language.Term.realize (v ∘ Sum.map id fun (i : Fin n) => if ↑i < m then Fin.castAdd n' i else Fin.addNat i n') t

@[simp]

theorem FirstOrder.Language.Term.realize_constants {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {c : FirstOrder.Language.Constants L} {v : α → M} : FirstOrder.Language.Term.realize v (FirstOrder.Language.Constants.term c) = ↑c

@[simp]

theorem FirstOrder.Language.Term.realize_functions_apply₁ {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {f : L.Functions 1} {t : FirstOrder.Language.Term L α} {v : α → M} : FirstOrder.Language.Term.realize v (FirstOrder.Language.Functions.apply₁ f t) = FirstOrder.Language.Structure.funMap f ![FirstOrder.Language.Term.realize v t]

@[simp]

theorem FirstOrder.Language.Term.realize_functions_apply₂ {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {f : L.Functions 2} {t₁ : FirstOrder.Language.Term L α} {t₂ : FirstOrder.Language.Term L α} {v : α → M} : FirstOrder.Language.Term.realize v (FirstOrder.Language.Functions.apply₂ f t₁ t₂) = FirstOrder.Language.Structure.funMap f ![FirstOrder.Language.Term.realize v t₁, FirstOrder.Language.Term.realize v t₂]

theorem FirstOrder.Language.Term.realize_con {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {A : Set M} {a : ↑A} {v : α → M} : FirstOrder.Language.Term.realize v (FirstOrder.Language.Constants.term (FirstOrder.Language.con L a)) = ↑a

@[simp]

theorem FirstOrder.Language.Term.realize_subst {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} {t : FirstOrder.Language.Term L α} {tf : α → FirstOrder.Language.Term L β} {v : β → M} : FirstOrder.Language.Term.realize v (FirstOrder.Language.Term.subst t tf) = FirstOrder.Language.Term.realize (fun (a : α) => FirstOrder.Language.Term.realize v (tf a)) t

@[simp]

theorem FirstOrder.Language.Term.realize_restrictVar {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} [DecidableEq α] {t : FirstOrder.Language.Term L α} {s : Set α} (h : ↑(FirstOrder.Language.Term.varFinset t) ⊆ s) {v : α → M} : FirstOrder.Language.Term.realize (v ∘ Subtype.val) (FirstOrder.Language.Term.restrictVar t (Set.inclusion h)) = FirstOrder.Language.Term.realize v t

@[simp]

theorem FirstOrder.Language.Term.realize_restrictVarLeft {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} [DecidableEq α] {γ : Type u_4} {t : FirstOrder.Language.Term L (α ⊕ γ)} {s : Set α} (h : ↑(FirstOrder.Language.Term.varFinsetLeft t) ⊆ s) {v : α → M} {xs : γ → M} : FirstOrder.Language.Term.realize (Sum.elim (v ∘ Subtype.val) xs) (FirstOrder.Language.Term.restrictVarLeft t (Set.inclusion h)) = FirstOrder.Language.Term.realize (Sum.elim v xs) t

@[simp]

theorem FirstOrder.Language.Term.realize_constantsToVars {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} [FirstOrder.Language.Structure (FirstOrder.Language.withConstants L α) M] [FirstOrder.Language.LHom.IsExpansionOn (FirstOrder.Language.lhomWithConstants L α) M] {t : FirstOrder.Language.Term (FirstOrder.Language.withConstants L α) β} {v : β → M} : FirstOrder.Language.Term.realize (Sum.elim (fun (a : α) => ↑(FirstOrder.Language.con L a)) v) (FirstOrder.Language.Term.constantsToVars t) = FirstOrder.Language.Term.realize v t

@[simp]

theorem FirstOrder.Language.Term.realize_varsToConstants {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} [FirstOrder.Language.Structure (FirstOrder.Language.withConstants L α) M] [FirstOrder.Language.LHom.IsExpansionOn (FirstOrder.Language.lhomWithConstants L α) M] {t : FirstOrder.Language.Term L (α ⊕ β)} {v : β → M} : FirstOrder.Language.Term.realize v (FirstOrder.Language.Term.varsToConstants t) = FirstOrder.Language.Term.realize (Sum.elim (fun (a : α) => ↑(FirstOrder.Language.con L a)) v) t

theorem FirstOrder.Language.Term.realize_constantsVarsEquivLeft {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} [FirstOrder.Language.Structure (FirstOrder.Language.withConstants L α) M] [FirstOrder.Language.LHom.IsExpansionOn (FirstOrder.Language.lhomWithConstants L α) M] {n : ℕ} {t : FirstOrder.Language.Term (FirstOrder.Language.withConstants L α) (β ⊕ Fin n)} {v : β → M} {xs : Fin n → M} : FirstOrder.Language.Term.realize (Sum.elim (Sum.elim (fun (a : α) => ↑(FirstOrder.Language.con L a)) v) xs) (FirstOrder.Language.Term.constantsVarsEquivLeft t) = FirstOrder.Language.Term.realize (Sum.elim v xs) t

@[simp]

theorem FirstOrder.Language.LHom.realize_onTerm {L : FirstOrder.Language} {L' : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} [FirstOrder.Language.Structure L' M] (φ : L →ᴸ L') [FirstOrder.Language.LHom.IsExpansionOn φ M] (t : FirstOrder.Language.Term L α) (v : α → M) : FirstOrder.Language.Term.realize v (FirstOrder.Language.LHom.onTerm φ t) = FirstOrder.Language.Term.realize v t

@[simp]

theorem FirstOrder.Language.Hom.realize_term {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] {α : Type u'} (g : FirstOrder.Language.Hom L M N) {t : FirstOrder.Language.Term L α} {v : α → M} : FirstOrder.Language.Term.realize (⇑g ∘ v) t = g (FirstOrder.Language.Term.realize v t)

@[simp]

theorem FirstOrder.Language.Embedding.realize_term {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] {α : Type u'} {v : α → M} (t : FirstOrder.Language.Term L α) (g : FirstOrder.Language.Embedding L M N) : FirstOrder.Language.Term.realize (⇑g ∘ v) t = g (FirstOrder.Language.Term.realize v t)

@[simp]

theorem FirstOrder.Language.Equiv.realize_term {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] {α : Type u'} {v : α → M} (t : FirstOrder.Language.Term L α) (g : FirstOrder.Language.Equiv L M N) : FirstOrder.Language.Term.realize (⇑g ∘ v) t = g (FirstOrder.Language.Term.realize v t)

def FirstOrder.Language.BoundedFormula.Realize {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {l : ℕ} (_f : FirstOrder.Language.BoundedFormula L α l) (_v : α → M) (_xs : Fin l → M) : Prop

A bounded formula can be evaluated as true or false by giving values to each free variable.

Equations

• One or more equations did not get rendered due to their size.
• FirstOrder.Language.BoundedFormula.Realize FirstOrder.Language.BoundedFormula.falsum x✝ x = False
• FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.all f) x✝ x = ∀ (x_1 : M), FirstOrder.Language.BoundedFormula.Realize f x✝ (Fin.snoc x x_1)

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_bot {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {l : ℕ} {v : α → M} {xs : Fin l → M} : FirstOrder.Language.BoundedFormula.Realize ⊥ v xs ↔ False

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_not {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {l : ℕ} {φ : FirstOrder.Language.BoundedFormula L α l} {v : α → M} {xs : Fin l → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.not φ) v xs ↔ ¬FirstOrder.Language.BoundedFormula.Realize φ v xs

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_bdEqual {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {l : ℕ} {v : α → M} {xs : Fin l → M} (t₁ : FirstOrder.Language.Term L (α ⊕ Fin l)) (t₂ : FirstOrder.Language.Term L (α ⊕ Fin l)) : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.Term.bdEqual t₁ t₂) v xs ↔ FirstOrder.Language.Term.realize (Sum.elim v xs) t₁ = FirstOrder.Language.Term.realize (Sum.elim v xs) t₂

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_top {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {l : ℕ} {v : α → M} {xs : Fin l → M} : FirstOrder.Language.BoundedFormula.Realize ⊤ v xs ↔ True

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_inf {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {l : ℕ} {φ : FirstOrder.Language.BoundedFormula L α l} {ψ : FirstOrder.Language.BoundedFormula L α l} {v : α → M} {xs : Fin l → M} : FirstOrder.Language.BoundedFormula.Realize (φ ⊓ ψ) v xs ↔ FirstOrder.Language.BoundedFormula.Realize φ v xs ∧ FirstOrder.Language.BoundedFormula.Realize ψ v xs

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_foldr_inf {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {n : ℕ} (l : List (FirstOrder.Language.BoundedFormula L α n)) (v : α → M) (xs : Fin n → M) : FirstOrder.Language.BoundedFormula.Realize (List.foldr (fun (x x_1 : FirstOrder.Language.BoundedFormula L α n) => x ⊓ x_1) ⊤ l) v xs ↔ ∀ φ ∈ l, FirstOrder.Language.BoundedFormula.Realize φ v xs

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_imp {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {l : ℕ} {φ : FirstOrder.Language.BoundedFormula L α l} {ψ : FirstOrder.Language.BoundedFormula L α l} {v : α → M} {xs : Fin l → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.imp φ ψ) v xs ↔ FirstOrder.Language.BoundedFormula.Realize φ v xs → FirstOrder.Language.BoundedFormula.Realize ψ v xs

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_rel {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {l : ℕ} {v : α → M} {xs : Fin l → M} {k : ℕ} {R : L.Relations k} {ts : Fin k → FirstOrder.Language.Term L (α ⊕ Fin l)} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.Relations.boundedFormula R ts) v xs ↔ FirstOrder.Language.Structure.RelMap R fun (i : Fin k) => FirstOrder.Language.Term.realize (Sum.elim v xs) (ts i)

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_rel₁ {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {l : ℕ} {v : α → M} {xs : Fin l → M} {R : L.Relations 1} {t : FirstOrder.Language.Term L (α ⊕ Fin l)} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.Relations.boundedFormula₁ R t) v xs ↔ FirstOrder.Language.Structure.RelMap R ![FirstOrder.Language.Term.realize (Sum.elim v xs) t]

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_rel₂ {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {l : ℕ} {v : α → M} {xs : Fin l → M} {R : L.Relations 2} {t₁ : FirstOrder.Language.Term L (α ⊕ Fin l)} {t₂ : FirstOrder.Language.Term L (α ⊕ Fin l)} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.Relations.boundedFormula₂ R t₁ t₂) v xs ↔ FirstOrder.Language.Structure.RelMap R ![FirstOrder.Language.Term.realize (Sum.elim v xs) t₁, FirstOrder.Language.Term.realize (Sum.elim v xs) t₂]

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_sup {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {l : ℕ} {φ : FirstOrder.Language.BoundedFormula L α l} {ψ : FirstOrder.Language.BoundedFormula L α l} {v : α → M} {xs : Fin l → M} : FirstOrder.Language.BoundedFormula.Realize (φ ⊔ ψ) v xs ↔ FirstOrder.Language.BoundedFormula.Realize φ v xs ∨ FirstOrder.Language.BoundedFormula.Realize ψ v xs

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_foldr_sup {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {n : ℕ} (l : List (FirstOrder.Language.BoundedFormula L α n)) (v : α → M) (xs : Fin n → M) : FirstOrder.Language.BoundedFormula.Realize (List.foldr (fun (x x_1 : FirstOrder.Language.BoundedFormula L α n) => x ⊔ x_1) ⊥ l) v xs ↔ ∃ φ ∈ l, FirstOrder.Language.BoundedFormula.Realize φ v xs

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_all {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {l : ℕ} {θ : FirstOrder.Language.BoundedFormula L α (Nat.succ l)} {v : α → M} {xs : Fin l → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.all θ) v xs ↔ ∀ (a : M), FirstOrder.Language.BoundedFormula.Realize θ v (Fin.snoc xs a)

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_ex {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {l : ℕ} {θ : FirstOrder.Language.BoundedFormula L α (Nat.succ l)} {v : α → M} {xs : Fin l → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.ex θ) v xs ↔ ∃ (a : M), FirstOrder.Language.BoundedFormula.Realize θ v (Fin.snoc xs a)

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_iff {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {l : ℕ} {φ : FirstOrder.Language.BoundedFormula L α l} {ψ : FirstOrder.Language.BoundedFormula L α l} {v : α → M} {xs : Fin l → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.iff φ ψ) v xs ↔ (FirstOrder.Language.BoundedFormula.Realize φ v xs ↔ FirstOrder.Language.BoundedFormula.Realize ψ v xs)

theorem FirstOrder.Language.BoundedFormula.realize_castLE_of_eq {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {m : ℕ} {n : ℕ} (h : m = n) {h' : m ≤ n} {φ : FirstOrder.Language.BoundedFormula L α m} {v : α → M} {xs : Fin n → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.castLE h' φ) v xs ↔ FirstOrder.Language.BoundedFormula.Realize φ v (xs ∘ Fin.cast h)

theorem FirstOrder.Language.BoundedFormula.realize_mapTermRel_id {L : FirstOrder.Language} {L' : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} [FirstOrder.Language.Structure L' M] {ft : (n : ℕ) → FirstOrder.Language.Term L (α ⊕ Fin n) → FirstOrder.Language.Term L' (β ⊕ Fin n)} {fr : (n : ℕ) → L.Relations n → L'.Relations n} {n : ℕ} {φ : FirstOrder.Language.BoundedFormula L α n} {v : α → M} {v' : β → M} {xs : Fin n → M} (h1 : ∀ (n : ℕ) (t : FirstOrder.Language.Term L (α ⊕ Fin n)) (xs : Fin n → M), FirstOrder.Language.Term.realize (Sum.elim v' xs) (ft n t) = FirstOrder.Language.Term.realize (Sum.elim v xs) t) (h2 : ∀ (n : ℕ) (R : L.Relations n) (x : Fin n → M), FirstOrder.Language.Structure.RelMap (fr n R) x = FirstOrder.Language.Structure.RelMap R x) : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.mapTermRel ft fr (fun (x : ℕ) => id) φ) v' xs ↔ FirstOrder.Language.BoundedFormula.Realize φ v xs

theorem FirstOrder.Language.BoundedFormula.realize_mapTermRel_add_castLe {L : FirstOrder.Language} {L' : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} [FirstOrder.Language.Structure L' M] {k : ℕ} {ft : (n : ℕ) → FirstOrder.Language.Term L (α ⊕ Fin n) → FirstOrder.Language.Term L' (β ⊕ Fin (k + n))} {fr : (n : ℕ) → L.Relations n → L'.Relations n} {n : ℕ} {φ : FirstOrder.Language.BoundedFormula L α n} (v : {n : ℕ} → (Fin (k + n) → M) → α → M) {v' : β → M} (xs : Fin (k + n) → M) (h1 : ∀ (n : ℕ) (t : FirstOrder.Language.Term L (α ⊕ Fin n)) (xs' : Fin (k + n) → M), FirstOrder.Language.Term.realize (Sum.elim v' xs') (ft n t) = FirstOrder.Language.Term.realize (Sum.elim (v xs') (xs' ∘ Fin.natAdd k)) t) (h2 : ∀ (n : ℕ) (R : L.Relations n) (x : Fin n → M), FirstOrder.Language.Structure.RelMap (fr n R) x = FirstOrder.Language.Structure.RelMap R x) (hv : ∀ (n : ℕ) (xs : Fin (k + n) → M) (x : M), v (Fin.snoc xs x) = v xs) : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.mapTermRel ft fr (fun (n : ℕ) => FirstOrder.Language.BoundedFormula.castLE (_ : k + (n + 1) ≤ k + n + 1)) φ) v' xs ↔ FirstOrder.Language.BoundedFormula.Realize φ (v xs) (xs ∘ Fin.natAdd k)

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_relabel {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} {m : ℕ} {n : ℕ} {φ : FirstOrder.Language.BoundedFormula L α n} {g : α → β ⊕ Fin m} {v : β → M} {xs : Fin (m + n) → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.relabel g φ) v xs ↔ FirstOrder.Language.BoundedFormula.Realize φ (Sum.elim v (xs ∘ Fin.castAdd n) ∘ g) (xs ∘ Fin.natAdd m)

theorem FirstOrder.Language.BoundedFormula.realize_liftAt {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {n : ℕ} {n' : ℕ} {m : ℕ} {φ : FirstOrder.Language.BoundedFormula L α n} {v : α → M} {xs : Fin (n + n') → M} (hmn : m + n' ≤ n + 1) : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.liftAt n' m φ) v xs ↔ FirstOrder.Language.BoundedFormula.Realize φ v (xs ∘ fun (i : Fin n) => if ↑i < m then Fin.castAdd n' i else Fin.addNat i n')

theorem FirstOrder.Language.BoundedFormula.realize_liftAt_one {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {n : ℕ} {m : ℕ} {φ : FirstOrder.Language.BoundedFormula L α n} {v : α → M} {xs : Fin (n + 1) → M} (hmn : m ≤ n) : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.liftAt 1 m φ) v xs ↔ FirstOrder.Language.BoundedFormula.Realize φ v (xs ∘ fun (i : Fin n) => if ↑i < m then Fin.castSucc i else Fin.succ i)

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_liftAt_one_self {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {n : ℕ} {φ : FirstOrder.Language.BoundedFormula L α n} {v : α → M} {xs : Fin (n + 1) → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.liftAt 1 n φ) v xs ↔ FirstOrder.Language.BoundedFormula.Realize φ v (xs ∘ Fin.castSucc)

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_subst {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} {n : ℕ} {φ : FirstOrder.Language.BoundedFormula L α n} {tf : α → FirstOrder.Language.Term L β} {v : β → M} {xs : Fin n → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.subst φ tf) v xs ↔ FirstOrder.Language.BoundedFormula.Realize φ (fun (a : α) => FirstOrder.Language.Term.realize v (tf a)) xs

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_restrictFreeVar {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} [DecidableEq α] {n : ℕ} {φ : FirstOrder.Language.BoundedFormula L α n} {s : Set α} (h : ↑(FirstOrder.Language.BoundedFormula.freeVarFinset φ) ⊆ s) {v : α → M} {xs : Fin n → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.restrictFreeVar φ (Set.inclusion h)) (v ∘ Subtype.val) xs ↔ FirstOrder.Language.BoundedFormula.Realize φ v xs

theorem FirstOrder.Language.BoundedFormula.realize_constantsVarsEquiv {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} [FirstOrder.Language.Structure (FirstOrder.Language.withConstants L α) M] [FirstOrder.Language.LHom.IsExpansionOn (FirstOrder.Language.lhomWithConstants L α) M] {n : ℕ} {φ : FirstOrder.Language.BoundedFormula (FirstOrder.Language.withConstants L α) β n} {v : β → M} {xs : Fin n → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.constantsVarsEquiv φ) (Sum.elim (fun (a : α) => ↑(FirstOrder.Language.con L a)) v) xs ↔ FirstOrder.Language.BoundedFormula.Realize φ v xs

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_relabelEquiv {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} {g : α ≃ β} {k : ℕ} {φ : FirstOrder.Language.BoundedFormula L α k} {v : β → M} {xs : Fin k → M} : FirstOrder.Language.BoundedFormula.Realize ((FirstOrder.Language.BoundedFormula.relabelEquiv g) φ) v xs ↔ FirstOrder.Language.BoundedFormula.Realize φ (v ∘ ⇑g) xs

theorem FirstOrder.Language.BoundedFormula.realize_all_liftAt_one_self {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} [Nonempty M] {n : ℕ} {φ : FirstOrder.Language.BoundedFormula L α n} {v : α → M} {xs : Fin n → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.all (FirstOrder.Language.BoundedFormula.liftAt 1 n φ)) v xs ↔ FirstOrder.Language.BoundedFormula.Realize φ v xs

theorem FirstOrder.Language.BoundedFormula.realize_toPrenexImpRight {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {n : ℕ} [Nonempty M] {φ : FirstOrder.Language.BoundedFormula L α n} {ψ : FirstOrder.Language.BoundedFormula L α n} (hφ : FirstOrder.Language.BoundedFormula.IsQF φ) (hψ : FirstOrder.Language.BoundedFormula.IsPrenex ψ) {v : α → M} {xs : Fin n → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.toPrenexImpRight φ ψ) v xs ↔ FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.imp φ ψ) v xs

theorem FirstOrder.Language.BoundedFormula.realize_toPrenexImp {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {n : ℕ} [Nonempty M] {φ : FirstOrder.Language.BoundedFormula L α n} {ψ : FirstOrder.Language.BoundedFormula L α n} (hφ : FirstOrder.Language.BoundedFormula.IsPrenex φ) (hψ : FirstOrder.Language.BoundedFormula.IsPrenex ψ) {v : α → M} {xs : Fin n → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.toPrenexImp φ ψ) v xs ↔ FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.imp φ ψ) v xs

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_toPrenex {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {n : ℕ} [Nonempty M] (φ : FirstOrder.Language.BoundedFormula L α n) {v : α → M} {xs : Fin n → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.toPrenex φ) v xs ↔ FirstOrder.Language.BoundedFormula.Realize φ v xs

@[simp]

theorem FirstOrder.Language.LHom.realize_onBoundedFormula {L : FirstOrder.Language} {L' : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} [FirstOrder.Language.Structure L' M] (φ : L →ᴸ L') [FirstOrder.Language.LHom.IsExpansionOn φ M] {n : ℕ} (ψ : FirstOrder.Language.BoundedFormula L α n) {v : α → M} {xs : Fin n → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.LHom.onBoundedFormula φ ψ) v xs ↔ FirstOrder.Language.BoundedFormula.Realize ψ v xs

def FirstOrder.Language.Formula.Realize {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} (φ : FirstOrder.Language.Formula L α) (v : α → M) : Prop

A formula can be evaluated as true or false by giving values to each free variable.

Equations

• FirstOrder.Language.Formula.Realize φ v = FirstOrder.Language.BoundedFormula.Realize φ v default

@[simp]

theorem FirstOrder.Language.Formula.realize_not {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {φ : FirstOrder.Language.Formula L α} {v : α → M} : FirstOrder.Language.Formula.Realize (FirstOrder.Language.Formula.not φ) v ↔ ¬FirstOrder.Language.Formula.Realize φ v

@[simp]

theorem FirstOrder.Language.Formula.realize_bot {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {v : α → M} : FirstOrder.Language.Formula.Realize ⊥ v ↔ False

@[simp]

theorem FirstOrder.Language.Formula.realize_top {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {v : α → M} : FirstOrder.Language.Formula.Realize ⊤ v ↔ True

@[simp]

theorem FirstOrder.Language.Formula.realize_inf {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {φ : FirstOrder.Language.Formula L α} {ψ : FirstOrder.Language.Formula L α} {v : α → M} : FirstOrder.Language.Formula.Realize (φ ⊓ ψ) v ↔ FirstOrder.Language.Formula.Realize φ v ∧ FirstOrder.Language.Formula.Realize ψ v

@[simp]

theorem FirstOrder.Language.Formula.realize_imp {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {φ : FirstOrder.Language.Formula L α} {ψ : FirstOrder.Language.Formula L α} {v : α → M} : FirstOrder.Language.Formula.Realize (FirstOrder.Language.Formula.imp φ ψ) v ↔ FirstOrder.Language.Formula.Realize φ v → FirstOrder.Language.Formula.Realize ψ v

@[simp]

theorem FirstOrder.Language.Formula.realize_rel {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {v : α → M} {k : ℕ} {R : L.Relations k} {ts : Fin k → FirstOrder.Language.Term L α} : FirstOrder.Language.Formula.Realize (FirstOrder.Language.Relations.formula R ts) v ↔ FirstOrder.Language.Structure.RelMap R fun (i : Fin k) => FirstOrder.Language.Term.realize v (ts i)

@[simp]

theorem FirstOrder.Language.Formula.realize_rel₁ {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {v : α → M} {R : L.Relations 1} {t : FirstOrder.Language.Term L α} : FirstOrder.Language.Formula.Realize (FirstOrder.Language.Relations.formula₁ R t) v ↔ FirstOrder.Language.Structure.RelMap R ![FirstOrder.Language.Term.realize v t]

@[simp]

theorem FirstOrder.Language.Formula.realize_rel₂ {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {v : α → M} {R : L.Relations 2} {t₁ : FirstOrder.Language.Term L α} {t₂ : FirstOrder.Language.Term L α} : FirstOrder.Language.Formula.Realize (FirstOrder.Language.Relations.formula₂ R t₁ t₂) v ↔ FirstOrder.Language.Structure.RelMap R ![FirstOrder.Language.Term.realize v t₁, FirstOrder.Language.Term.realize v t₂]

@[simp]

theorem FirstOrder.Language.Formula.realize_sup {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {φ : FirstOrder.Language.Formula L α} {ψ : FirstOrder.Language.Formula L α} {v : α → M} : FirstOrder.Language.Formula.Realize (φ ⊔ ψ) v ↔ FirstOrder.Language.Formula.Realize φ v ∨ FirstOrder.Language.Formula.Realize ψ v

@[simp]

theorem FirstOrder.Language.Formula.realize_iff {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {φ : FirstOrder.Language.Formula L α} {ψ : FirstOrder.Language.Formula L α} {v : α → M} : FirstOrder.Language.Formula.Realize (FirstOrder.Language.Formula.iff φ ψ) v ↔ (FirstOrder.Language.Formula.Realize φ v ↔ FirstOrder.Language.Formula.Realize ψ v)

@[simp]

theorem FirstOrder.Language.Formula.realize_relabel {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} {φ : FirstOrder.Language.Formula L α} {g : α → β} {v : β → M} : FirstOrder.Language.Formula.Realize (FirstOrder.Language.Formula.relabel g φ) v ↔ FirstOrder.Language.Formula.Realize φ (v ∘ g)

theorem FirstOrder.Language.Formula.realize_relabel_sum_inr {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {n : ℕ} (φ : FirstOrder.Language.Formula L (Fin n)) {v : Empty → M} {x : Fin n → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.relabel Sum.inr φ) v x ↔ FirstOrder.Language.Formula.Realize φ x

@[simp]

theorem FirstOrder.Language.Formula.realize_equal {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {t₁ : FirstOrder.Language.Term L α} {t₂ : FirstOrder.Language.Term L α} {x : α → M} : FirstOrder.Language.Formula.Realize (FirstOrder.Language.Term.equal t₁ t₂) x ↔ FirstOrder.Language.Term.realize x t₁ = FirstOrder.Language.Term.realize x t₂

@[simp]

theorem FirstOrder.Language.Formula.realize_graph {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {n : ℕ} {f : L.Functions n} {x : Fin n → M} {y : M} : FirstOrder.Language.Formula.Realize (FirstOrder.Language.Formula.graph f) (Fin.cons y x) ↔ FirstOrder.Language.Structure.funMap f x = y

@[simp]

theorem FirstOrder.Language.LHom.realize_onFormula {L : FirstOrder.Language} {L' : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} [FirstOrder.Language.Structure L' M] (φ : L →ᴸ L') [FirstOrder.Language.LHom.IsExpansionOn φ M] (ψ : FirstOrder.Language.Formula L α) {v : α → M} : FirstOrder.Language.Formula.Realize (FirstOrder.Language.LHom.onFormula φ ψ) v ↔ FirstOrder.Language.Formula.Realize ψ v

@[simp]

theorem FirstOrder.Language.LHom.setOf_realize_onFormula {L : FirstOrder.Language} {L' : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} [FirstOrder.Language.Structure L' M] (φ : L →ᴸ L') [FirstOrder.Language.LHom.IsExpansionOn φ M] (ψ : FirstOrder.Language.Formula L α) : setOf (FirstOrder.Language.Formula.Realize (FirstOrder.Language.LHom.onFormula φ ψ)) = setOf (FirstOrder.Language.Formula.Realize ψ)

def FirstOrder.Language.Sentence.Realize {L : FirstOrder.Language} (M : Type w) [FirstOrder.Language.Structure L M] (φ : FirstOrder.Language.Sentence L) : Prop

A sentence can be evaluated as true or false in a structure.

Equations

• M ⊨ φ = FirstOrder.Language.Formula.Realize φ default

def FirstOrder.Language.«term_⊨_» : Lean.TrailingParserDescr

A sentence can be evaluated as true or false in a structure.

Equations

• One or more equations did not get rendered due to their size.

@[simp]

theorem FirstOrder.Language.Sentence.realize_not {L : FirstOrder.Language} (M : Type w) [FirstOrder.Language.Structure L M] {φ : FirstOrder.Language.Sentence L} : M ⊨ FirstOrder.Language.Formula.not φ ↔ ¬M ⊨ φ

@[simp]

theorem FirstOrder.Language.Formula.realize_equivSentence_symm_con {L : FirstOrder.Language} (M : Type w) [FirstOrder.Language.Structure L M] {α : Type u'} [FirstOrder.Language.Structure (FirstOrder.Language.withConstants L α) M] [FirstOrder.Language.LHom.IsExpansionOn (FirstOrder.Language.lhomWithConstants L α) M] (φ : FirstOrder.Language.Sentence (FirstOrder.Language.withConstants L α)) : (FirstOrder.Language.Formula.Realize (FirstOrder.Language.Formula.equivSentence.symm φ) fun (a : α) => ↑(FirstOrder.Language.con L a)) ↔ M ⊨ φ

@[simp]

theorem FirstOrder.Language.Formula.realize_equivSentence {L : FirstOrder.Language} (M : Type w) [FirstOrder.Language.Structure L M] {α : Type u'} [FirstOrder.Language.Structure (FirstOrder.Language.withConstants L α) M] [FirstOrder.Language.LHom.IsExpansionOn (FirstOrder.Language.lhomWithConstants L α) M] (φ : FirstOrder.Language.Formula L α) : M ⊨ FirstOrder.Language.Formula.equivSentence φ ↔ FirstOrder.Language.Formula.Realize φ fun (a : α) => ↑(FirstOrder.Language.con L a)

theorem FirstOrder.Language.Formula.realize_equivSentence_symm {L : FirstOrder.Language} (M : Type w) [FirstOrder.Language.Structure L M] {α : Type u'} (φ : FirstOrder.Language.Sentence (FirstOrder.Language.withConstants L α)) (v : α → M) : FirstOrder.Language.Formula.Realize (FirstOrder.Language.Formula.equivSentence.symm φ) v ↔ M ⊨ φ

@[simp]

theorem FirstOrder.Language.LHom.realize_onSentence {L : FirstOrder.Language} {L' : FirstOrder.Language} (M : Type w) [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L' M] (φ : L →ᴸ L') [FirstOrder.Language.LHom.IsExpansionOn φ M] (ψ : FirstOrder.Language.Sentence L) : M ⊨ FirstOrder.Language.LHom.onSentence φ ψ ↔ M ⊨ ψ

def FirstOrder.Language.completeTheory (L : FirstOrder.Language) (M : Type w) [FirstOrder.Language.Structure L M] : FirstOrder.Language.Theory L

The complete theory of a structure M is the set of all sentences M satisfies.

Equations

• FirstOrder.Language.completeTheory L M = {φ : FirstOrder.Language.Sentence L | M ⊨ φ}

def FirstOrder.Language.ElementarilyEquivalent (L : FirstOrder.Language) (M : Type w) (N : Type u_1) [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] : Prop

Two structures are elementarily equivalent when they satisfy the same sentences.

Equations

• FirstOrder.Language.ElementarilyEquivalent L M N = (FirstOrder.Language.completeTheory L M = FirstOrder.Language.completeTheory L N)

def FirstOrder.«term_≅[_]_» : Lean.TrailingParserDescr

Two structures are elementarily equivalent when they satisfy the same sentences.

Equations

• One or more equations did not get rendered due to their size.

@[simp]

theorem FirstOrder.Language.mem_completeTheory {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {φ : FirstOrder.Language.Sentence L} : φ ∈ FirstOrder.Language.completeTheory L M ↔ M ⊨ φ

theorem FirstOrder.Language.elementarilyEquivalent_iff {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] : FirstOrder.Language.ElementarilyEquivalent L M N ↔ ∀ (φ : FirstOrder.Language.Sentence L), M ⊨ φ ↔ N ⊨ φ

class FirstOrder.Language.Theory.Model {L : FirstOrder.Language} (M : Type w) [FirstOrder.Language.Structure L M] (T : FirstOrder.Language.Theory L) : Prop

A model of a theory is a structure in which every sentence is realized as true.

• realize_of_mem : ∀ φ ∈ T, M ⊨ φ

def FirstOrder.Language.«term_⊨__1» : Lean.TrailingParserDescr

A model of a theory is a structure in which every sentence is realized as true.

Equations

• One or more equations did not get rendered due to their size.

@[simp]

theorem FirstOrder.Language.Theory.model_iff {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] (T : FirstOrder.Language.Theory L) : M ⊨ T ↔ ∀ φ ∈ T, M ⊨ φ

theorem FirstOrder.Language.Theory.realize_sentence_of_mem {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] (T : FirstOrder.Language.Theory L) [M ⊨ T] {φ : FirstOrder.Language.Sentence L} (h : φ ∈ T) : M ⊨ φ

@[simp]

theorem FirstOrder.Language.LHom.onTheory_model {L : FirstOrder.Language} {L' : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L' M] (φ : L →ᴸ L') [FirstOrder.Language.LHom.IsExpansionOn φ M] (T : FirstOrder.Language.Theory L) : M ⊨ FirstOrder.Language.LHom.onTheory φ T ↔ M ⊨ T

instance FirstOrder.Language.model_empty {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] : M ⊨ ∅

Equations

• (_ : M ⊨ ∅) = (_ : M ⊨ ∅)

theorem FirstOrder.Language.Theory.Model.mono {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {T : FirstOrder.Language.Theory L} {T' : FirstOrder.Language.Theory L} (_h : M ⊨ T') (hs : T ⊆ T') : M ⊨ T

theorem FirstOrder.Language.Theory.Model.union {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {T : FirstOrder.Language.Theory L} {T' : FirstOrder.Language.Theory L} (h : M ⊨ T) (h' : M ⊨ T') : M ⊨ T ∪ T'

@[simp]

theorem FirstOrder.Language.Theory.model_union_iff {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {T : FirstOrder.Language.Theory L} {T' : FirstOrder.Language.Theory L} : M ⊨ T ∪ T' ↔ M ⊨ T ∧ M ⊨ T'

theorem FirstOrder.Language.Theory.model_singleton_iff {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {φ : FirstOrder.Language.Sentence L} : M ⊨ {φ} ↔ M ⊨ φ

theorem FirstOrder.Language.Theory.model_iff_subset_completeTheory {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {T : FirstOrder.Language.Theory L} : M ⊨ T ↔ T ⊆ FirstOrder.Language.completeTheory L M

theorem FirstOrder.Language.Theory.completeTheory.subset {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {T : FirstOrder.Language.Theory L} [MT : M ⊨ T] : T ⊆ FirstOrder.Language.completeTheory L M

instance FirstOrder.Language.model_completeTheory {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] : M ⊨ FirstOrder.Language.completeTheory L M

Equations

• (_ : M ⊨ FirstOrder.Language.completeTheory L M) = (_ : M ⊨ FirstOrder.Language.completeTheory L M)

theorem FirstOrder.Language.realize_iff_of_model_completeTheory {L : FirstOrder.Language} (M : Type w) (N : Type u_1) [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] [N ⊨ FirstOrder.Language.completeTheory L M] (φ : FirstOrder.Language.Sentence L) : N ⊨ φ ↔ M ⊨ φ

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_alls {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {n : ℕ} {φ : FirstOrder.Language.BoundedFormula L α n} {v : α → M} : FirstOrder.Language.Formula.Realize (FirstOrder.Language.BoundedFormula.alls φ) v ↔ ∀ (xs : Fin n → M), FirstOrder.Language.BoundedFormula.Realize φ v xs

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_exs {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {n : ℕ} {φ : FirstOrder.Language.BoundedFormula L α n} {v : α → M} : FirstOrder.Language.Formula.Realize (FirstOrder.Language.BoundedFormula.exs φ) v ↔ ∃ (xs : Fin n → M), FirstOrder.Language.BoundedFormula.Realize φ v xs

@[simp]

theorem FirstOrder.Language.Formula.realize_iAlls {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} {γ : Type u_3} [Finite γ] {f : α → β ⊕ γ} {φ : FirstOrder.Language.Formula L α} {v : β → M} : FirstOrder.Language.Formula.Realize (FirstOrder.Language.Formula.iAlls f φ) v ↔ ∀ (i : γ → M), FirstOrder.Language.Formula.Realize φ fun (a : α) => Sum.elim v i (f a)

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_iAlls {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} {γ : Type u_3} [Finite γ] {f : α → β ⊕ γ} {φ : FirstOrder.Language.Formula L α} {v : β → M} {v' : Fin 0 → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.Formula.iAlls f φ) v v' ↔ ∀ (i : γ → M), FirstOrder.Language.Formula.Realize φ fun (a : α) => Sum.elim v i (f a)

@[simp]

theorem FirstOrder.Language.Formula.realize_iExs {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} {γ : Type u_3} [Finite γ] {f : α → β ⊕ γ} {φ : FirstOrder.Language.Formula L α} {v : β → M} : FirstOrder.Language.Formula.Realize (FirstOrder.Language.Formula.iExs f φ) v ↔ ∃ (i : γ → M), FirstOrder.Language.Formula.Realize φ fun (a : α) => Sum.elim v i (f a)

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_iExs {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} {γ : Type u_3} [Finite γ] {f : α → β ⊕ γ} {φ : FirstOrder.Language.Formula L α} {v : β → M} {v' : Fin 0 → M} : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.Formula.iExs f φ) v v' ↔ ∃ (i : γ → M), FirstOrder.Language.Formula.Realize φ fun (a : α) => Sum.elim v i (f a)

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_toFormula {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {n : ℕ} (φ : FirstOrder.Language.BoundedFormula L α n) (v : α ⊕ Fin n → M) : FirstOrder.Language.Formula.Realize (FirstOrder.Language.BoundedFormula.toFormula φ) v ↔ FirstOrder.Language.BoundedFormula.Realize φ (v ∘ Sum.inl) (v ∘ Sum.inr)

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_iSup {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} {n : ℕ} (s : Finset β) (f : β → FirstOrder.Language.BoundedFormula L α n) (v : α → M) (v' : Fin n → M) : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.iSup s f) v v' ↔ ∃ b ∈ s, FirstOrder.Language.BoundedFormula.Realize (f b) v v'

@[simp]

theorem FirstOrder.Language.BoundedFormula.realize_iInf {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {α : Type u'} {β : Type v'} {n : ℕ} (s : Finset β) (f : β → FirstOrder.Language.BoundedFormula L α n) (v : α → M) (v' : Fin n → M) : FirstOrder.Language.BoundedFormula.Realize (FirstOrder.Language.BoundedFormula.iInf s f) v v' ↔ ∀ b ∈ s, FirstOrder.Language.BoundedFormula.Realize (f b) v v'

@[simp]

theorem FirstOrder.Language.Equiv.realize_boundedFormula {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] {α : Type u'} {n : ℕ} (g : FirstOrder.Language.Equiv L M N) (φ : FirstOrder.Language.BoundedFormula L α n) {v : α → M} {xs : Fin n → M} : FirstOrder.Language.BoundedFormula.Realize φ (⇑g ∘ v) (⇑g ∘ xs) ↔ FirstOrder.Language.BoundedFormula.Realize φ v xs

@[simp]

theorem FirstOrder.Language.Equiv.realize_formula {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] {α : Type u'} (g : FirstOrder.Language.Equiv L M N) (φ : FirstOrder.Language.Formula L α) {v : α → M} : FirstOrder.Language.Formula.Realize φ (⇑g ∘ v) ↔ FirstOrder.Language.Formula.Realize φ v

theorem FirstOrder.Language.Equiv.realize_sentence {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] (g : FirstOrder.Language.Equiv L M N) (φ : FirstOrder.Language.Sentence L) : M ⊨ φ ↔ N ⊨ φ

theorem FirstOrder.Language.Equiv.theory_model {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] {T : FirstOrder.Language.Theory L} (g : FirstOrder.Language.Equiv L M N) [M ⊨ T] : N ⊨ T

theorem FirstOrder.Language.Equiv.elementarilyEquivalent {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] (g : FirstOrder.Language.Equiv L M N) : FirstOrder.Language.ElementarilyEquivalent L M N

@[simp]

theorem FirstOrder.Language.Relations.realize_reflexive {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {r : L.Relations 2} : M ⊨ FirstOrder.Language.Relations.reflexive r ↔ Reflexive fun (x y : M) => FirstOrder.Language.Structure.RelMap r ![x, y]

@[simp]

theorem FirstOrder.Language.Relations.realize_irreflexive {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {r : L.Relations 2} : M ⊨ FirstOrder.Language.Relations.irreflexive r ↔ Irreflexive fun (x y : M) => FirstOrder.Language.Structure.RelMap r ![x, y]

@[simp]

theorem FirstOrder.Language.Relations.realize_symmetric {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {r : L.Relations 2} : M ⊨ FirstOrder.Language.Relations.symmetric r ↔ Symmetric fun (x y : M) => FirstOrder.Language.Structure.RelMap r ![x, y]

@[simp]

theorem FirstOrder.Language.Relations.realize_antisymmetric {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {r : L.Relations 2} : M ⊨ FirstOrder.Language.Relations.antisymmetric r ↔ AntiSymmetric fun (x y : M) => FirstOrder.Language.Structure.RelMap r ![x, y]

@[simp]

theorem FirstOrder.Language.Relations.realize_transitive {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {r : L.Relations 2} : M ⊨ FirstOrder.Language.Relations.transitive r ↔ Transitive fun (x y : M) => FirstOrder.Language.Structure.RelMap r ![x, y]

@[simp]

theorem FirstOrder.Language.Relations.realize_total {L : FirstOrder.Language} {M : Type w} [FirstOrder.Language.Structure L M] {r : L.Relations 2} : M ⊨ FirstOrder.Language.Relations.total r ↔ Total fun (x y : M) => FirstOrder.Language.Structure.RelMap r ![x, y]

@[simp]

theorem FirstOrder.Language.Sentence.realize_cardGe (L : FirstOrder.Language) {M : Type w} [FirstOrder.Language.Structure L M] (n : ℕ) : M ⊨ FirstOrder.Language.Sentence.cardGe L n ↔ ↑n ≤ Cardinal.mk M

@[simp]

theorem FirstOrder.Language.model_infiniteTheory_iff (L : FirstOrder.Language) {M : Type w} [FirstOrder.Language.Structure L M] : M ⊨ FirstOrder.Language.infiniteTheory L ↔ Infinite M

instance FirstOrder.Language.model_infiniteTheory (L : FirstOrder.Language) {M : Type w} [FirstOrder.Language.Structure L M] [h : Infinite M] : M ⊨ FirstOrder.Language.infiniteTheory L

Equations

• (_ : M ⊨ FirstOrder.Language.infiniteTheory L) = (_ : M ⊨ FirstOrder.Language.infiniteTheory L)

@[simp]

theorem FirstOrder.Language.model_nonemptyTheory_iff (L : FirstOrder.Language) {M : Type w} [FirstOrder.Language.Structure L M] : M ⊨ FirstOrder.Language.nonemptyTheory L ↔ Nonempty M

instance FirstOrder.Language.model_nonempty (L : FirstOrder.Language) {M : Type w} [FirstOrder.Language.Structure L M] [h : Nonempty M] : M ⊨ FirstOrder.Language.nonemptyTheory L

Equations

• (_ : M ⊨ FirstOrder.Language.nonemptyTheory L) = (_ : M ⊨ FirstOrder.Language.nonemptyTheory L)

theorem FirstOrder.Language.model_distinctConstantsTheory (L : FirstOrder.Language) {α : Type u'} {M : Type w} [FirstOrder.Language.Structure (FirstOrder.Language.withConstants L α) M] (s : Set α) : M ⊨ FirstOrder.Language.distinctConstantsTheory L s ↔ Set.InjOn (fun (i : α) => ↑(FirstOrder.Language.con L i)) s

theorem FirstOrder.Language.card_le_of_model_distinctConstantsTheory (L : FirstOrder.Language) {α : Type u'} (s : Set α) (M : Type w) [FirstOrder.Language.Structure (FirstOrder.Language.withConstants L α) M] [h : M ⊨ FirstOrder.Language.distinctConstantsTheory L s] : Cardinal.lift.{w, u'} (Cardinal.mk ↑s) ≤ Cardinal.lift.{u', w} (Cardinal.mk M)

theorem FirstOrder.Language.ElementarilyEquivalent.symm {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] (h : FirstOrder.Language.ElementarilyEquivalent L M N) : FirstOrder.Language.ElementarilyEquivalent L N M

theorem FirstOrder.Language.ElementarilyEquivalent.trans {L : FirstOrder.Language} {M : Type w} {N : Type u_1} {P : Type u_2} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] [FirstOrder.Language.Structure L P] (MN : FirstOrder.Language.ElementarilyEquivalent L M N) (NP : FirstOrder.Language.ElementarilyEquivalent L N P) : FirstOrder.Language.ElementarilyEquivalent L M P

theorem FirstOrder.Language.ElementarilyEquivalent.completeTheory_eq {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] (h : FirstOrder.Language.ElementarilyEquivalent L M N) : FirstOrder.Language.completeTheory L M = FirstOrder.Language.completeTheory L N

theorem FirstOrder.Language.ElementarilyEquivalent.realize_sentence {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] (h : FirstOrder.Language.ElementarilyEquivalent L M N) (φ : FirstOrder.Language.Sentence L) : M ⊨ φ ↔ N ⊨ φ

theorem FirstOrder.Language.ElementarilyEquivalent.theory_model_iff {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] {T : FirstOrder.Language.Theory L} (h : FirstOrder.Language.ElementarilyEquivalent L M N) : M ⊨ T ↔ N ⊨ T

theorem FirstOrder.Language.ElementarilyEquivalent.theory_model {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] {T : FirstOrder.Language.Theory L} [MT : M ⊨ T] (h : FirstOrder.Language.ElementarilyEquivalent L M N) : N ⊨ T

theorem FirstOrder.Language.ElementarilyEquivalent.nonempty_iff {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] (h : FirstOrder.Language.ElementarilyEquivalent L M N) : Nonempty M ↔ Nonempty N

theorem FirstOrder.Language.ElementarilyEquivalent.nonempty {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] [Mn : Nonempty M] (h : FirstOrder.Language.ElementarilyEquivalent L M N) : Nonempty N

theorem FirstOrder.Language.ElementarilyEquivalent.infinite_iff {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] (h : FirstOrder.Language.ElementarilyEquivalent L M N) : Infinite M ↔ Infinite N

theorem FirstOrder.Language.ElementarilyEquivalent.infinite {L : FirstOrder.Language} {M : Type w} {N : Type u_1} [FirstOrder.Language.Structure L M] [FirstOrder.Language.Structure L N] [Mi : Infinite M] (h : FirstOrder.Language.ElementarilyEquivalent L M N) : Infinite N