Theorem: FOL.NV.Sub.Var.All.Rec.substitution_theorem_aux
Proof state before:
case cons
D : Type
I : Interpretation D
head✝ : Definition
tail✝ : List Definition
tail_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 tail✝ F ↔ Holds D I V' tail✝ (fastReplaceFree σ' F))
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
F : Formula
h1 : admitsAux σ binders F
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
⊢ Holds D I V (head✝ :: tail✝) F ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' F)
Tactic:
induction F generalizing binders V V' σ σ'
Proof state after:
case cons.pred_const_
D : Type
I : Interpretation D
head✝ : Definition
tail✝ : List Definition
tail_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 tail✝ F ↔ Holds D I V' tail✝ (fastReplaceFree σ' F))
a✝¹ : PredName
a✝ : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : admitsAux σ binders (pred_const_ a✝¹ a✝)
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
⊢ Holds D I V (head✝ :: tail✝) (pred_const_ a✝¹ a✝) ↔
    Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' (pred_const_ a✝¹ a✝))

case cons.pred_var_
D : Type
I : Interpretation D
head✝ : Definition
tail✝ : List Definition
tail_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 tail✝ F ↔ Holds D I V' tail✝ (fastReplaceFree σ' F))
a✝¹ : PredName
a✝ : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : admitsAux σ binders (pred_var_ a✝¹ a✝)
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
⊢ Holds D I V (head✝ :: tail✝) (pred_var_ a✝¹ a✝) ↔
    Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' (pred_var_ a✝¹ a✝))

case cons.eq_
D : Type
I : Interpretation D
head✝ : Definition
tail✝ : List Definition
tail_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 tail✝ F ↔ Holds D I V' tail✝ (fastReplaceFree σ' F))
a✝¹ a✝ : VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : admitsAux σ binders (eq_ a✝¹ a✝)
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
⊢ Holds D I V (head✝ :: tail✝) (eq_ a✝¹ a✝) ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' (eq_ a✝¹ a✝))

case cons.true_
D : Type
I : Interpretation D
head✝ : Definition
tail✝ : List Definition
tail_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 tail✝ F ↔ Holds D I V' tail✝ (fastReplaceFree σ' F))
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : admitsAux σ binders true_
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
⊢ Holds D I V (head✝ :: tail✝) true_ ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' true_)

case cons.false_
D : Type
I : Interpretation D
head✝ : Definition
tail✝ : List Definition
tail_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 tail✝ F ↔ Holds D I V' tail✝ (fastReplaceFree σ' F))
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : admitsAux σ binders false_
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
⊢ Holds D I V (head✝ :: tail✝) false_ ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' false_)

