internlm/Lean-Github huggingface dataset:
Theorem: FOL.NV.Sub.Var.All.Rec.substitution_theorem_aux
Proof state before:
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
⊢ Holds D I (Function.updateListITE V hd.args (List.map V xs)) tl hd.q ↔
    Holds D I (Function.updateListITE V' hd.args (List.map (V' ∘ σ') xs)) tl hd.q
Tactic:
have s1 : List.map V xs = List.map (V' ∘ σ') xs
Proof state after:
case s1
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
⊢ List.map V xs = List.map (V' ∘ σ') xs

D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
s1 : List.map V xs = List.map (V' ∘ σ') xs
⊢ Holds D I (Function.updateListITE V hd.args (List.map V xs)) tl hd.q ↔
    Holds D I (Function.updateListITE V' hd.args (List.map (V' ∘ σ') xs)) tl hd.q
Theorem: FOL.NV.Sub.Var.All.Rec.substitution_theorem_aux
Proof state before:
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
s1 : List.map V xs = List.map (V' ∘ σ') xs
⊢ Holds D I (Function.updateListITE V hd.args (List.map V xs)) tl hd.q ↔
    Holds D I (Function.updateListITE V' hd.args (List.map (V' ∘ σ') xs)) tl hd.q
Tactic:
simp only [s1]
Proof state after:
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
s1 : List.map V xs = List.map (V' ∘ σ') xs
⊢ Holds D I (Function.updateListITE V hd.args (List.map (V' ∘ σ') xs)) tl hd.q ↔
    Holds D I (Function.updateListITE V' hd.args (List.map (V' ∘ σ') xs)) tl hd.q
Theorem: FOL.NV.Sub.Var.All.Rec.substitution_theorem_aux
Proof state before:
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
s1 : List.map V xs = List.map (V' ∘ σ') xs
⊢ Holds D I (Function.updateListITE V hd.args (List.map (V' ∘ σ') xs)) tl hd.q ↔
    Holds D I (Function.updateListITE V' hd.args (List.map (V' ∘ σ') xs)) tl hd.q
Tactic:
apply Holds_coincide_Var
Proof state after:
case h1
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
s1 : List.map V xs = List.map (V' ∘ σ') xs
⊢ ∀ (v : VarName),
    isFreeIn v hd.q →
      Function.updateListITE V hd.args (List.map (V' ∘ σ') xs) v =
        Function.updateListITE V' hd.args (List.map (V' ∘ σ') xs) v
Theorem: FOL.NV.Sub.Var.All.Rec.substitution_theorem_aux
Proof state before:
case h1
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
s1 : List.map V xs = List.map (V' ∘ σ') xs
⊢ ∀ (v : VarName),
    isFreeIn v hd.q →
      Function.updateListITE V hd.args (List.map (V' ∘ σ') xs) v =
        Function.updateListITE V' hd.args (List.map (V' ∘ σ') xs) v
Tactic:
intro v a1
Proof state after:
case h1
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
s1 : List.map V xs = List.map (V' ∘ σ') xs
v : VarName
a1 : isFreeIn v hd.q
⊢ Function.updateListITE V hd.args (List.map (V' ∘ σ') xs) v =
    Function.updateListITE V' hd.args (List.map (V' ∘ σ') xs) v
Theorem: FOL.NV.Sub.Var.All.Rec.substitution_theorem_aux
Proof state before:
case h1
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
s1 : List.map V xs = List.map (V' ∘ σ') xs
v : VarName
a1 : isFreeIn v hd.q
⊢ Function.updateListITE V hd.args (List.map (V' ∘ σ') xs) v =
    Function.updateListITE V' hd.args (List.map (V' ∘ σ') xs) v
Tactic:
apply Function.updateListITE_mem_eq_len
Proof state after:
case h1.h1
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
s1 : List.map V xs = List.map (V' ∘ σ') xs
v : VarName
a1 : isFreeIn v hd.q
⊢ v ∈ hd.args

case h1.h2
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
s1 : List.map V xs = List.map (V' ∘ σ') xs
v : VarName
a1 : isFreeIn v hd.q
⊢ hd.args.length = (List.map (V' ∘ σ') xs).length
Theorem: FOL.NV.Sub.Var.All.Rec.substitution_theorem_aux
Proof state before:
case s1
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
⊢ List.map V xs = List.map (V' ∘ σ') xs
Tactic:
simp only [List.map_eq_map_iff]
Proof state after:
case s1
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
⊢ ∀ x ∈ xs, V x = (V' ∘ σ') x
Theorem: FOL.NV.Sub.Var.All.Rec.substitution_theorem_aux
Proof state before:
case s1
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
⊢ ∀ x ∈ xs, V x = (V' ∘ σ') x
Tactic:
intro x a1
Proof state after:
case s1
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
x : VarName
a1 : x ∈ xs
⊢ V x = (V' ∘ σ') x
Theorem: FOL.NV.Sub.Var.All.Rec.substitution_theorem_aux
Proof state before:
case s1
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
x : VarName
a1 : x ∈ xs
⊢ V x = (V' ∘ σ') x
Tactic:
simp
Proof state after:
case s1
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
x : VarName
a1 : x ∈ xs
⊢ V x = V' (σ' x)
Theorem: FOL.NV.Sub.Var.All.Rec.substitution_theorem_aux
Proof state before:
case s1
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
x : VarName
a1 : x ∈ xs
⊢ V x = V' (σ' x)
Tactic:
apply h2
Proof state after:
case s1.a
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
x : VarName
a1 : x ∈ xs
⊢ x ∈ binders ∨ σ' x ∉ binders
Theorem: FOL.NV.Sub.Var.All.Rec.substitution_theorem_aux
Proof state before:
case s1.a
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
x : VarName
a1 : x ∈ xs
⊢ x ∈ binders ∨ σ' x ∉ binders
Tactic:
by_cases c3 : x ∈ binders
Proof state after:
case pos
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
x : VarName
a1 : x ∈ xs
c3 : x ∈ binders
⊢ x ∈ binders ∨ σ' x ∉ binders

case neg
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
x : VarName
a1 : x ∈ xs
c3 : x ∉ binders
⊢ x ∈ binders ∨ σ' x ∉ binders
Theorem: FOL.NV.Sub.Var.All.Rec.substitution_theorem_aux
Proof state before:
case pos
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
x : VarName
a1 : x ∈ xs
c3 : x ∈ binders
⊢ x ∈ binders ∨ σ' x ∉ binders
Tactic:
left
Proof state after:
case pos.h
D : Type
I : Interpretation D
hd : Definition
tl : List Definition
ih :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName) (F : Formula),
    admitsAux σ binders F →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) → (Holds D I V tl F ↔ Holds D I V' tl (fastReplaceFree σ' F))
X : DefName
xs : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : ∀ v ∈ xs, v ∉ binders → σ v ∉ binders
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
c1 : X = hd.name ∧ xs.length = hd.args.length
c2 : X = hd.name ∧ (List.map σ' xs).length = hd.args.length
x : VarName
a1 : x ∈ xs
c3 : x ∈ binders
⊢ x ∈ binders