case intro
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
S : WSeq (WSeq α)
T : WSeq (WSeq β)
U : WSeq α → WSeq β → Prop
ST : LiftRel (LiftRel R) S T
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
a : Option (α × WSeq α)
ma : a ∈ destruct (join S)
n : ℕ
h : Results (destruct (join S)) a n
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
S : WSeq (WSeq α)
T : WSeq (WSeq β)
U : WSeq α → WSeq β → Prop
ST : LiftRel (LiftRel R) S T
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
a : Option (α × WSeq α)
ma : a ∈ destruct (join S)
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
cases' exists_results_of_mem ma with n h
case intro
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
S : WSeq (WSeq α)
T : WSeq (WSeq β)
U : WSeq α → WSeq β → Prop
ST : LiftRel (LiftRel R) S T
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
a : Option (α × WSeq α)
n : ℕ
h : Results (destruct (join S)) a n
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
case intro
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
S : WSeq (WSeq α)
T : WSeq (WSeq β)
U : WSeq α → WSeq β → Prop
ST : LiftRel (LiftRel R) S T
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
a : Option (α × WSeq α)
ma : a ∈ destruct (join S)
n : ℕ
h : Results (destruct (join S)) a n
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
clear ma
case intro
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
⊢ ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
    LiftRel (LiftRel R) S T →
      ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a n → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
case intro
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
S : WSeq (WSeq α)
T : WSeq (WSeq β)
U : WSeq α → WSeq β → Prop
ST : LiftRel (LiftRel R) S T
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
a : Option (α × WSeq α)
n : ℕ
h : Results (destruct (join S)) a n
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
revert S T ST a
case intro.ind
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
⊢ ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
    LiftRel (LiftRel R) S T →
      ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a n → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
case intro
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
⊢ ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
    LiftRel (LiftRel R) S T →
      ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a n → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
induction' n using Nat.strongInductionOn with n IH
case intro.ind
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra : Results (destruct (join S)) a n
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
case intro.ind
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
⊢ ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
    LiftRel (LiftRel R) S T →
      ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a n → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