case cons.not_
D : Type
I : Interpretation D
head✝ : Definition
tail✝ : List Definition
tail_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 tail✝ F ↔ Holds D I V' tail✝ (fastReplaceFree σ' F))
a✝ : Formula
a_ih✝ :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName),
    admitsAux σ binders a✝ →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) →
            (Holds D I V (head✝ :: tail✝) a✝ ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' a✝))
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : admitsAux σ binders a✝.not_
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
⊢ Holds D I V (head✝ :: tail✝) a✝.not_ ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' a✝.not_)

case cons.imp_
D : Type
I : Interpretation D
head✝ : Definition
tail✝ : List Definition
tail_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 tail✝ F ↔ Holds D I V' tail✝ (fastReplaceFree σ' F))
a✝¹ a✝ : Formula
a_ih✝¹ :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName),
    admitsAux σ binders a✝¹ →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) →
            (Holds D I V (head✝ :: tail✝) a✝¹ ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' a✝¹))
a_ih✝ :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName),
    admitsAux σ binders a✝ →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) →
            (Holds D I V (head✝ :: tail✝) a✝ ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' a✝))
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : admitsAux σ binders (a✝¹.imp_ a✝)
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
⊢ Holds D I V (head✝ :: tail✝) (a✝¹.imp_ a✝) ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' (a✝¹.imp_ a✝))

case cons.and_
D : Type
I : Interpretation D
head✝ : Definition
tail✝ : List Definition
tail_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 tail✝ F ↔ Holds D I V' tail✝ (fastReplaceFree σ' F))
a✝¹ a✝ : Formula
a_ih✝¹ :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName),
    admitsAux σ binders a✝¹ →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) →
            (Holds D I V (head✝ :: tail✝) a✝¹ ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' a✝¹))
a_ih✝ :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName),
    admitsAux σ binders a✝ →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) →
            (Holds D I V (head✝ :: tail✝) a✝ ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' a✝))
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : admitsAux σ binders (a✝¹.and_ a✝)
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
⊢ Holds D I V (head✝ :: tail✝) (a✝¹.and_ a✝) ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' (a✝¹.and_ a✝))

case cons.or_
D : Type
I : Interpretation D
head✝ : Definition
tail✝ : List Definition
tail_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 tail✝ F ↔ Holds D I V' tail✝ (fastReplaceFree σ' F))
a✝¹ a✝ : Formula
a_ih✝¹ :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName),
    admitsAux σ binders a✝¹ →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) →
            (Holds D I V (head✝ :: tail✝) a✝¹ ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' a✝¹))
a_ih✝ :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName),
    admitsAux σ binders a✝ →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) →
            (Holds D I V (head✝ :: tail✝) a✝ ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' a✝))
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : admitsAux σ binders (a✝¹.or_ a✝)
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
⊢ Holds D I V (head✝ :: tail✝) (a✝¹.or_ a✝) ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' (a✝¹.or_ a✝))

case cons.iff_
D : Type
I : Interpretation D
head✝ : Definition
tail✝ : List Definition
tail_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 tail✝ F ↔ Holds D I V' tail✝ (fastReplaceFree σ' F))
a✝¹ a✝ : Formula
a_ih✝¹ :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName),
    admitsAux σ binders a✝¹ →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) →
            (Holds D I V (head✝ :: tail✝) a✝¹ ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' a✝¹))
a_ih✝ :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName),
    admitsAux σ binders a✝ →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) →
            (Holds D I V (head✝ :: tail✝) a✝ ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' a✝))
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : admitsAux σ binders (a✝¹.iff_ a✝)
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
⊢ Holds D I V (head✝ :: tail✝) (a✝¹.iff_ a✝) ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' (a✝¹.iff_ a✝))

case cons.forall_
D : Type
I : Interpretation D
head✝ : Definition
tail✝ : List Definition
tail_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 tail✝ F ↔ Holds D I V' tail✝ (fastReplaceFree σ' F))
a✝¹ : VarName
a✝ : Formula
a_ih✝ :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName),
    admitsAux σ binders a✝ →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) →
            (Holds D I V (head✝ :: tail✝) a✝ ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' a✝))
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : admitsAux σ binders (forall_ a✝¹ a✝)
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
⊢ Holds D I V (head✝ :: tail✝) (forall_ a✝¹ a✝) ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' (forall_ a✝¹ a✝))

case cons.exists_
D : Type
I : Interpretation D
head✝ : Definition
tail✝ : List Definition
tail_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 tail✝ F ↔ Holds D I V' tail✝ (fastReplaceFree σ' F))
a✝¹ : VarName
a✝ : Formula
a_ih✝ :
  ∀ (V V' : VarAssignment D) (σ σ' : VarName → VarName) (binders : Finset VarName),
    admitsAux σ binders a✝ →
      (∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)) →
        (∀ v ∈ binders, v = σ' v) →
          (∀ v ∉ binders, σ' v = σ v) →
            (Holds D I V (head✝ :: tail✝) a✝ ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' a✝))
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : admitsAux σ binders (exists_ a✝¹ a✝)
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
⊢ Holds D I V (head✝ :: tail✝) (exists_ a✝¹ a✝) ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' (exists_ a✝¹ a✝))

case cons.def_
D : Type
I : Interpretation D
head✝ : Definition
tail✝ : List Definition
tail_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 tail✝ F ↔ Holds D I V' tail✝ (fastReplaceFree σ' F))
a✝¹ : DefName
a✝ : List VarName
V V' : VarAssignment D
σ σ' : VarName → VarName
binders : Finset VarName
h1 : admitsAux σ binders (def_ a✝¹ a✝)
h2 : ∀ (v : VarName), v ∈ binders ∨ σ' v ∉ binders → V v = V' (σ' v)
h2' : ∀ v ∈ binders, v = σ' v
h3 : ∀ v ∉ binders, σ' v = σ v
⊢ Holds D I V (head✝ :: tail✝) (def_ a✝¹ a✝) ↔ Holds D I V' (head✝ :: tail✝) (fastReplaceFree σ' (def_ a✝¹ a✝))