Boolean-valued set theory: LanguageExtension
DefinitionCH_Cohen_Library08ch-cohen-flypitch4forcingmodel-theoryset-theory
This module provides language embeddings, expansions, reducts, and formula transport. These objects form the language and model interfaces used in the forcing and completeness arguments.
Formalization Note The module retains the structural normalization facts needed by these definitions and their constructor proofs. The principal forcing and model-existence assertions are separate theorem nodes.
Original formalization: Jesse Han and Floris van Doorn. Lean 4 port: Ian Klatzco, with Claude (Apache-2.0). Adapted to the pinned Prove2Me environment.
Formalization credit: Wentao Li (Victor), under the Prove2Me account Victorized, with assistance from OpenAI Codex.
Definition code
import Mathlib.Data.Set.Countable
import Mathlib.SetTheory.Cardinal.Cofinality
import Mathlib.SetTheory.Cardinal.Order
import Mathlib.Order.CompleteBooleanAlgebra
import Mathlib.Topology.Bases
import Mathlib.Topology.Sets.Opens
import Mathlib.SetTheory.Cardinal.Basic
import Mathlib.SetTheory.Cardinal.Regular
import Mathlib.SetTheory.Ordinal.Basic
import Mathlib.SetTheory.ZFC.Basic
import Mathlib.SetTheory.ZFC.Ordinal
import Mathlib.SetTheory.Ordinal.Arithmetic
import Mathlib.Order.Zorn
import Mathlib.Data.Set.Card
import Mathlib.Topology.Clopen
import Mathlib.Topology.Constructions
import Mathlib.Data.PFun
import Mathlib.SetTheory.Cardinal.Arithmetic
import Mathlib.SetTheory.Ordinal.Family
import Mathlib.SetTheory.Cardinal.Pigeonhole
import Definitions.Def_CH_Cohen_Library07
/-
Physical source: Flypitch, Jesse Han and Floris van Doorn (Apache-2.0).
Lean 4 port: Ian Klatzco, with Claude.
Upstream commit ad649f89e9f3107b7e2ea97a58b2eafdfc80b815.
Original notices and source statements are retained.
**Formalization credit:** **Wentao Li (Victor)**, under the Prove2Me account **Victorized**, with assistance from OpenAI Codex.
-/
set_option Elab.async false
set_option maxHeartbeats 2000000
set_option maxRecDepth 8192
/- Source module: Definitions.Flypitch4.LanguageExtension -/
section CohenSource_LanguageExtension
set_option autoImplicit false
/-
Copyright (c) 2019 The Flypitch Project. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Jesse Han, Floris van Doorn
Lean 4 port: Ian Klatzco, Claude
-/
/- Lean 4 port of src/language_extension.lean -/
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency false
set_option backward.isDefEq.respectTransparency.types false
open Set Function
namespace Fol
universe u
/-! ## Language.Lconstants, Language.sum, Language.symbols -/
namespace Language
def symbols (L : Language.{u}) := (Σ l, L.functions l) ⊕ (Σ l, L.relations l)
end Language
variable {L : Language.{u}}
/-! ## symbols_in_term, symbols_in_formula -/
@[simp] def symbols_in_term : ∀ {l}, preterm L l → Set (Language.symbols L)
| _, &_ => ∅
| l, preterm.func f => {Sum.inl ⟨l, f⟩}
| _, preterm.app t₁ t₂ => symbols_in_term t₁ ∪ symbols_in_term t₂
@[simp] def symbols_in_formula : ∀ {l}, @preformula L l → Set (Language.symbols L)
| _, preformula.falsum => ∅
| _, preformula.equal t₁ t₂ => symbols_in_term t₁ ∪ symbols_in_term t₂
| l, preformula.rel R => {Sum.inr ⟨l, R⟩}
| _, preformula.apprel f t => symbols_in_formula f ∪ symbols_in_term t
| _, preformula.imp f₁ f₂ => symbols_in_formula f₁ ∪ symbols_in_formula f₂
| _, preformula.all f => symbols_in_formula f
@[simp] lemma symbols_in_term_lift_at (n m : ℕ) : ∀ {l} (t : preterm L l),
symbols_in_term (t ↑' n # m) = symbols_in_term t
| _, &k => by by_cases h : m ≤ k <;> simp [h]
| _, preterm.func _ => rfl
| _, preterm.app t₁ t₂ => by simp [symbols_in_term_lift_at n m t₁, symbols_in_term_lift_at n m t₂]
@[simp] lemma symbols_in_term_lift (n : ℕ) {l} (t : preterm L l) :
symbols_in_term (t ↑ n) = symbols_in_term t :=
symbols_in_term_lift_at n 0 t
lemma symbols_in_term_subst (s : term L) (n : ℕ) : ∀ {l} (t : preterm L l),
symbols_in_term (subst_term t s n) ⊆ symbols_in_term t ∪ symbols_in_term s
| _, &k => by
rcases Nat.lt_trichotomy k n with h | h | h
· simp [subst_term_var_lt s h]
· subst h; simp [subst_term_var_eq, symbols_in_term_lift_at]
· simp [subst_term_var_gt s h]
| _, preterm.func _ => Set.subset_union_left
| _, preterm.app t₁ t₂ => by
simp only [subst_term_app, symbols_in_term]
intro x hx
rcases hx with h | h
· rcases symbols_in_term_subst s n t₁ h with h' | h'
· exact Or.inl (Or.inl h')
· exact Or.inr h'
· rcases symbols_in_term_subst s n t₂ h with h' | h'
· exact Or.inl (Or.inr h')
· exact Or.inr h'
lemma symbols_in_formula_subst : ∀ {l} (f : @preformula L l) (s : term L) (n : ℕ),
symbols_in_formula (subst_formula f s n) ⊆ symbols_in_formula f ∪ symbols_in_term s
| _, preformula.falsum, _, _ => Set.empty_subset _
| _, preformula.equal t₁ t₂, s, n => by
simp only [subst_formula, symbols_in_formula]
intro x hx
rcases hx with h | h
· rcases symbols_in_term_subst s n t₁ h with h' | h'
· exact Or.inl (Or.inl h')
· exact Or.inr h'
· rcases symbols_in_term_subst s n t₂ h with h' | h'
· exact Or.inl (Or.inr h')
· exact Or.inr h'
| _, preformula.rel _, _, _ => Set.subset_union_left
| _, preformula.apprel f t, s, n => by
simp only [subst_formula, symbols_in_formula]
intro x hx
rcases hx with h | h
· rcases symbols_in_formula_subst f s n h with h' | h'
· exact Or.inl (Or.inl h')
· exact Or.inr h'
· rcases symbols_in_term_subst s n t h with h' | h'
· exact Or.inl (Or.inr h')
· exact Or.inr h'
| _, preformula.imp f₁ f₂, s, n => by
simp only [subst_formula, symbols_in_formula]
intro x hx
rcases hx with h | h
· rcases symbols_in_formula_subst f₁ s n h with h' | h'
· exact Or.inl (Or.inl h')
· exact Or.inr h'
· rcases symbols_in_formula_subst f₂ s n h with h' | h'
· exact Or.inl (Or.inr h')
· exact Or.inr h'
| _, preformula.all f, s, n => by
simp only [subst_formula, symbols_in_formula]
exact symbols_in_formula_subst f s (n + 1)
/-! ## Lhom — language homomorphism -/
structure Lhom (L L' : Language.{u}) where
on_function : ∀ {n}, L.functions n → L'.functions n
on_relation : ∀ {n}, L.relations n → L'.relations n
infix:10 " →ᴸ " => Lhom -- \^L
namespace Lhom
variable {L' : Language.{u}} (ϕ : L →ᴸ L')
protected def id (L : Language.{u}) : L →ᴸ L :=
⟨fun {_} => id, fun {_} => id⟩
@[reducible] def comp {L1 L2 L3 : Language.{u}} (g : L2 →ᴸ L3) (f : L1 →ᴸ L2) : L1 →ᴸ L3 :=
⟨fun {n} => g.on_function ∘ f.on_function (n := n),
fun {n} => g.on_relation ∘ f.on_relation (n := n)⟩
local infixr:60 " ∘ᴸ " => Lhom.comp
lemma Lhom_funext {L1 L2 : Language.{u}} {F G : L1 →ᴸ L2}
(h_fun : @Lhom.on_function _ _ F = @Lhom.on_function _ _ G)
(h_rel : @Lhom.on_relation _ _ F = @Lhom.on_relation _ _ G) : F = G := by
cases F; cases G; simp only at h_fun h_rel; subst h_fun; subst h_rel; rfl
@[simp] lemma id_is_left_identity {L1 L2 : Language.{u}} {F : L1 →ᴸ L2} :
(Lhom.id L2) ∘ᴸ F = F := by cases F; rfl
@[simp] lemma id_is_right_identity {L1 L2 : Language.{u}} {F : L1 →ᴸ L2} :
F ∘ᴸ (Lhom.id L1) = F := by cases F; rfl
structure is_injective : Prop where
on_function {n} : Function.Injective (ϕ.on_function (n := n))
on_relation {n} : Function.Injective (ϕ.on_relation (n := n))
class has_decidable_range : Type u where
on_function {n} : DecidablePred (· ∈ Set.range (ϕ.on_function (n := n)))
on_relation {n} : DecidablePred (· ∈ Set.range (ϕ.on_relation (n := n)))
instance (priority := 100) inst_dec_fn [h : has_decidable_range ϕ] {n} :
DecidablePred (· ∈ Set.range (ϕ.on_function (n := n))) := h.on_function
instance (priority := 100) inst_dec_rel [h : has_decidable_range ϕ] {n} :
DecidablePred (· ∈ Set.range (ϕ.on_relation (n := n))) := h.on_relation
@[simp] def on_symbol : Language.symbols L → Language.symbols L'
| Sum.inl ⟨l, f⟩ => Sum.inl ⟨l, ϕ.on_function f⟩
| Sum.inr ⟨l, R⟩ => Sum.inr ⟨l, ϕ.on_relation R⟩
@[simp] def on_term : ∀ {l}, preterm L l → preterm L' l
| _, &k => &k
| _, preterm.func f => preterm.func (ϕ.on_function f)
| _, preterm.app t₁ t₂ => preterm.app (on_term t₁) (on_term t₂)
@[simp] lemma on_term_lift_at : ∀ {l} (t : preterm L l) (n m : ℕ),
ϕ.on_term (t ↑' n # m) = ϕ.on_term t ↑' n # m
| _, &k, n, m => by simp [lift_term_at]
| _, preterm.func _, _, _ => rfl
| _, preterm.app t₁ t₂, n, m => by
simp only [on_term, lift_term_at, on_term_lift_at]
@[simp] lemma on_term_lift {l} (n : ℕ) (t : preterm L l) :
ϕ.on_term (lift_term t n) = lift_term (ϕ.on_term t) n := by
simp only [lift_term, on_term_lift_at]
@[simp] lemma on_term_subst : ∀ {l} (t : preterm L l) (s : term L) (n : ℕ),
ϕ.on_term (subst_term t s n) = subst_term (ϕ.on_term t) (ϕ.on_term s) n
| _, &k, s, n => by
rcases Nat.lt_trichotomy k n with h | h | h
· simp [subst_term_var_lt _ h]
· subst h
simp [subst_term_var_eq, on_term_lift_at]
· simp [subst_term_var_gt _ h]
| _, preterm.func _, _, _ => rfl
| _, preterm.app t₁ t₂, s, n => by simp [on_term_subst t₁ s n, on_term_subst t₂ s n]
@[simp] lemma on_term_apps : ∀ {l} (t : preterm L l) (ts : DVec (term L) l),
ϕ.on_term (apps t ts) = apps (ϕ.on_term t) (ts.map ϕ.on_term)
| _, _, DVec.nil => rfl
| _, t, DVec.cons t' ts => by
simp only [apps, DVec.map]
exact on_term_apps (preterm.app t t') ts
lemma not_mem_symbols_in_term_on_term {s : Language.symbols L'}
(hs : s ∉ Set.range (ϕ.on_symbol)) : ∀ {l} (t : preterm L l),
s ∉ symbols_in_term (ϕ.on_term t) := by
intro l t
induction t with
| var k => simp [on_term, symbols_in_term, Set.notMem_empty]
| func f => exact fun h' => hs ⟨Sum.inl ⟨_, f⟩, (Set.mem_singleton_iff.mp h').symm⟩
| app t₁ t₂ ih₁ ih₂ =>
simp only [on_term, symbols_in_term, Set.mem_union, not_or]
exact ⟨ih₁, ih₂⟩
@[simp] def on_formula : ∀ {l}, @preformula L l → @preformula L' l
| _, preformula.falsum => preformula.falsum
| _, preformula.equal t₁ t₂ => preformula.equal (ϕ.on_term t₁) (ϕ.on_term t₂)
| _, preformula.rel R => preformula.rel (ϕ.on_relation R)
| _, preformula.apprel f t => preformula.apprel (on_formula f) (ϕ.on_term t)
| _, preformula.imp f₁ f₂ => preformula.imp (on_formula f₁) (on_formula f₂)
| _, preformula.all f => preformula.all (on_formula f)
@[simp] lemma on_formula_lift_at : ∀ {l} (n m : ℕ) (f : @preformula L l),
ϕ.on_formula (f ↑f' n # m) = ϕ.on_formula f ↑f' n # m
| _, _, _, preformula.falsum => rfl
| _, _, _, preformula.equal t₁ t₂ => by simp [on_term_lift_at]
| _, _, _, preformula.rel _ => rfl
| _, _, _, preformula.apprel f t => by simp [on_formula_lift_at, on_term_lift_at]
| _, _, _, preformula.imp f₁ f₂ => by simp [on_formula_lift_at]
| _, _, _, preformula.all f => by simp [on_formula_lift_at]
@[simp] lemma on_formula_lift {l} (n : ℕ) (f : @preformula L l) :
ϕ.on_formula (lift_formula f n) = lift_formula (ϕ.on_formula f) n := by
simp only [lift_formula, on_formula_lift_at]
@[simp] lemma on_formula_subst : ∀ {l} (f : @preformula L l) (s : term L) (n : ℕ),
ϕ.on_formula (f [s // n]f) = (ϕ.on_formula f) [ϕ.on_term s // n]f
| _, preformula.falsum, _, _ => rfl
| _, preformula.equal t₁ t₂, s, n => by simp [on_term_subst]
| _, preformula.rel _, _, _ => rfl
| _, preformula.apprel f t, s, n => by simp [on_formula_subst f s n, on_term_subst]
| _, preformula.imp f₁ f₂, s, n => by simp [on_formula_subst f₁ s n, on_formula_subst f₂ s n]
| _, preformula.all f, s, n => by simp [on_formula_subst f s (n + 1)]
@[simp] lemma on_formula_apps_rel : ∀ {l} (f : @preformula L l) (ts : DVec (term L) l),
ϕ.on_formula (apps_rel f ts) = apps_rel (ϕ.on_formula f) (ts.map ϕ.on_term)
| _, _, DVec.nil => rfl
| _, f, DVec.cons t' ts => by
simp only [apps_rel, DVec.map]
exact on_formula_apps_rel (preformula.apprel f t') ts
lemma not_mem_symbols_in_formula_on_formula {s : Language.symbols L'}
(hs : s ∉ Set.range (ϕ.on_symbol)) : ∀ {l} (f : @preformula L l),
s ∉ symbols_in_formula (ϕ.on_formula f) := by
intro l f
induction f with
| falsum => simp [on_formula, symbols_in_formula, Set.notMem_empty]
| equal t₁ t₂ =>
simp only [on_formula, symbols_in_formula, Set.mem_union, not_or]
exact ⟨ϕ.not_mem_symbols_in_term_on_term hs t₁, ϕ.not_mem_symbols_in_term_on_term hs t₂⟩
| rel R => exact fun h' => hs ⟨Sum.inr ⟨_, R⟩, (Set.mem_singleton_iff.mp h').symm⟩
| apprel f t ihf =>
simp only [on_formula, symbols_in_formula, Set.mem_union, not_or]
exact ⟨ihf, ϕ.not_mem_symbols_in_term_on_term hs t⟩
| imp f₁ f₂ ihf₁ ihf₂ =>
simp only [on_formula, symbols_in_formula, Set.mem_union, not_or]
exact ⟨ihf₁, ihf₂⟩
| all f ihf => exact ihf
lemma not_mem_function_in_formula_on_formula {l'} {f' : L'.functions l'}
(h : f' ∉ Set.range (ϕ.on_function (n := l'))) {l} (f : @preformula L l) :
(Sum.inl ⟨l', f'⟩ : Language.symbols L') ∉ symbols_in_formula (ϕ.on_formula f) := by
apply not_mem_symbols_in_formula_on_formula
intro ⟨s, hs⟩
apply h
match s with
| Sum.inl ⟨m, g⟩ =>
simp only [on_symbol] at hs
have heq : (⟨m, ϕ.on_function g⟩ : Σ l, L'.functions l) = ⟨l', f'⟩ := Sum.inl.inj hs
have hm : m = l' := congrArg Sigma.fst heq
subst hm
exact ⟨g, eq_of_heq (Sigma.mk.inj heq).2⟩
| Sum.inr p =>
simp only [on_symbol] at hs
exact absurd hs (by simp)
/-! ## on_bounded_term, on_bounded_formula -/
@[simp] def on_bounded_term {n} : ∀ {l} (t : bounded_preterm L n l), bounded_preterm L' n l
| _, bounded_preterm.bd_var k => bounded_preterm.bd_var k
| _, bounded_preterm.bd_func f => bounded_preterm.bd_func (ϕ.on_function f)
| _, bounded_preterm.bd_app t s => bounded_preterm.bd_app (on_bounded_term t) (on_bounded_term s)
@[simp] lemma on_bounded_term_fst {n} : ∀ {l} (t : bounded_preterm L n l),
(ϕ.on_bounded_term t).fst = ϕ.on_term t.fst
| _, bounded_preterm.bd_var _ => rfl
| _, bounded_preterm.bd_func _ => rfl
| _, bounded_preterm.bd_app t s => by simp [on_bounded_term_fst t, on_bounded_term_fst s]
@[simp] def on_bounded_formula : ∀ {n l} (f : bounded_preformula L n l), bounded_preformula L' n l
| _, _, bd_falsum => bd_falsum
| _, _, bd_equal t₁ t₂ => bd_equal (ϕ.on_bounded_term t₁) (ϕ.on_bounded_term t₂)
| _, _, bd_rel R => bd_rel (ϕ.on_relation R)
| _, _, bd_apprel f t => bd_apprel (on_bounded_formula f) (ϕ.on_bounded_term t)
| _, _, bd_imp f₁ f₂ => bd_imp (on_bounded_formula f₁) (on_bounded_formula f₂)
| _, _, bd_all f => bd_all (on_bounded_formula f)
@[simp] lemma on_bounded_formula_fst : ∀ {n l} (f : bounded_preformula L n l),
(ϕ.on_bounded_formula f).fst = ϕ.on_formula f.fst
| _, _, bd_falsum => rfl
| _, _, bd_equal t₁ t₂ => by simp [on_bounded_term_fst]
| _, _, bd_rel _ => rfl
| _, _, bd_apprel f t => by simp [on_bounded_formula_fst f, on_bounded_term_fst]
| _, _, bd_imp f₁ f₂ => by simp [on_bounded_formula_fst f₁, on_bounded_formula_fst f₂]
| _, _, bd_all f => by simp [on_bounded_formula_fst f]
/-! ## Functoriality lemmas -/
@[simp] lemma comp_on_term {L1 L2 L3 : Language.{u}} {l : ℕ} (g : L2 →ᴸ L3) (f : L1 →ᴸ L2) :
@on_term L1 L3 (g.comp f) l = Function.comp (@on_term L2 L3 g l) (@on_term L1 L2 f l) := by
funext x
induction x with
| var k => rfl
| func ff => rfl
| app t₁ t₂ ih₁ ih₂ =>
simp only [on_term, Function.comp]
exact congrArg₂ preterm.app ih₁ ih₂
@[simp] lemma comp_on_formula {L1 L2 L3 : Language.{u}} {l : ℕ} (g : L2 →ᴸ L3) (f : L1 →ᴸ L2) :
@on_formula L1 L3 (g.comp f) l = Function.comp (@on_formula L2 L3 g l) (@on_formula L1 L2 f l) := by
funext x
induction x with
| falsum => rfl
| equal t₁ t₂ => simp [on_formula, comp_on_term]
| rel R => rfl
| apprel f t ihf =>
simp only [on_formula, Function.comp]
exact congrArg₂ preformula.apprel ihf (by simp [comp_on_term])
| imp f₁ f₂ ihf₁ ihf₂ =>
simp only [on_formula, Function.comp]
exact congrArg₂ preformula.imp ihf₁ ihf₂
| all f ihf =>
simp only [on_formula, Function.comp]
exact congrArg preformula.all ihf
@[simp] lemma comp_on_bounded_term {L1 L2 L3 : Language.{u}} {n l : ℕ}
(g : L2 →ᴸ L3) (f : L1 →ᴸ L2) :
@on_bounded_term L1 L3 (g.comp f) n l =
Function.comp (@on_bounded_term L2 L3 g n l) (@on_bounded_term L1 L2 f n l) := by
funext x
induction x with
| bd_var k => rfl
| bd_func ff => rfl
| bd_app t s iht ihs =>
simp only [on_bounded_term, Function.comp]
exact congrArg₂ bounded_preterm.bd_app iht ihs
@[simp] lemma comp_on_bounded_formula {L1 L2 L3 : Language.{u}} {n l : ℕ}
(g : L2 →ᴸ L3) (f : L1 →ᴸ L2) :
@on_bounded_formula L1 L3 (g.comp f) n l =
Function.comp (@on_bounded_formula L2 L3 g n l) (@on_bounded_formula L1 L2 f n l) := by
funext x
apply bounded_preformula.eq
simp [on_bounded_formula_fst, comp_on_formula]
@[simp] def on_closed_term (t : closed_term L) : closed_term L' := ϕ.on_bounded_term t
@[simp] def on_sentence (f : sentence L) : sentence L' := ϕ.on_bounded_formula f
def on_sentence_fst (f : sentence L) : (ϕ.on_sentence f).fst = ϕ.on_formula f.fst :=
ϕ.on_bounded_formula_fst f
/-! ## on_prf — Lhom lifts proofs -/
noncomputable def on_prf {Γ : Set (formula L)} {f : formula L} (h : Γ ⊢ f) :
ϕ.on_formula '' Γ ⊢ ϕ.on_formula f := by
induction h with
| axm hΓ => exact prf.axm (Set.mem_image_of_mem _ hΓ)
| impI _ ih =>
apply prf.impI
rw [← Set.image_insert_eq]
exact ih
| impE A _ _ ih₁ ih₂ => exact prf.impE _ ih₁ ih₂
| falsumE _ ih =>
apply prf.falsumE
rw [Set.image_insert_eq] at ih
exact ih
| allI _ ih =>
simp only [on_formula]
apply prf.allI
rw [Set.image_image] at ih ⊢
have key : ∀ g : formula L, ϕ.on_formula (lift_formula1 g) = lift_formula1 (ϕ.on_formula g) :=
fun g => by simp only [lift_formula1, on_formula_lift_at]
simp_rw [key] at ih
exact ih
| allE₂ A t _ ih =>
have heq : ϕ.on_formula (A [t // 0]f) = (ϕ.on_formula A) [ϕ.on_term t // 0]f := by
simp [on_formula_subst]
rw [heq]
exact prf.allE₂ _ _ ih
| ref _ _ => exact prf.ref _ _
| subst₂ s t f₁ _ _ ih₁ ih₂ =>
have heq1 : ϕ.on_formula (f₁ [s // 0]f) = (ϕ.on_formula f₁) [ϕ.on_term s // 0]f := by
simp [on_formula_subst]
have heq2 : ϕ.on_formula (f₁ [t // 0]f) = (ϕ.on_formula f₁) [ϕ.on_term t // 0]f := by
simp [on_formula_subst]
rw [heq2]
rw [heq1] at ih₂
exact prf.subst₂ _ _ _ ih₁ ih₂
noncomputable def on_sprf {Γ : SentTheory L} {f : sentence L} (h : Γ ⊢ₛ f) :
(ϕ.on_sentence '' Γ) ⊢ₛ ϕ.on_sentence f := by
have := ϕ.on_prf h
simp only [SentTheory.sprf, SentTheory.fst, Set.image_image, Function.comp,
on_bounded_formula_fst, on_sentence] at this ⊢
exact this
/-! ## reflect_term -/
noncomputable def reflect_term [has_decidable_range ϕ] (t : term L') (m : ℕ) : term L :=
term.elim (fun k => lift_term_at (&k) 1 m)
(fun {l} f' _ts' ts =>
if hf' : f' ∈ Set.range (ϕ.on_function (n := l))
then apps (preterm.func (Classical.choose hf')) ts
else &m) t
variable {ϕ}
lemma reflect_term_apps_pos [has_decidable_range ϕ] {l} {f : L'.functions l}
(hf : f ∈ Set.range (ϕ.on_function (n := l))) (ts : DVec (term L') l) (m : ℕ) :
ϕ.reflect_term (apps (preterm.func f) ts) m =
apps (preterm.func (Classical.choose hf)) (ts.map (fun t => ϕ.reflect_term t m)) :=
(term.elim_apps _ _ f ts).trans (by rw [dif_pos hf]; rfl)
lemma reflect_term_apps_neg [has_decidable_range ϕ] {l} {f : L'.functions l}
(hf : f ∉ Set.range (ϕ.on_function (n := l))) (ts : DVec (term L') l) (m : ℕ) :
ϕ.reflect_term (apps (preterm.func f) ts) m = &m :=
(term.elim_apps _ _ f ts).trans (by rw [dif_neg hf])
lemma reflect_term_const_neg [has_decidable_range ϕ] {c : L'.constants}
(hf : c ∉ Set.range (ϕ.on_function (n := 0))) (m : ℕ) :
ϕ.reflect_term (preterm.func c) m = &m :=
reflect_term_apps_neg hf DVec.nil m
@[simp] lemma reflect_term_var [has_decidable_range ϕ] (k m : ℕ) :
ϕ.reflect_term (&k) m = &k ↑' 1 # m := rfl
@[simp] lemma reflect_term_on_term [has_decidable_range ϕ] (hϕ : is_injective ϕ) (t : term L)
(m : ℕ) : ϕ.reflect_term (ϕ.on_term t) m = t ↑' 1 # m := by
refine @term.rec L (fun t => ϕ.reflect_term (ϕ.on_term t) m = t ↑' 1 # m)
(fun k => ?_) (fun f ts ih_ts => ?_) t
· -- var k: reflect_term (&k) m = &k ↑' 1 # m
simp [reflect_term_var, lift_term_at]
· -- func f applied to ts: reflect_term (on_term (apps (func f) ts)) m = (apps (func f) ts) ↑' 1 # m
have hf : ϕ.on_function f ∈ Set.range (ϕ.on_function) := Set.mem_range_self f
simp only [on_term_apps, on_term,
reflect_term_apps_pos hf, lift_term_at_apps]
congr 1
· -- preterm.func (Classical.choose hf) = preterm.func f (modulo lift which is identity on func)
simp only [lift_term_at]
exact congrArg preterm.func (hϕ.on_function (Classical.choose_spec hf))
· -- DVec.map (fun t => reflect_term t m) (DVec.map on_term ts) = DVec.map (· ↑' 1 # m) ts
rw [DVec.map_map]
apply DVec.map_congr_pmem
intro t hmem
exact ih_ts t hmem
lemma reflect_term_lift_at [has_decidable_range ϕ] (hϕ : is_injective ϕ) {n m m' : ℕ}
(h : m ≤ m') (t : term L') :
ϕ.reflect_term (t ↑' n # m) (m' + n) = ϕ.reflect_term t m' ↑' n # m := by
refine @term.rec L' (fun t => ϕ.reflect_term (t ↑' n # m) (m' + n) = ϕ.reflect_term t m' ↑' n # m)
(fun k => ?_) (fun f ts ih_ts => ?_) t
· -- var k: ((&k) ↑' n # m) reflected at (m'+n) = reflected (&k) at m' lifted n at m
simp only [reflect_term_var, lift_term_at]
split_ifs <;> simp_all [lift_term_at] <;> omega
· -- func f applied to ts: by_cases on f ∈ range
by_cases hf : f ∈ Set.range ϕ.on_function
· simp only [lift_term_at_apps, reflect_term_apps_pos hf, lift_term_at, DVec.map_map,
Function.comp]
congr 1
apply DVec.map_congr_pmem
intro t hmem; exact ih_ts t hmem
· show ϕ.reflect_term ((apps (preterm.func f) ts) ↑' n # m) (m' + n) =
ϕ.reflect_term (apps (preterm.func f) ts) m' ↑' n # m
simp only [lift_term_at_apps, lift_term_at, reflect_term_apps_neg hf, reflect_term_var, h,
ite_true]
lemma reflect_term_lift [has_decidable_range ϕ] (hϕ : is_injective ϕ) {n m : ℕ}
(t : term L') :
ϕ.reflect_term (lift_term t n) (m + n) = lift_term (ϕ.reflect_term t m) n :=
reflect_term_lift_at hϕ (Nat.zero_le m) t
lemma reflect_term_subst [has_decidable_range ϕ] (hϕ : is_injective ϕ) (n m : ℕ)
(s t : term L') :
ϕ.reflect_term (subst_term t s n) (m + n) =
subst_term (ϕ.reflect_term t (m + n + 1)) (ϕ.reflect_term s m) n := by
induction t using @term.rec L' with
| hvar k =>
show ϕ.reflect_term (subst_term (&k) s n) (m + n) =
subst_term (ϕ.reflect_term (&k) (m + n + 1)) (ϕ.reflect_term s m) n
rcases Nat.lt_trichotomy k n with hk | hk | hk
· -- k < n
simp only [subst_term_var_lt s hk, reflect_term_var, lift_term_at,
if_neg (by omega : ¬(m + n ≤ k)),
if_neg (by omega : ¬(m + n + 1 ≤ k)),
subst_term_var_lt _ hk]
· -- k = n: reflect_term (s ↑' n # 0) (m+n) = subst_term (&n ↑' 1 # (m+n+1)) (reflect_term s m) n
simp only [hk, subst_term_var_eq, reflect_term_var,
lift_term_at, if_neg (by omega : ¬(m + n + 1 ≤ n)),
subst_term_var_eq, lift_term]
exact reflect_term_lift hϕ s
· -- k > n
have hk1 : 1 ≤ k := Nat.one_le_of_lt hk
by_cases h₂' : m + n + 1 ≤ k
· -- k ≥ m+n+1: both sides = &k
simp only [subst_term_var_gt s hk, reflect_term_var, lift_term_at, h₂', ite_true,
if_pos (by omega : m + n ≤ k - 1),
subst_term_var_gt _ (by omega : n < k - 1 + 1),
Nat.sub_add_cancel hk1,
subst_term_var_gt _ (by omega : n < k + 1),
show k + 1 - 1 = k from by omega]
· -- n < k < m+n+1: both sides = &(k-1)
simp only [subst_term_var_gt s hk, reflect_term_var, lift_term_at,
if_neg (by omega : ¬(m + n ≤ k - 1)),
if_neg h₂', subst_term_var_gt _ hk]
| hfunc f ts ih_ts =>
show ϕ.reflect_term (subst_term (apps (preterm.func f) ts) s n) (m + n) =
subst_term (ϕ.reflect_term (apps (preterm.func f) ts) (m + n + 1)) (ϕ.reflect_term s m) n
have hn : n < m + n + 1 := by omega
by_cases hf : f ∈ Set.range ϕ.on_function
· simp only [subst_term_apps, reflect_term_apps_pos hf, subst_term_func, subst_term_apps,
DVec.map_map, Function.comp]
exact congrArg (apps (preterm.func _))
(DVec.map_congr_pmem (fun t hmem => ih_ts t hmem))
· simp only [subst_term_apps, subst_term_func, reflect_term_apps_neg hf, reflect_term_var,
subst_term_var_gt _ hn, show m + n + 1 - 1 = m + n from by omega]
variable (ϕ)
/-! ## reflect_formula -/
-- reflect_formula auxiliary: builds ℕ → formula L from formula L'
-- using C = fun _ => ℕ → formula L in formula.rec
noncomputable def reflect_formula_aux' [has_decidable_range ϕ] (f : formula L') :
ℕ → formula L :=
(formula.rec (C := fun _ => ℕ → formula L)
(fun _ => ⊥')
(fun t₁ t₂ m' => ϕ.reflect_term t₁ m' ≃ ϕ.reflect_term t₂ m')
(fun {l} R ts m' =>
if hR : R ∈ Set.range (ϕ.on_relation (n := l))
then apps_rel (preformula.rel (Classical.choose hR))
(DVec.map (fun t => ϕ.reflect_term t m') ts)
else ⊥')
(fun {_f₁} {_f₂} (ih₁ : ℕ → formula L) (ih₂ : ℕ → formula L) (m' : ℕ) => (ih₁ m') ⟹ (ih₂ m'))
(fun {_f} (ih : ℕ → formula L) (m' : ℕ) => ∀' (ih (m' + 1)))
f : ℕ → formula L)
noncomputable def reflect_formula [has_decidable_range ϕ] (m : ℕ) (f : formula L') : formula L :=
@reflect_formula_aux' L L' ϕ _ f m
variable {ϕ}
lemma reflect_formula_apps_rel_pos [has_decidable_range ϕ] {l} {R : L'.relations l}
(hR : R ∈ Set.range (ϕ.on_relation (n := l))) (ts : DVec (term L') l) (m : ℕ) :
ϕ.reflect_formula m (apps_rel (preformula.rel R) ts) =
apps_rel (preformula.rel (Classical.choose hR)) (ts.map (fun t => ϕ.reflect_term t m)) := by
simp only [reflect_formula, reflect_formula_aux', formula.rec_apps_rel, dif_pos hR]
lemma reflect_formula_apps_rel_neg [has_decidable_range ϕ] {l} {R : L'.relations l}
(hR : R ∉ Set.range (ϕ.on_relation (n := l))) (ts : DVec (term L') l) (m : ℕ) :
ϕ.reflect_formula m (apps_rel (preformula.rel R) ts) = ⊥' := by
simp only [reflect_formula, reflect_formula_aux', formula.rec_apps_rel, dif_neg hR]
@[simp] lemma reflect_formula_equal [has_decidable_range ϕ] (t₁ t₂ : term L') (m : ℕ) :
ϕ.reflect_formula m (t₁ ≃ t₂) = ϕ.reflect_term t₁ m ≃ ϕ.reflect_term t₂ m := by
simp only [reflect_formula, preformula.equal]
rfl
@[simp] lemma reflect_formula_imp [has_decidable_range ϕ] (f₁ f₂ : formula L') (m : ℕ) :
ϕ.reflect_formula m (f₁ ⟹ f₂) = ϕ.reflect_formula m f₁ ⟹ ϕ.reflect_formula m f₂ := by
simp only [reflect_formula, preformula.imp]
rfl
@[simp] lemma reflect_formula_all [has_decidable_range ϕ] (f : formula L') (m : ℕ) :
ϕ.reflect_formula m (∀' f) = ∀' (ϕ.reflect_formula (m + 1) f) := by
simp only [reflect_formula, preformula.all]
rfl
@[simp] lemma reflect_formula_on_formula [has_decidable_range ϕ] (hϕ : is_injective ϕ) (m : ℕ)
(f : formula L) : ϕ.reflect_formula m (ϕ.on_formula f) = f ↑f' 1 # m := by
refine @formula.rec L (fun f => ∀ m, ϕ.reflect_formula m (ϕ.on_formula f) = f ↑f' 1 # m)
?_ ?_ ?_ ?_ ?_ f m
· intro m; rfl
· intro t₁ t₂ m
simp only [on_formula, reflect_formula_equal, lift_formula_at, reflect_term_on_term hϕ]
· intro l R ts m
have hR : ϕ.on_relation R ∈ Set.range ϕ.on_relation := Set.mem_range_self _
simp only [on_formula_apps_rel, on_formula,
reflect_formula_apps_rel_pos hR, lift_formula_at_apps_rel]
congr 1
· simp only [lift_formula_at]
exact congrArg preformula.rel (hϕ.on_relation (Classical.choose_spec hR))
· rw [DVec.map_map]
apply DVec.map_congr_pmem
intro t _
exact reflect_term_on_term hϕ t m
· intro f₁ f₂ ih₁ ih₂ m
simp only [on_formula, reflect_formula_imp, lift_formula_at, ih₁ m, ih₂ m]
· intro f ih m
simp only [on_formula, reflect_formula_all, lift_formula_at, ih (m + 1)]
lemma reflect_formula_lift_at [has_decidable_range ϕ] (hϕ : is_injective ϕ) {n m m' : ℕ}
(h : m ≤ m') (f : formula L') :
ϕ.reflect_formula (m' + n) (f ↑f' n # m) = ϕ.reflect_formula m' f ↑f' n # m := by
refine @formula.rec L'
(fun f => ∀ m m', m ≤ m' →
ϕ.reflect_formula (m' + n) (f ↑f' n # m) = ϕ.reflect_formula m' f ↑f' n # m)
?_ ?_ ?_ ?_ ?_ f m m' h
· intro m m' _; rfl
· intro t₁ t₂ m m' h'
simp only [lift_formula_at, reflect_formula_equal, reflect_term_lift_at hϕ h']
· intro l R ts m m' h'
by_cases hR : R ∈ Set.range (ϕ.on_relation (n := l))
· show ϕ.reflect_formula (m' + n) ((apps_rel (preformula.rel R) ts) ↑f' n # m) =
ϕ.reflect_formula m' (apps_rel (preformula.rel R) ts) ↑f' n # m
simp only [lift_formula_at_apps_rel, lift_formula_at, reflect_formula_apps_rel_pos hR,
lift_formula_at_apps_rel, DVec.map_map, Function.comp]
congr 1
apply DVec.map_congr_pmem
intro t _; exact reflect_term_lift_at hϕ h' t
· show ϕ.reflect_formula (m' + n) ((apps_rel (preformula.rel R) ts) ↑f' n # m) =
ϕ.reflect_formula m' (apps_rel (preformula.rel R) ts) ↑f' n # m
simp only [lift_formula_at_apps_rel, lift_formula_at, reflect_formula_apps_rel_neg hR]
· intro f₁ f₂ ih₁ ih₂ m m' h'
simp only [lift_formula_at, reflect_formula_imp, ih₁ m m' h', ih₂ m m' h']
· intro f ih m m' h'
simp only [lift_formula_at, reflect_formula_all]
rw [show m' + n + 1 = (m' + 1) + n from by omega,
ih (m + 1) (m' + 1) (Nat.add_le_add_right h' 1)]
lemma reflect_formula_lift [has_decidable_range ϕ] (hϕ : is_injective ϕ) (n m : ℕ)
(f : formula L') : ϕ.reflect_formula (m + n) (f ↑f n) = ϕ.reflect_formula m f ↑f n :=
reflect_formula_lift_at hϕ (Nat.zero_le m) f
lemma reflect_formula_lift1 [has_decidable_range ϕ] (hϕ : is_injective ϕ) (m : ℕ)
(f : formula L') : ϕ.reflect_formula (m + 1) (f ↑f 1) = ϕ.reflect_formula m f ↑f 1 :=
reflect_formula_lift hϕ 1 m f
lemma reflect_formula_subst [has_decidable_range ϕ] (hϕ : is_injective ϕ) (f : formula L')
(n m : ℕ) (s : term L') :
ϕ.reflect_formula (m + n) (f [s // n]f) =
(ϕ.reflect_formula (m + n + 1) f) [ϕ.reflect_term s m // n]f := by
refine @formula.rec L'
(fun f => ∀ n, ϕ.reflect_formula (m + n) (f [s // n]f) =
(ϕ.reflect_formula (m + n + 1) f) [ϕ.reflect_term s m // n]f)
?_ ?_ ?_ ?_ ?_ f n
· intro n; rfl
· intro t₁ t₂ n'
simp only [subst_formula, reflect_formula_equal, reflect_term_subst hϕ]
· intro l R ts n'
by_cases hR : R ∈ Set.range (ϕ.on_relation (n := l))
· show ϕ.reflect_formula (m + n') ((apps_rel (preformula.rel R) ts) [s // n']f) =
(ϕ.reflect_formula (m + n' + 1) (apps_rel (preformula.rel R) ts)) [ϕ.reflect_term s m // n']f
simp only [subst_formula_apps_rel, subst_formula, reflect_formula_apps_rel_pos hR,
subst_formula_apps_rel, DVec.map_map, Function.comp]
congr 1
exact DVec.map_congr_pmem (fun t _ => reflect_term_subst hϕ n' m s t)
· show ϕ.reflect_formula (m + n') ((apps_rel (preformula.rel R) ts) [s // n']f) =
(ϕ.reflect_formula (m + n' + 1) (apps_rel (preformula.rel R) ts)) [ϕ.reflect_term s m // n']f
simp only [subst_formula_apps_rel, reflect_formula_apps_rel_neg hR, subst_formula]
· intro f₁ f₂ ih₁ ih₂ n'
simp only [subst_formula, reflect_formula_imp, ih₁ n', ih₂ n']
· intro f ih n'
simp only [subst_formula, reflect_formula_all]
rw [show m + n' + 1 = m + (n' + 1) from by omega]
exact congrArg preformula.all (ih (n' + 1))
@[simp] lemma reflect_formula_subst0 [has_decidable_range ϕ] (hϕ : is_injective ϕ) (m : ℕ)
(f : formula L') (s : term L') :
ϕ.reflect_formula m (f [s // 0]f) =
(ϕ.reflect_formula (m + 1) f) [ϕ.reflect_term s m // 0]f :=
reflect_formula_subst hϕ f 0 m s
/-! ## reflect_prf_gen -/
noncomputable def reflect_prf_gen [has_decidable_range ϕ] (hϕ : is_injective ϕ) {Γ}
{f : formula L'} (m : ℕ) (H : Γ ⊢ f) :
(fun g => ϕ.reflect_formula m g) '' Γ ⊢ ϕ.reflect_formula m f := by
induction H generalizing m with
| axm hΓ => exact prf.axm (Set.mem_image_of_mem _ hΓ)
| impI _ ih =>
apply prf.impI
have h := ih m
rw [Set.image_insert_eq] at h
exact h
| impE A _ _ ih₁ ih₂ => exact prf.impE _ (ih₁ m) (ih₂ m)
| falsumE _ ih =>
apply prf.falsumE
have h := ih m
rw [Set.image_insert_eq] at h
exact h
| allI _ ih =>
apply prf.allI
rw [Set.image_image]
have h := ih (m + 1)
rw [Set.image_image] at h
-- Need: lift_formula1 ∘ (fun g => ϕ.reflect_formula m g) = (fun g => ϕ.reflect_formula (m+1) g) ∘ lift_formula1
-- i.e., lift_formula1 (ϕ.reflect_formula m g) = ϕ.reflect_formula (m+1) (lift_formula1 g)
-- which is reflect_formula_lift1 hϕ m g
have key : ∀ g : formula L', ϕ.reflect_formula (m + 1) (lift_formula1 g) =
lift_formula1 (ϕ.reflect_formula m g) :=
fun g => reflect_formula_lift1 hϕ m g
simp_rw [key] at h
exact h
| allE₂ A t _ ih =>
have h := ih m
rw [reflect_formula_all] at h
rw [reflect_formula_subst0 hϕ]
exact prf.allE₂ _ _ h
| ref _ _ => exact prf.ref _ _
| subst₂ s t f₁ _ _ ih₁ ih₂ =>
have h₁ := ih₁ m
simp only [reflect_formula_equal] at h₁
have h₂ := ih₂ m
rw [reflect_formula_subst0 hϕ] at h₂
rw [reflect_formula_subst0 hϕ]
exact prf.subst₂ _ _ _ h₁ h₂
/-! ## filter_symbols -/
section
@[reducible] def filter_symbols (p : Language.symbols L → Prop) : Language.{u} :=
⟨fun l => {f // p (Sum.inl ⟨l, f⟩)}, fun l => {R // p (Sum.inr ⟨l, R⟩)}⟩
def filter_symbols_Lhom (p : Language.symbols L → Prop) : filter_symbols p →ᴸ L :=
⟨fun {_} => Subtype.val, fun {_} => Subtype.val⟩
def is_injective_filter_symbols_Lhom (p : Language.symbols L → Prop) :
is_injective (filter_symbols_Lhom p) :=
⟨fun {_} => Subtype.val_injective, fun {_} => Subtype.val_injective⟩
noncomputable def find_term_filter_symbols (p : Language.symbols L → Prop) :
∀ {l} (t : preterm L l) (_h : symbols_in_term t ⊆ {s | p s}),
{t' : preterm (filter_symbols p) l // (filter_symbols_Lhom p).on_term t' = t}
| _, &k, _h => ⟨&k, rfl⟩
| _, preterm.func f, h => ⟨preterm.func ⟨f, h (Set.mem_singleton _)⟩, rfl⟩
| _, preterm.app t₁ t₂, h => by
have ih₁ := find_term_filter_symbols p t₁ (Set.Subset.trans Set.subset_union_left h)
have ih₂ := find_term_filter_symbols p t₂ (Set.Subset.trans Set.subset_union_right h)
exact ⟨preterm.app ih₁.1 ih₂.1, by
simp only [on_term]
exact congrArg₂ preterm.app ih₁.2 ih₂.2⟩
noncomputable def find_formula_filter_symbols (p : Language.symbols L → Prop) :
∀ {l} (f : @preformula L l) (_h : symbols_in_formula f ⊆ {s | p s}),
{f' : @preformula (filter_symbols p) l // (filter_symbols_Lhom p).on_formula f' = f}
| _, preformula.falsum, _ => ⟨preformula.falsum, rfl⟩
| _, preformula.equal t₁ t₂, h => by
have ih₁ := find_term_filter_symbols p t₁ (Set.Subset.trans Set.subset_union_left h)
have ih₂ := find_term_filter_symbols p t₂ (Set.Subset.trans Set.subset_union_right h)
exact ⟨preformula.equal ih₁.1 ih₂.1, by
simp only [on_formula]; exact congrArg₂ preformula.equal ih₁.2 ih₂.2⟩
| _, preformula.rel R, h =>
⟨preformula.rel ⟨R, h (Set.mem_singleton _)⟩, rfl⟩
| _, preformula.apprel f t, h => by
have ih₁ := find_formula_filter_symbols p f (Set.Subset.trans Set.subset_union_left h)
have ih₂ := find_term_filter_symbols p t (Set.Subset.trans Set.subset_union_right h)
exact ⟨preformula.apprel ih₁.1 ih₂.1, by
simp only [on_formula]; exact congrArg₂ preformula.apprel ih₁.2 ih₂.2⟩
| _, preformula.imp f₁ f₂, h => by
have ih₁ := find_formula_filter_symbols p f₁ (Set.Subset.trans Set.subset_union_left h)
have ih₂ := find_formula_filter_symbols p f₂ (Set.Subset.trans Set.subset_union_right h)
exact ⟨preformula.imp ih₁.1 ih₂.1, by
simp only [on_formula]; exact congrArg₂ preformula.imp ih₁.2 ih₂.2⟩
| _, preformula.all f, h => by
have ih := find_formula_filter_symbols p f h
exact ⟨preformula.all ih.1, by simp only [on_formula]; exact congrArg preformula.all ih.2⟩
end
/-! ## generalize_constant -/
noncomputable def generalize_constant {Γ : Set (formula L)} (c : L.constants)
(hΓ : (Sum.inl ⟨0, c⟩ : Language.symbols L) ∉ ⋃₀ (symbols_in_formula '' Γ))
{f : formula L} (hf : (Sum.inl ⟨0, c⟩ : Language.symbols L) ∉ symbols_in_formula f)
(H : Γ ⊢ f [preterm.func c // 0]f) : Γ ⊢ ∀' f := by
apply prf.allI
-- Filter morphism that removes c from the language
let p : Language.symbols L → Prop := (· ≠ Sum.inl ⟨0, c⟩)
let ψ : filter_symbols p →ᴸ L := filter_symbols_Lhom p
have hψ : is_injective ψ := is_injective_filter_symbols_Lhom p
haveI : has_decidable_range ψ :=
⟨fun {_} _f => Classical.propDecidable _, fun {_} _R => Classical.propDecidable _⟩
-- c is not in the range of ψ.on_function (since filter language excludes it)
have hc : c ∉ Set.range (ψ.on_function (n := 0)) := by
rintro ⟨c', hc'⟩
-- c'.val = c, but c'.2 says Sum.inl ⟨0, c'.val⟩ ≠ Sum.inl ⟨0, c⟩
exact c'.2 (congrArg (Sum.inl ∘ Sigma.mk 0) hc')
-- f lifts back to the filtered language
have hf' : symbols_in_formula f ⊆ {s | p s} := by
intro s hs hps; subst hps; exact hf hs
obtain ⟨f₀, hf₀⟩ := find_formula_filter_symbols p f hf'
-- Rename: now f = ψ.on_formula f₀
subst hf₀
-- Find filtered preimage of Γ
-- Each formula in Γ lifts to filter language (c not in symbols)
have hΓ_lift : ∀ f' ∈ Γ, ∃ f₁ : formula (filter_symbols p), ψ.on_formula f₁ = f' := by
intro f' hf'mem
have hf'sym : symbols_in_formula f' ⊆ {s | p s} := by
intro s hs hps; subst hps; exact hΓ ⟨_, Set.mem_image_of_mem _ hf'mem, hs⟩
exact ⟨(find_formula_filter_symbols p f' hf'sym).1, (find_formula_filter_symbols p f' hf'sym).2⟩
-- Build Γ₀ as preimage of Γ under ψ.on_formula
let Γ₀ := ψ.on_formula ⁻¹' Γ
have hΓ₀ : ψ.on_formula '' Γ₀ = Γ :=
image_preimage_eq_of_subset_image (fun f' hf' => by
obtain ⟨f₁, hf₁⟩ := hΓ_lift f' hf'
exact ⟨f₁, show ψ.on_formula f₁ ∈ Γ by rw [hf₁]; exact hf', hf₁⟩)
-- Rewrite goal: lift_formula1 '' Γ ⊢ ψ.on_formula f₀
-- as ψ.on_formula '' (lift_formula1 '' Γ₀) ⊢ ψ.on_formula f₀
have comm : ∀ (g : formula (filter_symbols p)),
lift_formula1 (ψ.on_formula g) = ψ.on_formula (lift_formula1 g) :=
fun g => by simp [lift_formula1, on_formula_lift_at]
conv_lhs => rw [← hΓ₀]
rw [Set.image_image, Set.image_congr' comm, ← Set.image_image]
-- Apply ψ.on_prf: suffices lift_formula1 '' Γ₀ ⊢ f₀
apply ψ.on_prf
-- Use reflect_prf_gen to reflect H back to filtered language
-- H : ψ.on_formula '' Γ₀ ⊢ (ψ.on_formula f₀) [preterm.func c // 0]
have H' : ψ.on_formula '' Γ₀ ⊢ (ψ.on_formula f₀) [preterm.func c // 0]f := by
rwa [hΓ₀]
have step := reflect_prf_gen hψ 0 H'
-- Simplify the LHS: (reflect_formula 0 ∘ ψ.on_formula) '' Γ₀ = lift_formula1 '' Γ₀
-- via reflect_formula_on_formula hψ 0: reflect_formula 0 (ψ.on_formula g) = g ↑f' 1 # 0
-- Simplify the RHS via reflect_formula_subst0, reflect_term_const_neg, reflect_formula_on_formula, lift_subst_formula_cancel
rw [Set.image_image] at step
simp only [reflect_formula_on_formula hψ 0] at step
rw [reflect_formula_subst0 hψ] at step
rw [reflect_term_const_neg hc, reflect_formula_on_formula hψ 1, lift_subst_formula_cancel] at step
exact step
noncomputable def sgeneralize_constant {T : SentTheory L} (c : L.constants)
(hΓ : (Sum.inl ⟨0, c⟩ : Language.symbols L) ∉ ⋃₀ (symbols_in_formula '' T.fst))
{f : bounded_formula L 1} (hf : (Sum.inl ⟨0, c⟩ : Language.symbols L) ∉ symbols_in_formula f.fst)
(H : T ⊢ₛ subst0_bounded_formula f (bd_const c)) : T ⊢ₛ bd_all f := by
simp only [SentTheory.sprf, SentTheory.fst] at H ⊢
simp only [subst0_bounded_formula_fst, subst_formula, bd_const] at H
exact generalize_constant c hΓ hf H
/-! ## reflect_prf -/
noncomputable def reflect_prf {Γ : Set (formula L)} {f : formula L} (hϕ : ϕ.is_injective)
(h : ϕ.on_formula '' Γ ⊢ ϕ.on_formula f) : Γ ⊢ f := by
haveI : has_decidable_range ϕ :=
⟨fun {l} _f => Classical.propDecidable _, fun {l} _R => Classical.propDecidable _⟩
apply reflect_prf_lift1
have := reflect_prf_gen hϕ 0 h
simp only [Set.image_image, reflect_formula_on_formula hϕ 0] at this
exact this
noncomputable def reflect_sprf {Γ : SentTheory L} {f : sentence L} (hϕ : ϕ.is_injective)
(h : (ϕ.on_sentence '' Γ) ⊢ₛ ϕ.on_sentence f) : Γ ⊢ₛ f := by
apply reflect_prf hϕ
simp only [SentTheory.sprf, SentTheory.fst, Set.image_image, Function.comp,
on_bounded_formula_fst, on_sentence] at h ⊢
exact h
/-! ## Injectivity of on_term / on_formula -/
lemma on_term_inj (h : ϕ.is_injective) {l} :
Function.Injective (ϕ.on_term : preterm L l → preterm L' l) := by
intro x y hxy
induction x with
| var k =>
cases y with
| var k' => simp [on_term] at hxy; exact congrArg preterm.var hxy
| func _ => simp [on_term] at hxy
| app _ _ => simp [on_term] at hxy
| func f =>
cases y with
| var _ => simp [on_term] at hxy
| func f' => simp [on_term] at hxy; exact congrArg preterm.func (h.on_function hxy)
| app _ _ => simp [on_term] at hxy
| app t₁ t₂ iht₁ iht₂ =>
cases y with
| var _ => simp [on_term] at hxy
| func _ => simp [on_term] at hxy
| app t₁' t₂' =>
simp [on_term] at hxy
exact congrArg₂ preterm.app (iht₁ hxy.1) (iht₂ hxy.2)
lemma on_formula_inj (h : ϕ.is_injective) {l} :
Function.Injective (ϕ.on_formula : @preformula L l → @preformula L' l) := by
intro x y hxy
induction x with
| falsum => cases y <;> simp [on_formula] at hxy ⊢ <;> rfl
| equal t₁ t₂ =>
cases y with
| equal t₁' t₂' =>
simp [on_formula] at hxy
exact congrArg₂ preformula.equal (on_term_inj h hxy.1) (on_term_inj h hxy.2)
| _ => simp [on_formula] at hxy
| rel R =>
cases y with
| rel R' => simp [on_formula] at hxy; exact congrArg preformula.rel (h.on_relation hxy)
| _ => simp [on_formula] at hxy
| apprel f t ihf =>
cases y with
| apprel f' t' =>
simp [on_formula] at hxy
exact congrArg₂ preformula.apprel (ihf hxy.1) (on_term_inj h hxy.2)
| _ => simp [on_formula] at hxy
| imp f₁ f₂ ihf₁ ihf₂ =>
cases y with
| imp f₁' f₂' =>
simp [on_formula] at hxy
exact congrArg₂ preformula.imp (ihf₁ hxy.1) (ihf₂ hxy.2)
| _ => simp [on_formula] at hxy
| all f ihf =>
cases y with
| all f' => simp [on_formula] at hxy; exact congrArg preformula.all (ihf hxy)
| _ => simp [on_formula] at hxy
lemma on_bounded_term_inj (h : ϕ.is_injective) {n l} :
Function.Injective (ϕ.on_bounded_term : bounded_preterm L n l → bounded_preterm L' n l) := by
intro x y hxy
apply bounded_preterm.eq
exact on_term_inj h (by simpa [on_bounded_term_fst] using congrArg bounded_preterm.fst hxy)
lemma on_bounded_formula_inj (h : ϕ.is_injective) {n l} :
Function.Injective (ϕ.on_bounded_formula : bounded_preformula L n l → bounded_preformula L' n l) := by
intro x y hxy
apply bounded_preformula.eq
exact on_formula_inj h (by simpa [on_bounded_formula_fst] using congrArg bounded_preformula.fst hxy)
variable (ϕ)
/-! ## reduct — L-structure from L'-structure via ϕ -/
def reduct (S : Structure L') : Structure L :=
⟨S.carrier, fun {n} f => S.fun_map (ϕ.on_function f), fun {n} R => S.rel_map (ϕ.on_relation R)⟩
notation:95 S "[[" ϕ "]]" => Lhom.reduct ϕ S
variable {ϕ}
@[simp] lemma reduct_coe (S : Structure L') : (reduct ϕ S).carrier = S.carrier := rfl
@[simp] lemma reduct_term_eq {S : Structure L'} (hϕ : ϕ.is_injective) {n} (xs : DVec S n) :
∀ {l} (t : bounded_preterm L n l) (xs' : DVec S l),
realize_bounded_term xs (ϕ.on_bounded_term t) xs' =
@realize_bounded_term L (ϕ.reduct S) n xs l t xs'
| _, bounded_preterm.bd_var k, xs' => rfl
| _, bounded_preterm.bd_func f, xs' => rfl
| _, bounded_preterm.bd_app t s, xs' => by
simp only [on_bounded_term, realize_bounded_term]
rw [reduct_term_eq hϕ xs s DVec.nil]
exact reduct_term_eq hϕ xs t _
lemma reduct_bounded_formula_iff {S : Structure L'} (hϕ : ϕ.is_injective) :
∀ {n l} (xs : DVec S n) (xs' : DVec S l) (f : bounded_preformula L n l),
realize_bounded_formula xs (ϕ.on_bounded_formula f) xs' ↔
@realize_bounded_formula L (ϕ.reduct S) n l xs f xs'
| _, _, xs, xs', bd_falsum => Iff.rfl
| _, _, xs, xs', bd_equal t₁ t₂ => by
simp only [on_bounded_formula, realize_bounded_formula,
reduct_term_eq hϕ xs t₁ DVec.nil, reduct_term_eq hϕ xs t₂ DVec.nil]
| _, _, xs, xs', bd_rel _ => Iff.rfl
| _, _, xs, xs', bd_apprel f t => by
simp only [on_bounded_formula, realize_bounded_formula,
reduct_term_eq hϕ xs t DVec.nil]
exact reduct_bounded_formula_iff hϕ xs (DVec.cons _ xs') f
| _, _, xs, xs', bd_imp f₁ f₂ => by
simp only [on_bounded_formula, realize_bounded_formula]
exact Iff.imp (reduct_bounded_formula_iff hϕ xs xs' f₁) (reduct_bounded_formula_iff hϕ xs xs' f₂)
| _, _, xs, xs', bd_all f => by
simp only [on_bounded_formula, realize_bounded_formula]
constructor
· intro h x; exact (reduct_bounded_formula_iff hϕ (DVec.cons x xs) xs' f).mp (h x)
· intro h x; exact (reduct_bounded_formula_iff hϕ (DVec.cons x xs) xs' f).mpr (h x)
lemma reduct_ssatisfied {S : Structure L'} {f : sentence L} (hϕ : ϕ.is_injective)
(h : S ⊨ₘ ϕ.on_sentence f) : ϕ.reduct S ⊨ₘ f :=
(reduct_bounded_formula_iff hϕ DVec.nil DVec.nil f).mp h
def reduct_all_ssatisfied {S : Structure L'} {T : SentTheory L} (hϕ : ϕ.is_injective)
(h : all_realize_sentence S (ϕ.on_sentence '' T)) : all_realize_sentence (reduct ϕ S) T :=
fun f hf => reduct_ssatisfied hϕ (h (Set.mem_image_of_mem _ hf))
variable (ϕ)
@[reducible] def Theory_induced (T : SentTheory L) : SentTheory L' := ϕ.on_sentence '' T
variable {ϕ}
lemma is_consistent_Theory_induced (hϕ : ϕ.is_injective) {T : SentTheory L}
(hT : T.is_consistent) : (ϕ.Theory_induced T).is_consistent := by
intro H
apply hT
-- H : (ϕ.Theory_induced T).fst ⊢' ⊥'
-- Need: T.fst ⊢' ⊥'
-- Use reflect_sprf: (ϕ.on_sentence '' T) ⊢ₛ ϕ.on_sentence bd_falsum → T ⊢ₛ bd_falsum
exact H.map (fun h => by
have := reflect_sprf hϕ (f := bd_falsum) h
exact this)
/-! ## is_consistent_extend (the main compactness argument) -/
lemma is_consistent_extend {T : SentTheory L} (hT : T.is_consistent) (hϕ : ϕ.is_injective)
(h : bounded_formula L 1 → bounded_formula L 1)
(hT' : ∀ (f : bounded_formula L 1), T ⊢ₛ' bd_ex (h f))
(g : bounded_formula L 1 → L'.constants) (hg : Function.Injective g)
(hg' : ∀ x, g x ∉ Set.range (ϕ.on_function (n := 0))) :
(ϕ.Theory_induced T ∪
(fun f => subst0_bounded_formula (ϕ.on_bounded_formula (h f)) (bd_const (g f))) ''
Set.univ).is_consistent := by
haveI : DecidableEq (bounded_formula L 1) := fun x y => Classical.propDecidable _
haveI : DecidableEq (sentence L') := fun x y => Classical.propDecidable _
-- Auxiliary lemma: consistency for any finite subset of witnesses.
have lem : ∀ (s₀ : Finset (bounded_formula L 1)),
(ϕ.Theory_induced T ∪
(fun f => subst0_bounded_formula (ϕ.on_bounded_formula (h f)) (bd_const (g f))) ''
(↑s₀ : Set (bounded_formula L 1))).is_consistent := by
intro s₀
induction s₀ using Finset.induction with
| empty =>
simp only [Finset.coe_empty, Set.image_empty, Set.union_empty]
exact is_consistent_Theory_induced hϕ hT
| insert ψ s hψ ih =>
intro hs
apply ih
-- Goal: (ϕ.Theory_induced T ∪ image '' ↑s).fst ⊢' ⊥'
-- Note: (image '' ↑(insert ψ s)) = insert (subst0... ψ) (image '' ↑s)
rw [Finset.coe_insert, Set.image_insert_eq] at hs
-- hs : (T_ind ∪ insert (witness ψ) (image '' ↑s)).fst ⊢' ⊥'
-- Convert: insert ... (...) ∪ T_ind = insert (witness ψ) (T_ind ∪ image '' ↑s)
have hs1 : (insert
(subst0_bounded_formula (ϕ.on_bounded_formula (h ψ)) (bd_const (g ψ)))
(ϕ.Theory_induced T ∪
(fun f => subst0_bounded_formula (ϕ.on_bounded_formula (h f)) (bd_const (g f)))
'' (↑s : Set (bounded_formula L 1)))).fst ⊢' ⊥' := by
have heq : (ϕ.Theory_induced T ∪ insert
(subst0_bounded_formula (ϕ.on_bounded_formula (h ψ)) (bd_const (g ψ)))
((fun f => subst0_bounded_formula (ϕ.on_bounded_formula (h f)) (bd_const (g f)))
'' (↑s : Set (bounded_formula L 1)))) =
(insert
(subst0_bounded_formula (ϕ.on_bounded_formula (h ψ)) (bd_const (g ψ)))
(ϕ.Theory_induced T ∪
(fun f => subst0_bounded_formula (ϕ.on_bounded_formula (h f)) (bd_const (g f)))
'' (↑s : Set (bounded_formula L 1)))) := by
ext x
simp only [Set.mem_union, Set.mem_insert_iff]
tauto
rw [heq] at hs; exact hs
-- Step 1: convert hs1 to a proof of ¬(witness ψ) from T_ind ∪ image '' ↑s
-- (impI/¬-introduction at sentence level)
let Γ := ϕ.Theory_induced T ∪
(fun f => subst0_bounded_formula (ϕ.on_bounded_formula (h f)) (bd_const (g f)))
'' (↑s : Set (bounded_formula L 1))
let ψ' : sentence L' := subst0_bounded_formula (ϕ.on_bounded_formula (h ψ)) (bd_const (g ψ))
change Γ.fst ⊢' ⊥'
-- hs1 : (insert ψ' Γ).fst ⊢' ⊥'
-- Get: Γ ⊢ ψ' ⟹ ⊥, ie Γ ⊢ ¬ψ'
have hneg : Γ.fst ⊢' (∼ψ'.fst) := by
show Γ.fst ⊢' (ψ'.fst ⟹ ⊥')
apply impI'
show insert ψ'.fst Γ.fst ⊢' (⊥' : formula L')
have himg : insert ψ'.fst Γ.fst = (insert ψ' Γ).fst := by
simp only [SentTheory.fst, Set.image_insert_eq]
rw [himg]; exact hs1
-- Now: ¬ψ' is the formula (¬ϕ.on_bounded_formula (h ψ))[bd_const (g ψ)/0] essentially
-- Specifically: ψ'.fst = subst_formula (ϕ.on_bounded_formula (h ψ)).fst (bd_const (g ψ)).fst 0
-- We want to apply sgeneralize_constant on (g ψ) and the formula
-- (∼ϕ.on_bounded_formula (h ψ)) [bd_const (g ψ)/0]
let nhψ : bounded_formula L' 1 := bd_not (ϕ.on_bounded_formula (h ψ))
-- Re-cast hneg as a proof of subst0_bounded_formula nhψ (bd_const (g ψ))
have hneg' : Γ ⊢ₛ' subst0_bounded_formula nhψ (bd_const (g ψ)) := by
show Γ.fst ⊢' (subst0_bounded_formula nhψ (bd_const (g ψ))).fst
have hfst : (subst0_bounded_formula nhψ (bd_const (g ψ))).fst = ∼ψ'.fst := by
rw [subst0_bounded_formula_fst]
show subst_formula nhψ.fst (bd_const (g ψ)).fst 0 = _
change subst_formula ((ϕ.on_bounded_formula (h ψ)).fst ⟹ ⊥') (bd_const (g ψ)).fst 0
= ∼ψ'.fst
change (subst_formula (ϕ.on_bounded_formula (h ψ)).fst (bd_const (g ψ)).fst 0) ⟹ ⊥' =
∼ψ'.fst
change _ = ψ'.fst ⟹ ⊥'
rw [show ψ'.fst = subst_formula (ϕ.on_bounded_formula (h ψ)).fst (bd_const (g ψ)).fst 0
from subst0_bounded_formula_fst _ _]
rw [hfst]; exact hneg
-- Now sgeneralize_constant requires:
-- - g ψ ∉ symbols of T (here T = Γ — yes, since g ψ doesn't appear in image of ϕ
-- nor in image of substitutions involving other g f for f ≠ ψ)
-- - g ψ ∉ symbols of nhψ
-- The symbol that we generalize:
let c : Language.symbols L' := Sum.inl ⟨0, g ψ⟩
-- Show c ∉ ⋃₀ (symbols_in_formula '' Γ.fst)
have hΓ_no_c : c ∉ ⋃₀ (symbols_in_formula '' Γ.fst) := by
rintro ⟨X, hX, hcX⟩
rcases hX with ⟨f', hf', rfl⟩
-- f' ∈ Γ.fst means f' = (some sentence in Γ).fst
rcases hf' with ⟨σ, hσ, rfl⟩
rcases hσ with hσ_T | hσ_img
· -- σ ∈ Theory_induced T = ϕ.on_sentence '' T
rcases hσ_T with ⟨τ, _hτ, rfl⟩
-- σ.fst = (ϕ.on_sentence τ).fst = ϕ.on_formula τ.fst
simp only [on_sentence_fst] at hcX
exact ϕ.not_mem_function_in_formula_on_formula (hg' ψ) τ.fst hcX
· -- σ in image
rcases hσ_img with ⟨φ, hφ, rfl⟩
-- σ = subst0_bounded_formula (ϕ.on_bounded_formula (h φ)) (bd_const (g φ))
simp only [subst0_bounded_formula_fst] at hcX
-- symbols_in_formula (subst_formula ...) ⊆ ... ∪ ...
have hsubset := symbols_in_formula_subst
(ϕ.on_bounded_formula (h φ)).fst (@bd_const L' 0 (g φ)).fst 0
have hcX' := hsubset hcX
simp only [bd_const, bounded_preterm.fst, symbols_in_term,
Set.mem_union] at hcX'
rcases hcX' with hL | hR
· -- c ∈ symbols_in_formula (ϕ.on_bounded_formula (h φ)).fst
-- Recall c = Sum.inl ⟨0, g ψ⟩; use hg' ψ
rw [on_bounded_formula_fst] at hL
exact ϕ.not_mem_function_in_formula_on_formula (hg' ψ) _ hL
· -- c = Sum.inl ⟨0, g φ⟩, which means g ψ = g φ, hence ψ = φ
have : (⟨0, g ψ⟩ : Σ l, L'.functions l) = ⟨0, g φ⟩ := Sum.inl.inj hR
have hgeq : g ψ = g φ := eq_of_heq (Sigma.mk.inj this).2
have hpsi : ψ = φ := hg hgeq
subst hpsi
exact hψ hφ
have hnhψ_no_c : c ∉ symbols_in_formula nhψ.fst := by
simp only [nhψ, bd_not, bounded_preformula.fst, on_bounded_formula_fst,
symbols_in_formula, Set.mem_union, Set.mem_empty_iff_false, or_false]
exact ϕ.not_mem_function_in_formula_on_formula (hg' ψ) (h ψ).fst
-- Apply sgeneralize_constant via Nonempty.map
have hgen : Γ ⊢ₛ' bd_all nhψ := hneg'.map
(fun pf => sgeneralize_constant (g ψ) hΓ_no_c hnhψ_no_c pf)
-- Now bd_all nhψ = bd_all (bd_not (ϕ.on_bounded_formula (h ψ))) = bd_not (bd_ex ...)
-- which contradicts bd_ex (h ψ) being provable from T (lifted to ϕ.Theory_induced T ⊆ Γ)
-- Get ϕ-image of hT' ψ
have hT'_img : (ϕ.Theory_induced T) ⊢ₛ' ϕ.on_sentence (bd_ex (h ψ)) := by
exact hT' ψ |>.map (fun pf => ϕ.on_sprf pf)
-- ϕ.on_sentence (bd_ex (h ψ)) = bd_ex (ϕ.on_bounded_formula (h ψ))
have hex_eq : ϕ.on_sentence (bd_ex (h ψ)) = bd_ex (ϕ.on_bounded_formula (h ψ)) := by
apply bounded_preformula.eq
simp only [on_sentence_fst, on_bounded_formula_fst, on_formula, bd_ex, bd_not,
bounded_preformula.fst]
rw [hex_eq] at hT'_img
-- Lift to Γ
have hex : Γ ⊢ₛ' bd_ex (ϕ.on_bounded_formula (h ψ)) := by
have hsub : ϕ.Theory_induced T ⊆ Γ := Set.subset_union_left
exact hT'_img.map (fun pf => weakening (Set.image_mono hsub) pf)
-- bd_ex φ = bd_not (bd_all (bd_not φ)), so:
-- bd_ex (ϕ.on_bounded_formula (h ψ)) = bd_not (bd_all nhψ)
have hex_def : bd_ex (ϕ.on_bounded_formula (h ψ)) = bd_not (bd_all nhψ) := rfl
rw [hex_def] at hex
-- hex : Γ ⊢ₛ' ¬(bd_all nhψ); hgen : Γ ⊢ₛ' bd_all nhψ
-- Combine: Γ ⊢ₛ' ⊥
show Γ.fst ⊢' (⊥' : formula L')
have hex_fst : (bd_not (bd_all nhψ)).fst = (bd_all nhψ).fst ⟹ ⊥' := rfl
change Γ.fst ⊢' (bd_not (bd_all nhψ)).fst at hex
rw [hex_fst] at hex
exact impE' _ hex hgen
-- Main goal: derive consistency from `lem`.
intro H
-- H : (T_ind ∪ image '' univ).fst ⊢' ⊥'. Recast as sprovable:
have H' : (ϕ.Theory_induced T ∪
(fun f => subst0_bounded_formula (ϕ.on_bounded_formula (h f)) (bd_const (g f))) ''
Set.univ) ⊢ₛ' (bd_falsum : sentence L') := H
rcases theory_proof_compactness H' with ⟨T₀, h₀, hT₀⟩
-- Decompose T₀ ⊆ T_ind ∪ image
have hT₀' : (↑T₀ : Set (sentence L')) ⊆
ϕ.Theory_induced T ∪
(fun f => subst0_bounded_formula (ϕ.on_bounded_formula (h f)) (bd_const (g f))) ''
Set.univ := hT₀
obtain ⟨t₀, s₀, hunion, ht₀, hs₀⟩ := Finset.subset_union_elim hT₀'
have hs₀' : (↑s₀ : Set (sentence L')) ⊆
(fun f => subst0_bounded_formula (ϕ.on_bounded_formula (h f)) (bd_const (g f))) ''
Set.univ := hs₀.trans (Set.diff_subset)
-- Pull back s₀ through the image map
rw [show ((fun f => subst0_bounded_formula (ϕ.on_bounded_formula (h f)) (bd_const (g f))) ''
Set.univ : Set (sentence L')) = (fun f =>
subst0_bounded_formula (ϕ.on_bounded_formula (h f)) (bd_const (g f))) '' Set.univ
from rfl] at hs₀'
rw [Finset.subset_set_image_iff] at hs₀'
obtain ⟨s₀', _hs₀'_sub, hs₀'_img⟩ := hs₀'
-- Apply lem at s₀'
apply lem s₀'
-- Need: (ϕ.Theory_induced T ∪ image '' ↑s₀').fst ⊢' ⊥'
-- We have h₀ : (↑T₀).fst ⊢' ⊥'
apply h₀.map
intro pf
apply weakening _ pf
-- Show ↑T₀.fst ⊆ (T_ind ∪ image '' ↑s₀').fst
-- We have hunion : t₀ ∪ s₀ = T₀, ht₀ : ↑t₀ ⊆ T_ind, hs₀'_img : s₀'.image (...) = s₀
intro x hx
rw [SentTheory.fst] at hx ⊢
rcases hx with ⟨σ, hσ, rfl⟩
have : σ ∈ (↑t₀ : Set (sentence L')) ∨ σ ∈ (↑s₀ : Set (sentence L')) := by
have : σ ∈ (↑(t₀ ∪ s₀) : Set (sentence L')) := by
rw [hunion]; exact hσ
simpa [Finset.coe_union, Set.mem_union] using this
rcases this with hl | hr
· refine ⟨σ, Or.inl (ht₀ hl), rfl⟩
· -- σ ∈ s₀; pull back via hs₀'_img
have hσ_in : σ ∈ (↑(s₀'.image (fun f =>
subst0_bounded_formula (ϕ.on_bounded_formula (h f)) (bd_const (g f))))
: Set (sentence L')) := by
rw [Finset.coe_image]
have : σ ∈ (↑s₀ : Set (sentence L')) := hr
rw [← hs₀'_img] at this
simpa [Finset.coe_image] using this
rw [Finset.coe_image] at hσ_in
rcases hσ_in with ⟨φ, hφ, hφ_eq⟩
refine ⟨σ, Or.inr ?_, rfl⟩
exact ⟨φ, hφ, hφ_eq⟩
end Lhom
end Fol
end CohenSource_LanguageExtension
Source