intro S T ST a ra
case intro.ind
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
case intro.ind
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra : Results (destruct (join S)) a n
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
simp [destruct_join] at ra
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
x✝¹ : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) none none
x✝ : Results (destruct S) none m
rs2 :
  Results
    (match none with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
mT : none ∈ destruct T
⊢ ∃ b, b ∈ Computation.bind (destruct T) destruct_join.aux ∧ LiftRelO R U a b
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
x✝¹ : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) none none
x✝ : Results (destruct S) none m
rs2 :
  Results
    (match none with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
mT : none ∈ destruct T
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
simp only [destruct_join]
no goals
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
x✝¹ : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) none none
x✝ : Results (destruct S) none m
rs2 :
  Results
    (match none with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
mT : none ∈ destruct T
⊢ ∃ b, b ∈ Computation.bind (destruct T) destruct_join.aux ∧ LiftRelO R U a b
exact ⟨none, mem_bind mT (ret_mem _), by rw [eq_of_pure_mem rs2.mem]; trivial⟩
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
x✝¹ : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) none none
x✝ : Results (destruct S) none m
rs2 :
  Results
    (match none with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
mT : none ∈ destruct T
⊢ LiftRelO R U none none
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
x✝¹ : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) none none
x✝ : Results (destruct S) none m
rs2 :
  Results
    (match none with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
mT : none ∈ destruct T
⊢ LiftRelO R U a none
rw [eq_of_pure_mem rs2.mem]
no goals
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
x✝¹ : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) none none
x✝ : Results (destruct S) none m
rs2 :
  Results
    (match none with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
mT : none ∈ destruct T
⊢ LiftRelO R U none none
trivial
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝ : Results (destruct S) (some (s, S')) m
rs2 :
  Results
    (match some (s, S') with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
mT : some (t, T') ∈ destruct T
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
simp [destruct_append] at rs2
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
this : n1 < n
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
have : n1 < n := by
  rw [en, ek, ek1]
  apply lt_of_lt_of_le _ (Nat.le_add_right _ _)
  apply Nat.lt_succ_of_le (Nat.le_add_right _ _)
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
this : n1 < n
ob : Option (β × WSeq β)
mb : ob ∈ destruct (join T')
rob : LiftRelO R U a ob
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
this : n1 < n
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
let ⟨ob, mb, rob⟩ := IH _ this ST' rs5'
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
this : n1 < n
ob : Option (β × WSeq β)
mb : ob ∈ destruct (join T')
rob : LiftRelO R U a ob
⊢ ob ∈ destruct (join T)
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
this : n1 < n
ob : Option (β × WSeq β)
mb : ob ∈ destruct (join T')
rob : LiftRelO R U a ob
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
refine' ⟨ob, _, rob⟩
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
⊢ n1 < n1 + m1 + 1 + m
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
⊢ n1 < n
rw [en, ek, ek1]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
⊢ n1 < n1 + m1 + 1
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
⊢ n1 < n1 + m1 + 1 + m
apply lt_of_lt_of_le _ (Nat.le_add_right _ _)
no goals
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
⊢ n1 < n1 + m1 + 1
apply Nat.lt_succ_of_le (Nat.le_add_right _ _)
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
this : n1 < n
ob : Option (β × WSeq β)
mb : ob ∈ destruct (join T')
rob : LiftRelO R U a ob
⊢ ob ∈
    Computation.bind (destruct T) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S)))
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
this : n1 < n
ob : Option (β × WSeq β)
mb : ob ∈ destruct (join T')
rob : LiftRelO R U a ob
⊢ ob ∈ destruct (join T)
simp [destruct_join]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
this : n1 < n
ob : Option (β × WSeq β)
mb : ob ∈ destruct (join T')
rob : LiftRelO R U a ob
⊢ ob ∈
    match some (t, T') with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S)))
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
this : n1 < n
ob : Option (β × WSeq β)
mb : ob ∈ destruct (join T')
rob : LiftRelO R U a ob
⊢ ob ∈
    Computation.bind (destruct T) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S)))
apply mem_bind mT
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
this : n1 < n
ob : Option (β × WSeq β)
mb : ob ∈ destruct (join T')
rob : LiftRelO R U a ob
⊢ ob ∈
    Computation.think
      (Computation.bind (destruct t) fun x =>
        match x with
        | none => destruct (join T')
        | some (a, s) => Computation.pure (some (a, append s (join T'))))
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
this : n1 < n
ob : Option (β × WSeq β)
mb : ob ∈ destruct (join T')
rob : LiftRelO R U a ob
⊢ ob ∈
    match some (t, T') with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S)))
simp [destruct_append]
case a
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
this : n1 < n
ob : Option (β × WSeq β)
mb : ob ∈ destruct (join T')
rob : LiftRelO R U a ob
⊢ ob ∈
    Computation.bind (destruct t) fun x =>
      match x with
      | none => destruct (join T')
      | some (a, s) => Computation.pure (some (a, append s (join T')))
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
this : n1 < n
ob : Option (β × WSeq β)
mb : ob ∈ destruct (join T')
rob : LiftRelO R U a ob
⊢ ob ∈
    Computation.think
      (Computation.bind (destruct t) fun x =>
        match x with
        | none => destruct (join T')
        | some (a, s) => Computation.pure (some (a, append s (join T'))))
apply think_mem
case a
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
this : n1 < n
ob : Option (β × WSeq β)
mb : ob ∈ destruct (join T')
rob : LiftRelO R U a ob
⊢ ob ∈
    match none with
    | none => destruct (join T')
    | some (a, s) => Computation.pure (some (a, append s (join T')))
case a
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
this : n1 < n
ob : Option (β × WSeq β)
mb : ob ∈ destruct (join T')
rob : LiftRelO R U a ob
⊢ ob ∈
    Computation.bind (destruct t) fun x =>
      match x with
      | none => destruct (join T')
      | some (a, s) => Computation.pure (some (a, append s (join T')))
apply mem_bind mt
no goals
case a
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝² : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5 :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
x✝¹ : LiftRelO R (LiftRel R) none none
x✝ : Results (destruct s) none m1
rs5' :
  Results
    (match none with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a n1
mt : none ∈ destruct t
this : n1 < n
ob : Option (β × WSeq β)
mb : ob ∈ destruct (join T')
rob : LiftRelO R U a ob
⊢ ob ∈
    match none with
    | none => destruct (join T')
    | some (a, s) => Computation.pure (some (a, append s (join T')))
exact mb
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a✝ b
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 :
  Results
    (match some (a, s') with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
mt : some (b, t') ∈ destruct t
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a✝ b
simp at rs5
case refine'_1
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ some (b, append t' (join T')) ∈ destruct (join T)

case refine'_2
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ LiftRelO R U a✝ (some (b, append t' (join T')))
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a✝ b
refine' ⟨some (b, append t' (join T')), _, _⟩
case refine'_2
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ LiftRelO R U (some (a, append s' (join S'))) (some (b, append t' (join T')))
case refine'_2
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ LiftRelO R U a✝ (some (b, append t' (join T')))
rw [eq_of_pure_mem rs5.mem]
no goals
case refine'_2
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ LiftRelO R U (some (a, append s' (join S'))) (some (b, append t' (join T')))
exact ⟨ab, HU _ _ ⟨s', t', S', T', rfl, rfl, st', ST'⟩⟩
case refine'_1
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ some (b, append t' (join T')) ∈
    Computation.bind (destruct T) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S)))
case refine'_1
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ some (b, append t' (join T')) ∈ destruct (join T)
simp [destruct_join]
case refine'_1
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ some (b, append t' (join T')) ∈
    match some (t, T') with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S)))
case refine'_1
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ some (b, append t' (join T')) ∈
    Computation.bind (destruct T) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S)))
apply mem_bind mT
case refine'_1
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ some (b, append t' (join T')) ∈
    Computation.think
      (Computation.bind (destruct t) fun x =>
        match x with
        | none => destruct (join T')
        | some (a, s) => Computation.pure (some (a, append s (join T'))))
case refine'_1
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ some (b, append t' (join T')) ∈
    match some (t, T') with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S)))
simp [destruct_append]
case refine'_1.a
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ some (b, append t' (join T')) ∈
    Computation.bind (destruct t) fun x =>
      match x with
      | none => destruct (join T')
      | some (a, s) => Computation.pure (some (a, append s (join T')))
case refine'_1
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ some (b, append t' (join T')) ∈
    Computation.think
      (Computation.bind (destruct t) fun x =>
        match x with
        | none => destruct (join T')
        | some (a, s) => Computation.pure (some (a, append s (join T'))))
apply think_mem
case refine'_1.a
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ some (b, append t' (join T')) ∈
    match some (b, t') with
    | none => destruct (join T')
    | some (a, s) => Computation.pure (some (a, append s (join T')))
case refine'_1.a
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ some (b, append t' (join T')) ∈
    Computation.bind (destruct t) fun x =>
      match x with
      | none => destruct (join T')
      | some (a, s) => Computation.pure (some (a, append s (join T')))
apply mem_bind mt
no goals
case refine'_1.a
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
U : WSeq α → WSeq β → Prop
HU :
  ∀ (s1 : WSeq α) (s2 : WSeq β),
    (∃ s t S T, s1 = append s (join S) ∧ s2 = append t (join T) ∧ LiftRel R s t ∧ LiftRel (LiftRel R) S T) → U s1 s2
n : ℕ
IH :
  ∀ (m : ℕ),
    m < n →
      ∀ {S : WSeq (WSeq α)} {T : WSeq (WSeq β)},
        LiftRel (LiftRel R) S T →
          ∀ {a : Option (α × WSeq α)}, Results (destruct (join S)) a m → ∃ b, b ∈ destruct (join T) ∧ LiftRelO R U a b
S : WSeq (WSeq α)
T : WSeq (WSeq β)
ST : LiftRel (LiftRel R) S T
a✝ : Option (α × WSeq α)
ra :
  Results
    (Computation.bind (destruct S) fun x =>
      match x with
      | none => Computation.pure none
      | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ n
o : Option (WSeq α × WSeq (WSeq α))
m k : ℕ
rs1 : Results (destruct S) o m
rs2✝ :
  Results
    (match o with
    | none => Computation.pure none
    | some (s, S) => Computation.think (destruct (append s (join S))))
    a✝ k
en : n = k + m
p : Option (WSeq β × WSeq (WSeq β))
mT✝ : p ∈ destruct T
rop : LiftRelO (LiftRel R) (LiftRel (LiftRel R)) o p
s : WSeq α
S' : WSeq (WSeq α)
t : WSeq β
T' : WSeq (WSeq β)
st : LiftRel R s t
ST' : LiftRel (LiftRel R) S' T'
x✝¹ : Results (destruct S) (some (s, S')) m
mT : some (t, T') ∈ destruct T
rs2 :
  Results
    (Computation.think
      (Computation.bind (destruct s) fun x =>
        match x with
        | none => destruct (join S')
        | some (a, s) => Computation.pure (some (a, append s (join S')))))
    a✝ k
k1 : ℕ
rs3 :
  Results
    (Computation.bind (destruct s) fun x =>
      match x with
      | none => destruct (join S')
      | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ k1
ek : k = k1 + 1
o' : Option (α × WSeq α)
m1 n1 : ℕ
rs4 : Results (destruct s) o' m1
rs5✝ :
  Results
    (match o' with
    | none => destruct (join S')
    | some (a, s) => Computation.pure (some (a, append s (join S'))))
    a✝ n1
ek1 : k1 = n1 + m1
p' : Option (β × WSeq β)
mt✝ : p' ∈ destruct t
rop' : LiftRelO R (LiftRel R) o' p'
a : α
s' : WSeq α
b : β
t' : WSeq β
ab : R a b
st' : LiftRel R s' t'
x✝ : Results (destruct s) (some (a, s')) m1
rs5 : Results (Computation.pure (some (a, append s' (join S')))) a✝ n1
mt : some (b, t') ∈ destruct t
⊢ some (b, append t' (join T')) ∈
    match some (b, t') with
    | none => destruct (join T')
    | some (a, s) => Computation.pure (some (a, append s (join T')))
apply ret_mem