Theorem: LO.FirstOrder.Completeness.chainSet_or (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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️
Tactic:
have : ∃ s, p ⋎ q ∈ ⛓️[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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
this : ∃ s, p ⋎ q ∈ ⛓️[s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️

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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
this : ∃ s, p ⋎ q ∈ ⛓️[s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️
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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️

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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️
Tactic:
have : ⛓️[(encode $ Code.or p q).pair s + 1] ≺[Code.or p q] ⛓️[(encode $ Code.or p q).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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
this : ⛓️[(encode (Code.or p q)).pair s + 1] ≺[Code.or p q] ⛓️[(encode (Code.or p q)).pair s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️

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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
this : ⛓️[(encode (Code.or p q)).pair s + 1] ≺[Code.or p q] ⛓️[(encode (Code.or p q)).pair s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️
Tactic:
generalize hΔ : ⛓️[(encode $ Code.or p q).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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
Δ : Sequent L
hΔ : ⛓️[(encode (Code.or p q)).pair s + 1] = Δ
this : Δ ≺[Code.or p q] ⛓️[(encode (Code.or p q)).pair s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️

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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
Δ : Sequent L
hΔ : ⛓️[(encode (Code.or p q)).pair s + 1] = Δ
this : Δ ≺[Code.or p q] ⛓️[(encode (Code.or p q)).pair s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️
Tactic:
rcases this
State after:
case intro.or
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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
a✝ : p ⋎ q ∈ ⛓️[(encode (Code.or p q)).pair s]
hΔ : ⛓️[(encode (Code.or p q)).pair s + 1] = p :: q :: ⛓️[(encode (Code.or p q)).pair s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️

case intro.orRefl
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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
hΔ : ⛓️[(encode (Code.or p q)).pair s + 1] = ⛓️[(encode (Code.or p q)).pair s]
a✝ : p ⋎ q ∉ ⛓️[(encode (Code.or p q)).pair s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️

State before:
case intro.or
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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
a✝ : p ⋎ q ∈ ⛓️[(encode (Code.or p q)).pair s]
hΔ : ⛓️[(encode (Code.or p q)).pair s + 1] = p :: q :: ⛓️[(encode (Code.or p q)).pair s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️

case intro.orRefl
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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
hΔ : ⛓️[(encode (Code.or p q)).pair s + 1] = ⛓️[(encode (Code.or p q)).pair s]
a✝ : p ⋎ q ∉ ⛓️[(encode (Code.or p q)).pair s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️
Tactic:
{ exact ⟨Set.mem_iUnion.mpr ⟨(encode $ Code.or p q).pair s + 1, by simp[hΔ]⟩,
  Set.mem_iUnion.mpr ⟨(encode $ Code.or p q).pair s + 1, by simp[hΔ]⟩⟩ }
State after:
case intro.orRefl
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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
hΔ : ⛓️[(encode (Code.or p q)).pair s + 1] = ⛓️[(encode (Code.or p q)).pair s]
a✝ : p ⋎ q ∉ ⛓️[(encode (Code.or p q)).pair s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️

State before:
case intro.orRefl
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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
hΔ : ⛓️[(encode (Code.or p q)).pair s + 1] = ⛓️[(encode (Code.or p q)).pair s]
a✝ : p ⋎ q ∉ ⛓️[(encode (Code.or p q)).pair s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️
Tactic:
{ have : p ⋎ q ∈ ⛓️[(encode $ Code.or p q).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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
⊢ ∃ s, p ⋎ q ∈ ⛓️[s]
Tactic:
simpa[chainSet] using h
State after:
no goals

State before:
case intro.or
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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
a✝ : p ⋎ q ∈ ⛓️[(encode (Code.or p q)).pair s]
hΔ : ⛓️[(encode (Code.or p q)).pair s + 1] = p :: q :: ⛓️[(encode (Code.or p q)).pair s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️
Tactic:
exact ⟨Set.mem_iUnion.mpr ⟨(encode $ Code.or p q).pair s + 1, by simp[hΔ]⟩,
Set.mem_iUnion.mpr ⟨(encode $ Code.or p q).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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
a✝ : p ⋎ q ∈ ⛓️[(encode (Code.or p q)).pair s]
hΔ : ⛓️[(encode (Code.or p q)).pair s + 1] = p :: q :: ⛓️[(encode (Code.or p q)).pair s]
⊢ p ∈ {x | x ∈ ⛓️[(encode (Code.or p q)).pair s + 1]}
Tactic:
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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
a✝ : p ⋎ q ∈ ⛓️[(encode (Code.or p q)).pair s]
hΔ : ⛓️[(encode (Code.or p q)).pair s + 1] = p :: q :: ⛓️[(encode (Code.or p q)).pair s]
⊢ q ∈ {x | x ∈ ⛓️[(encode (Code.or p q)).pair s + 1]}
Tactic:
simp[hΔ]
State after:
no goals

State before:
case intro.orRefl
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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
hΔ : ⛓️[(encode (Code.or p q)).pair s + 1] = ⛓️[(encode (Code.or p q)).pair s]
a✝ : p ⋎ q ∉ ⛓️[(encode (Code.or p q)).pair s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️
Tactic:
have : p ⋎ q ∈ ⛓️[(encode $ Code.or p q).pair s] := chain_monotone nwf (Nat.right_le_pair _ _) hs
State after:
case intro.orRefl
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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
hΔ : ⛓️[(encode (Code.or p q)).pair s + 1] = ⛓️[(encode (Code.or p q)).pair s]
a✝ : p ⋎ q ∉ ⛓️[(encode (Code.or p q)).pair s]
this : p ⋎ q ∈ ⛓️[(encode (Code.or p q)).pair s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️

State before:
case intro.orRefl
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 q : SyntacticFormula L
h : p ⋎ q ∈ ⛓️
s : ℕ
hs : p ⋎ q ∈ ⛓️[s]
hΔ : ⛓️[(encode (Code.or p q)).pair s + 1] = ⛓️[(encode (Code.or p q)).pair s]
a✝ : p ⋎ q ∉ ⛓️[(encode (Code.or p q)).pair s]
this : p ⋎ q ∈ ⛓️[(encode (Code.or p q)).pair s]
⊢ p ∈ ⛓️ ∧ q ∈ ⛓️
Tactic:
contradiction
State after:
no goals