Theorem: LO.FirstOrder.Completeness.chainSet_and (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.and p q).pair s + 1] ≺[Code.and p q] ⛓️[(encode $ Code.and 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.and p q)).pair s + 1] ≺[Code.and p q] ⛓️[(encode (Code.and 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.and p q)).pair s + 1] ≺[Code.and p q] ⛓️[(encode (Code.and p q)).pair s]
⊢ p ∈ ⛓️ ∨ q ∈ ⛓️
Tactic:
generalize hΔ : ⛓️[(encode $ Code.and 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.and p q)).pair s + 1] = Δ
this : Δ ≺[Code.and p q] ⛓️[(encode (Code.and 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.and p q)).pair s + 1] = Δ
this : Δ ≺[Code.and p q] ⛓️[(encode (Code.and p q)).pair s]
⊢ p ∈ ⛓️ ∨ q ∈ ⛓️
Tactic:
rcases this
State after:
case intro.and₁
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.and p q)).pair s]
hΔ : ⛓️[(encode (Code.and p q)).pair s + 1] = p :: ⛓️[(encode (Code.and p q)).pair s]
⊢ p ∈ ⛓️ ∨ q ∈ ⛓️

case intro.and₂
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.and p q)).pair s]
hΔ : ⛓️[(encode (Code.and p q)).pair s + 1] = q :: ⛓️[(encode (Code.and p q)).pair s]
⊢ p ∈ ⛓️ ∨ q ∈ ⛓️

case intro.andRefl
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.and p q)).pair s + 1] = ⛓️[(encode (Code.and p q)).pair s]
a✝ : p ⋏ q ∉ ⛓️[(encode (Code.and p q)).pair 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 ∈ ⛓️
s : ℕ
hs : p ⋏ q ∈ ⛓️[s]
a✝ : p ⋏ q ∈ ⛓️[(encode (Code.and p q)).pair s]
hΔ : ⛓️[(encode (Code.and p q)).pair s + 1] = p :: ⛓️[(encode (Code.and p q)).pair s]
⊢ p ∈ ⛓️ ∨ q ∈ ⛓️
Tactic:
case and₁ =>
  exact Or.inl (Set.mem_iUnion.mpr ⟨(encode $ Code.and 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.and p q)).pair s]
hΔ : ⛓️[(encode (Code.and p q)).pair s + 1] = q :: ⛓️[(encode (Code.and p q)).pair s]
⊢ p ∈ ⛓️ ∨ q ∈ ⛓️
Tactic:
case and₂ =>
  exact Or.inr (Set.mem_iUnion.mpr ⟨(encode $ Code.and 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]
hΔ : ⛓️[(encode (Code.and p q)).pair s + 1] = ⛓️[(encode (Code.and p q)).pair s]
a✝ : p ⋏ q ∉ ⛓️[(encode (Code.and p q)).pair s]
⊢ p ∈ ⛓️ ∨ q ∈ ⛓️
Tactic:
case andRefl =>
  have : p ⋏ q ∈ ⛓️[(encode $ Code.and 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:
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.and p q)).pair s]
hΔ : ⛓️[(encode (Code.and p q)).pair s + 1] = p :: ⛓️[(encode (Code.and p q)).pair s]
⊢ p ∈ ⛓️ ∨ q ∈ ⛓️
Tactic:
exact Or.inl (Set.mem_iUnion.mpr ⟨(encode $ Code.and 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.and p q)).pair s]
hΔ : ⛓️[(encode (Code.and p q)).pair s + 1] = p :: ⛓️[(encode (Code.and p q)).pair s]
⊢ p ∈ {x | x ∈ ⛓️[(encode (Code.and 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.and p q)).pair s]
hΔ : ⛓️[(encode (Code.and p q)).pair s + 1] = q :: ⛓️[(encode (Code.and p q)).pair s]
⊢ p ∈ ⛓️ ∨ q ∈ ⛓️
Tactic:
exact Or.inr (Set.mem_iUnion.mpr ⟨(encode $ Code.and 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.and p q)).pair s]
hΔ : ⛓️[(encode (Code.and p q)).pair s + 1] = q :: ⛓️[(encode (Code.and p q)).pair s]
⊢ q ∈ {x | x ∈ ⛓️[(encode (Code.and 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]
hΔ : ⛓️[(encode (Code.and p q)).pair s + 1] = ⛓️[(encode (Code.and p q)).pair s]
a✝ : p ⋏ q ∉ ⛓️[(encode (Code.and p q)).pair s]
⊢ p ∈ ⛓️ ∨ q ∈ ⛓️
Tactic:
have : p ⋏ q ∈ ⛓️[(encode $ Code.and p q).pair s] := chain_monotone nwf (Nat.right_le_pair _ _) hs
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 ∈ ⛓️
s : ℕ
hs : p ⋏ q ∈ ⛓️[s]
hΔ : ⛓️[(encode (Code.and p q)).pair s + 1] = ⛓️[(encode (Code.and p q)).pair s]
a✝ : p ⋏ q ∉ ⛓️[(encode (Code.and p q)).pair s]
this : p ⋏ q ∈ ⛓️[(encode (Code.and p q)).pair 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 ∈ ⛓️
s : ℕ
hs : p ⋏ q ∈ ⛓️[s]
hΔ : ⛓️[(encode (Code.and p q)).pair s + 1] = ⛓️[(encode (Code.and p q)).pair s]
a✝ : p ⋏ q ∉ ⛓️[(encode (Code.and p q)).pair s]
this : p ⋏ q ∈ ⛓️[(encode (Code.and p q)).pair s]
⊢ p ∈ ⛓️ ∨ q ∈ ⛓️
Tactic:
contradiction
State after:
no goals