union_eq — Mathlib

English

If xs and ys are disjoint, then xs ∪ ys equals xs.dedup ++ ys.

Русский

Если xs и ys дисjoint, то xs ∪ ys = xs.dedup ++ ys.

LaTeX

$$$xs \\ Disjoint\\ ys \\Rightarrow xs \\cup ys = xs.dedup \\;\\cup\\; ys$$$

Lean4

theorem union_eq {xs ys : List α} (h : Disjoint xs ys) : xs ∪ ys = xs.dedup ++ ys := by
  induction xs with
  | nil => simp
  | cons x xs ih =>
    rw [cons_union]
    rw [disjoint_cons_left] at h
    by_cases hx : x ∈ xs
    · rw [dedup_cons_of_mem hx, insert_of_mem (mem_union_left hx _), ih h.2]
    · rw [dedup_cons_of_notMem hx, insert_of_not_mem, ih h.2, cons_append]
      rw [mem_union_iff, not_or]
      exact ⟨hx, h.1⟩

Похожие утверждения