[GOAL]
α : Type u
β : Type v
γ : Type w
c : Computation α
n : ℕ
a : α
h : Stream'.cons none (↑c) n = some a
⊢ Stream'.cons none (↑c) (n + 1) = some a
[PROOFSTEP]
cases' n with n
[GOAL]
case zero
α : Type u
β : Type v
γ : Type w
c : Computation α
a : α
h : Stream'.cons none (↑c) Nat.zero = some a
⊢ Stream'.cons none (↑c) (Nat.zero + 1) = some a
[PROOFSTEP]
contradiction
[GOAL]
case succ
α : Type u
β : Type v
γ : Type w
c : Computation α
a : α
n : ℕ
h : Stream'.cons none (↑c) (Nat.succ n) = some a
⊢ Stream'.cons none (↑c) (Nat.succ n + 1) = some a
[PROOFSTEP]
exact c.2 h
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
⊢ destruct s = Sum.inl a → s = pure a
[PROOFSTEP]
dsimp [destruct]
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
⊢ (match ↑s 0 with
      | none => Sum.inr (tail s)
      | some a => Sum.inl a) =
      Sum.inl a →
    s = pure a
[PROOFSTEP]
induction' f0 : s.1 0 with _
[GOAL]
case none
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
x✝ : Option α
f0✝ : ↑s 0 = x✝
f0 : ↑s 0 = none
⊢ (match none with
      | none => Sum.inr (tail s)
      | some a => Sum.inl a) =
      Sum.inl a →
    s = pure a
[PROOFSTEP]
intro h
[GOAL]
case some
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
x✝ : Option α
f0✝ : ↑s 0 = x✝
val✝ : α
f0 : ↑s 0 = some val✝
⊢ (match some val✝ with
      | none => Sum.inr (tail s)
      | some a => Sum.inl a) =
      Sum.inl a →
    s = pure a
[PROOFSTEP]
intro h
[GOAL]
case none
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
x✝ : Option α
f0✝ : ↑s 0 = x✝
f0 : ↑s 0 = none
h :
  (match none with
    | none => Sum.inr (tail s)
    | some a => Sum.inl a) =
    Sum.inl a
⊢ s = pure a
[PROOFSTEP]
contradiction
[GOAL]
case some
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
x✝ : Option α
f0✝ : ↑s 0 = x✝
val✝ : α
f0 : ↑s 0 = some val✝
h :
  (match some val✝ with
    | none => Sum.inr (tail s)
    | some a => Sum.inl a) =
    Sum.inl a
⊢ s = pure a
[PROOFSTEP]
apply Subtype.eq
[GOAL]
case some.a
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
x✝ : Option α
f0✝ : ↑s 0 = x✝
val✝ : α
f0 : ↑s 0 = some val✝
h :
  (match some val✝ with
    | none => Sum.inr (tail s)
    | some a => Sum.inl a) =
    Sum.inl a
⊢ ↑s = ↑(pure a)
[PROOFSTEP]
funext n
[GOAL]
case some.a.h
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
x✝ : Option α
f0✝ : ↑s 0 = x✝
val✝ : α
f0 : ↑s 0 = some val✝
h :
  (match some val✝ with
    | none => Sum.inr (tail s)
    | some a => Sum.inl a) =
    Sum.inl a
n : ℕ
⊢ ↑s n = ↑(pure a) n
[PROOFSTEP]
induction' n with n IH
[GOAL]
case some.a.h.zero
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
x✝ : Option α
f0✝ : ↑s 0 = x✝
val✝ : α
f0 : ↑s 0 = some val✝
h :
  (match some val✝ with
    | none => Sum.inr (tail s)
    | some a => Sum.inl a) =
    Sum.inl a
