Theorem: LO.FirstOrder.Completeness.chainSet_all (Logic/FirstOrder/Completeness/SearchTree.lean)

State before:
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
⊢ ∃ t, [→ t].hom p ∈ ⛓️
Tactic:
have : ∃ s, ∀' p ∈ ⛓️[s] := by simpa[chainSet] using h
State after:
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
this : ∃ s, ∀' p ∈ ⛓️[s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️

State before:
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
this : ∃ s, ∀' p ∈ ⛓️[s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️
Tactic:
rcases this with ⟨s, hs⟩
State after:
case intro
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
s : ℕ
hs : ∀' p ∈ ⛓️[s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️

State before:
case intro
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
s : ℕ
hs : ∀' p ∈ ⛓️[s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️
Tactic:
have : ⛓️[(encode $ Code.all p).pair s + 1] ≺[Code.all p] ⛓️[(encode $ Code.all p).pair s] := chain_spec' nwf _ _
State after:
case intro
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
s : ℕ
hs : ∀' p ∈ ⛓️[s]
this : ⛓️[(encode (Code.all p)).pair s + 1] ≺[Code.all p] ⛓️[(encode (Code.all p)).pair s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️

State before:
case intro
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
s : ℕ
hs : ∀' p ∈ ⛓️[s]
this : ⛓️[(encode (Code.all p)).pair s + 1] ≺[Code.all p] ⛓️[(encode (Code.all p)).pair s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️
Tactic:
generalize hΔ : ⛓️[(encode $ Code.all p).pair s + 1] = Δ at this
State after:
case intro
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
s : ℕ
hs : ∀' p ∈ ⛓️[s]
Δ : Sequent L
hΔ : ⛓️[(encode (Code.all p)).pair s + 1] = Δ
this : Δ ≺[Code.all p] ⛓️[(encode (Code.all p)).pair s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️

State before:
case intro
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
s : ℕ
hs : ∀' p ∈ ⛓️[s]
Δ : Sequent L
hΔ : ⛓️[(encode (Code.all p)).pair s + 1] = Δ
this : Δ ≺[Code.all p] ⛓️[(encode (Code.all p)).pair s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️
Tactic:
rcases this
State after:
case intro.all
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
s : ℕ
hs : ∀' p ∈ ⛓️[s]
a✝ : ∀' p ∈ ⛓️[(encode (Code.all p)).pair s]
hΔ :
  ⛓️[(encode (Code.all p)).pair s + 1] =
    [→ &(newVar ⛓️[(encode (Code.all p)).pair s])].hom p :: ⛓️[(encode (Code.all p)).pair s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️

case intro.allRefl
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
s : ℕ
hs : ∀' p ∈ ⛓️[s]
hΔ : ⛓️[(encode (Code.all p)).pair s + 1] = ⛓️[(encode (Code.all p)).pair s]
a✝ : ∀' p ∉ ⛓️[(encode (Code.all p)).pair s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️

State before:
case intro.all
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
s : ℕ
hs : ∀' p ∈ ⛓️[s]
a✝ : ∀' p ∈ ⛓️[(encode (Code.all p)).pair s]
hΔ :
  ⛓️[(encode (Code.all p)).pair s + 1] =
    [→ &(newVar ⛓️[(encode (Code.all p)).pair s])].hom p :: ⛓️[(encode (Code.all p)).pair s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️

case intro.allRefl
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
s : ℕ
hs : ∀' p ∈ ⛓️[s]
hΔ : ⛓️[(encode (Code.all p)).pair s + 1] = ⛓️[(encode (Code.all p)).pair s]
a✝ : ∀' p ∉ ⛓️[(encode (Code.all p)).pair s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️
Tactic:
{ exact ⟨&(newVar ⛓️[(encode $ Code.all p).pair s]), Set.mem_iUnion.mpr ⟨(encode $ Code.all p).pair s + 1, by simp[hΔ]⟩⟩ }
State after:
case intro.allRefl
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
s : ℕ
hs : ∀' p ∈ ⛓️[s]
hΔ : ⛓️[(encode (Code.all p)).pair s + 1] = ⛓️[(encode (Code.all p)).pair s]
a✝ : ∀' p ∉ ⛓️[(encode (Code.all p)).pair s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️

State before:
case intro.allRefl
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
s : ℕ
hs : ∀' p ∈ ⛓️[s]
hΔ : ⛓️[(encode (Code.all p)).pair s + 1] = ⛓️[(encode (Code.all p)).pair s]
a✝ : ∀' p ∉ ⛓️[(encode (Code.all p)).pair s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️
Tactic:
{ have : ∀' p ∈ ⛓️[(encode $ Code.all p).pair s] := chain_monotone nwf (Nat.right_le_pair _ _) hs
  contradiction }
State after:
no goals

State before:
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
⊢ ∃ s, ∀' p ∈ ⛓️[s]
Tactic:
simpa[chainSet] using h
State after:
no goals

State before:
case intro.all
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
s : ℕ
hs : ∀' p ∈ ⛓️[s]
a✝ : ∀' p ∈ ⛓️[(encode (Code.all p)).pair s]
hΔ :
  ⛓️[(encode (Code.all p)).pair s + 1] =
    [→ &(newVar ⛓️[(encode (Code.all p)).pair s])].hom p :: ⛓️[(encode (Code.all p)).pair s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️
Tactic:
exact ⟨&(newVar ⛓️[(encode $ Code.all p).pair s]), Set.mem_iUnion.mpr ⟨(encode $ Code.all p).pair s + 1, by simp[hΔ]⟩⟩
State after:
no goals

State before:
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
s : ℕ
hs : ∀' p ∈ ⛓️[s]
a✝ : ∀' p ∈ ⛓️[(encode (Code.all p)).pair s]
hΔ :
  ⛓️[(encode (Code.all p)).pair s + 1] =
    [→ &(newVar ⛓️[(encode (Code.all p)).pair s])].hom p :: ⛓️[(encode (Code.all p)).pair s]
⊢ [→ &(newVar ⛓️[(encode (Code.all p)).pair s])].hom p ∈ {x | x ∈ ⛓️[(encode (Code.all p)).pair s + 1]}
Tactic:
simp[hΔ]
State after:
no goals

State before:
case intro.allRefl
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
s : ℕ
hs : ∀' p ∈ ⛓️[s]
hΔ : ⛓️[(encode (Code.all p)).pair s + 1] = ⛓️[(encode (Code.all p)).pair s]
a✝ : ∀' p ∉ ⛓️[(encode (Code.all p)).pair s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️
Tactic:
have : ∀' p ∈ ⛓️[(encode $ Code.all p).pair s] := chain_monotone nwf (Nat.right_le_pair _ _) hs
State after:
case intro.allRefl
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
s : ℕ
hs : ∀' p ∈ ⛓️[s]
hΔ : ⛓️[(encode (Code.all p)).pair s + 1] = ⛓️[(encode (Code.all p)).pair s]
a✝ : ∀' p ∉ ⛓️[(encode (Code.all p)).pair s]
this : ∀' p ∈ ⛓️[(encode (Code.all p)).pair s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️

State before:
case intro.allRefl
L : Language
inst✝³ : (k : ℕ) → DecidableEq (L.Func k)
inst✝² : (k : ℕ) → DecidableEq (L.Rel k)
inst✝¹ : (k : ℕ) → Encodable (L.Func k)
inst✝ : (k : ℕ) → Encodable (L.Rel k)
T : Theory L
Γ : Sequent L
nwf : ¬WellFounded (SearchTree.Lt T Γ)
p : SyntacticSemiformula L 1
h : ∀' p ∈ ⛓️
s : ℕ
hs : ∀' p ∈ ⛓️[s]
hΔ : ⛓️[(encode (Code.all p)).pair s + 1] = ⛓️[(encode (Code.all p)).pair s]
a✝ : ∀' p ∉ ⛓️[(encode (Code.all p)).pair s]
this : ∀' p ∈ ⛓️[(encode (Code.all p)).pair s]
⊢ ∃ t, [→ t].hom p ∈ ⛓️
Tactic:
contradiction
State after:
no goals