Documentation

LeanPool.InfinitaryLogic.Lomega1omega.OpenBoundsSemantics

Semantics of openBounds and of relabeling by insertLastBound #

Two semantic round-trip lemmas about the bound/free variable bookkeeping of Lomega1omega/Operations, in a neutral module so that consumers below the Henkin construction and the Scott analysis can use them without importing either:

Both were previously proved inside Scott/Formula.lean and Methods/Henkin/Construction.lean respectively; the statements and names are unchanged.

theorem FirstOrder.Language.realize_relabel_insertLastBound_zero {L : Language} {N : Type w} [L.Structure N] {n : } (φ : L.Formulaω (Fin (n + 1))) (v : Fin nN) (xs : Fin 1N) :

The key semantics lemma for formulas with 0 bound variables: relabeling with insertLastBound shifts the last free variable to a bound variable position.

For φ : L.Formulaω (Fin (n+1)) (a formula with n+1 free vars and 0 bound vars):

  • φ.relabel insertLastBound : L.BoundedFormulaω (Fin n) 1 has n free vars and 1 bound var
  • When we evaluate with free var assignment v : Fin n → N and bound var assignment xs : Fin 1 → N, this corresponds to evaluating the original formula with snoc v (xs 0) : Fin (n+1) → N

Helper: snoc Fin.elim0 x evaluated at 0 : Fin 1 gives x.

theorem FirstOrder.Language.realize_openBounds {L : Language} {M : Type u_1} [L.Structure M] {n : } (φ : L.BoundedFormulaω Empty n) (xs : Fin nM) :

Semantic roundtrip: openBounds preserves semantics. For φ : BoundedFormulaω Empty n, evaluating openBounds φ with free variable assignment xs : Fin n → M is equivalent to evaluating φ with bound variable assignment xs.