⊢ ↑s Nat.zero = ↑(pure a) Nat.zero
[PROOFSTEP]
injection h with h'
[GOAL]
case some.a.h.zero
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
x✝ : Option α
f0✝ : ↑s 0 = x✝
val✝ : α
f0 : ↑s 0 = some val✝
h' : val✝ = a
⊢ ↑s Nat.zero = ↑(pure a) Nat.zero
[PROOFSTEP]
rwa [h'] at f0 
[GOAL]
case some.a.h.succ
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
x✝ : Option α
f0✝ : ↑s 0 = x✝
val✝ : α
f0 : ↑s 0 = some val✝
h :
  (match some val✝ with
    | none => Sum.inr (tail s)
    | some a => Sum.inl a) =
    Sum.inl a
n : ℕ
IH : ↑s n = ↑(pure a) n
⊢ ↑s (Nat.succ n) = ↑(pure a) (Nat.succ n)
[PROOFSTEP]
exact s.2 IH
[GOAL]
α : Type u
β : Type v
γ : Type w
s s' : Computation α
⊢ destruct s = Sum.inr s' → s = think s'
[PROOFSTEP]
dsimp [destruct]
[GOAL]
α : Type u
β : Type v
γ : Type w
s s' : Computation α
⊢ (match ↑s 0 with
      | none => Sum.inr (tail s)
      | some a => Sum.inl a) =
      Sum.inr s' →
    s = think s'
[PROOFSTEP]
induction' f0 : s.1 0 with a'
[GOAL]
case none
α : Type u
β : Type v
γ : Type w
s s' : Computation α
x✝ : Option α
f0✝ : ↑s 0 = x✝
f0 : ↑s 0 = none
⊢ (match none with
      | none => Sum.inr (tail s)
      | some a => Sum.inl a) =
      Sum.inr s' →
    s = think s'
[PROOFSTEP]
intro h
[GOAL]
case some
α : Type u
β : Type v
γ : Type w
s s' : Computation α
x✝ : Option α
f0✝ : ↑s 0 = x✝
a' : α
f0 : ↑s 0 = some a'
⊢ (match some a' with
      | none => Sum.inr (tail s)
      | some a => Sum.inl a) =
      Sum.inr s' →
    s = think s'
[PROOFSTEP]
intro h
[GOAL]
case none
α : Type u
β : Type v
γ : Type w
s s' : Computation α
x✝ : Option α
f0✝ : ↑s 0 = x✝
f0 : ↑s 0 = none
h :
  (match none with
    | none => Sum.inr (tail s)
    | some a => Sum.inl a) =
    Sum.inr s'
⊢ s = think s'
[PROOFSTEP]
injection h with h'
[GOAL]
case none
α : Type u
β : Type v
γ : Type w
s s' : Computation α
x✝ : Option α
f0✝ : ↑s 0 = x✝
f0 : ↑s 0 = none
h' : tail s = s'
⊢ s = think s'
[PROOFSTEP]
rw [← h']
[GOAL]
case none
α : Type u
β : Type v
γ : Type w
s s' : Computation α
x✝ : Option α
f0✝ : ↑s 0 = x✝
f0 : ↑s 0 = none
h' : tail s = s'
⊢ s = think (tail s)
[PROOFSTEP]
cases' s with f al
[GOAL]
case none.mk
α : Type u
β : Type v
γ : Type w
s' : Computation α
x✝ : Option α
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
f0✝ : ↑{ val := f, property := al } 0 = x✝
f0 : ↑{ val := f, property := al } 0 = none
h' : tail { val := f, property := al } = s'
⊢ { val := f, property := al } = think (tail { val := f, property := al })
[PROOFSTEP]
apply Subtype.eq
[GOAL]
case none.mk.a
α : Type u
β : Type v
γ : Type w
s' : Computation α
x✝ : Option α
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
f0✝ : ↑{ val := f, property := al } 0 = x✝
f0 : ↑{ val := f, property := al } 0 = none
h' : tail { val := f, property := al } = s'
⊢ ↑{ val := f, property := al } = ↑(think (tail { val := f, property := al }))
[PROOFSTEP]
dsimp [think, tail]
[GOAL]
case none.mk.a
α : Type u
β : Type v
γ : Type w
s' : Computation α
x✝ : Option α
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
f0✝ : ↑{ val := f, property := al } 0 = x✝
f0 : ↑{ val := f, property := al } 0 = none
h' : tail { val := f, property := al } = s'
⊢ f = Stream'.cons none (Stream'.tail f)
[PROOFSTEP]
rw [← f0]
[GOAL]
case none.mk.a
α : Type u
β : Type v
γ : Type w
s' : Computation α
x✝ : Option α
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
f0✝ : ↑{ val := f, property := al } 0 = x✝
f0 : ↑{ val := f, property := al } 0 = none
h' : tail { val := f, property := al } = s'
⊢ f = Stream'.cons (↑{ val := f, property := al } 0) (Stream'.tail f)
[PROOFSTEP]
exact (Stream'.eta f).symm
[GOAL]
case some
α : Type u
β : Type v
γ : Type w
s s' : Computation α
x✝ : Option α
f0✝ : ↑s 0 = x✝
a' : α
f0 : ↑s 0 = some a'
h :
  (match some a' with
    | none => Sum.inr (tail s)
    | some a => Sum.inl a) =
    Sum.inr s'
⊢ s = think s'
[PROOFSTEP]
contradiction
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
⊢ tail (think s) = s
[PROOFSTEP]
cases' s with f al
[GOAL]
case mk
α : Type u
β : Type v
γ : Type w
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
⊢ tail (think { val := f, property := al }) = { val := f, property := al }
[PROOFSTEP]
apply Subtype.eq
[GOAL]
case mk.a
α : Type u
β : Type v
γ : Type w
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
⊢ ↑(tail (think { val := f, property := al })) = ↑{ val := f, property := al }
[PROOFSTEP]
dsimp [tail, think]
[GOAL]
α : Type u
β : Type v
γ : Type w
C : Computation α → Sort v
s : Computation α
h1 : (a : α) → C (pure a)
h2 : (s : Computation α) → C (think s)
v : α
H : destruct s = Sum.inl v
⊢ C s
[PROOFSTEP]
rw [destruct_eq_pure H]
[GOAL]
α : Type u
β : Type v
γ : Type w
C : Computation α → Sort v
s : Computation α
h1 : (a : α) → C (pure a)
h2 : (s : Computation α) → C (think s)
v : α
H : destruct s = Sum.inl v
⊢ C (pure v)
[PROOFSTEP]
apply h1
[GOAL]
α : Type u
β : Type v
γ : Type w
C : Computation α → Sort v
s : Computation α
h1 : (a : α) → C (pure a)
h2 : (s : Computation α) → C (think s)
v : Computation α
a : Stream' (Option α)
s' : ∀ ⦃n : ℕ⦄ ⦃a_1 : α⦄, a n = some a_1 → a (n + 1) = some a_1
H : destruct s = Sum.inr { val := a, property := s' }
⊢ C s
[PROOFSTEP]
rw [destruct_eq_think H]
[GOAL]
α : Type u
β : Type v
γ : Type w
C : Computation α → Sort v
s : Computation α
h1 : (a : α) → C (pure a)
h2 : (s : Computation α) → C (think s)
v : Computation α
a : Stream' (Option α)
s' : ∀ ⦃n : ℕ⦄ ⦃a_1 : α⦄, a n = some a_1 → a (n + 1) = some a_1
H : destruct s = Sum.inr { val := a, property := s' }
⊢ C (think { val := a, property := s' })
[PROOFSTEP]
apply h2
[GOAL]
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
⊢ Computation α
[PROOFSTEP]
refine' ⟨Stream'.corec' (Corec.f f) (Sum.inr b), fun n a' h => _⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
n : ℕ
a' : α
h : Stream'.corec' (Corec.f f) (Sum.inr b) n = some a'
⊢ Stream'.corec' (Corec.f f) (Sum.inr b) (n + 1) = some a'
[PROOFSTEP]
rw [Stream'.corec'_eq]
[GOAL]
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
n : ℕ
a' : α
h : Stream'.corec' (Corec.f f) (Sum.inr b) n = some a'
⊢ Stream'.cons (Corec.f f (Sum.inr b)).fst (Stream'.corec' (Corec.f f) (Corec.f f (Sum.inr b)).snd) (n + 1) = some a'
[PROOFSTEP]
change Stream'.corec' (Corec.f f) (Corec.f f (Sum.inr b)).2 n = some a'
[GOAL]
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
n : ℕ
a' : α
h : Stream'.corec' (Corec.f f) (Sum.inr b) n = some a'
⊢ Stream'.corec' (Corec.f f) (Corec.f f (Sum.inr b)).snd n = some a'
[PROOFSTEP]
revert h
[GOAL]
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
n : ℕ
a' : α
⊢ Stream'.corec' (Corec.f f) (Sum.inr b) n = some a' →
    Stream'.corec' (Corec.f f) (Corec.f f (Sum.inr b)).snd n = some a'
[PROOFSTEP]
generalize Sum.inr b = o
[GOAL]
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
n : ℕ
a' : α
o : α ⊕ β
⊢ Stream'.corec' (Corec.f f) o n = some a' → Stream'.corec' (Corec.f f) (Corec.f f o).snd n = some a'
[PROOFSTEP]
revert o
[GOAL]
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
n : ℕ
a' : α
⊢ ∀ (o : α ⊕ β), Stream'.corec' (Corec.f f) o n = some a' → Stream'.corec' (Corec.f f) (Corec.f f o).snd n = some a'
[PROOFSTEP]
induction' n with n IH
[GOAL]
case zero
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
a' : α
⊢ ∀ (o : α ⊕ β),
    Stream'.corec' (Corec.f f) o Nat.zero = some a' → Stream'.corec' (Corec.f f) (Corec.f f o).snd Nat.zero = some a'
[PROOFSTEP]
intro o
[GOAL]
case succ
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
a' : α
n : ℕ
IH : ∀ (o : α ⊕ β), Stream'.corec' (Corec.f f) o n = some a' → Stream'.corec' (Corec.f f) (Corec.f f o).snd n = some a'
⊢ ∀ (o : α ⊕ β),
    Stream'.corec' (Corec.f f) o (Nat.succ n) = some a' →
      Stream'.corec' (Corec.f f) (Corec.f f o).snd (Nat.succ n) = some a'
[PROOFSTEP]
intro o
[GOAL]
case zero
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
a' : α
o : α ⊕ β
⊢ Stream'.corec' (Corec.f f) o Nat.zero = some a' → Stream'.corec' (Corec.f f) (Corec.f f o).snd Nat.zero = some a'
[PROOFSTEP]
change (Corec.f f o).1 = some a' → (Corec.f f (Corec.f f o).2).1 = some a'
[GOAL]
case zero
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
a' : α
o : α ⊕ β
⊢ (Corec.f f o).fst = some a' → (Corec.f f (Corec.f f o).snd).fst = some a'
[PROOFSTEP]
cases' o with _ b
[GOAL]
case zero.inl
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
a' val✝ : α
⊢ (Corec.f f (Sum.inl val✝)).fst = some a' → (Corec.f f (Corec.f f (Sum.inl val✝)).snd).fst = some a'
[PROOFSTEP]
intro h
[GOAL]
case zero.inr
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b✝ : β
a' : α
b : β
⊢ (Corec.f f (Sum.inr b)).fst = some a' → (Corec.f f (Corec.f f (Sum.inr b)).snd).fst = some a'
[PROOFSTEP]
intro h
[GOAL]
case zero.inl
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
a' val✝ : α
h : (Corec.f f (Sum.inl val✝)).fst = some a'
⊢ (Corec.f f (Corec.f f (Sum.inl val✝)).snd).fst = some a'
[PROOFSTEP]
exact h
[GOAL]
case zero.inr
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b✝ : β
a' : α
b : β
h : (Corec.f f (Sum.inr b)).fst = some a'
⊢ (Corec.f f (Corec.f f (Sum.inr b)).snd).fst = some a'
[PROOFSTEP]
unfold Corec.f at *
[GOAL]
case zero.inr
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b✝ : β
a' : α
b : β
h :
  (match Sum.inr b with
      | Sum.inl a => (some a, Sum.inl a)
      | Sum.inr b =>
        (match f b with
          | Sum.inl a => some a
          | Sum.inr val => none,
          f b)).fst =
    some a'
⊢ (match
        (match Sum.inr b with
          | Sum.inl a => (some a, Sum.inl a)
          | Sum.inr b =>
            (match f b with
              | Sum.inl a => some a
              | Sum.inr val => none,
              f b)).snd with
      | Sum.inl a => (some a, Sum.inl a)
      | Sum.inr b =>
        (match f b with
          | Sum.inl a => some a
          | Sum.inr val => none,
          f b)).fst =
    some a'
[PROOFSTEP]
split
[GOAL]
case zero.inr.h_1
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b✝ : β
a' : α
b : β
h :
  (match Sum.inr b with
      | Sum.inl a => (some a, Sum.inl a)
      | Sum.inr b =>
        (match f b with
          | Sum.inl a => some a
          | Sum.inr val => none,
          f b)).fst =
    some a'
x✝ : α ⊕ β
a✝ : α
heq✝ :
  (match Sum.inr b with
      | Sum.inl a => (some a, Sum.inl a)
      | Sum.inr b =>
        (match f b with
          | Sum.inl a => some a
          | Sum.inr val => none,
          f b)).snd =
    Sum.inl a✝
⊢ (some a✝, Sum.inl a✝).fst = some a'
[PROOFSTEP]
simp_all
[GOAL]
case zero.inr.h_2
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b✝ : β
a' : α
b : β
h :
  (match Sum.inr b with
      | Sum.inl a => (some a, Sum.inl a)
      | Sum.inr b =>
        (match f b with
          | Sum.inl a => some a
          | Sum.inr val => none,
          f b)).fst =
    some a'
x✝ : α ⊕ β
val✝ : β
heq✝ :
  (match Sum.inr b with
      | Sum.inl a => (some a, Sum.inl a)
      | Sum.inr b =>
        (match f b with
          | Sum.inl a => some a
          | Sum.inr val => none,
          f b)).snd =
    Sum.inr val✝
⊢ (match f val✝ with
        | Sum.inl a => some a
        | Sum.inr val => none,
        f val✝).fst =
    some a'
[PROOFSTEP]
simp_all
[GOAL]
case succ
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
a' : α
n : ℕ
IH : ∀ (o : α ⊕ β), Stream'.corec' (Corec.f f) o n = some a' → Stream'.corec' (Corec.f f) (Corec.f f o).snd n = some a'
o : α ⊕ β
⊢ Stream'.corec' (Corec.f f) o (Nat.succ n) = some a' →
    Stream'.corec' (Corec.f f) (Corec.f f o).snd (Nat.succ n) = some a'
[PROOFSTEP]
rw [Stream'.corec'_eq (Corec.f f) (Corec.f f o).2, Stream'.corec'_eq (Corec.f f) o]
[GOAL]
case succ
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
a' : α
n : ℕ
IH : ∀ (o : α ⊕ β), Stream'.corec' (Corec.f f) o n = some a' → Stream'.corec' (Corec.f f) (Corec.f f o).snd n = some a'
o : α ⊕ β
⊢ Stream'.cons (Corec.f f o).fst (Stream'.corec' (Corec.f f) (Corec.f f o).snd) (Nat.succ n) = some a' →
    Stream'.cons (Corec.f f (Corec.f f o).snd).fst (Stream'.corec' (Corec.f f) (Corec.f f (Corec.f f o).snd).snd)
        (Nat.succ n) =
      some a'
[PROOFSTEP]
exact IH (Corec.f f o).2
[GOAL]
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
⊢ destruct (corec f b) = rmap (corec f) (f b)
[PROOFSTEP]
dsimp [corec, destruct]
[GOAL]
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
⊢ (match Stream'.corec' (Corec.f f) (Sum.inr b) 0 with
    | none =>
      Sum.inr
        (tail
          { val := Stream'.corec' (Corec.f f) (Sum.inr b),
            property :=
              (_ :
                ∀ (n : ℕ) (a' : α),
                  Stream'.corec' (Corec.f f) (Sum.inr b) n = some a' →
                    Stream'.corec' (Corec.f f) (Sum.inr b) (n + 1) = some a') })
    | some a => Sum.inl a) =
    match f b with
    | Sum.inl a => Sum.inl a
    | Sum.inr b =>
      Sum.inr
        { val := Stream'.corec' (Corec.f f) (Sum.inr b),
          property :=
            (_ :
              ∀ (n : ℕ) (a' : α),
                Stream'.corec' (Corec.f f) (Sum.inr b) n = some a' →
                  Stream'.corec' (Corec.f f) (Sum.inr b) (n + 1) = some a') }
[PROOFSTEP]
rw [show Stream'.corec' (Corec.f f) (Sum.inr b) 0 = Sum.rec Option.some (λ _ => none) (f b)
    by
    dsimp [Corec.f, Stream'.corec', Stream'.corec, Stream'.map, Stream'.nth, Stream'.iterate]
    match (f b) with
    | Sum.inl x => rfl
    | Sum.inr x => rfl]
[GOAL]
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
⊢ Stream'.corec' (Corec.f f) (Sum.inr b) 0 = Sum.rec some (fun x => none) (f b)
[PROOFSTEP]
dsimp [Corec.f, Stream'.corec', Stream'.corec, Stream'.map, Stream'.nth, Stream'.iterate]
[GOAL]
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
⊢ (match f b with
    | Sum.inl a => some a
    | Sum.inr val => none) =
    Sum.rec some (fun x => none) (f b)
[PROOFSTEP]
match (f b) with
| Sum.inl x => rfl
| Sum.inr x => rfl
[GOAL]
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
x : α
⊢ (match Sum.inl x with
    | Sum.inl a => some a
    | Sum.inr val => none) =
    Sum.rec some (fun x => none) (Sum.inl x)
[PROOFSTEP]
rfl
[GOAL]
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b x : β
⊢ (match Sum.inr x with
    | Sum.inl a => some a
    | Sum.inr val => none) =
    Sum.rec some (fun x => none) (Sum.inr x)
[PROOFSTEP]
rfl
[GOAL]
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
⊢ (match Sum.rec some (fun x => none) (f b) with
    | none =>
      Sum.inr
        (tail
          { val := Stream'.corec' (Corec.f f) (Sum.inr b),
            property :=
              (_ :
                ∀ (n : ℕ) (a' : α),
                  Stream'.corec' (Corec.f f) (Sum.inr b) n = some a' →
                    Stream'.corec' (Corec.f f) (Sum.inr b) (n + 1) = some a') })
    | some a => Sum.inl a) =
    match f b with
    | Sum.inl a => Sum.inl a
    | Sum.inr b =>
      Sum.inr
        { val := Stream'.corec' (Corec.f f) (Sum.inr b),
          property :=
            (_ :
              ∀ (n : ℕ) (a' : α),
                Stream'.corec' (Corec.f f) (Sum.inr b) n = some a' →
                  Stream'.corec' (Corec.f f) (Sum.inr b) (n + 1) = some a') }
[PROOFSTEP]
induction' h : f b with a b'
[GOAL]
case inl
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
x✝ : α ⊕ β
h✝ : f b = x✝
a : α
h : f b = Sum.inl a
⊢ (match Sum.rec some (fun x => none) (Sum.inl a) with
    | none =>
      Sum.inr
        (tail
          { val := Stream'.corec' (Corec.f f) (Sum.inr b),
            property :=
              (_ :
                ∀ (n : ℕ) (a' : α),
                  Stream'.corec' (Corec.f f) (Sum.inr b) n = some a' →
                    Stream'.corec' (Corec.f f) (Sum.inr b) (n + 1) = some a') })
    | some a => Sum.inl a) =
    match Sum.inl a with
    | Sum.inl a => Sum.inl a
    | Sum.inr b =>
      Sum.inr
        { val := Stream'.corec' (Corec.f f) (Sum.inr b),
          property :=
            (_ :
              ∀ (n : ℕ) (a' : α),
                Stream'.corec' (Corec.f f) (Sum.inr b) n = some a' →
                  Stream'.corec' (Corec.f f) (Sum.inr b) (n + 1) = some a') }
[PROOFSTEP]
rfl
[GOAL]
case inr
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
x✝ : α ⊕ β
h✝ : f b = x✝
b' : β
h : f b = Sum.inr b'
⊢ (match Sum.rec some (fun x => none) (Sum.inr b') with
    | none =>
      Sum.inr
        (tail
          { val := Stream'.corec' (Corec.f f) (Sum.inr b),
            property :=
              (_ :
                ∀ (n : ℕ) (a' : α),
                  Stream'.corec' (Corec.f f) (Sum.inr b) n = some a' →
                    Stream'.corec' (Corec.f f) (Sum.inr b) (n + 1) = some a') })
    | some a => Sum.inl a) =
    match Sum.inr b' with
    | Sum.inl a => Sum.inl a
    | Sum.inr b =>
      Sum.inr
        { val := Stream'.corec' (Corec.f f) (Sum.inr b),
          property :=
            (_ :
              ∀ (n : ℕ) (a' : α),
                Stream'.corec' (Corec.f f) (Sum.inr b) n = some a' →
                  Stream'.corec' (Corec.f f) (Sum.inr b) (n + 1) = some a') }
[PROOFSTEP]
dsimp [Corec.f, destruct]
[GOAL]
case inr
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
x✝ : α ⊕ β
h✝ : f b = x✝
b' : β
h : f b = Sum.inr b'
⊢ Sum.inr
      (tail
        {
          val :=
            Stream'.corec'
              (fun x =>
                match x with
                | Sum.inl a => (some a, Sum.inl a)
                | Sum.inr b =>
                  (match f b with
                    | Sum.inl a => some a
                    | Sum.inr val => none,
                    f b))
              (Sum.inr b),
          property :=
            (_ :
              ∀ (n : ℕ) (a' : α),
                Stream'.corec' (Corec.f f) (Sum.inr b) n = some a' →
                  Stream'.corec' (Corec.f f) (Sum.inr b) (n + 1) = some a') }) =
    Sum.inr
      {
        val :=
          Stream'.corec'
            (fun x =>
              match x with
              | Sum.inl a => (some a, Sum.inl a)
              | Sum.inr b =>
                (match f b with
                  | Sum.inl a => some a
                  | Sum.inr val => none,
                  f b))
            (Sum.inr b'),
        property :=
          (_ :
            ∀ (n : ℕ) (a' : α),
              Stream'.corec' (Corec.f f) (Sum.inr b') n = some a' →
                Stream'.corec' (Corec.f f) (Sum.inr b') (n + 1) = some a') }
[PROOFSTEP]
apply congr_arg
[GOAL]
case inr.h
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
x✝ : α ⊕ β
h✝ : f b = x✝
b' : β
h : f b = Sum.inr b'
⊢ tail
      {
        val :=
          Stream'.corec'
            (fun x =>
              match x with
              | Sum.inl a => (some a, Sum.inl a)
              | Sum.inr b =>
                (match f b with
                  | Sum.inl a => some a
                  | Sum.inr val => none,
                  f b))
            (Sum.inr b),
        property :=
          (_ :
            ∀ (n : ℕ) (a' : α),
              Stream'.corec' (Corec.f f) (Sum.inr b) n = some a' →
                Stream'.corec' (Corec.f f) (Sum.inr b) (n + 1) = some a') } =
    {
      val :=
        Stream'.corec'
          (fun x =>
            match x with
            | Sum.inl a => (some a, Sum.inl a)
            | Sum.inr b =>
              (match f b with
                | Sum.inl a => some a
                | Sum.inr val => none,
                f b))
          (Sum.inr b'),
      property :=
        (_ :
          ∀ (n : ℕ) (a' : α),
            Stream'.corec' (Corec.f f) (Sum.inr b') n = some a' →
              Stream'.corec' (Corec.f f) (Sum.inr b') (n + 1) = some a') }
[PROOFSTEP]
apply Subtype.eq
[GOAL]
case inr.h.a
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
x✝ : α ⊕ β
h✝ : f b = x✝
b' : β
h : f b = Sum.inr b'
⊢ ↑(tail
        {
          val :=
            Stream'.corec'
              (fun x =>
                match x with
                | Sum.inl a => (some a, Sum.inl a)
                | Sum.inr b =>
                  (match f b with
                    | Sum.inl a => some a
                    | Sum.inr val => none,
                    f b))
              (Sum.inr b),
          property :=
            (_ :
              ∀ (n : ℕ) (a' : α),
                Stream'.corec' (Corec.f f) (Sum.inr b) n = some a' →
                  Stream'.corec' (Corec.f f) (Sum.inr b) (n + 1) = some a') }) =
    ↑{
        val :=
          Stream'.corec'
            (fun x =>
              match x with
              | Sum.inl a => (some a, Sum.inl a)
              | Sum.inr b =>
                (match f b with
                  | Sum.inl a => some a
                  | Sum.inr val => none,
                  f b))
            (Sum.inr b'),
        property :=
          (_ :
            ∀ (n : ℕ) (a' : α),
              Stream'.corec' (Corec.f f) (Sum.inr b') n = some a' →
                Stream'.corec' (Corec.f f) (Sum.inr b') (n + 1) = some a') }
[PROOFSTEP]
dsimp [corec, tail]
[GOAL]
case inr.h.a
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
x✝ : α ⊕ β
h✝ : f b = x✝
b' : β
h : f b = Sum.inr b'
⊢ Stream'.tail
      (Stream'.corec'
        (fun x =>
          match x with
          | Sum.inl a => (some a, Sum.inl a)
          | Sum.inr b =>
            (match f b with
              | Sum.inl a => some a
              | Sum.inr val => none,
              f b))
        (Sum.inr b)) =
    Stream'.corec'
      (fun x =>
        match x with
        | Sum.inl a => (some a, Sum.inl a)
        | Sum.inr b =>
          (match f b with
            | Sum.inl a => some a
            | Sum.inr val => none,
            f b))
      (Sum.inr b')
[PROOFSTEP]
rw [Stream'.corec'_eq, Stream'.tail_cons]
[GOAL]
case inr.h.a
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
x✝ : α ⊕ β
h✝ : f b = x✝
b' : β
h : f b = Sum.inr b'
⊢ Stream'.corec'
      (fun x =>
        match x with
        | Sum.inl a => (some a, Sum.inl a)
        | Sum.inr b =>
          (match f b with
            | Sum.inl a => some a
            | Sum.inr val => none,
            f b))
      (match Sum.inr b with
        | Sum.inl a => (some a, Sum.inl a)
        | Sum.inr b =>
          (match f b with
            | Sum.inl a => some a
            | Sum.inr val => none,
            f b)).snd =
    Stream'.corec'
      (fun x =>
        match x with
        | Sum.inl a => (some a, Sum.inl a)
        | Sum.inr b =>
          (match f b with
            | Sum.inl a => some a
            | Sum.inr val => none,
            f b))
      (Sum.inr b')
[PROOFSTEP]
dsimp [Corec.f]
[GOAL]
case inr.h.a
α : Type u
β : Type v
γ : Type w
f : β → α ⊕ β
b : β
x✝ : α ⊕ β
h✝ : f b = x✝
b' : β
h : f b = Sum.inr b'
⊢ Stream'.corec'
      (fun x =>
        match x with
        | Sum.inl a => (some a, Sum.inl a)
        | Sum.inr b =>
          (match f b with
            | Sum.inl a => some a
            | Sum.inr val => none,
            f b))
      (f b) =
    Stream'.corec'
      (fun x =>
        match x with
        | Sum.inl a => (some a, Sum.inl a)
        | Sum.inr b =>
          (match f b with
            | Sum.inl a => some a
            | Sum.inr val => none,
            f b))
      (Sum.inr b')
[PROOFSTEP]
rw [h]
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
⊢ s₁ = s₂
[PROOFSTEP]
apply Subtype.eq
[GOAL]
case a
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
⊢ ↑s₁ = ↑s₂
[PROOFSTEP]
apply Stream'.eq_of_bisim fun x y => ∃ s s' : Computation α, s.1 = x ∧ s'.1 = y ∧ R s s'
[GOAL]
case a.bisim
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
⊢ Stream'.IsBisimulation fun x y => ∃ s s', ↑s = x ∧ ↑s' = y ∧ R s s'
case a.a
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
⊢ ∃ s s', ↑s = ↑s₁ ∧ ↑s' = ↑s₂ ∧ R s s'
[PROOFSTEP]
dsimp [Stream'.IsBisimulation]
[GOAL]
case a.bisim
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
⊢ ∀ ⦃s₁ s₂ : Stream' (Option α)⦄,
    (∃ s s', ↑s = s₁ ∧ ↑s' = s₂ ∧ R s s') →
      Stream'.head s₁ = Stream'.head s₂ ∧ ∃ s s', ↑s = Stream'.tail s₁ ∧ ↑s' = Stream'.tail s₂ ∧ R s s'
case a.a
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
⊢ ∃ s s', ↑s = ↑s₁ ∧ ↑s' = ↑s₂ ∧ R s s'
[PROOFSTEP]
intro t₁ t₂ e
[GOAL]
case a.bisim
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
⊢ Stream'.head t₁ = Stream'.head t₂ ∧ ∃ s s', ↑s = Stream'.tail t₁ ∧ ↑s' = Stream'.tail t₂ ∧ R s s'
case a.a
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
⊢ ∃ s s', ↑s = ↑s₁ ∧ ↑s' = ↑s₂ ∧ R s s'
[PROOFSTEP]
exact
  match t₁, t₂, e with
  | _, _, ⟨s, s', rfl, rfl, r⟩ =>
    by
    suffices head s = head s' ∧ R (tail s) (tail s') from
      And.imp id (fun r => ⟨tail s, tail s', by cases s; rfl, by cases s'; rfl, r⟩) this
    have h := bisim r; revert r h
    apply recOn s _ _ <;> intro r' <;> apply recOn s' _ _ <;> intro a' r h
    · constructor <;> dsimp at h 
      · rw [h]
      · rw [h] at r 
        rw [tail_pure, tail_pure, h]
        assumption
    · rw [destruct_pure, destruct_think] at h 
      exact False.elim h
    · rw [destruct_pure, destruct_think] at h 
      exact False.elim h
    · simp at h 
      simp [*]
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
r : R s s'
⊢ Stream'.head ↑s = Stream'.head ↑s' ∧ ∃ s_1 s'_1, ↑s_1 = Stream'.tail ↑s ∧ ↑s'_1 = Stream'.tail ↑s' ∧ R s_1 s'_1
[PROOFSTEP]
suffices head s = head s' ∧ R (tail s) (tail s') from
  And.imp id (fun r => ⟨tail s, tail s', by cases s; rfl, by cases s'; rfl, r⟩) this
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝¹ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
r✝ : R s s'
this : head s = head s' ∧ R (tail s) (tail s')
r : R (tail s) (tail s')
⊢ ↑(tail s) = Stream'.tail ↑s
[PROOFSTEP]
cases s
[GOAL]
case mk
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝¹ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s' : Computation α
val✝ : Stream' (Option α)
property✝ : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, val✝ n = some a → val✝ (n + 1) = some a
r✝ : R { val := val✝, property := property✝ } s'
this : head { val := val✝, property := property✝ } = head s' ∧ R (tail { val := val✝, property := property✝ }) (tail s')
r : R (tail { val := val✝, property := property✝ }) (tail s')
⊢ ↑(tail { val := val✝, property := property✝ }) = Stream'.tail ↑{ val := val✝, property := property✝ }
[PROOFSTEP]
rfl
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝¹ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
r✝ : R s s'
this : head s = head s' ∧ R (tail s) (tail s')
r : R (tail s) (tail s')
⊢ ↑(tail s') = Stream'.tail ↑s'
[PROOFSTEP]
cases s'
[GOAL]
case mk
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝¹ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s : Computation α
val✝ : Stream' (Option α)
property✝ : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, val✝ n = some a → val✝ (n + 1) = some a
r✝ : R s { val := val✝, property := property✝ }
this : head s = head { val := val✝, property := property✝ } ∧ R (tail s) (tail { val := val✝, property := property✝ })
r : R (tail s) (tail { val := val✝, property := property✝ })
⊢ ↑(tail { val := val✝, property := property✝ }) = Stream'.tail ↑{ val := val✝, property := property✝ }
[PROOFSTEP]
rfl
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
r : R s s'
⊢ head s = head s' ∧ R (tail s) (tail s')
[PROOFSTEP]
have h := bisim r
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
r : R s s'
h : BisimO R (destruct s) (destruct s')
⊢ head s = head s' ∧ R (tail s) (tail s')
[PROOFSTEP]
revert r h
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
⊢ R s s' → BisimO R (destruct s) (destruct s') → head s = head s' ∧ R (tail s) (tail s')
[PROOFSTEP]
apply recOn s _ _
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
⊢ ∀ (a : α),
    R (pure a) s' → BisimO R (destruct (pure a)) (destruct s') → head (pure a) = head s' ∧ R (tail (pure a)) (tail s')
[PROOFSTEP]
intro r'
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
⊢ ∀ (s : Computation α),
    R (think s) s' →
      BisimO R (destruct (think s)) (destruct s') → head (think s) = head s' ∧ R (tail (think s)) (tail s')
[PROOFSTEP]
intro r'
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
r' : α
⊢ R (pure r') s' → BisimO R (destruct (pure r')) (destruct s') → head (pure r') = head s' ∧ R (tail (pure r')) (tail s')
[PROOFSTEP]
apply recOn s' _ _
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' r' : Computation α
⊢ R (think r') s' →
    BisimO R (destruct (think r')) (destruct s') → head (think r') = head s' ∧ R (tail (think r')) (tail s')
[PROOFSTEP]
apply recOn s' _ _
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
r' : α
⊢ ∀ (a : α),
    R (pure r') (pure a) →
      BisimO R (destruct (pure r')) (destruct (pure a)) →
        head (pure r') = head (pure a) ∧ R (tail (pure r')) (tail (pure a))
[PROOFSTEP]
intro a' r h
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
r' : α
⊢ ∀ (s : Computation α),
    R (pure r') (think s) →
      BisimO R (destruct (pure r')) (destruct (think s)) →
        head (pure r') = head (think s) ∧ R (tail (pure r')) (tail (think s))
[PROOFSTEP]
intro a' r h
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' r' : Computation α
⊢ ∀ (a : α),
    R (think r') (pure a) →
      BisimO R (destruct (think r')) (destruct (pure a)) →
        head (think r') = head (pure a) ∧ R (tail (think r')) (tail (pure a))
[PROOFSTEP]
intro a' r h
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' r' : Computation α
⊢ ∀ (s : Computation α),
    R (think r') (think s) →
      BisimO R (destruct (think r')) (destruct (think s)) →
        head (think r') = head (think s) ∧ R (tail (think r')) (tail (think s))
[PROOFSTEP]
intro a' r h
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
r' a' : α
r : R (pure r') (pure a')
h : BisimO R (destruct (pure r')) (destruct (pure a'))
⊢ head (pure r') = head (pure a') ∧ R (tail (pure r')) (tail (pure a'))
[PROOFSTEP]
constructor
[GOAL]
case left
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
r' a' : α
r : R (pure r') (pure a')
h : BisimO R (destruct (pure r')) (destruct (pure a'))
⊢ head (pure r') = head (pure a')
[PROOFSTEP]
dsimp at h 
[GOAL]
case right
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
r' a' : α
r : R (pure r') (pure a')
h : BisimO R (destruct (pure r')) (destruct (pure a'))
⊢ R (tail (pure r')) (tail (pure a'))
[PROOFSTEP]
dsimp at h 
[GOAL]
case left
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
r' a' : α
r : R (pure r') (pure a')
h : r' = a'
⊢ head (pure r') = head (pure a')
[PROOFSTEP]
rw [h]
[GOAL]
case right
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
r' a' : α
r : R (pure r') (pure a')
h : r' = a'
⊢ R (tail (pure r')) (tail (pure a'))
[PROOFSTEP]
rw [h] at r 
[GOAL]
case right
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
r' a' : α
r : R (pure a') (pure a')
h : r' = a'
⊢ R (tail (pure r')) (tail (pure a'))
[PROOFSTEP]
rw [tail_pure, tail_pure, h]
[GOAL]
case right
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
r' a' : α
r : R (pure a') (pure a')
h : r' = a'
⊢ R (pure a') (pure a')
[PROOFSTEP]
assumption
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
r' : α
a' : Computation α
r : R (pure r') (think a')
h : BisimO R (destruct (pure r')) (destruct (think a'))
⊢ head (pure r') = head (think a') ∧ R (tail (pure r')) (tail (think a'))
[PROOFSTEP]
rw [destruct_pure, destruct_think] at h 
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' : Computation α
r' : α
a' : Computation α
r : R (pure r') (think a')
h : BisimO R (Sum.inl r') (Sum.inr a')
⊢ head (pure r') = head (think a') ∧ R (tail (pure r')) (tail (think a'))
[PROOFSTEP]
exact False.elim h
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' r' : Computation α
a' : α
r : R (think r') (pure a')
h : BisimO R (destruct (think r')) (destruct (pure a'))
⊢ head (think r') = head (pure a') ∧ R (tail (think r')) (tail (pure a'))
[PROOFSTEP]
rw [destruct_pure, destruct_think] at h 
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' r' : Computation α
a' : α
r : R (think r') (pure a')
h : BisimO R (Sum.inr r') (Sum.inl a')
⊢ head (think r') = head (pure a') ∧ R (tail (think r')) (tail (pure a'))
[PROOFSTEP]
exact False.elim h
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' r' a' : Computation α
r : R (think r') (think a')
h : BisimO R (destruct (think r')) (destruct (think a'))
⊢ head (think r') = head (think a') ∧ R (tail (think r')) (tail (think a'))
[PROOFSTEP]
simp at h 
[GOAL]
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r✝ : R s₁ s₂
t₁ t₂ : Stream' (Option α)
e : ∃ s s', ↑s = t₁ ∧ ↑s' = t₂ ∧ R s s'
s s' r' a' : Computation α
r : R (think r') (think a')
h : R r' a'
⊢ head (think r') = head (think a') ∧ R (tail (think r')) (tail (think a'))
[PROOFSTEP]
simp [*]
[GOAL]
case a.a
α : Type u
β : Type v
γ : Type w
R : Computation α → Computation α → Prop
bisim : IsBisimulation R
s₁ s₂ : Computation α
r : R s₁ s₂
⊢ ∃ s s', ↑s = ↑s₁ ∧ ↑s' = ↑s₂ ∧ R s s'
[PROOFSTEP]
exact ⟨s₁, s₂, rfl, rfl, r⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
m n : ℕ
h : m ≤ n
⊢ ↑s m = some a → ↑s n = some a
[PROOFSTEP]
cases' s with f al
[GOAL]
case mk
α : Type u
β : Type v
γ : Type w
a : α
m n : ℕ
h : m ≤ n
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
⊢ ↑{ val := f, property := al } m = some a → ↑{ val := f, property := al } n = some a
[PROOFSTEP]
induction' h with n _ IH
[GOAL]
case mk.refl
α : Type u
β : Type v
γ : Type w
a : α
m n : ℕ
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
⊢ ↑{ val := f, property := al } m = some a → ↑{ val := f, property := al } m = some a
case mk.step
α : Type u
β : Type v
γ : Type w
a : α
m n✝ : ℕ
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
n : ℕ
a✝ : Nat.le m n
IH : ↑{ val := f, property := al } m = some a → ↑{ val := f, property := al } n = some a
⊢ ↑{ val := f, property := al } m = some a → ↑{ val := f, property := al } (Nat.succ n) = some a
[PROOFSTEP]
exacts [id, fun h2 => al (IH h2)]
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
a b : α
m : ℕ
ha : (fun b => some a = b) (Stream'.nth (↑s) m)
n : ℕ
hb : (fun b_1 => some b = b_1) (Stream'.nth (↑s) n)
⊢ a = b
[PROOFSTEP]
injection (le_stable s (le_max_left m n) ha.symm).symm.trans (le_stable s (le_max_right m n) hb.symm)
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
x✝ : Terminates s
a : α
n : ℕ
h : (fun b => some a = b) (Stream'.nth (↑s) n)
⊢ Option.isSome (↑s n) = true
[PROOFSTEP]
dsimp [Stream'.nth] at h 
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
x✝ : Terminates s
a : α
n : ℕ
h : some a = ↑s n
⊢ Option.isSome (↑s n) = true
[PROOFSTEP]
rw [← h]
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
x✝ : Terminates s
a : α
n : ℕ
h : some a = ↑s n
⊢ Option.isSome (some a) = true
[PROOFSTEP]
exact rfl
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
n : ℕ
h : (fun b => some a = b) (Stream'.nth (↑(think s)) n)
⊢ a ∈ s
[PROOFSTEP]
cases' n with n'
[GOAL]
case zero
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
h : some a = Stream'.nth (↑(think s)) Nat.zero
⊢ a ∈ s
case succ
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
n' : ℕ
h : some a = Stream'.nth (↑(think s)) (Nat.succ n')
⊢ a ∈ s
[PROOFSTEP]
contradiction
[GOAL]
case succ
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
n' : ℕ
h : some a = Stream'.nth (↑(think s)) (Nat.succ n')
⊢ a ∈ s
[PROOFSTEP]
exact ⟨n', h⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
a : α
x✝ : a ∈ empty α
n : ℕ
h : (fun b => some a = b) (Stream'.nth (↑(empty α)) n)
⊢ False
[PROOFSTEP]
contradiction
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
H : ¬Terminates s
⊢ s = empty α
[PROOFSTEP]
apply Subtype.eq
[GOAL]
case a
α : Type u
β : Type v
γ : Type w
s : Computation α
H : ¬Terminates s
⊢ ↑s = ↑(empty α)
[PROOFSTEP]
funext n
[GOAL]
case a.h
α : Type u
β : Type v
γ : Type w
s : Computation α
H : ¬Terminates s
n : ℕ
⊢ ↑s n = ↑(empty α) n
[PROOFSTEP]
induction' h : s.val n with _
[GOAL]
case a.h.none
α : Type u
β : Type v
γ : Type w
s : Computation α
H : ¬Terminates s
n : ℕ
x✝ : Option α
h✝ : ↑s n = x✝
h : ↑s n = none
⊢ none = ↑(empty α) n
[PROOFSTEP]
rfl
[GOAL]
case a.h.some
α : Type u
β : Type v
γ : Type w
s : Computation α
H : ¬Terminates s
n : ℕ
x✝ : Option α
h✝ : ↑s n = x✝
val✝ : α
h : ↑s n = some val✝
⊢ some val✝ = ↑(empty α) n
[PROOFSTEP]
refine' absurd _ H
[GOAL]
case a.h.some
α : Type u
β : Type v
γ : Type w
s : Computation α
H : ¬Terminates s
n : ℕ
x✝ : Option α
h✝ : ↑s n = x✝
val✝ : α
h : ↑s n = some val✝
⊢ Terminates s
[PROOFSTEP]
exact ⟨⟨_, _, h.symm⟩⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
h : Terminates s
a : α
⊢ get s = a → a ∈ s
[PROOFSTEP]
intro h
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
h✝ : Terminates s
a : α
h : get s = a
⊢ a ∈ s
[PROOFSTEP]
rw [← h]
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
h✝ : Terminates s
a : α
h : get s = a
⊢ get s ∈ s
[PROOFSTEP]
apply get_mem
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
h : Terminates s
a : α
p : s ~> a
⊢ a ∈ s
[PROOFSTEP]
cases' h with h
[GOAL]
case mk
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
p : s ~> a
h : ∃ a, a ∈ s
⊢ a ∈ s
[PROOFSTEP]
cases' h with a' h
[GOAL]
case mk.intro
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
p : s ~> a
a' : α
h : a' ∈ s
⊢ a ∈ s
[PROOFSTEP]
rw [p h]
[GOAL]
case mk.intro
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
p : s ~> a
a' : α
h : a' ∈ s
⊢ a' ∈ s
[PROOFSTEP]
exact h
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
T : Terminates s
a : α
h : a ∈ s
⊢ Results s a (length s)
[PROOFSTEP]
rw [← get_eq_of_mem _ h]
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
T : Terminates s
a : α
h : a ∈ s
⊢ Results s (get s) (length s)
[PROOFSTEP]
apply results_of_terminates
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
a b : α
m n : ℕ
h1 : Results s a m
h2 : Results s b n
⊢ m = n
[PROOFSTEP]
haveI := h1.terminates
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
a b : α
m n : ℕ
h1 : Results s a m
h2 : Results s b n
this : Terminates s
⊢ m = n
[PROOFSTEP]
haveI := h2.terminates
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
a b : α
m n : ℕ
h1 : Results s a m
h2 : Results s b n
this✝ this : Terminates s
⊢ m = n
[PROOFSTEP]
rw [← h1.length, h2.length]
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
h : Terminates s
⊢ length (think s) = length s + 1
[PROOFSTEP]
apply le_antisymm
[GOAL]
case a
α : Type u
β : Type v
γ : Type w
s : Computation α
h : Terminates s
⊢ length (think s) ≤ length s + 1
[PROOFSTEP]
exact Nat.find_min' _ (Nat.find_spec ((terminates_def _).1 h))
[GOAL]
case a
α : Type u
β : Type v
γ : Type w
s : Computation α
h : Terminates s
⊢ length s + 1 ≤ length (think s)
[PROOFSTEP]
have : (Option.isSome ((think s).val (length (think s))) : Prop) :=
  Nat.find_spec ((terminates_def _).1 s.think_terminates)
[GOAL]
case a
α : Type u
β : Type v
γ : Type w
s : Computation α
h : Terminates s
this : Option.isSome (↑(think s) (length (think s))) = true
⊢ length s + 1 ≤ length (think s)
[PROOFSTEP]
revert this
[GOAL]
case a
α : Type u
β : Type v
γ : Type w
s : Computation α
h : Terminates s
⊢ Option.isSome (↑(think s) (length (think s))) = true → length s + 1 ≤ length (think s)
[PROOFSTEP]
cases' length (think s) with n
[GOAL]
case a.zero
α : Type u
β : Type v
γ : Type w
s : Computation α
h : Terminates s
⊢ Option.isSome (↑(think s) Nat.zero) = true → length s + 1 ≤ Nat.zero
[PROOFSTEP]
intro this
[GOAL]
case a.succ
α : Type u
β : Type v
γ : Type w
s : Computation α
h : Terminates s
n : ℕ
⊢ Option.isSome (↑(think s) (Nat.succ n)) = true → length s + 1 ≤ Nat.succ n
[PROOFSTEP]
intro this
[GOAL]
case a.zero
α : Type u
β : Type v
γ : Type w
s : Computation α
h : Terminates s
this : Option.isSome (↑(think s) Nat.zero) = true
⊢ length s + 1 ≤ Nat.zero
[PROOFSTEP]
simp [think, Stream'.cons] at this 
[GOAL]
case a.succ
α : Type u
β : Type v
γ : Type w
s : Computation α
h : Terminates s
n : ℕ
this : Option.isSome (↑(think s) (Nat.succ n)) = true
⊢ length s + 1 ≤ Nat.succ n
[PROOFSTEP]
apply Nat.succ_le_succ
[GOAL]
case a.succ.a
α : Type u
β : Type v
γ : Type w
s : Computation α
h : Terminates s
n : ℕ
this : Option.isSome (↑(think s) (Nat.succ n)) = true
⊢ length s ≤ n
[PROOFSTEP]
apply Nat.find_min'
[GOAL]
case a.succ.a.h
α : Type u
β : Type v
γ : Type w
s : Computation α
h : Terminates s
n : ℕ
this : Option.isSome (↑(think s) (Nat.succ n)) = true
⊢ Option.isSome (↑s n) = true
[PROOFSTEP]
apply this
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
n : ℕ
h : Results s a n
this : Terminates s
⊢ length (think s) = n + 1
[PROOFSTEP]
rw [length_think, h.length]
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
n : ℕ
h : Results (think s) a n
⊢ ∃ m, Results s a m ∧ n = m + 1
[PROOFSTEP]
haveI := of_think_terminates h.terminates
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
n : ℕ
h : Results (think s) a n
this : Terminates s
⊢ ∃ m, Results s a m ∧ n = m + 1
[PROOFSTEP]
have := results_of_terminates' _ (of_think_mem h.mem)
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
n : ℕ
h : Results (think s) a n
this✝ : Terminates s
this : Results s a (length s)
⊢ ∃ m, Results s a m ∧ n = m + 1
[PROOFSTEP]
exact ⟨_, this, Results.len_unique h (results_think this)⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
n : ℕ
h : Results (think s) a (n + 1)
⊢ Results s a n
[PROOFSTEP]
let ⟨n', r, e⟩ := of_results_think h
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
n : ℕ
h : Results (think s) a (n + 1)
n' : ℕ
r : Results s a n'
e : n + 1 = n' + 1
⊢ Results s a n
[PROOFSTEP]
injection e with h'
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
n : ℕ
h : Results (think s) a (n + 1)
n' : ℕ
r : Results s a n'
h' : Nat.add n 0 = Nat.add n' 0
⊢ Results s a n
[PROOFSTEP]
rw [Nat.add, Nat.add] at h' 
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
n : ℕ
h : Results (think s) a (n + 1)
n' : ℕ
r : Results s a n'
h' : n = n'
⊢ Results s a n
[PROOFSTEP]
rwa [h']
[GOAL]
α : Type u
β : Type v
γ : Type w
a : α
n : ℕ
⊢ Results (thinkN (pure a) n) a n
[PROOFSTEP]
have := results_thinkN n (results_pure a)
[GOAL]
α : Type u
β : Type v
γ : Type w
a : α
n : ℕ
this : Results (thinkN (pure a) n) a (0 + n)
⊢ Results (thinkN (pure a) n) a n
[PROOFSTEP]
rwa [Nat.zero_add] at this 
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
a : α
n : ℕ
h : Results s a n
⊢ s = thinkN (pure a) n
[PROOFSTEP]
revert s
[GOAL]
α : Type u
β : Type v
γ : Type w
a : α
n : ℕ
⊢ ∀ {s : Computation α}, Results s a n → s = thinkN (pure a) n
[PROOFSTEP]
induction' n with n IH
[GOAL]
case zero
α : Type u
β : Type v
γ : Type w
a : α
⊢ ∀ {s : Computation α}, Results s a Nat.zero → s = thinkN (pure a) Nat.zero
[PROOFSTEP]
intro s
[GOAL]
case succ
α : Type u
β : Type v
γ : Type w
a : α
n : ℕ
IH : ∀ {s : Computation α}, Results s a n → s = thinkN (pure a) n
⊢ ∀ {s : Computation α}, Results s a (Nat.succ n) → s = thinkN (pure a) (Nat.succ n)
[PROOFSTEP]
intro s
[GOAL]
case zero
α : Type u
β : Type v
γ : Type w
a : α
s : Computation α
⊢ Results s a Nat.zero → s = thinkN (pure a) Nat.zero
[PROOFSTEP]
apply recOn s (fun a' => _) fun s => _
[GOAL]
case succ
α : Type u
β : Type v
γ : Type w
a : α
n : ℕ
IH : ∀ {s : Computation α}, Results s a n → s = thinkN (pure a) n
s : Computation α
⊢ Results s a (Nat.succ n) → s = thinkN (pure a) (Nat.succ n)
[PROOFSTEP]
apply recOn s (fun a' => _) fun s => _
[GOAL]
α : Type u
β : Type v
γ : Type w
a : α
s : Computation α
⊢ ∀ (a' : α), Results (pure a') a Nat.zero → pure a' = thinkN (pure a) Nat.zero
[PROOFSTEP]
intro a h
[GOAL]
α : Type u
β : Type v
γ : Type w
a : α
s : Computation α
⊢ ∀ (s : Computation α), Results (think s) a Nat.zero → think s = thinkN (pure a) Nat.zero
[PROOFSTEP]
intro a h
[GOAL]
α : Type u
β : Type v
γ : Type w
a : α
n : ℕ
IH : ∀ {s : Computation α}, Results s a n → s = thinkN (pure a) n
s : Computation α
⊢ ∀ (a' : α), Results (pure a') a (Nat.succ n) → pure a' = thinkN (pure a) (Nat.succ n)
[PROOFSTEP]
intro a h
[GOAL]
α : Type u
β : Type v
γ : Type w
a : α
n : ℕ
IH : ∀ {s : Computation α}, Results s a n → s = thinkN (pure a) n
s : Computation α
⊢ ∀ (s : Computation α), Results (think s) a (Nat.succ n) → think s = thinkN (pure a) (Nat.succ n)
[PROOFSTEP]
intro a h
[GOAL]
α : Type u
β : Type v
γ : Type w
a✝ : α
s : Computation α
a : α
h : Results (pure a) a✝ Nat.zero
⊢ pure a = thinkN (pure a✝) Nat.zero
[PROOFSTEP]
rw [← eq_of_pure_mem h.mem]
[GOAL]
α : Type u
β : Type v
γ : Type w
a✝ : α
s : Computation α
a : α
h : Results (pure a) a✝ Nat.zero
⊢ pure a✝ = thinkN (pure a✝) Nat.zero
[PROOFSTEP]
rfl
[GOAL]
α : Type u
β : Type v
γ : Type w
a✝ : α
s a : Computation α
h : Results (think a) a✝ Nat.zero
⊢ think a = thinkN (pure a✝) Nat.zero
[PROOFSTEP]
cases' of_results_think h with n h
[GOAL]
case intro
α : Type u
β : Type v
γ : Type w
a✝ : α
s a : Computation α
h✝ : Results (think a) a✝ Nat.zero
n : ℕ
h : Results a a✝ n ∧ Nat.zero = n + 1
⊢ think a = thinkN (pure a✝) Nat.zero
[PROOFSTEP]
cases h
[GOAL]
case intro.intro
α : Type u
β : Type v
γ : Type w
a✝ : α
s a : Computation α
h : Results (think a) a✝ Nat.zero
n : ℕ
left✝ : Results a a✝ n
right✝ : Nat.zero = n + 1
⊢ think a = thinkN (pure a✝) Nat.zero
[PROOFSTEP]
contradiction
[GOAL]
α : Type u
β : Type v
γ : Type w
a✝ : α
n : ℕ
IH : ∀ {s : Computation α}, Results s a✝ n → s = thinkN (pure a✝) n
s : Computation α
a : α
h : Results (pure a) a✝ (Nat.succ n)
⊢ pure a = thinkN (pure a✝) (Nat.succ n)
[PROOFSTEP]
have := h.len_unique (results_pure _)
[GOAL]
α : Type u
β : Type v
γ : Type w
a✝ : α
n : ℕ
IH : ∀ {s : Computation α}, Results s a✝ n → s = thinkN (pure a✝) n
s : Computation α
a : α
h : Results (pure a) a✝ (Nat.succ n)
this : Nat.succ n = 0
⊢ pure a = thinkN (pure a✝) (Nat.succ n)
[PROOFSTEP]
contradiction
[GOAL]
α : Type u
β : Type v
γ : Type w
a✝ : α
n : ℕ
IH : ∀ {s : Computation α}, Results s a✝ n → s = thinkN (pure a✝) n
s a : Computation α
h : Results (think a) a✝ (Nat.succ n)
⊢ think a = thinkN (pure a✝) (Nat.succ n)
[PROOFSTEP]
rw [IH (results_think_iff.1 h)]
[GOAL]
α : Type u
β : Type v
γ : Type w
a✝ : α
n : ℕ
IH : ∀ {s : Computation α}, Results s a✝ n → s = thinkN (pure a✝) n
s a : Computation α
h : Results (think a) a✝ (Nat.succ n)
⊢ think (thinkN (pure a✝) n) = thinkN (pure a✝) (Nat.succ n)
[PROOFSTEP]
rfl
[GOAL]
α : Type u
β : Type v
γ : Type w
C : Computation α → Sort v
a : α
s : Computation α
M : a ∈ s
h1 : C (pure a)
h2 : (s : Computation α) → C s → C (think s)
⊢ C s
[PROOFSTEP]
haveI T := terminates_of_mem M
[GOAL]
α : Type u
β : Type v
γ : Type w
C : Computation α → Sort v
a : α
s : Computation α
M : a ∈ s
h1 : C (pure a)
h2 : (s : Computation α) → C s → C (think s)
T : Terminates s
⊢ C s
[PROOFSTEP]
rw [eq_thinkN' s, get_eq_of_mem s M]
[GOAL]
α : Type u
β : Type v
γ : Type w
C : Computation α → Sort v
a : α
s : Computation α
M : a ∈ s
h1 : C (pure a)
h2 : (s : Computation α) → C s → C (think s)
T : Terminates s
⊢ C (thinkN (pure a) (length s))
[PROOFSTEP]
generalize length s = n
[GOAL]
α : Type u
β : Type v
γ : Type w
C : Computation α → Sort v
a : α
s : Computation α
M : a ∈ s
h1 : C (pure a)
h2 : (s : Computation α) → C s → C (think s)
T : Terminates s
n : ℕ
⊢ C (thinkN (pure a) n)
[PROOFSTEP]
induction' n with n IH
[GOAL]
case zero
α : Type u
β : Type v
γ : Type w
C : Computation α → Sort v
a : α
s : Computation α
M : a ∈ s
h1 : C (pure a)
h2 : (s : Computation α) → C s → C (think s)
T : Terminates s
⊢ C (thinkN (pure a) Nat.zero)
case succ
α : Type u
β : Type v
γ : Type w
C : Computation α → Sort v
a : α
s : Computation α
M : a ∈ s
h1 : C (pure a)
h2 : (s : Computation α) → C s → C (think s)
T : Terminates s
n : ℕ
IH : C (thinkN (pure a) n)
⊢ C (thinkN (pure a) (Nat.succ n))
[PROOFSTEP]
exacts [h1, h2 _ IH]
[GOAL]
α : Type u
β : Type v
γ : Type w
f : α → β
s : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, s n = some a → s (n + 1) = some a
n : ℕ
b : β
⊢ Stream'.map (fun o => Option.casesOn o none (some ∘ f)) s n = some b →
    Stream'.map (fun o => Option.casesOn o none (some ∘ f)) s (n + 1) = some b
[PROOFSTEP]
dsimp [Stream'.map, Stream'.nth]
[GOAL]
α : Type u
β : Type v
γ : Type w
f : α → β
s : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, s n = some a → s (n + 1) = some a
n : ℕ
b : β
⊢ Option.rec none (fun val => some (f val)) (s n) = some b →
    Option.rec none (fun val => some (f val)) (s (n + 1)) = some b
[PROOFSTEP]
induction' e : s n with a
[GOAL]
case none
α : Type u
β : Type v
γ : Type w
f : α → β
s : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, s n = some a → s (n + 1) = some a
n : ℕ
b : β
x✝ : Option α
e✝ : s n = x✝
e : s n = none
⊢ Option.rec none (fun val => some (f val)) none = some b →
    Option.rec none (fun val => some (f val)) (s (n + 1)) = some b
[PROOFSTEP]
intro h
[GOAL]
case some
α : Type u
β : Type v
γ : Type w
f : α → β
s : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, s n = some a → s (n + 1) = some a
n : ℕ
b : β
x✝ : Option α
e✝ : s n = x✝
a : α
e : s n = some a
⊢ Option.rec none (fun val => some (f val)) (some a) = some b →
    Option.rec none (fun val => some (f val)) (s (n + 1)) = some b
[PROOFSTEP]
intro h
[GOAL]
case none
α : Type u
β : Type v
γ : Type w
f : α → β
s : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, s n = some a → s (n + 1) = some a
n : ℕ
b : β
x✝ : Option α
e✝ : s n = x✝
e : s n = none
h : Option.rec none (fun val => some (f val)) none = some b
⊢ Option.rec none (fun val => some (f val)) (s (n + 1)) = some b
[PROOFSTEP]
contradiction
[GOAL]
case some
α : Type u
β : Type v
γ : Type w
f : α → β
s : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, s n = some a → s (n + 1) = some a
n : ℕ
b : β
x✝ : Option α
e✝ : s n = x✝
a : α
e : s n = some a
h : Option.rec none (fun val => some (f val)) (some a) = some b
⊢ Option.rec none (fun val => some (f val)) (s (n + 1)) = some b
[PROOFSTEP]
rw [al e]
[GOAL]
case some
α : Type u
β : Type v
γ : Type w
f : α → β
s : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, s n = some a → s (n + 1) = some a
n : ℕ
b : β
x✝ : Option α
e✝ : s n = x✝
a : α
e : s n = some a
h : Option.rec none (fun val => some (f val)) (some a) = some b
⊢ Option.rec none (fun val => some (f val)) (some a) = some b
[PROOFSTEP]
exact h
[GOAL]
α : Type u
β : Type v
γ : Type w
f : α → β
s : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, s n = some a → s (n + 1) = some a
⊢ map f (think { val := s, property := al }) = think (map f { val := s, property := al })
[PROOFSTEP]
apply Subtype.eq
[GOAL]
case a
α : Type u
β : Type v
γ : Type w
f : α → β
s : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, s n = some a → s (n + 1) = some a
⊢ ↑(map f (think { val := s, property := al })) = ↑(think (map f { val := s, property := al }))
[PROOFSTEP]
dsimp [think, map]
[GOAL]
case a
α : Type u
β : Type v
γ : Type w
f : α → β
s : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, s n = some a → s (n + 1) = some a
⊢ Stream'.map (fun o => Option.rec none (fun val => some (f val)) o) (Stream'.cons none s) =
    Stream'.cons none (Stream'.map (fun o => Option.rec none (fun val => some (f val)) o) s)
[PROOFSTEP]
rw [Stream'.map_cons]
[GOAL]
α : Type u
β : Type v
γ : Type w
f : α → β
s : Computation α
⊢ destruct (map f s) = lmap f (rmap (map f) (destruct s))
[PROOFSTEP]
apply s.recOn
[GOAL]
case h1
α : Type u
β : Type v
γ : Type w
f : α → β
s : Computation α
⊢ ∀ (a : α), destruct (map f (pure a)) = lmap f (rmap (map f) (destruct (pure a)))
[PROOFSTEP]
intro
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
f : α → β
s : Computation α
⊢ ∀ (s : Computation α), destruct (map f (think s)) = lmap f (rmap (map f) (destruct (think s)))
[PROOFSTEP]
intro
[GOAL]
case h1
α : Type u
β : Type v
γ : Type w
f : α → β
s : Computation α
a✝ : α
⊢ destruct (map f (pure a✝)) = lmap f (rmap (map f) (destruct (pure a✝)))
[PROOFSTEP]
simp
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
f : α → β
s s✝ : Computation α
⊢ destruct (map f (think s✝)) = lmap f (rmap (map f) (destruct (think s✝)))
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
⊢ map id { val := f, property := al } = { val := f, property := al }
[PROOFSTEP]
apply Subtype.eq
[GOAL]
case a
α : Type u
β : Type v
γ : Type w
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
⊢ ↑(map id { val := f, property := al }) = ↑{ val := f, property := al }
[PROOFSTEP]
simp [map, Function.comp]
[GOAL]
case a
α : Type u
β : Type v
γ : Type w
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
⊢ Stream'.map (fun o => Option.rec none (fun val => some val) o) f = f
[PROOFSTEP]
have e : @Option.rec α (fun _ => Option α) none some = id := by ext ⟨⟩ <;> rfl
[GOAL]
α : Type u
β : Type v
γ : Type w
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
⊢ Option.rec none some = id
[PROOFSTEP]
ext ⟨⟩
[GOAL]
case h.none.a
α : Type u
β : Type v
γ : Type w
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
a✝ : α
⊢ a✝ ∈ Option.rec none some none ↔ a✝ ∈ id none
[PROOFSTEP]
rfl
[GOAL]
case h.some.a
α : Type u
β : Type v
γ : Type w
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
val✝ a✝ : α
⊢ a✝ ∈ Option.rec none some (some val✝) ↔ a✝ ∈ id (some val✝)
[PROOFSTEP]
rfl
[GOAL]
case a
α : Type u
β : Type v
γ : Type w
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
e : Option.rec none some = id
⊢ Stream'.map (fun o => Option.rec none (fun val => some val) o) f = f
[PROOFSTEP]
have h : ((fun x : Option α => x) = id) := by rfl
[GOAL]
α : Type u
β : Type v
γ : Type w
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
e : Option.rec none some = id
⊢ (fun x => x) = id
[PROOFSTEP]
rfl
[GOAL]
case a
α : Type u
β : Type v
γ : Type w
f : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, f n = some a → f (n + 1) = some a
e : Option.rec none some = id
h : (fun x => x) = id
⊢ Stream'.map (fun o => Option.rec none (fun val => some val) o) f = f
[PROOFSTEP]
simp [e, h, Stream'.map_id]
[GOAL]
α : Type u
β : Type v
γ : Type w
f : α → β
g : β → γ
s : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, s n = some a → s (n + 1) = some a
⊢ map (g ∘ f) { val := s, property := al } = map g (map f { val := s, property := al })
[PROOFSTEP]
apply Subtype.eq
[GOAL]
case a
α : Type u
β : Type v
γ : Type w
f : α → β
g : β → γ
s : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, s n = some a → s (n + 1) = some a
⊢ ↑(map (g ∘ f) { val := s, property := al }) = ↑(map g (map f { val := s, property := al }))
[PROOFSTEP]
dsimp [map]
[GOAL]
case a
α : Type u
β : Type v
γ : Type w
f : α → β
g : β → γ
s : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, s n = some a → s (n + 1) = some a
⊢ Stream'.map (fun o => Option.rec none (fun val => some (g (f val))) o) s =
    Stream'.map
      ((fun o => Option.rec none (fun val => some (g val)) o) ∘ fun o => Option.rec none (fun val => some (f val)) o) s
[PROOFSTEP]
apply congr_arg fun f : _ → Option γ => Stream'.map f s
[GOAL]
case a
α : Type u
β : Type v
γ : Type w
f : α → β
g : β → γ
s : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, s n = some a → s (n + 1) = some a
⊢ (fun o => Option.rec none (fun val => some (g (f val))) o) =
    (fun o => Option.rec none (fun val => some (g val)) o) ∘ fun o => Option.rec none (fun val => some (f val)) o
[PROOFSTEP]
ext ⟨⟩
[GOAL]
case a.h.none.a
α : Type u
β : Type v
γ : Type w
f : α → β
g : β → γ
s : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, s n = some a → s (n + 1) = some a
a✝ : γ
⊢ a✝ ∈ Option.rec none (fun val => some (g (f val))) none ↔
    a✝ ∈
      ((fun o => Option.rec none (fun val => some (g val)) o) ∘ fun o => Option.rec none (fun val => some (f val)) o)
        none
[PROOFSTEP]
rfl
[GOAL]
case a.h.some.a
α : Type u
β : Type v
γ : Type w
f : α → β
g : β → γ
s : Stream' (Option α)
al : ∀ ⦃n : ℕ⦄ ⦃a : α⦄, s n = some a → s (n + 1) = some a
val✝ : α
a✝ : γ
⊢ a✝ ∈ Option.rec none (fun val => some (g (f val))) (some val✝) ↔
    a✝ ∈
      ((fun o => Option.rec none (fun val => some (g val)) o) ∘ fun o => Option.rec none (fun val => some (f val)) o)
        (some val✝)
[PROOFSTEP]
rfl
[GOAL]
α : Type u
β : Type v
γ : Type w
a : α
f : α → Computation β
⊢ bind (pure a) f = f a
[PROOFSTEP]
apply eq_of_bisim fun c₁ c₂ => c₁ = bind (pure a) f ∧ c₂ = f a ∨ c₁ = corec (Bind.f f) (Sum.inr c₂)
[GOAL]
case bisim
α : Type u
β : Type v
γ : Type w
a : α
f : α → Computation β
⊢ IsBisimulation fun c₁ c₂ => c₁ = bind (pure a) f ∧ c₂ = f a ∨ c₁ = corec (Bind.f f) (Sum.inr c₂)
[PROOFSTEP]
intro c₁ c₂ h
[GOAL]
case bisim
α : Type u
β : Type v
γ : Type w
a : α
f : α → Computation β
c₁ c₂ : Computation β
h : c₁ = bind (pure a) f ∧ c₂ = f a ∨ c₁ = corec (Bind.f f) (Sum.inr c₂)
⊢ BisimO (fun c₁ c₂ => c₁ = bind (pure a) f ∧ c₂ = f a ∨ c₁ = corec (Bind.f f) (Sum.inr c₂)) (destruct c₁) (destruct c₂)
[PROOFSTEP]
exact
  match c₁, c₂, h with
  | _, _, Or.inl ⟨rfl, rfl⟩ => by
    simp [bind, Bind.f]
    cases' destruct (f a) with b cb <;> simp [Bind.g]
  | _, c, Or.inr rfl => by
    simp [Bind.f]
    cases' destruct c with b cb <;> simp [Bind.g]
[GOAL]
α : Type u
β : Type v
γ : Type w
a : α
f : α → Computation β
c₁ c₂ : Computation β
h : c₁ = bind (pure a) f ∧ c₂ = f a ∨ c₁ = corec (Bind.f f) (Sum.inr c₂)
⊢ BisimO (fun c₁ c₂ => c₁ = bind (pure a) f ∧ c₂ = f a ∨ c₁ = corec (Bind.f f) (Sum.inr c₂))
    (destruct (bind (pure a) f)) (destruct (f a))
[PROOFSTEP]
simp [bind, Bind.f]
[GOAL]
α : Type u
β : Type v
γ : Type w
a : α
f : α → Computation β
c₁ c₂ : Computation β
h : c₁ = bind (pure a) f ∧ c₂ = f a ∨ c₁ = corec (Bind.f f) (Sum.inr c₂)
⊢ match
    match Bind.g (destruct (f a)) with
    | Sum.inl a => Sum.inl a
    | Sum.inr b =>
      Sum.inr
        (corec
          (fun x =>
            match x with
            | Sum.inl ca =>
              match destruct ca with
              | Sum.inl a => Bind.g (destruct (f a))
              | Sum.inr ca' => Sum.inr (Sum.inl ca')
            | Sum.inr cb => Bind.g (destruct cb))
          b),
    destruct (f a) with
  | Sum.inl a, Sum.inl a' => a = a'
  | Sum.inr s, Sum.inr s' =>
    s =
          corec
            (fun x =>
              match x with
              | Sum.inl ca =>
                match destruct ca with
                | Sum.inl a => Bind.g (destruct (f a))
                | Sum.inr ca' => Sum.inr (Sum.inl ca')
              | Sum.inr cb => Bind.g (destruct cb))
            (Sum.inl (pure a)) ∧
        s' = f a ∨
      s =
        corec
          (fun x =>
            match x with
            | Sum.inl ca =>
              match destruct ca with
              | Sum.inl a => Bind.g (destruct (f a))
              | Sum.inr ca' => Sum.inr (Sum.inl ca')
            | Sum.inr cb => Bind.g (destruct cb))
          (Sum.inr s')
  | x, x_1 => False
[PROOFSTEP]
cases' destruct (f a) with b cb
[GOAL]
case inl
α : Type u
β : Type v
γ : Type w
a : α
f : α → Computation β
c₁ c₂ : Computation β
h : c₁ = bind (pure a) f ∧ c₂ = f a ∨ c₁ = corec (Bind.f f) (Sum.inr c₂)
b : β
⊢ match
    match Bind.g (Sum.inl b) with
    | Sum.inl a => Sum.inl a
    | Sum.inr b =>
      Sum.inr
        (corec
          (fun x =>
            match x with
            | Sum.inl ca =>
              match destruct ca with
              | Sum.inl a => Bind.g (destruct (f a))
              | Sum.inr ca' => Sum.inr (Sum.inl ca')
            | Sum.inr cb => Bind.g (destruct cb))
          b),
    Sum.inl b with
  | Sum.inl a, Sum.inl a' => a = a'
  | Sum.inr s, Sum.inr s' =>
    s =
          corec
            (fun x =>
              match x with
              | Sum.inl ca =>
                match destruct ca with
                | Sum.inl a => Bind.g (destruct (f a))
                | Sum.inr ca' => Sum.inr (Sum.inl ca')
              | Sum.inr cb => Bind.g (destruct cb))
            (Sum.inl (pure a)) ∧
        s' = f a ∨
      s =
        corec
          (fun x =>
            match x with
            | Sum.inl ca =>
              match destruct ca with
              | Sum.inl a => Bind.g (destruct (f a))
              | Sum.inr ca' => Sum.inr (Sum.inl ca')
            | Sum.inr cb => Bind.g (destruct cb))
          (Sum.inr s')
  | x, x_1 => False
[PROOFSTEP]
simp [Bind.g]
[GOAL]
case inr
α : Type u
β : Type v
γ : Type w
a : α
f : α → Computation β
c₁ c₂ : Computation β
h : c₁ = bind (pure a) f ∧ c₂ = f a ∨ c₁ = corec (Bind.f f) (Sum.inr c₂)
cb : Computation β
⊢ match
    match Bind.g (Sum.inr cb) with
    | Sum.inl a => Sum.inl a
    | Sum.inr b =>
      Sum.inr
        (corec
          (fun x =>
            match x with
            | Sum.inl ca =>
              match destruct ca with
              | Sum.inl a => Bind.g (destruct (f a))
              | Sum.inr ca' => Sum.inr (Sum.inl ca')
            | Sum.inr cb => Bind.g (destruct cb))
          b),
    Sum.inr cb with
  | Sum.inl a, Sum.inl a' => a = a'
  | Sum.inr s, Sum.inr s' =>
    s =
          corec
            (fun x =>
              match x with
              | Sum.inl ca =>
                match destruct ca with
                | Sum.inl a => Bind.g (destruct (f a))
                | Sum.inr ca' => Sum.inr (Sum.inl ca')
              | Sum.inr cb => Bind.g (destruct cb))
            (Sum.inl (pure a)) ∧
        s' = f a ∨
      s =
        corec
          (fun x =>
            match x with
            | Sum.inl ca =>
              match destruct ca with
              | Sum.inl a => Bind.g (destruct (f a))
              | Sum.inr ca' => Sum.inr (Sum.inl ca')
            | Sum.inr cb => Bind.g (destruct cb))
          (Sum.inr s')
  | x, x_1 => False
[PROOFSTEP]
simp [Bind.g]
[GOAL]
α : Type u
β : Type v
γ : Type w
a : α
f : α → Computation β
c₁ c₂ : Computation β
h : c₁ = bind (pure a) f ∧ c₂ = f a ∨ c₁ = corec (Bind.f f) (Sum.inr c₂)
c : Computation β
⊢ BisimO (fun c₁ c₂ => c₁ = bind (pure a) f ∧ c₂ = f a ∨ c₁ = corec (Bind.f f) (Sum.inr c₂))
    (destruct (corec (Bind.f f) (Sum.inr c))) (destruct c)
[PROOFSTEP]
simp [Bind.f]
[GOAL]
α : Type u
β : Type v
γ : Type w
a : α
f : α → Computation β
c₁ c₂ : Computation β
h : c₁ = bind (pure a) f ∧ c₂ = f a ∨ c₁ = corec (Bind.f f) (Sum.inr c₂)
c : Computation β
⊢ match
    match Bind.g (destruct c) with
    | Sum.inl a => Sum.inl a
    | Sum.inr b =>
      Sum.inr
        (corec
          (fun x =>
            match x with
            | Sum.inl ca =>
              match destruct ca with
              | Sum.inl a => Bind.g (destruct (f a))
              | Sum.inr ca' => Sum.inr (Sum.inl ca')
            | Sum.inr cb => Bind.g (destruct cb))
          b),
    destruct c with
  | Sum.inl a, Sum.inl a' => a = a'
  | Sum.inr s, Sum.inr s' =>
    s = bind (pure a) f ∧ s' = f a ∨
      s =
        corec
          (fun x =>
            match x with
            | Sum.inl ca =>
              match destruct ca with
              | Sum.inl a => Bind.g (destruct (f a))
              | Sum.inr ca' => Sum.inr (Sum.inl ca')
            | Sum.inr cb => Bind.g (destruct cb))
          (Sum.inr s')
  | x, x_1 => False
[PROOFSTEP]
cases' destruct c with b cb
[GOAL]
case inl
α : Type u
β : Type v
γ : Type w
a : α
f : α → Computation β
c₁ c₂ : Computation β
h : c₁ = bind (pure a) f ∧ c₂ = f a ∨ c₁ = corec (Bind.f f) (Sum.inr c₂)
c : Computation β
b : β
⊢ match
    match Bind.g (Sum.inl b) with
    | Sum.inl a => Sum.inl a
    | Sum.inr b =>
      Sum.inr
        (corec
          (fun x =>
            match x with
            | Sum.inl ca =>
              match destruct ca with
              | Sum.inl a => Bind.g (destruct (f a))
              | Sum.inr ca' => Sum.inr (Sum.inl ca')
            | Sum.inr cb => Bind.g (destruct cb))
          b),
    Sum.inl b with
  | Sum.inl a, Sum.inl a' => a = a'
  | Sum.inr s, Sum.inr s' =>
    s = bind (pure a) f ∧ s' = f a ∨
      s =
        corec
          (fun x =>
            match x with
            | Sum.inl ca =>
              match destruct ca with
              | Sum.inl a => Bind.g (destruct (f a))
              | Sum.inr ca' => Sum.inr (Sum.inl ca')
            | Sum.inr cb => Bind.g (destruct cb))
          (Sum.inr s')
  | x, x_1 => False
[PROOFSTEP]
simp [Bind.g]
[GOAL]
case inr
α : Type u
β : Type v
γ : Type w
a : α
f : α → Computation β
c₁ c₂ : Computation β
h : c₁ = bind (pure a) f ∧ c₂ = f a ∨ c₁ = corec (Bind.f f) (Sum.inr c₂)
c cb : Computation β
⊢ match
    match Bind.g (Sum.inr cb) with
    | Sum.inl a => Sum.inl a
    | Sum.inr b =>
      Sum.inr
        (corec
          (fun x =>
            match x with
            | Sum.inl ca =>
              match destruct ca with
              | Sum.inl a => Bind.g (destruct (f a))
              | Sum.inr ca' => Sum.inr (Sum.inl ca')
            | Sum.inr cb => Bind.g (destruct cb))
          b),
    Sum.inr cb with
  | Sum.inl a, Sum.inl a' => a = a'
  | Sum.inr s, Sum.inr s' =>
    s = bind (pure a) f ∧ s' = f a ∨
      s =
        corec
          (fun x =>
            match x with
            | Sum.inl ca =>
              match destruct ca with
              | Sum.inl a => Bind.g (destruct (f a))
              | Sum.inr ca' => Sum.inr (Sum.inl ca')
            | Sum.inr cb => Bind.g (destruct cb))
          (Sum.inr s')
  | x, x_1 => False
[PROOFSTEP]
simp [Bind.g]
[GOAL]
case r
α : Type u
β : Type v
γ : Type w
a : α
f : α → Computation β
⊢ bind (pure a) f = bind (pure a) f ∧ f a = f a ∨ bind (pure a) f = corec (Bind.f f) (Sum.inr (f a))
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
c : Computation α
f : α → Computation β
⊢ destruct (bind (think c) f) = Sum.inr (bind c f)
[PROOFSTEP]
simp [bind, Bind.f]
[GOAL]
α : Type u
β : Type v
γ : Type w
f : α → β
s : Computation α
⊢ bind s (pure ∘ f) = map f s
[PROOFSTEP]
apply eq_of_bisim fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s
[GOAL]
case bisim
α : Type u
β : Type v
γ : Type w
f : α → β
s : Computation α
⊢ IsBisimulation fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s
[PROOFSTEP]
intro c₁ c₂ h
[GOAL]
case bisim
α : Type u
β : Type v
γ : Type w
f : α → β
s : Computation α
c₁ c₂ : Computation β
h : c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s) (destruct c₁) (destruct c₂)
[PROOFSTEP]
exact
  match c₁, c₂, h with
  | _, c₂, Or.inl (Eq.refl _) => by cases' destruct c₂ with b cb <;> simp
  | _, _, Or.inr ⟨s, rfl, rfl⟩ => by
    apply recOn s <;> intro s <;> simp
    exact Or.inr ⟨s, rfl, rfl⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
f : α → β
s : Computation α
c₁ c₂✝ : Computation β
h : c₁ = c₂✝ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂✝ = map f s
c₂ : Computation β
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s) (destruct c₂) (destruct c₂)
[PROOFSTEP]
cases' destruct c₂ with b cb
[GOAL]
case inl
α : Type u
β : Type v
γ : Type w
f : α → β
s : Computation α
c₁ c₂✝ : Computation β
h : c₁ = c₂✝ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂✝ = map f s
c₂ : Computation β
b : β
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s) (Sum.inl b) (Sum.inl b)
[PROOFSTEP]
simp
[GOAL]
case inr
α : Type u
β : Type v
γ : Type w
f : α → β
s : Computation α
c₁ c₂✝ : Computation β
h : c₁ = c₂✝ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂✝ = map f s
c₂ cb : Computation β
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s) (Sum.inr cb) (Sum.inr cb)
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
f : α → β
s✝ : Computation α
c₁ c₂ : Computation β
h : c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s
s : Computation α
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s) (destruct (bind s (pure ∘ f)))
    (destruct (map f s))
[PROOFSTEP]
apply recOn s
[GOAL]
case h1
α : Type u
β : Type v
γ : Type w
f : α → β
s✝ : Computation α
c₁ c₂ : Computation β
h : c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s
s : Computation α
⊢ ∀ (a : α),
    BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s) (destruct (bind (pure a) (pure ∘ f)))
      (destruct (map f (pure a)))
[PROOFSTEP]
intro s
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
f : α → β
s✝ : Computation α
c₁ c₂ : Computation β
h : c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s
s : Computation α
⊢ ∀ (s : Computation α),
    BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s) (destruct (bind (think s) (pure ∘ f)))
      (destruct (map f (think s)))
[PROOFSTEP]
intro s
[GOAL]
case h1
α : Type u
β : Type v
γ : Type w
f : α → β
s✝¹ : Computation α
c₁ c₂ : Computation β
h : c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s
s✝ : Computation α
s : α
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s) (destruct (bind (pure s) (pure ∘ f)))
    (destruct (map f (pure s)))
[PROOFSTEP]
simp
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
f : α → β
s✝¹ : Computation α
c₁ c₂ : Computation β
h : c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s
s✝ s : Computation α
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s) (destruct (bind (think s) (pure ∘ f)))
    (destruct (map f (think s)))
[PROOFSTEP]
simp
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
f : α → β
s✝¹ : Computation α
c₁ c₂ : Computation β
h : c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure ∘ f) ∧ c₂ = map f s
s✝ s : Computation α
⊢ bind s (pure ∘ f) = map f s ∨ ∃ s_1, bind s (pure ∘ f) = bind s_1 (pure ∘ f) ∧ map f s = map f s_1
[PROOFSTEP]
exact Or.inr ⟨s, rfl, rfl⟩
[GOAL]
case r
α : Type u
β : Type v
γ : Type w
f : α → β
s : Computation α
⊢ bind s (pure ∘ f) = map f s ∨ ∃ s_1, bind s (pure ∘ f) = bind s_1 (pure ∘ f) ∧ map f s = map f s_1
[PROOFSTEP]
exact Or.inr ⟨s, rfl, rfl⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
⊢ bind s pure = s
[PROOFSTEP]
apply eq_of_bisim fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s (pure) ∧ c₂ = s
[GOAL]
case bisim
α : Type u
β : Type v
γ : Type w
s : Computation α
⊢ IsBisimulation fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s pure ∧ c₂ = s
[PROOFSTEP]
intro c₁ c₂ h
[GOAL]
case bisim
α : Type u
β : Type v
γ : Type w
s c₁ c₂ : Computation α
h : c₁ = c₂ ∨ ∃ s, c₁ = bind s pure ∧ c₂ = s
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s pure ∧ c₂ = s) (destruct c₁) (destruct c₂)
[PROOFSTEP]
exact
  match c₁, c₂, h with
  | _, c₂, Or.inl (Eq.refl _) => by cases' destruct c₂ with b cb <;> simp
  | _, _, Or.inr ⟨s, rfl, rfl⟩ => by apply recOn s <;> intro s <;> simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s c₁ c₂✝ : Computation α
h : c₁ = c₂✝ ∨ ∃ s, c₁ = bind s pure ∧ c₂✝ = s
c₂ : Computation α
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s pure ∧ c₂ = s) (destruct c₂) (destruct c₂)
[PROOFSTEP]
cases' destruct c₂ with b cb
[GOAL]
case inl
α : Type u
β : Type v
γ : Type w
s c₁ c₂✝ : Computation α
h : c₁ = c₂✝ ∨ ∃ s, c₁ = bind s pure ∧ c₂✝ = s
c₂ : Computation α
b : α
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s pure ∧ c₂ = s) (Sum.inl b) (Sum.inl b)
[PROOFSTEP]
simp
[GOAL]
case inr
α : Type u
β : Type v
γ : Type w
s c₁ c₂✝ : Computation α
h : c₁ = c₂✝ ∨ ∃ s, c₁ = bind s pure ∧ c₂✝ = s
c₂ cb : Computation α
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s pure ∧ c₂ = s) (Sum.inr cb) (Sum.inr cb)
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ c₁ c₂ : Computation α
h : c₁ = c₂ ∨ ∃ s, c₁ = bind s pure ∧ c₂ = s
s : Computation α
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s pure ∧ c₂ = s) (destruct (bind s pure)) (destruct s)
[PROOFSTEP]
apply recOn s
[GOAL]
case h1
α : Type u
β : Type v
γ : Type w
s✝ c₁ c₂ : Computation α
h : c₁ = c₂ ∨ ∃ s, c₁ = bind s pure ∧ c₂ = s
s : Computation α
⊢ ∀ (a : α),
    BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s pure ∧ c₂ = s) (destruct (bind (pure a) pure)) (destruct (pure a))
[PROOFSTEP]
intro s
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
s✝ c₁ c₂ : Computation α
h : c₁ = c₂ ∨ ∃ s, c₁ = bind s pure ∧ c₂ = s
s : Computation α
⊢ ∀ (s : Computation α),
    BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s pure ∧ c₂ = s) (destruct (bind (think s) pure)) (destruct (think s))
[PROOFSTEP]
intro s
[GOAL]
case h1
α : Type u
β : Type v
γ : Type w
s✝¹ c₁ c₂ : Computation α
h : c₁ = c₂ ∨ ∃ s, c₁ = bind s pure ∧ c₂ = s
s✝ : Computation α
s : α
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s pure ∧ c₂ = s) (destruct (bind (pure s) pure)) (destruct (pure s))
[PROOFSTEP]
simp
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
s✝¹ c₁ c₂ : Computation α
h : c₁ = c₂ ∨ ∃ s, c₁ = bind s pure ∧ c₂ = s
s✝ s : Computation α
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind s pure ∧ c₂ = s) (destruct (bind (think s) pure)) (destruct (think s))
[PROOFSTEP]
simp
[GOAL]
case r
α : Type u
β : Type v
γ : Type w
s : Computation α
⊢ bind s pure = s ∨ ∃ s_1, bind s pure = bind s_1 pure ∧ s = s_1
[PROOFSTEP]
exact Or.inr ⟨s, rfl, rfl⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
g : β → Computation γ
⊢ bind (bind s f) g = bind s fun x => bind (f x) g
[PROOFSTEP]
apply eq_of_bisim fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x : α => bind (f x) g
[GOAL]
case bisim
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
g : β → Computation γ
⊢ IsBisimulation fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g
[PROOFSTEP]
intro c₁ c₂ h
[GOAL]
case bisim
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂ : Computation γ
h : c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g) (destruct c₁)
    (destruct c₂)
[PROOFSTEP]
exact
  match c₁, c₂, h with
  | _, c₂, Or.inl (Eq.refl _) => by cases' destruct c₂ with b cb <;> simp
  | _, _, Or.inr ⟨s, rfl, rfl⟩ => by
    apply recOn s <;> intro s <;> simp
    · generalize f s = fs
      apply recOn fs <;> intro t <;> simp
      · cases' destruct (g t) with b cb <;> simp
    · exact Or.inr ⟨s, rfl, rfl⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂✝ : Computation γ
h : c₁ = c₂✝ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂✝ = bind s fun x => bind (f x) g
c₂ : Computation γ
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g) (destruct c₂)
    (destruct c₂)
[PROOFSTEP]
cases' destruct c₂ with b cb
[GOAL]
case inl
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂✝ : Computation γ
h : c₁ = c₂✝ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂✝ = bind s fun x => bind (f x) g
c₂ : Computation γ
b : γ
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g) (Sum.inl b)
    (Sum.inl b)
[PROOFSTEP]
simp
[GOAL]
case inr
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂✝ : Computation γ
h : c₁ = c₂✝ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂✝ = bind s fun x => bind (f x) g
c₂ cb : Computation γ
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g) (Sum.inr cb)
    (Sum.inr cb)
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂ : Computation γ
h : c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g
s : Computation α
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g)
    (destruct (bind (bind s f) g)) (destruct (bind s fun x => bind (f x) g))
[PROOFSTEP]
apply recOn s
[GOAL]
case h1
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂ : Computation γ
h : c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g
s : Computation α
⊢ ∀ (a : α),
    BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g)
      (destruct (bind (bind (pure a) f) g)) (destruct (bind (pure a) fun x => bind (f x) g))
[PROOFSTEP]
intro s
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂ : Computation γ
h : c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g
s : Computation α
⊢ ∀ (s : Computation α),
    BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g)
      (destruct (bind (bind (think s) f) g)) (destruct (bind (think s) fun x => bind (f x) g))
[PROOFSTEP]
intro s
[GOAL]
case h1
α : Type u
β : Type v
γ : Type w
s✝¹ : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂ : Computation γ
h : c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g
s✝ : Computation α
s : α
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g)
    (destruct (bind (bind (pure s) f) g)) (destruct (bind (pure s) fun x => bind (f x) g))
[PROOFSTEP]
simp
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
s✝¹ : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂ : Computation γ
h : c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g
s✝ s : Computation α
⊢ BisimO (fun c₁ c₂ => c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g)
    (destruct (bind (bind (think s) f) g)) (destruct (bind (think s) fun x => bind (f x) g))
[PROOFSTEP]
simp
[GOAL]
case h1
α : Type u
β : Type v
γ : Type w
s✝¹ : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂ : Computation γ
h : c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g
s✝ : Computation α
s : α
⊢ match destruct (bind (f s) g), destruct (bind (f s) g) with
  | Sum.inl a, Sum.inl a' => a = a'
  | Sum.inr s, Sum.inr s' => s = s' ∨ ∃ s_1, s = bind (bind s_1 f) g ∧ s' = bind s_1 fun x => bind (f x) g
  | x, x_1 => False
[PROOFSTEP]
generalize f s = fs
[GOAL]
case h1
α : Type u
β : Type v
γ : Type w
s✝¹ : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂ : Computation γ
h : c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g
s✝ : Computation α
s : α
fs : Computation β
⊢ match destruct (bind fs g), destruct (bind fs g) with
  | Sum.inl a, Sum.inl a' => a = a'
  | Sum.inr s, Sum.inr s' => s = s' ∨ ∃ s_1, s = bind (bind s_1 f) g ∧ s' = bind s_1 fun x => bind (f x) g
  | x, x_1 => False
[PROOFSTEP]
apply recOn fs
[GOAL]
case h1.h1
α : Type u
β : Type v
γ : Type w
s✝¹ : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂ : Computation γ
h : c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g
s✝ : Computation α
s : α
fs : Computation β
⊢ ∀ (a : β),
    match destruct (bind (pure a) g), destruct (bind (pure a) g) with
    | Sum.inl a, Sum.inl a' => a = a'
    | Sum.inr s, Sum.inr s' => s = s' ∨ ∃ s_1, s = bind (bind s_1 f) g ∧ s' = bind s_1 fun x => bind (f x) g
    | x, x_1 => False
[PROOFSTEP]
intro t
[GOAL]
case h1.h2
α : Type u
β : Type v
γ : Type w
s✝¹ : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂ : Computation γ
h : c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g
s✝ : Computation α
s : α
fs : Computation β
⊢ ∀ (s : Computation β),
    match destruct (bind (think s) g), destruct (bind (think s) g) with
    | Sum.inl a, Sum.inl a' => a = a'
    | Sum.inr s, Sum.inr s' => s = s' ∨ ∃ s_1, s = bind (bind s_1 f) g ∧ s' = bind s_1 fun x => bind (f x) g
    | x, x_1 => False
[PROOFSTEP]
intro t
[GOAL]
case h1.h1
α : Type u
β : Type v
γ : Type w
s✝¹ : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂ : Computation γ
h : c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g
s✝ : Computation α
s : α
fs : Computation β
t : β
⊢ match destruct (bind (pure t) g), destruct (bind (pure t) g) with
  | Sum.inl a, Sum.inl a' => a = a'
  | Sum.inr s, Sum.inr s' => s = s' ∨ ∃ s_1, s = bind (bind s_1 f) g ∧ s' = bind s_1 fun x => bind (f x) g
  | x, x_1 => False
[PROOFSTEP]
simp
[GOAL]
case h1.h2
α : Type u
β : Type v
γ : Type w
s✝¹ : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂ : Computation γ
h : c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g
s✝ : Computation α
s : α
fs t : Computation β
⊢ match destruct (bind (think t) g), destruct (bind (think t) g) with
  | Sum.inl a, Sum.inl a' => a = a'
  | Sum.inr s, Sum.inr s' => s = s' ∨ ∃ s_1, s = bind (bind s_1 f) g ∧ s' = bind s_1 fun x => bind (f x) g
  | x, x_1 => False
[PROOFSTEP]
simp
[GOAL]
case h1.h1
α : Type u
β : Type v
γ : Type w
s✝¹ : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂ : Computation γ
h : c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g
s✝ : Computation α
s : α
fs : Computation β
t : β
⊢ match destruct (g t), destruct (g t) with
  | Sum.inl a, Sum.inl a' => a = a'
  | Sum.inr s, Sum.inr s' => s = s' ∨ ∃ s_1, s = bind (bind s_1 f) g ∧ s' = bind s_1 fun x => bind (f x) g
  | x, x_1 => False
[PROOFSTEP]
cases' destruct (g t) with b cb
[GOAL]
case h1.h1.inl
α : Type u
β : Type v
γ : Type w
s✝¹ : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂ : Computation γ
h : c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g
s✝ : Computation α
s : α
fs : Computation β
t : β
b : γ
⊢ match Sum.inl b, Sum.inl b with
  | Sum.inl a, Sum.inl a' => a = a'
  | Sum.inr s, Sum.inr s' => s = s' ∨ ∃ s_1, s = bind (bind s_1 f) g ∧ s' = bind s_1 fun x => bind (f x) g
  | x, x_1 => False
[PROOFSTEP]
simp
[GOAL]
case h1.h1.inr
α : Type u
β : Type v
γ : Type w
s✝¹ : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂ : Computation γ
h : c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g
s✝ : Computation α
s : α
fs : Computation β
t : β
cb : Computation γ
⊢ match Sum.inr cb, Sum.inr cb with
  | Sum.inl a, Sum.inl a' => a = a'
  | Sum.inr s, Sum.inr s' => s = s' ∨ ∃ s_1, s = bind (bind s_1 f) g ∧ s' = bind s_1 fun x => bind (f x) g
  | x, x_1 => False
[PROOFSTEP]
simp
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
s✝¹ : Computation α
f : α → Computation β
g : β → Computation γ
c₁ c₂ : Computation γ
h : c₁ = c₂ ∨ ∃ s, c₁ = bind (bind s f) g ∧ c₂ = bind s fun x => bind (f x) g
s✝ s : Computation α
⊢ (bind (bind s f) g = bind s fun x => bind (f x) g) ∨
    ∃ s_1, bind (bind s f) g = bind (bind s_1 f) g ∧ (bind s fun x => bind (f x) g) = bind s_1 fun x => bind (f x) g
[PROOFSTEP]
exact Or.inr ⟨s, rfl, rfl⟩
[GOAL]
case r
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
g : β → Computation γ
⊢ (bind (bind s f) g = bind s fun x => bind (f x) g) ∨
    ∃ s_1, bind (bind s f) g = bind (bind s_1 f) g ∧ (bind s fun x => bind (f x) g) = bind s_1 fun x => bind (f x) g
[PROOFSTEP]
exact Or.inr ⟨s, rfl, rfl⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
a : α
b : β
m n : ℕ
h1 : Results s a m
h2 : Results (f a) b n
⊢ Results (bind s f) b (n + m)
[PROOFSTEP]
have := h1.mem
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
a : α
b : β
m n : ℕ
h1 : Results s a m
h2 : Results (f a) b n
this : a ∈ s
⊢ Results (bind s f) b (n + m)
[PROOFSTEP]
revert m
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
a : α
b : β
n : ℕ
h2 : Results (f a) b n
this : a ∈ s
⊢ ∀ {m : ℕ}, Results s a m → Results (bind s f) b (n + m)
[PROOFSTEP]
apply memRecOn this _ fun s IH => _
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
a : α
b : β
n : ℕ
h2 : Results (f a) b n
this : a ∈ s
⊢ ∀ {m : ℕ}, Results (pure a) a m → Results (bind (pure a) f) b (n + m)
[PROOFSTEP]
intro _ h1
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
a : α
b : β
n : ℕ
h2 : Results (f a) b n
this : a ∈ s
m✝ : ℕ
h1 : Results (pure a) a m✝
⊢ Results (bind (pure a) f) b (n + m✝)
[PROOFSTEP]
rw [ret_bind]
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
a : α
b : β
n : ℕ
h2 : Results (f a) b n
this : a ∈ s
m✝ : ℕ
h1 : Results (pure a) a m✝
⊢ Results (f a) b (n + m✝)
[PROOFSTEP]
rw [h1.len_unique (results_pure _)]
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
a : α
b : β
n : ℕ
h2 : Results (f a) b n
this : a ∈ s
m✝ : ℕ
h1 : Results (pure a) a m✝
⊢ Results (f a) b (n + 0)
[PROOFSTEP]
exact h2
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
a : α
b : β
n : ℕ
h2 : Results (f a) b n
this : a ∈ s
⊢ ∀ (s : Computation α),
    (∀ {m : ℕ}, Results s a m → Results (bind s f) b (n + m)) →
      ∀ {m : ℕ}, Results (think s) a m → Results (bind (think s) f) b (n + m)
[PROOFSTEP]
intro _ h3 _ h1
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
a : α
b : β
n : ℕ
h2 : Results (f a) b n
this : a ∈ s
s✝ : Computation α
h3 : ∀ {m : ℕ}, Results s✝ a m → Results (bind s✝ f) b (n + m)
m✝ : ℕ
h1 : Results (think s✝) a m✝
⊢ Results (bind (think s✝) f) b (n + m✝)
[PROOFSTEP]
rw [think_bind]
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
a : α
b : β
n : ℕ
h2 : Results (f a) b n
this : a ∈ s
s✝ : Computation α
h3 : ∀ {m : ℕ}, Results s✝ a m → Results (bind s✝ f) b (n + m)
m✝ : ℕ
h1 : Results (think s✝) a m✝
⊢ Results (think (bind s✝ f)) b (n + m✝)
[PROOFSTEP]
cases' of_results_think h1 with m' h
[GOAL]
case intro
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
a : α
b : β
n : ℕ
h2 : Results (f a) b n
this : a ∈ s
s✝ : Computation α
h3 : ∀ {m : ℕ}, Results s✝ a m → Results (bind s✝ f) b (n + m)
m✝ : ℕ
h1 : Results (think s✝) a m✝
m' : ℕ
h : Results s✝ a m' ∧ m✝ = m' + 1
⊢ Results (think (bind s✝ f)) b (n + m✝)
[PROOFSTEP]
cases' h with h1 e
[GOAL]
case intro.intro
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
a : α
b : β
n : ℕ
h2 : Results (f a) b n
this : a ∈ s
s✝ : Computation α
h3 : ∀ {m : ℕ}, Results s✝ a m → Results (bind s✝ f) b (n + m)
m✝ : ℕ
h1✝ : Results (think s✝) a m✝
m' : ℕ
h1 : Results s✝ a m'
e : m✝ = m' + 1
⊢ Results (think (bind s✝ f)) b (n + m✝)
[PROOFSTEP]
rw [e]
[GOAL]
case intro.intro
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
a : α
b : β
n : ℕ
h2 : Results (f a) b n
this : a ∈ s
s✝ : Computation α
h3 : ∀ {m : ℕ}, Results s✝ a m → Results (bind s✝ f) b (n + m)
m✝ : ℕ
h1✝ : Results (think s✝) a m✝
m' : ℕ
h1 : Results s✝ a m'
e : m✝ = m' + 1
⊢ Results (think (bind s✝ f)) b (n + (m' + 1))
[PROOFSTEP]
exact results_think (h3 h1)
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
b : β
k : ℕ
⊢ Results (bind s f) b k → ∃ a m n, Results s a m ∧ Results (f a) b n ∧ k = n + m
[PROOFSTEP]
induction' k with n IH generalizing s
[GOAL]
case zero
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
b : β
s : Computation α
⊢ Results (bind s f) b Nat.zero → ∃ a m n, Results s a m ∧ Results (f a) b n ∧ Nat.zero = n + m
[PROOFSTEP]
apply recOn s (fun a => _) fun s' => _
[GOAL]
case succ
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
b : β
n : ℕ
IH : ∀ {s : Computation α}, Results (bind s f) b n → ∃ a m n_1, Results s a m ∧ Results (f a) b n_1 ∧ n = n_1 + m
s : Computation α
⊢ Results (bind s f) b (Nat.succ n) → ∃ a m n_1, Results s a m ∧ Results (f a) b n_1 ∧ Nat.succ n = n_1 + m
[PROOFSTEP]
apply recOn s (fun a => _) fun s' => _
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
b : β
s : Computation α
⊢ ∀ (a : α),
    Results (bind (pure a) f) b Nat.zero → ∃ a_2 m n, Results (pure a) a_2 m ∧ Results (f a_2) b n ∧ Nat.zero = n + m
[PROOFSTEP]
intro e h
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
b : β
s : Computation α
⊢ ∀ (s' : Computation α),
    Results (bind (think s') f) b Nat.zero → ∃ a m n, Results (think s') a m ∧ Results (f a) b n ∧ Nat.zero = n + m
[PROOFSTEP]
intro e h
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
b : β
n : ℕ
IH : ∀ {s : Computation α}, Results (bind s f) b n → ∃ a m n_1, Results s a m ∧ Results (f a) b n_1 ∧ n = n_1 + m
s : Computation α
⊢ ∀ (a : α),
    Results (bind (pure a) f) b (Nat.succ n) →
      ∃ a_2 m n_1, Results (pure a) a_2 m ∧ Results (f a_2) b n_1 ∧ Nat.succ n = n_1 + m
[PROOFSTEP]
intro e h
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
b : β
n : ℕ
IH : ∀ {s : Computation α}, Results (bind s f) b n → ∃ a m n_1, Results s a m ∧ Results (f a) b n_1 ∧ n = n_1 + m
s : Computation α
⊢ ∀ (s' : Computation α),
    Results (bind (think s') f) b (Nat.succ n) →
      ∃ a m n_1, Results (think s') a m ∧ Results (f a) b n_1 ∧ Nat.succ n = n_1 + m
[PROOFSTEP]
intro e h
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
b : β
s : Computation α
e : α
h : Results (bind (pure e) f) b Nat.zero
⊢ ∃ a m n, Results (pure e) a m ∧ Results (f a) b n ∧ Nat.zero = n + m
[PROOFSTEP]
simp [thinkN] at h 
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
b : β
s : Computation α
e : α
h : Results (f e) b 0
⊢ ∃ a m n, Results (pure e) a m ∧ Results (f a) b n ∧ Nat.zero = n + m
[PROOFSTEP]
refine' ⟨e, _, _, results_pure _, h, rfl⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
b : β
s e : Computation α
h : Results (bind (think e) f) b Nat.zero
⊢ ∃ a m n, Results (think e) a m ∧ Results (f a) b n ∧ Nat.zero = n + m
[PROOFSTEP]
have := congr_arg head (eq_thinkN h)
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
b : β
s e : Computation α
h : Results (bind (think e) f) b Nat.zero
this : head (bind (think e) f) = head (thinkN (pure b) Nat.zero)
⊢ ∃ a m n, Results (think e) a m ∧ Results (f a) b n ∧ Nat.zero = n + m
[PROOFSTEP]
contradiction
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
b : β
n : ℕ
IH : ∀ {s : Computation α}, Results (bind s f) b n → ∃ a m n_1, Results s a m ∧ Results (f a) b n_1 ∧ n = n_1 + m
s : Computation α
e : α
h : Results (bind (pure e) f) b (Nat.succ n)
⊢ ∃ a m n_1, Results (pure e) a m ∧ Results (f a) b n_1 ∧ Nat.succ n = n_1 + m
[PROOFSTEP]
simp at h 
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
b : β
n : ℕ
IH : ∀ {s : Computation α}, Results (bind s f) b n → ∃ a m n_1, Results s a m ∧ Results (f a) b n_1 ∧ n = n_1 + m
s : Computation α
e : α
h : Results (f e) b (Nat.succ n)
⊢ ∃ a m n_1, Results (pure e) a m ∧ Results (f a) b n_1 ∧ Nat.succ n = n_1 + m
[PROOFSTEP]
refine' ⟨e, _, n + 1, results_pure _, h, rfl⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
b : β
n : ℕ
IH : ∀ {s : Computation α}, Results (bind s f) b n → ∃ a m n_1, Results s a m ∧ Results (f a) b n_1 ∧ n = n_1 + m
s e : Computation α
h : Results (bind (think e) f) b (Nat.succ n)
⊢ ∃ a m n_1, Results (think e) a m ∧ Results (f a) b n_1 ∧ Nat.succ n = n_1 + m
[PROOFSTEP]
simp at h 
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
b : β
n : ℕ
IH : ∀ {s : Computation α}, Results (bind s f) b n → ∃ a m n_1, Results s a m ∧ Results (f a) b n_1 ∧ n = n_1 + m
s e : Computation α
h : Results (bind e f) b n
⊢ ∃ a m n_1, Results (think e) a m ∧ Results (f a) b n_1 ∧ Nat.succ n = n_1 + m
[PROOFSTEP]
exact by
  let ⟨a, m, n', h1, h2, e'⟩ := IH h
  rw [e']; exact ⟨a, m.succ, n', results_think h1, h2, rfl⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
b : β
n : ℕ
IH : ∀ {s : Computation α}, Results (bind s f) b n → ∃ a m n_1, Results s a m ∧ Results (f a) b n_1 ∧ n = n_1 + m
s e : Computation α
h : Results (bind e f) b n
⊢ ∃ a m n_1, Results (think e) a m ∧ Results (f a) b n_1 ∧ Nat.succ n = n_1 + m
[PROOFSTEP]
let ⟨a, m, n', h1, h2, e'⟩ := IH h
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
b : β
n : ℕ
IH : ∀ {s : Computation α}, Results (bind s f) b n → ∃ a m n_1, Results s a m ∧ Results (f a) b n_1 ∧ n = n_1 + m
s e : Computation α
h : Results (bind e f) b n
a : α
m n' : ℕ
h1 : Results e a m
h2 : Results (f a) b n'
e' : n = n' + m
⊢ ∃ a m n_1, Results (think e) a m ∧ Results (f a) b n_1 ∧ Nat.succ n = n_1 + m
[PROOFSTEP]
rw [e']
[GOAL]
α : Type u
β : Type v
γ : Type w
s✝ : Computation α
f : α → Computation β
b : β
n : ℕ
IH : ∀ {s : Computation α}, Results (bind s f) b n → ∃ a m n_1, Results s a m ∧ Results (f a) b n_1 ∧ n = n_1 + m
s e : Computation α
h : Results (bind e f) b n
a : α
m n' : ℕ
h1 : Results e a m
h2 : Results (f a) b n'
e' : n = n' + m
⊢ ∃ a m_1 n, Results (think e) a m_1 ∧ Results (f a) b n ∧ Nat.succ (n' + m) = n + m_1
[PROOFSTEP]
exact ⟨a, m.succ, n', results_think h1, h2, rfl⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
a : α
b : β
h1 : s ~> a
h2 : f a ~> b
b' : β
bB : b' ∈ bind s f
⊢ b = b'
[PROOFSTEP]
rcases exists_of_mem_bind bB with ⟨a', a's, ba'⟩
[GOAL]
case intro.intro
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
a : α
b : β
h1 : s ~> a
h2 : f a ~> b
b' : β
bB : b' ∈ bind s f
a' : α
a's : a' ∈ s
ba' : b' ∈ f a'
⊢ b = b'
[PROOFSTEP]
rw [← h1 a's] at ba' 
[GOAL]
case intro.intro
α : Type u
β : Type v
γ : Type w
s : Computation α
f : α → Computation β
a : α
b : β
h1 : s ~> a
h2 : f a ~> b
b' : β
bB : b' ∈ bind s f
a' : α
a's : a' ∈ s
ba' : b' ∈ f a
⊢ b = b'
[PROOFSTEP]
exact h2 ba'
[GOAL]
α : Type u
β : Type v
γ : Type w
f : α → β
a : α
s : Computation α
m : a ∈ s
⊢ f a ∈ map f s
[PROOFSTEP]
rw [← bind_pure]
[GOAL]
α : Type u
β : Type v
γ : Type w
f : α → β
a : α
s : Computation α
m : a ∈ s
⊢ f a ∈ bind s (pure ∘ f)
[PROOFSTEP]
apply mem_bind m
[GOAL]
α : Type u
β : Type v
γ : Type w
f : α → β
a : α
s : Computation α
m : a ∈ s
⊢ f a ∈ (pure ∘ f) a
[PROOFSTEP]
apply ret_mem
[GOAL]
α : Type u
β : Type v
γ : Type w
f : α → β
b : β
s : Computation α
h : b ∈ map f s
⊢ ∃ a, a ∈ s ∧ f a = b
[PROOFSTEP]
rw [← bind_pure] at h 
[GOAL]
α : Type u
β : Type v
γ : Type w
f : α → β
b : β
s : Computation α
h : b ∈ bind s (pure ∘ f)
⊢ ∃ a, a ∈ s ∧ f a = b
[PROOFSTEP]
exact
  let ⟨a, as, fb⟩ := exists_of_mem_bind h
  ⟨a, as, mem_unique (ret_mem _) fb⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
f : α → β
s : Computation α
inst✝ : Terminates s
⊢ Terminates (map f s)
[PROOFSTEP]
rw [← bind_pure]
[GOAL]
α : Type u
β : Type v
γ : Type w
f : α → β
s : Computation α
inst✝ : Terminates s
⊢ Terminates (bind s (pure ∘ f))
[PROOFSTEP]
exact terminates_of_mem (mem_bind (get_mem s) (get_mem (f (get s))))
[GOAL]
α : Type u
β : Type v
γ : Type w
a : α
c₂ : Computation α
⊢ destruct (HOrElse.hOrElse (pure a) fun x => c₂) = Sum.inl a
[PROOFSTEP]
unfold HOrElse.hOrElse instHOrElse
[GOAL]
α : Type u
β : Type v
γ : Type w
a : α
c₂ : Computation α
⊢ destruct ({ hOrElse := fun a b => OrElse.orElse a b }.1 (pure a) fun x => c₂) = Sum.inl a
[PROOFSTEP]
unfold OrElse.orElse instOrElse Alternative.orElse instAlternativeComputation
[GOAL]
α : Type u
β : Type v
γ : Type w
a : α
c₂ : Computation α
⊢ destruct
      ({
            hOrElse := fun a b =>
              {
                    orElse :=
                      (let src := monad;
                        Alternative.mk empty @orElse).3 }.1
                a b }.1
        (pure a) fun x => c₂) =
    Sum.inl a
[PROOFSTEP]
simp [orElse]
[GOAL]
α : Type u
β : Type v
γ : Type w
c₁ : Computation α
a : α
⊢ destruct (HOrElse.hOrElse (think c₁) fun x => pure a) = Sum.inl a
[PROOFSTEP]
unfold HOrElse.hOrElse instHOrElse
[GOAL]
α : Type u
β : Type v
γ : Type w
c₁ : Computation α
a : α
⊢ destruct ({ hOrElse := fun a b => OrElse.orElse a b }.1 (think c₁) fun x => pure a) = Sum.inl a
[PROOFSTEP]
unfold OrElse.orElse instOrElse Alternative.orElse instAlternativeComputation
[GOAL]
α : Type u
β : Type v
γ : Type w
c₁ : Computation α
a : α
⊢ destruct
      ({
            hOrElse := fun a b =>
              {
                    orElse :=
                      (let src := monad;
                        Alternative.mk empty @orElse).3 }.1
                a b }.1
        (think c₁) fun x => pure a) =
    Sum.inl a
[PROOFSTEP]
simp [orElse]
[GOAL]
α : Type u
β : Type v
γ : Type w
c₁ c₂ : Computation α
⊢ destruct (HOrElse.hOrElse (think c₁) fun x => think c₂) = Sum.inr (HOrElse.hOrElse c₁ fun x => c₂)
[PROOFSTEP]
unfold HOrElse.hOrElse instHOrElse
[GOAL]
α : Type u
β : Type v
γ : Type w
c₁ c₂ : Computation α
⊢ destruct ({ hOrElse := fun a b => OrElse.orElse a b }.1 (think c₁) fun x => think c₂) =
    Sum.inr ({ hOrElse := fun a b => OrElse.orElse a b }.1 c₁ fun x => c₂)
[PROOFSTEP]
unfold OrElse.orElse instOrElse Alternative.orElse instAlternativeComputation
[GOAL]
α : Type u
β : Type v
γ : Type w
c₁ c₂ : Computation α
⊢ destruct
      ({
            hOrElse := fun a b =>
              {
                    orElse :=
                      (let src := monad;
                        Alternative.mk empty @orElse).3 }.1
                a b }.1
        (think c₁) fun x => think c₂) =
    Sum.inr
      ({
            hOrElse := fun a b =>
              {
                    orElse :=
                      (let src := monad;
                        Alternative.mk empty @orElse).3 }.1
                a b }.1
        c₁ fun x => c₂)
[PROOFSTEP]
simp [orElse]
[GOAL]
α : Type u
β : Type v
γ : Type w
c : Computation α
⊢ (HOrElse.hOrElse (empty α) fun x => c) = c
[PROOFSTEP]
apply eq_of_bisim (fun c₁ c₂ => (empty α <|> c₂) = c₁) _ rfl
[GOAL]
α : Type u
β : Type v
γ : Type w
c : Computation α
⊢ IsBisimulation fun c₁ c₂ => (HOrElse.hOrElse (empty α) fun x => c₂) = c₁
[PROOFSTEP]
intro s' s h
[GOAL]
α : Type u
β : Type v
γ : Type w
c s' s : Computation α
h : (HOrElse.hOrElse (empty α) fun x => s) = s'
⊢ BisimO (fun c₁ c₂ => (HOrElse.hOrElse (empty α) fun x => c₂) = c₁) (destruct s') (destruct s)
[PROOFSTEP]
rw [← h]
[GOAL]
α : Type u
β : Type v
γ : Type w
c s' s : Computation α
h : (HOrElse.hOrElse (empty α) fun x => s) = s'
⊢ BisimO (fun c₁ c₂ => (HOrElse.hOrElse (empty α) fun x => c₂) = c₁) (destruct (HOrElse.hOrElse (empty α) fun x => s))
    (destruct s)
[PROOFSTEP]
apply recOn s
[GOAL]
case h1
α : Type u
β : Type v
γ : Type w
c s' s : Computation α
h : (HOrElse.hOrElse (empty α) fun x => s) = s'
⊢ ∀ (a : α),
    BisimO (fun c₁ c₂ => (HOrElse.hOrElse (empty α) fun x => c₂) = c₁)
      (destruct (HOrElse.hOrElse (empty α) fun x => pure a)) (destruct (pure a))
[PROOFSTEP]
intro s
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
c s' s : Computation α
h : (HOrElse.hOrElse (empty α) fun x => s) = s'
⊢ ∀ (s : Computation α),
    BisimO (fun c₁ c₂ => (HOrElse.hOrElse (empty α) fun x => c₂) = c₁)
      (destruct (HOrElse.hOrElse (empty α) fun x => think s)) (destruct (think s))
[PROOFSTEP]
intro s
[GOAL]
case h1
α : Type u
β : Type v
γ : Type w
c s' s✝ : Computation α
h : (HOrElse.hOrElse (empty α) fun x => s✝) = s'
s : α
⊢ BisimO (fun c₁ c₂ => (HOrElse.hOrElse (empty α) fun x => c₂) = c₁)
    (destruct (HOrElse.hOrElse (empty α) fun x => pure s)) (destruct (pure s))
[PROOFSTEP]
rw [think_empty]
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
c s' s✝ : Computation α
h : (HOrElse.hOrElse (empty α) fun x => s✝) = s'
s : Computation α
⊢ BisimO (fun c₁ c₂ => (HOrElse.hOrElse (empty α) fun x => c₂) = c₁)
    (destruct (HOrElse.hOrElse (empty α) fun x => think s)) (destruct (think s))
[PROOFSTEP]
rw [think_empty]
[GOAL]
case h1
α : Type u
β : Type v
γ : Type w
c s' s✝ : Computation α
h : (HOrElse.hOrElse (empty α) fun x => s✝) = s'
s : α
⊢ BisimO (fun c₁ c₂ => (HOrElse.hOrElse (think (empty α)) fun x => c₂) = c₁)
    (destruct (HOrElse.hOrElse (think (empty α)) fun x => pure s)) (destruct (pure s))
[PROOFSTEP]
simp
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
c s' s✝ : Computation α
h : (HOrElse.hOrElse (empty α) fun x => s✝) = s'
s : Computation α
⊢ BisimO (fun c₁ c₂ => (HOrElse.hOrElse (think (empty α)) fun x => c₂) = c₁)
    (destruct (HOrElse.hOrElse (think (empty α)) fun x => think s)) (destruct (think s))
[PROOFSTEP]
simp
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
c s' s✝ : Computation α
h : (HOrElse.hOrElse (empty α) fun x => s✝) = s'
s : Computation α
⊢ (HOrElse.hOrElse (think (empty α)) fun x => s) = HOrElse.hOrElse (empty α) fun x => s
[PROOFSTEP]
rw [← think_empty]
[GOAL]
α : Type u
β : Type v
γ : Type w
c : Computation α
⊢ (HOrElse.hOrElse c fun x => empty α) = c
[PROOFSTEP]
apply eq_of_bisim (fun c₁ c₂ => (c₂ <|> empty α) = c₁) _ rfl
[GOAL]
α : Type u
β : Type v
γ : Type w
c : Computation α
⊢ IsBisimulation fun c₁ c₂ => (HOrElse.hOrElse c₂ fun x => empty α) = c₁
[PROOFSTEP]
intro s' s h
[GOAL]
α : Type u
β : Type v
γ : Type w
c s' s : Computation α
h : (HOrElse.hOrElse s fun x => empty α) = s'
⊢ BisimO (fun c₁ c₂ => (HOrElse.hOrElse c₂ fun x => empty α) = c₁) (destruct s') (destruct s)
[PROOFSTEP]
rw [← h]
[GOAL]
α : Type u
β : Type v
γ : Type w
c s' s : Computation α
h : (HOrElse.hOrElse s fun x => empty α) = s'
⊢ BisimO (fun c₁ c₂ => (HOrElse.hOrElse c₂ fun x => empty α) = c₁) (destruct (HOrElse.hOrElse s fun x => empty α))
    (destruct s)
[PROOFSTEP]
apply recOn s
[GOAL]
case h1
α : Type u
β : Type v
γ : Type w
c s' s : Computation α
h : (HOrElse.hOrElse s fun x => empty α) = s'
⊢ ∀ (a : α),
    BisimO (fun c₁ c₂ => (HOrElse.hOrElse c₂ fun x => empty α) = c₁)
      (destruct (HOrElse.hOrElse (pure a) fun x => empty α)) (destruct (pure a))
[PROOFSTEP]
intro s
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
c s' s : Computation α
h : (HOrElse.hOrElse s fun x => empty α) = s'
⊢ ∀ (s : Computation α),
    BisimO (fun c₁ c₂ => (HOrElse.hOrElse c₂ fun x => empty α) = c₁)
      (destruct (HOrElse.hOrElse (think s) fun x => empty α)) (destruct (think s))
[PROOFSTEP]
intro s
[GOAL]
case h1
α : Type u
β : Type v
γ : Type w
c s' s✝ : Computation α
h : (HOrElse.hOrElse s✝ fun x => empty α) = s'
s : α
⊢ BisimO (fun c₁ c₂ => (HOrElse.hOrElse c₂ fun x => empty α) = c₁)
    (destruct (HOrElse.hOrElse (pure s) fun x => empty α)) (destruct (pure s))
[PROOFSTEP]
rw [think_empty]
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
c s' s✝ : Computation α
h : (HOrElse.hOrElse s✝ fun x => empty α) = s'
s : Computation α
⊢ BisimO (fun c₁ c₂ => (HOrElse.hOrElse c₂ fun x => empty α) = c₁)
    (destruct (HOrElse.hOrElse (think s) fun x => empty α)) (destruct (think s))
[PROOFSTEP]
rw [think_empty]
[GOAL]
case h1
α : Type u
β : Type v
γ : Type w
c s' s✝ : Computation α
h : (HOrElse.hOrElse s✝ fun x => empty α) = s'
s : α
⊢ BisimO (fun c₁ c₂ => (HOrElse.hOrElse c₂ fun x => think (empty α)) = c₁)
    (destruct (HOrElse.hOrElse (pure s) fun x => think (empty α))) (destruct (pure s))
[PROOFSTEP]
simp
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
c s' s✝ : Computation α
h : (HOrElse.hOrElse s✝ fun x => empty α) = s'
s : Computation α
⊢ BisimO (fun c₁ c₂ => (HOrElse.hOrElse c₂ fun x => think (empty α)) = c₁)
    (destruct (HOrElse.hOrElse (think s) fun x => think (empty α))) (destruct (think s))
[PROOFSTEP]
simp
[GOAL]
case h2
α : Type u
β : Type v
γ : Type w
c s' s✝ : Computation α
h : (HOrElse.hOrElse s✝ fun x => empty α) = s'
s : Computation α
⊢ (HOrElse.hOrElse s fun x => think (empty α)) = HOrElse.hOrElse s fun x => empty α
[PROOFSTEP]
rw [← think_empty]
[GOAL]
α : Type u
β : Type v
γ : Type w
s t : Computation α
a : α
h1 : a ∈ s
h2 : a ∈ t
a' : α
ma : a' ∈ s
⊢ a' ∈ t
[PROOFSTEP]
rw [mem_unique ma h1]
[GOAL]
α : Type u
β : Type v
γ : Type w
s t : Computation α
a : α
h1 : a ∈ s
h2 : a ∈ t
a' : α
ma : a' ∈ s
⊢ a ∈ t
[PROOFSTEP]
exact h2
[GOAL]
α : Type u
β : Type v
γ : Type w
s t : Computation α
a : α
h1 : a ∈ s
h2 : a ∈ t
a' : α
ma : a' ∈ t
⊢ a' ∈ s
[PROOFSTEP]
rw [mem_unique ma h2]
[GOAL]
α : Type u
β : Type v
γ : Type w
s t : Computation α
a : α
h1 : a ∈ s
h2 : a ∈ t
a' : α
ma : a' ∈ t
⊢ a ∈ s
[PROOFSTEP]
exact h1
[GOAL]
α : Type u
β : Type v
γ : Type w
c₁ c₂ : Computation α
h : c₁ ~ c₂
⊢ Terminates c₁ ↔ Terminates c₂
[PROOFSTEP]
simp only [terminates_iff, exists_congr h]
[GOAL]
α : Type u
β : Type v
γ : Type w
c₁ c₂ : Computation α
x✝ : LiftRel (fun x x_1 => x = x_1) c₁ c₂
a : α
h1 : ∀ {a : α}, a ∈ c₁ → ∃ b, b ∈ c₂ ∧ (fun x x_1 => x = x_1) a b
h2 : ∀ {b : α}, b ∈ c₂ → ∃ a, a ∈ c₁ ∧ (fun x x_1 => x = x_1) a b
a1 : a ∈ c₁
⊢ a ∈ c₂
[PROOFSTEP]
let ⟨b, b2, ab⟩ := h1 a1
[GOAL]
α : Type u
β : Type v
γ : Type w
c₁ c₂ : Computation α
x✝ : LiftRel (fun x x_1 => x = x_1) c₁ c₂
a : α
h1 : ∀ {a : α}, a ∈ c₁ → ∃ b, b ∈ c₂ ∧ (fun x x_1 => x = x_1) a b
h2 : ∀ {b : α}, b ∈ c₂ → ∃ a, a ∈ c₁ ∧ (fun x x_1 => x = x_1) a b
a1 : a ∈ c₁
b : α
b2 : b ∈ c₂
ab : (fun x x_1 => x = x_1) a b
⊢ a ∈ c₂
[PROOFSTEP]
rwa [ab]
[GOAL]
α : Type u
β : Type v
γ : Type w
c₁ c₂ : Computation α
x✝ : LiftRel (fun x x_1 => x = x_1) c₁ c₂
a : α
h1 : ∀ {a : α}, a ∈ c₁ → ∃ b, b ∈ c₂ ∧ (fun x x_1 => x = x_1) a b
h2 : ∀ {b : α}, b ∈ c₂ → ∃ a, a ∈ c₁ ∧ (fun x x_1 => x = x_1) a b
a2 : a ∈ c₂
⊢ a ∈ c₁
[PROOFSTEP]
let ⟨b, b1, ab⟩ := h2 a2
[GOAL]
α : Type u
β : Type v
γ : Type w
c₁ c₂ : Computation α
x✝ : LiftRel (fun x x_1 => x = x_1) c₁ c₂
a : α
h1 : ∀ {a : α}, a ∈ c₁ → ∃ b, b ∈ c₂ ∧ (fun x x_1 => x = x_1) a b
h2 : ∀ {b : α}, b ∈ c₂ → ∃ a, a ∈ c₁ ∧ (fun x x_1 => x = x_1) a b
a2 : a ∈ c₂
b : α
b1 : b ∈ c₁
ab : (fun x x_1 => x = x_1) b a
⊢ a ∈ c₁
[PROOFSTEP]
rwa [← ab]
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → α → Prop
refl : ∀ (x : α), R x x
symm : ∀ {x y : α}, R x y → R y x
trans : ∀ {x y z : α}, R x y → R y z → R x z
⊢ ∀ {x y : Computation α}, LiftRel R x y → LiftRel R y x
[PROOFSTEP]
apply LiftRel.symm
[GOAL]
case H
α : Type u
β : Type v
γ : Type w
R : α → α → Prop
refl : ∀ (x : α), R x x
symm : ∀ {x y : α}, R x y → R y x
trans : ∀ {x y z : α}, R x y → R y z → R x z
⊢ Symmetric R
[PROOFSTEP]
apply symm
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → α → Prop
refl : ∀ (x : α), R x x
symm : ∀ {x y : α}, R x y → R y x
trans : ∀ {x y z : α}, R x y → R y z → R x z
⊢ ∀ {x y z : Computation α}, LiftRel R x y → LiftRel R y z → LiftRel R x z
[PROOFSTEP]
apply LiftRel.trans
[GOAL]
case H
α : Type u
β : Type v
γ : Type w
R : α → α → Prop
refl : ∀ (x : α), R x x
symm : ∀ {x y : α}, R x y → R y x
trans : ∀ {x y z : α}, R x y → R y z → R x z
⊢ Transitive R
[PROOFSTEP]
apply trans
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
ca : Computation α
cb : Computation β
l : ∀ {a : α}, a ∈ ca → ∃ b, b ∈ cb ∧ R a b
right✝ : ∀ {b : β}, b ∈ cb → ∃ a, a ∈ ca ∧ R a b
a : α
b : β
ma : a ∈ ca
mb : b ∈ cb
⊢ R a b
[PROOFSTEP]
let ⟨b', mb', ab'⟩ := l ma
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
ca : Computation α
cb : Computation β
l : ∀ {a : α}, a ∈ ca → ∃ b, b ∈ cb ∧ R a b
right✝ : ∀ {b : β}, b ∈ cb → ∃ a, a ∈ ca ∧ R a b
a : α
b : β
ma : a ∈ ca
mb : b ∈ cb
b' : β
mb' : b' ∈ cb
ab' : R a b'
⊢ R a b
[PROOFSTEP]
rw [mem_unique mb mb']
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
ca : Computation α
cb : Computation β
l : ∀ {a : α}, a ∈ ca → ∃ b, b ∈ cb ∧ R a b
right✝ : ∀ {b : β}, b ∈ cb → ∃ a, a ∈ ca ∧ R a b
a : α
b : β
ma : a ∈ ca
mb : b ∈ cb
b' : β
mb' : b' ∈ cb
ab' : R a b'
⊢ R a b'
[PROOFSTEP]
exact ab'
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
a : α
b : β
ca : Computation α
cb : Computation β
ma : a ∈ ca
mb : b ∈ cb
ab : R a b
a' : α
ma' : a' ∈ ca
⊢ ∃ b, b ∈ cb ∧ R a' b
[PROOFSTEP]
rw [mem_unique ma' ma]
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
a : α
b : β
ca : Computation α
cb : Computation β
ma : a ∈ ca
mb : b ∈ cb
ab : R a b
a' : α
ma' : a' ∈ ca
⊢ ∃ b, b ∈ cb ∧ R a b
[PROOFSTEP]
exact ⟨b, mb, ab⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
a : α
b : β
ca : Computation α
cb : Computation β
ma : a ∈ ca
mb : b ∈ cb
ab : R a b
b' : β
mb' : b' ∈ cb
⊢ ∃ a, a ∈ ca ∧ R a b'
[PROOFSTEP]
rw [mem_unique mb' mb]
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
a : α
b : β
ca : Computation α
cb : Computation β
ma : a ∈ ca
mb : b ∈ cb
ab : R a b
b' : β
mb' : b' ∈ cb
⊢ ∃ a, a ∈ ca ∧ R a b
[PROOFSTEP]
exact ⟨a, ma, ab⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
ca : Computation α
cb : Computation β
h : LiftRel R ca cb
a : α
b : β
ma : a ∈ ca
mb : b ∈ cb
⊢ R a b
[PROOFSTEP]
let ⟨b', mb', ab⟩ := h.left ma
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
ca : Computation α
cb : Computation β
h : LiftRel R ca cb
a : α
b : β
ma : a ∈ ca
mb : b ∈ cb
b' : β
mb' : b' ∈ cb
ab : R a b'
⊢ R a b
[PROOFSTEP]
rwa [mem_unique mb mb']
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
a : α
cb : Computation β
x✝ : ∃ b, b ∈ cb ∧ R a b
b : β
mb : b ∈ cb
ab : R a b
a' : α
ma' : a' ∈ pure a
⊢ ∃ b, b ∈ cb ∧ R a' b
[PROOFSTEP]
rw [eq_of_pure_mem ma']
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
a : α
cb : Computation β
x✝ : ∃ b, b ∈ cb ∧ R a b
b : β
mb : b ∈ cb
ab : R a b
a' : α
ma' : a' ∈ pure a
⊢ ∃ b, b ∈ cb ∧ R a b
[PROOFSTEP]
exact ⟨b, mb, ab⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
a : α
cb : Computation β
x✝ : ∃ b, b ∈ cb ∧ R a b
b : β
mb : b ∈ cb
ab : R a b
b' : β
mb' : b' ∈ cb
⊢ R a b'
[PROOFSTEP]
rw [mem_unique mb' mb]
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
a : α
cb : Computation β
x✝ : ∃ b, b ∈ cb ∧ R a b
b : β
mb : b ∈ cb
ab : R a b
b' : β
mb' : b' ∈ cb
⊢ R a b
[PROOFSTEP]
exact ab
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
ca : Computation α
b : β
⊢ LiftRel R ca (pure b) ↔ ∃ a, a ∈ ca ∧ R a b
[PROOFSTEP]
rw [LiftRel.swap, liftRel_pure_left]
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
a : α
b : β
⊢ LiftRel R (pure a) (pure b) ↔ R a b
[PROOFSTEP]
rw [liftRel_pure_left]
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
a : α
b : β
⊢ (∃ b_1, b_1 ∈ pure b ∧ R a b_1) ↔ R a b
[PROOFSTEP]
exact ⟨fun ⟨b', mb', ab'⟩ => by rwa [eq_of_pure_mem mb'] at ab' , fun ab => ⟨_, ret_mem _, ab⟩⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
a : α
b : β
x✝ : ∃ b_1, b_1 ∈ pure b ∧ R a b_1
b' : β
mb' : b' ∈ pure b
ab' : R a b'
⊢ R a b
[PROOFSTEP]
rwa [eq_of_pure_mem mb'] at ab' 
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
ca : Computation α
cb : Computation β
⊢ LiftRel R ca (think cb) ↔ LiftRel R ca cb
[PROOFSTEP]
rw [← LiftRel.swap R, ← LiftRel.swap R]
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
ca : Computation α
cb : Computation β
⊢ LiftRel (swap R) (think cb) ca ↔ LiftRel (swap R) cb ca
[PROOFSTEP]
apply liftRel_think_left
[GOAL]
α : Type u
β : Type v
γ : Type w
δ : Type u_1
R : α → β → Prop
S : γ → δ → Prop
s1 : Computation α
s2 : Computation β
f1 : α → γ
f2 : β → δ
h1 : LiftRel R s1 s2
h2 : ∀ {a : α} {b : β}, R a b → S (f1 a) (f2 b)
⊢ LiftRel S (map f1 s1) (map f2 s2)
[PROOFSTEP]
rw [← bind_pure, ← bind_pure]
[GOAL]
α : Type u
β : Type v
γ : Type w
δ : Type u_1
R : α → β → Prop
S : γ → δ → Prop
s1 : Computation α
s2 : Computation β
f1 : α → γ
f2 : β → δ
h1 : LiftRel R s1 s2
h2 : ∀ {a : α} {b : β}, R a b → S (f1 a) (f2 b)
⊢ LiftRel S (bind s1 (pure ∘ f1)) (bind s2 (pure ∘ f2))
[PROOFSTEP]
apply liftRel_bind _ _ h1
[GOAL]
α : Type u
β : Type v
γ : Type w
δ : Type u_1
R : α → β → Prop
S : γ → δ → Prop
s1 : Computation α
s2 : Computation β
f1 : α → γ
f2 : β → δ
h1 : LiftRel R s1 s2
h2 : ∀ {a : α} {b : β}, R a b → S (f1 a) (f2 b)
⊢ ∀ {a : α} {b : β}, R a b → LiftRel S ((pure ∘ f1) a) ((pure ∘ f2) b)
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
γ : Type w
δ : Type u_1
R : α → β → Prop
S : γ → δ → Prop
s1 : Computation α
s2 : Computation β
f1 : α → γ
f2 : β → δ
h1 : LiftRel R s1 s2
h2 : ∀ {a : α} {b : β}, R a b → S (f1 a) (f2 b)
⊢ ∀ {a : α} {b : β}, R a b → ∃ a_2, a_2 ∈ pure (f1 a) ∧ S a_2 (f2 b)
[PROOFSTEP]
intros a b h
[GOAL]
α : Type u
β : Type v
γ : Type w
δ : Type u_1
R : α → β → Prop
S : γ → δ → Prop
s1 : Computation α
s2 : Computation β
f1 : α → γ
f2 : β → δ
h1 : LiftRel R s1 s2
h2 : ∀ {a : α} {b : β}, R a b → S (f1 a) (f2 b)
a : α
b : β
h : R a b
⊢ ∃ a_1, a_1 ∈ pure (f1 a) ∧ S a_1 (f2 b)
[PROOFSTEP]
exact ⟨f1 a, ⟨ret_mem _, @h2 a b h⟩⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
s1 s2 : Computation α
f : α → β
h1 : s1 ~ s2
⊢ map f s1 ~ map f s2
[PROOFSTEP]
rw [← lift_eq_iff_equiv]
[GOAL]
α : Type u
β : Type v
γ : Type w
s1 s2 : Computation α
f : α → β
h1 : s1 ~ s2
⊢ LiftRel (fun x x_1 => x = x_1) (map f s1) (map f s2)
[PROOFSTEP]
exact liftRel_map Eq _ ((lift_eq_iff_equiv _ _).2 h1) fun {a} b => congr_arg _
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
a : α
cb : Computation β
⊢ LiftRelAux R C (Sum.inl a) (destruct cb) ↔ ∃ b, b ∈ cb ∧ R a b
[PROOFSTEP]
apply cb.recOn (fun b => _) fun cb => _
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
a : α
cb : Computation β
⊢ ∀ (b : β), LiftRelAux R C (Sum.inl a) (destruct (pure b)) ↔ ∃ b_1, b_1 ∈ pure b ∧ R a b_1
[PROOFSTEP]
intro b
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
a : α
cb : Computation β
b : β
⊢ LiftRelAux R C (Sum.inl a) (destruct (pure b)) ↔ ∃ b_1, b_1 ∈ pure b ∧ R a b_1
[PROOFSTEP]
exact ⟨fun h => ⟨_, ret_mem _, h⟩, fun ⟨b', mb, h⟩ => by rw [mem_unique (ret_mem _) mb]; exact h⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
a : α
cb : Computation β
b : β
x✝ : ∃ b_1, b_1 ∈ pure b ∧ R a b_1
b' : β
mb : b' ∈ pure b
h : R a b'
⊢ LiftRelAux R C (Sum.inl a) (destruct (pure b))
[PROOFSTEP]
rw [mem_unique (ret_mem _) mb]
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
a : α
cb : Computation β
b : β
x✝ : ∃ b_1, b_1 ∈ pure b ∧ R a b_1
b' : β
mb : b' ∈ pure b
h : R a b'
⊢ LiftRelAux R C (Sum.inl a) (destruct (pure b'))
[PROOFSTEP]
exact h
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
a : α
cb : Computation β
⊢ ∀ (cb : Computation β), LiftRelAux R C (Sum.inl a) (destruct (think cb)) ↔ ∃ b, b ∈ think cb ∧ R a b
[PROOFSTEP]
intro
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
a : α
cb cb✝ : Computation β
⊢ LiftRelAux R C (Sum.inl a) (destruct (think cb✝)) ↔ ∃ b, b ∈ think cb✝ ∧ R a b
[PROOFSTEP]
rw [destruct_think]
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
a : α
cb cb✝ : Computation β
⊢ LiftRelAux R C (Sum.inl a) (Sum.inr cb✝) ↔ ∃ b, b ∈ think cb✝ ∧ R a b
[PROOFSTEP]
exact ⟨fun ⟨b, h, r⟩ => ⟨b, think_mem h, r⟩, fun ⟨b, h, r⟩ => ⟨b, of_think_mem h, r⟩⟩
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
a : α ⊕ Computation α
b : β ⊕ Computation β
⊢ LiftRelAux (Function.swap R) (Function.swap C) b a = LiftRelAux R C a b
[PROOFSTEP]
cases' a with a ca
[GOAL]
case inl
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
b : β ⊕ Computation β
a : α
⊢ LiftRelAux (Function.swap R) (Function.swap C) b (Sum.inl a) = LiftRelAux R C (Sum.inl a) b
[PROOFSTEP]
cases' b with b cb
[GOAL]
case inr
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
b : β ⊕ Computation β
ca : Computation α
⊢ LiftRelAux (Function.swap R) (Function.swap C) b (Sum.inr ca) = LiftRelAux R C (Sum.inr ca) b
[PROOFSTEP]
cases' b with b cb
[GOAL]
case inl.inl
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
a : α
b : β
⊢ LiftRelAux (Function.swap R) (Function.swap C) (Sum.inl b) (Sum.inl a) = LiftRelAux R C (Sum.inl a) (Sum.inl b)
[PROOFSTEP]
simp only [LiftRelAux]
[GOAL]
case inl.inr
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
a : α
cb : Computation β
⊢ LiftRelAux (Function.swap R) (Function.swap C) (Sum.inr cb) (Sum.inl a) = LiftRelAux R C (Sum.inl a) (Sum.inr cb)
[PROOFSTEP]
simp only [LiftRelAux]
[GOAL]
case inr.inl
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
ca : Computation α
b : β
⊢ LiftRelAux (Function.swap R) (Function.swap C) (Sum.inl b) (Sum.inr ca) = LiftRelAux R C (Sum.inr ca) (Sum.inl b)
[PROOFSTEP]
simp only [LiftRelAux]
[GOAL]
case inr.inr
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
ca : Computation α
cb : Computation β
⊢ LiftRelAux (Function.swap R) (Function.swap C) (Sum.inr cb) (Sum.inr ca) = LiftRelAux R C (Sum.inr ca) (Sum.inr cb)
[PROOFSTEP]
simp only [LiftRelAux]
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
b : β
ca : Computation α
⊢ LiftRelAux R C (destruct ca) (Sum.inl b) ↔ ∃ a, a ∈ ca ∧ R a b
[PROOFSTEP]
rw [← LiftRelAux.swap, LiftRelAux.ret_left]
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
cb : Computation β
Hc : C ca cb
a : α
ha : a ∈ ca
⊢ LiftRel R ca cb
[PROOFSTEP]
revert cb
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
a : α
ha : a ∈ ca
⊢ ∀ (cb : Computation β), C ca cb → LiftRel R ca cb
[PROOFSTEP]
refine' memRecOn (C := (λ ca => ∀ (cb : Computation β), C ca cb → LiftRel R ca cb)) ha _ (fun ca' IH => _)
[GOAL]
case refine'_1
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
a : α
ha : a ∈ ca
⊢ (fun ca => ∀ (cb : Computation β), C ca cb → LiftRel R ca cb) (pure a)
[PROOFSTEP]
intro cb Hc
[GOAL]
case refine'_2
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
a : α
ha : a ∈ ca
ca' : Computation α
IH : (fun ca => ∀ (cb : Computation β), C ca cb → LiftRel R ca cb) ca'
⊢ (fun ca => ∀ (cb : Computation β), C ca cb → LiftRel R ca cb) (think ca')
[PROOFSTEP]
intro cb Hc
[GOAL]
case refine'_1
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
a : α
ha : a ∈ ca
cb : Computation β
Hc : C (pure a) cb
⊢ LiftRel R (pure a) cb
[PROOFSTEP]
have h := H Hc
[GOAL]
case refine'_2
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
a : α
ha : a ∈ ca
ca' : Computation α
IH : (fun ca => ∀ (cb : Computation β), C ca cb → LiftRel R ca cb) ca'
cb : Computation β
Hc : C (think ca') cb
⊢ LiftRel R (think ca') cb
[PROOFSTEP]
have h := H Hc
[GOAL]
case refine'_1
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
a : α
ha : a ∈ ca
cb : Computation β
Hc : C (pure a) cb
h : LiftRelAux R C (destruct (pure a)) (destruct cb)
⊢ LiftRel R (pure a) cb
[PROOFSTEP]
simp at h 
[GOAL]
case refine'_1
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
a : α
ha : a ∈ ca
cb : Computation β
Hc : C (pure a) cb
h : ∃ b, b ∈ cb ∧ R a b
⊢ LiftRel R (pure a) cb
[PROOFSTEP]
simp [h]
[GOAL]
case refine'_2
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
a : α
ha : a ∈ ca
ca' : Computation α
IH : (fun ca => ∀ (cb : Computation β), C ca cb → LiftRel R ca cb) ca'
cb : Computation β
Hc : C (think ca') cb
h : LiftRelAux R C (destruct (think ca')) (destruct cb)
⊢ LiftRel R (think ca') cb
[PROOFSTEP]
simp
[GOAL]
case refine'_2
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
a : α
ha : a ∈ ca
ca' : Computation α
IH : (fun ca => ∀ (cb : Computation β), C ca cb → LiftRel R ca cb) ca'
cb : Computation β
Hc : C (think ca') cb
h : LiftRelAux R C (destruct (think ca')) (destruct cb)
⊢ LiftRel R ca' cb
[PROOFSTEP]
revert h
[GOAL]
case refine'_2
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
a : α
ha : a ∈ ca
ca' : Computation α
IH : (fun ca => ∀ (cb : Computation β), C ca cb → LiftRel R ca cb) ca'
cb : Computation β
Hc : C (think ca') cb
⊢ LiftRelAux R C (destruct (think ca')) (destruct cb) → LiftRel R ca' cb
[PROOFSTEP]
apply cb.recOn (fun b => _) fun cb' => _
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
a : α
ha : a ∈ ca
ca' : Computation α
IH : (fun ca => ∀ (cb : Computation β), C ca cb → LiftRel R ca cb) ca'
cb : Computation β
Hc : C (think ca') cb
⊢ ∀ (b : β), LiftRelAux R C (destruct (think ca')) (destruct (pure b)) → LiftRel R ca' (pure b)
[PROOFSTEP]
intros _ h
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
a : α
ha : a ∈ ca
ca' : Computation α
IH : (fun ca => ∀ (cb : Computation β), C ca cb → LiftRel R ca cb) ca'
cb : Computation β
Hc : C (think ca') cb
⊢ ∀ (cb' : Computation β), LiftRelAux R C (destruct (think ca')) (destruct (think cb')) → LiftRel R ca' (think cb')
[PROOFSTEP]
intros _ h
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
a : α
ha : a ∈ ca
ca' : Computation α
IH : (fun ca => ∀ (cb : Computation β), C ca cb → LiftRel R ca cb) ca'
cb : Computation β
Hc : C (think ca') cb
b✝ : β
h : LiftRelAux R C (destruct (think ca')) (destruct (pure b✝))
⊢ LiftRel R ca' (pure b✝)
[PROOFSTEP]
simp at h 
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
a : α
ha : a ∈ ca
ca' : Computation α
IH : (fun ca => ∀ (cb : Computation β), C ca cb → LiftRel R ca cb) ca'
cb : Computation β
Hc : C (think ca') cb
cb'✝ : Computation β
h : LiftRelAux R C (destruct (think ca')) (destruct (think cb'✝))
⊢ LiftRel R ca' (think cb'✝)
[PROOFSTEP]
simp at h 
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
a : α
ha : a ∈ ca
ca' : Computation α
IH : (fun ca => ∀ (cb : Computation β), C ca cb → LiftRel R ca cb) ca'
cb : Computation β
Hc : C (think ca') cb
b✝ : β
h : ∃ a, a ∈ ca' ∧ R a b✝
⊢ LiftRel R ca' (pure b✝)
[PROOFSTEP]
simp [h]
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
a : α
ha : a ∈ ca
ca' : Computation α
IH : (fun ca => ∀ (cb : Computation β), C ca cb → LiftRel R ca cb) ca'
cb : Computation β
Hc : C (think ca') cb
cb'✝ : Computation β
h : C ca' cb'✝
⊢ LiftRel R ca' (think cb'✝)
[PROOFSTEP]
simp [h]
[GOAL]
α : Type u
β : Type v
γ : Type w
R : α → β → Prop
C : Computation α → Computation β → Prop
H : ∀ {ca : Computation α} {cb : Computation β}, C ca cb → LiftRelAux R C (destruct ca) (destruct cb)
ca : Computation α
a : α
ha : a ∈ ca
ca' : Computation α
IH : (fun ca => ∀ (cb : Computation β), C ca cb → LiftRel R ca cb) ca'
cb : Computation β
Hc : C (think ca') cb
cb'✝ : Computation β
h : C ca' cb'✝
⊢ LiftRel R ca' cb'✝
[PROOFSTEP]
exact IH _ h
