[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a✝ b a : α
l : List α
⊢ Nodup (a :: l) ↔ ¬a ∈ l ∧ Nodup l
[PROOFSTEP]
simp only [Nodup, pairwise_cons, forall_mem_ne]
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r✝ : α → α → Prop
a b : α
r : α → β → Prop
hr : Relator.BiUnique r
⊢ (fun x x_1 => x ↔ x_1) (Nodup []) (Nodup [])
[PROOFSTEP]
simp only [nodup_nil]
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r✝ : α → α → Prop
a b : α
r : α → β → Prop
hr : Relator.BiUnique r
a✝ : α
b✝ : β
l₁✝ : List α
l₂✝ : List β
hab : r a✝ b✝
h : Forall₂ r l₁✝ l₂✝
⊢ (fun x x_1 => x ↔ x_1) (Nodup (a✝ :: l₁✝)) (Nodup (b✝ :: l₂✝))
[PROOFSTEP]
simpa only [nodup_cons] using Relator.rel_and (Relator.rel_not (rel_mem hr hab h)) (rel_nodup hr h)
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
⊢ (∀ (a : α), ¬[a, a] <+ l) → Nodup l
[PROOFSTEP]
induction' l with a l IH
[GOAL]
case nil
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
⊢ (∀ (a : α), ¬[a, a] <+ []) → Nodup []
[PROOFSTEP]
intro h
[GOAL]
case cons
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a✝ b a : α
l : List α
IH : (∀ (a : α), ¬[a, a] <+ l) → Nodup l
⊢ (∀ (a_1 : α), ¬[a_1, a_1] <+ a :: l) → Nodup (a :: l)
[PROOFSTEP]
intro h
[GOAL]
case nil
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
h : ∀ (a : α), ¬[a, a] <+ []
⊢ Nodup []
[PROOFSTEP]
exact nodup_nil
[GOAL]
case cons
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a✝ b a : α
l : List α
IH : (∀ (a : α), ¬[a, a] <+ l) → Nodup l
h : ∀ (a_1 : α), ¬[a_1, a_1] <+ a :: l
⊢ Nodup (a :: l)
[PROOFSTEP]
exact (IH fun a s => h a <| sublist_cons_of_sublist _ s).cons fun al => h a <| (singleton_sublist.2 al).cons_cons _
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h : ∀ (i j : Fin (length l)), i < j → get l i ≠ get l j
i j : Fin (length l)
hg : get l i = get l j
⊢ i = j
[PROOFSTEP]
cases' i with i hi
[GOAL]
case mk
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h : ∀ (i j : Fin (length l)), i < j → get l i ≠ get l j
j : Fin (length l)
i : ℕ
hi : i < length l
hg : get l { val := i, isLt := hi } = get l j
⊢ { val := i, isLt := hi } = j
[PROOFSTEP]
cases' j with j hj
[GOAL]
case mk.mk
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h : ∀ (i j : Fin (length l)), i < j → get l i ≠ get l j
i : ℕ
hi : i < length l
j : ℕ
hj : j < length l
hg : get l { val := i, isLt := hi } = get l { val := j, isLt := hj }
⊢ { val := i, isLt := hi } = { val := j, isLt := hj }
[PROOFSTEP]
rcases lt_trichotomy i j with (hij | rfl | hji)
[GOAL]
case mk.mk.inl
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h : ∀ (i j : Fin (length l)), i < j → get l i ≠ get l j
i : ℕ
hi : i < length l
j : ℕ
hj : j < length l
hg : get l { val := i, isLt := hi } = get l { val := j, isLt := hj }
hij : i < j
⊢ { val := i, isLt := hi } = { val := j, isLt := hj }
[PROOFSTEP]
exact (h ⟨i, hi⟩ ⟨j, hj⟩ hij hg).elim
[GOAL]
case mk.mk.inr.inl
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h : ∀ (i j : Fin (length l)), i < j → get l i ≠ get l j
i : ℕ
hi hj : i < length l
hg : get l { val := i, isLt := hi } = get l { val := i, isLt := hj }
⊢ { val := i, isLt := hi } = { val := i, isLt := hj }
[PROOFSTEP]
rfl
[GOAL]
case mk.mk.inr.inr
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h : ∀ (i j : Fin (length l)), i < j → get l i ≠ get l j
i : ℕ
hi : i < length l
j : ℕ
hj : j < length l
hg : get l { val := i, isLt := hi } = get l { val := j, isLt := hj }
hji : j < i
⊢ { val := i, isLt := hi } = { val := j, isLt := hj }
[PROOFSTEP]
exact (h ⟨j, hj⟩ ⟨i, hi⟩ hji hg.symm).elim
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h : Nodup l
i j : ℕ
hi : i < length l
hj : j < length l
⊢ i = j → nthLe l i hi = nthLe l j hj
[PROOFSTEP]
simp (config := { contextual := true })
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
⊢ Nodup l ↔ ∀ (i j : ℕ), i < j → j < length l → get? l i ≠ get? l j
[PROOFSTEP]
rw [Nodup, pairwise_iff_get]
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
⊢ (∀ (i j : Fin (length l)), i < j → get l i ≠ get l j) ↔ ∀ (i j : ℕ), i < j → j < length l → get? l i ≠ get? l j
[PROOFSTEP]
constructor
[GOAL]
case mp
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
⊢ (∀ (i j : Fin (length l)), i < j → get l i ≠ get l j) → ∀ (i j : ℕ), i < j → j < length l → get? l i ≠ get? l j
[PROOFSTEP]
intro h i j hij hj
[GOAL]
case mp
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h : ∀ (i j : Fin (length l)), i < j → get l i ≠ get l j
i j : ℕ
hij : i < j
hj : j < length l
⊢ get? l i ≠ get? l j
[PROOFSTEP]
rw [get?_eq_get (lt_trans hij hj), get?_eq_get hj, Ne.def, Option.some_inj]
[GOAL]
case mp
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h : ∀ (i j : Fin (length l)), i < j → get l i ≠ get l j
i j : ℕ
hij : i < j
hj : j < length l
⊢ ¬get l { val := i, isLt := (_ : i < length l) } = get l { val := j, isLt := hj }
[PROOFSTEP]
exact h _ _ hij
[GOAL]
case mpr
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
⊢ (∀ (i j : ℕ), i < j → j < length l → get? l i ≠ get? l j) → ∀ (i j : Fin (length l)), i < j → get l i ≠ get l j
[PROOFSTEP]
intro h i j hij
[GOAL]
case mpr
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h : ∀ (i j : ℕ), i < j → j < length l → get? l i ≠ get? l j
i j : Fin (length l)
hij : i < j
⊢ get l i ≠ get l j
[PROOFSTEP]
rw [Ne.def, ← Option.some_inj, ← get?_eq_get, ← get?_eq_get]
[GOAL]
case mpr
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h : ∀ (i j : ℕ), i < j → j < length l → get? l i ≠ get? l j
i j : Fin (length l)
hij : i < j
⊢ ¬get? l ↑i = get? l ↑j
[PROOFSTEP]
exact h i j hij j.2
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h : Nodup l
x : α
⊢ l ≠ [x] ↔ l = [] ∨ ∃ y, y ∈ l ∧ y ≠ x
[PROOFSTEP]
induction' l with hd tl hl
[GOAL]
case nil
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h✝ : Nodup l
x : α
h : Nodup []
⊢ [] ≠ [x] ↔ [] = [] ∨ ∃ y, y ∈ [] ∧ y ≠ x
[PROOFSTEP]
simp
[GOAL]
case cons
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h✝ : Nodup l
x hd : α
tl : List α
hl : Nodup tl → (tl ≠ [x] ↔ tl = [] ∨ ∃ y, y ∈ tl ∧ y ≠ x)
h : Nodup (hd :: tl)
⊢ hd :: tl ≠ [x] ↔ hd :: tl = [] ∨ ∃ y, y ∈ hd :: tl ∧ y ≠ x
[PROOFSTEP]
specialize hl h.of_cons
[GOAL]
case cons
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h✝ : Nodup l
x hd : α
tl : List α
h : Nodup (hd :: tl)
hl : tl ≠ [x] ↔ tl = [] ∨ ∃ y, y ∈ tl ∧ y ≠ x
⊢ hd :: tl ≠ [x] ↔ hd :: tl = [] ∨ ∃ y, y ∈ hd :: tl ∧ y ≠ x
[PROOFSTEP]
by_cases hx : tl = [x]
[GOAL]
case pos
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h✝ : Nodup l
x hd : α
tl : List α
h : Nodup (hd :: tl)
hl : tl ≠ [x] ↔ tl = [] ∨ ∃ y, y ∈ tl ∧ y ≠ x
hx : tl = [x]
⊢ hd :: tl ≠ [x] ↔ hd :: tl = [] ∨ ∃ y, y ∈ hd :: tl ∧ y ≠ x
[PROOFSTEP]
simpa [hx, and_comm, and_or_left] using h
[GOAL]
case neg
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h✝ : Nodup l
x hd : α
tl : List α
h : Nodup (hd :: tl)
hl : tl ≠ [x] ↔ tl = [] ∨ ∃ y, y ∈ tl ∧ y ≠ x
hx : ¬tl = [x]
⊢ hd :: tl ≠ [x] ↔ hd :: tl = [] ∨ ∃ y, y ∈ hd :: tl ∧ y ≠ x
[PROOFSTEP]
rw [← Ne.def, hl] at hx 
[GOAL]
case neg
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h✝ : Nodup l
x hd : α
tl : List α
h : Nodup (hd :: tl)
hl : tl ≠ [x] ↔ tl = [] ∨ ∃ y, y ∈ tl ∧ y ≠ x
hx : tl = [] ∨ ∃ y, y ∈ tl ∧ y ≠ x
⊢ hd :: tl ≠ [x] ↔ hd :: tl = [] ∨ ∃ y, y ∈ hd :: tl ∧ y ≠ x
[PROOFSTEP]
rcases hx with (rfl | ⟨y, hy, hx⟩)
[GOAL]
case neg.inl
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h✝ : Nodup l
x hd : α
h : Nodup [hd]
hl : [] ≠ [x] ↔ [] = [] ∨ ∃ y, y ∈ [] ∧ y ≠ x
⊢ [hd] ≠ [x] ↔ [hd] = [] ∨ ∃ y, y ∈ [hd] ∧ y ≠ x
[PROOFSTEP]
simp
[GOAL]
case neg.inr.intro.intro
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h✝ : Nodup l
x hd : α
tl : List α
h : Nodup (hd :: tl)
hl : tl ≠ [x] ↔ tl = [] ∨ ∃ y, y ∈ tl ∧ y ≠ x
y : α
hy : y ∈ tl
hx : y ≠ x
⊢ hd :: tl ≠ [x] ↔ hd :: tl = [] ∨ ∃ y, y ∈ hd :: tl ∧ y ≠ x
[PROOFSTEP]
suffices ∃ (y : α) (_ : y ∈ hd :: tl), y ≠ x by simpa [ne_nil_of_mem hy]
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h✝ : Nodup l
x hd : α
tl : List α
h : Nodup (hd :: tl)
hl : tl ≠ [x] ↔ tl = [] ∨ ∃ y, y ∈ tl ∧ y ≠ x
y : α
hy : y ∈ tl
hx : y ≠ x
this : ∃ y x_1, y ≠ x
⊢ hd :: tl ≠ [x] ↔ hd :: tl = [] ∨ ∃ y, y ∈ hd :: tl ∧ y ≠ x
[PROOFSTEP]
simpa [ne_nil_of_mem hy]
[GOAL]
case neg.inr.intro.intro
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
h✝ : Nodup l
x hd : α
tl : List α
h : Nodup (hd :: tl)
hl : tl ≠ [x] ↔ tl = [] ∨ ∃ y, y ∈ tl ∧ y ≠ x
y : α
hy : y ∈ tl
hx : y ≠ x
⊢ ∃ y x_1, y ≠ x
[PROOFSTEP]
exact ⟨y, mem_cons_of_mem _ hy, hx⟩
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
xs : List α
n m : Fin (length xs)
h : get xs n = get xs m
hne : n ≠ m
⊢ ¬Nodup xs
[PROOFSTEP]
rw [nodup_iff_injective_get]
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
xs : List α
n m : Fin (length xs)
h : get xs n = get xs m
hne : n ≠ m
⊢ ¬Injective (get xs)
[PROOFSTEP]
exact fun hinj => hne (hinj h)
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
xs : List α
n m : ℕ
hn : n < length xs
hm : m < length xs
h : nthLe xs n hn = nthLe xs m hm
hne : n ≠ m
⊢ ¬Nodup xs
[PROOFSTEP]
rw [nodup_iff_nthLe_inj]
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
xs : List α
n m : ℕ
hn : n < length xs
hm : m < length xs
h : nthLe xs n hn = nthLe xs m hm
hne : n ≠ m
⊢ ¬∀ (i j : ℕ) (h₁ : i < length xs) (h₂ : j < length xs), nthLe xs i h₁ = nthLe xs j h₂ → i = j
[PROOFSTEP]
simp only [exists_prop, exists_and_right, not_forall]
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
xs : List α
n m : ℕ
hn : n < length xs
hm : m < length xs
h : nthLe xs n hn = nthLe xs m hm
hne : n ≠ m
⊢ ∃ x x_1, (∃ x_2 x_3, nthLe xs x (_ : x < length xs) = nthLe xs x_1 (_ : x_1 < length xs)) ∧ ¬x = x_1
[PROOFSTEP]
exact ⟨n, m, ⟨hn, hm, h⟩, hne⟩
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
l : List α
H : Nodup l
i : Fin (length l)
⊢ get l { val := indexOf (get l i) l, isLt := (_ : indexOf (get l i) l < length l) } = get l i
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a✝ b a : α
⊢ Nodup (replicate 0 a) ↔ 0 ≤ 1
[PROOFSTEP]
simp [Nat.zero_le]
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a✝ b a : α
⊢ Nodup (replicate 1 a) ↔ 1 ≤ 1
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a✝ b : α
inst✝ : DecidableEq α
a : α
l : List α
d : Nodup l
⊢ count a l = if a ∈ l then 1 else 0
[PROOFSTEP]
split_ifs with h
[GOAL]
case pos
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a✝ b : α
inst✝ : DecidableEq α
a : α
l : List α
d : Nodup l
h : a ∈ l
⊢ count a l = 1
[PROOFSTEP]
exact count_eq_one_of_mem d h
[GOAL]
case neg
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a✝ b : α
inst✝ : DecidableEq α
a : α
l : List α
d : Nodup l
h : ¬a ∈ l
⊢ count a l = 0
[PROOFSTEP]
exact count_eq_zero_of_not_mem h
[GOAL]
α : Type u
β : Type v
l l₁✝ l₂✝ : List α
r : α → α → Prop
a b : α
l₁ l₂ : List α
⊢ Nodup (l₁ ++ l₂) ↔ Nodup l₁ ∧ Nodup l₂ ∧ Disjoint l₁ l₂
[PROOFSTEP]
simp only [Nodup, pairwise_append, disjoint_iff_ne]
[GOAL]
α : Type u
β : Type v
l l₁✝ l₂✝ : List α
r : α → α → Prop
a b : α
l₁ l₂ : List α
⊢ Nodup (l₁ ++ l₂) ↔ Nodup (l₂ ++ l₁)
[PROOFSTEP]
simp only [nodup_append, and_left_comm, disjoint_comm]
[GOAL]
α : Type u
β : Type v
l l₁✝ l₂✝ : List α
r : α → α → Prop
a✝ b a : α
l₁ l₂ : List α
⊢ Nodup (l₁ ++ a :: l₂) ↔ Nodup (a :: (l₁ ++ l₂))
[PROOFSTEP]
simp only [nodup_append, not_or, and_left_comm, and_assoc, nodup_cons, mem_append, disjoint_cons_right]
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
f : α → β
l : List α
d : Nodup (map f l)
⊢ ∀ ⦃x : α⦄, x ∈ l → ∀ ⦃y : α⦄, y ∈ l → f x = f y → x = y
[PROOFSTEP]
induction' l with hd tl ih
[GOAL]
case nil
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
f : α → β
l : List α
d✝ : Nodup (map f l)
d : Nodup (map f [])
⊢ ∀ ⦃x : α⦄, x ∈ [] → ∀ ⦃y : α⦄, y ∈ [] → f x = f y → x = y
[PROOFSTEP]
simp
[GOAL]
case cons
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
f : α → β
l : List α
d✝ : Nodup (map f l)
hd : α
tl : List α
ih : Nodup (map f tl) → ∀ ⦃x : α⦄, x ∈ tl → ∀ ⦃y : α⦄, y ∈ tl → f x = f y → x = y
d : Nodup (map f (hd :: tl))
⊢ ∀ ⦃x : α⦄, x ∈ hd :: tl → ∀ ⦃y : α⦄, y ∈ hd :: tl → f x = f y → x = y
[PROOFSTEP]
simp only [map, nodup_cons, mem_map, not_exists, not_and, ← Ne.def] at d 
[GOAL]
case cons
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
f : α → β
l : List α
d✝ : Nodup (map f l)
hd : α
tl : List α
ih : Nodup (map f tl) → ∀ ⦃x : α⦄, x ∈ tl → ∀ ⦃y : α⦄, y ∈ tl → f x = f y → x = y
d : (∀ (x : α), x ∈ tl → f x ≠ f hd) ∧ Nodup (map f tl)
⊢ ∀ ⦃x : α⦄, x ∈ hd :: tl → ∀ ⦃y : α⦄, y ∈ hd :: tl → f x = f y → x = y
[PROOFSTEP]
simp only [mem_cons]
[GOAL]
case cons
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
f : α → β
l : List α
d✝ : Nodup (map f l)
hd : α
tl : List α
ih : Nodup (map f tl) → ∀ ⦃x : α⦄, x ∈ tl → ∀ ⦃y : α⦄, y ∈ tl → f x = f y → x = y
d : (∀ (x : α), x ∈ tl → f x ≠ f hd) ∧ Nodup (map f tl)
⊢ ∀ ⦃x : α⦄, x = hd ∨ x ∈ tl → ∀ ⦃y : α⦄, y = hd ∨ y ∈ tl → f x = f y → x = y
[PROOFSTEP]
rintro _ (rfl | h₁) _ (rfl | h₂) h₃
[GOAL]
case cons.inl.inl
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
f : α → β
l : List α
d✝ : Nodup (map f l)
tl : List α
ih : Nodup (map f tl) → ∀ ⦃x : α⦄, x ∈ tl → ∀ ⦃y : α⦄, y ∈ tl → f x = f y → x = y
y✝ : α
d : (∀ (x : α), x ∈ tl → f x ≠ f y✝) ∧ Nodup (map f tl)
h₃ : f y✝ = f y✝
⊢ y✝ = y✝
[PROOFSTEP]
rfl
[GOAL]
case cons.inl.inr
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
f : α → β
l : List α
d✝ : Nodup (map f l)
tl : List α
ih : Nodup (map f tl) → ∀ ⦃x : α⦄, x ∈ tl → ∀ ⦃y : α⦄, y ∈ tl → f x = f y → x = y
x✝ : α
d : (∀ (x : α), x ∈ tl → f x ≠ f x✝) ∧ Nodup (map f tl)
y✝ : α
h₂ : y✝ ∈ tl
h₃ : f x✝ = f y✝
⊢ x✝ = y✝
[PROOFSTEP]
apply (d.1 _ h₂ h₃.symm).elim
[GOAL]
case cons.inr.inl
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
f : α → β
l : List α
d✝ : Nodup (map f l)
tl : List α
ih : Nodup (map f tl) → ∀ ⦃x : α⦄, x ∈ tl → ∀ ⦃y : α⦄, y ∈ tl → f x = f y → x = y
x✝ : α
h₁ : x✝ ∈ tl
y✝ : α
d : (∀ (x : α), x ∈ tl → f x ≠ f y✝) ∧ Nodup (map f tl)
h₃ : f x✝ = f y✝
⊢ x✝ = y✝
[PROOFSTEP]
apply (d.1 _ h₁ h₃).elim
[GOAL]
case cons.inr.inr
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
f : α → β
l : List α
d✝ : Nodup (map f l)
hd : α
tl : List α
ih : Nodup (map f tl) → ∀ ⦃x : α⦄, x ∈ tl → ∀ ⦃y : α⦄, y ∈ tl → f x = f y → x = y
d : (∀ (x : α), x ∈ tl → f x ≠ f hd) ∧ Nodup (map f tl)
x✝ : α
h₁ : x✝ ∈ tl
y✝ : α
h₂ : y✝ ∈ tl
h₃ : f x✝ = f y✝
⊢ x✝ = y✝
[PROOFSTEP]
apply ih d.2 h₁ h₂ h₃
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
p : α → Prop
f : (a : α) → p a → β
l : List α
H : ∀ (a : α), a ∈ l → p a
hf : ∀ (a : α) (ha : p a) (b : α) (hb : p b), f a ha = f b hb → a = b
h : Nodup l
⊢ Nodup (List.pmap f l H)
[PROOFSTEP]
rw [pmap_eq_map_attach]
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
p : α → Prop
f : (a : α) → p a → β
l : List α
H : ∀ (a : α), a ∈ l → p a
hf : ∀ (a : α) (ha : p a) (b : α) (hb : p b), f a ha = f b hb → a = b
h : Nodup l
⊢ Nodup (map (fun x => f ↑x (_ : p ↑x)) (List.attach l))
[PROOFSTEP]
exact h.attach.map fun ⟨a, ha⟩ ⟨b, hb⟩ h => by congr; exact hf a (H _ ha) b (H _ hb) h
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a✝ b✝ : α
p : α → Prop
f : (a : α) → p a → β
l : List α
H : ∀ (a : α), a ∈ l → p a
hf : ∀ (a : α) (ha : p a) (b : α) (hb : p b), f a ha = f b hb → a = b
h✝ : Nodup l
x✝¹ x✝ : { x // x ∈ l }
a : α
ha : a ∈ l
b : α
hb : b ∈ l
h :
  f ↑{ val := a, property := ha } (_ : p ↑{ val := a, property := ha }) =
    f ↑{ val := b, property := hb } (_ : p ↑{ val := b, property := hb })
⊢ { val := a, property := ha } = { val := b, property := hb }
[PROOFSTEP]
congr
[GOAL]
case e_val
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a✝ b✝ : α
p : α → Prop
f : (a : α) → p a → β
l : List α
H : ∀ (a : α), a ∈ l → p a
hf : ∀ (a : α) (ha : p a) (b : α) (hb : p b), f a ha = f b hb → a = b
h✝ : Nodup l
x✝¹ x✝ : { x // x ∈ l }
a : α
ha : a ∈ l
b : α
hb : b ∈ l
h :
  f ↑{ val := a, property := ha } (_ : p ↑{ val := a, property := ha }) =
    f ↑{ val := b, property := hb } (_ : p ↑{ val := b, property := hb })
⊢ a = b
[PROOFSTEP]
exact hf a (H _ ha) b (H _ hb) h
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
p : α → Bool
l : List α
⊢ Nodup l → Nodup (List.filter p l)
[PROOFSTEP]
simpa using Pairwise.filter (fun a ↦ p a)
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
l : List α
⊢ Pairwise (fun a b => b ≠ a) l ↔ Nodup l
[PROOFSTEP]
simp only [Nodup, Ne.def, eq_comm]
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a✝ b : α
inst✝ : DecidableEq α
l : List α
d : Nodup l
a : α
⊢ List.erase l a = List.filter (fun x => decide (x ≠ a)) l
[PROOFSTEP]
induction' d with b l m _ IH
[GOAL]
case nil
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a✝ b : α
inst✝ : DecidableEq α
l : List α
a : α
⊢ List.erase [] a = List.filter (fun x => decide (x ≠ a)) []
[PROOFSTEP]
rfl
[GOAL]
case cons
α : Type u
β : Type v
l✝¹ l₁ l₂ : List α
r : α → α → Prop
a✝¹ b✝ : α
inst✝ : DecidableEq α
l✝ : List α
a b : α
l : List α
m : ∀ (a' : α), a' ∈ l → b ≠ a'
a✝ : Pairwise (fun x x_1 => x ≠ x_1) l
IH : List.erase l a = List.filter (fun x => decide (x ≠ a)) l
⊢ List.erase (b :: l) a = List.filter (fun x => decide (x ≠ a)) (b :: l)
[PROOFSTEP]
by_cases h : b = a
[GOAL]
case pos
α : Type u
β : Type v
l✝¹ l₁ l₂ : List α
r : α → α → Prop
a✝¹ b✝ : α
inst✝ : DecidableEq α
l✝ : List α
a b : α
l : List α
m : ∀ (a' : α), a' ∈ l → b ≠ a'
a✝ : Pairwise (fun x x_1 => x ≠ x_1) l
IH : List.erase l a = List.filter (fun x => decide (x ≠ a)) l
h : b = a
⊢ List.erase (b :: l) a = List.filter (fun x => decide (x ≠ a)) (b :: l)
[PROOFSTEP]
subst h
[GOAL]
case pos
α : Type u
β : Type v
l✝¹ l₁ l₂ : List α
r : α → α → Prop
a b✝ : α
inst✝ : DecidableEq α
l✝ : List α
b : α
l : List α
m : ∀ (a' : α), a' ∈ l → b ≠ a'
a✝ : Pairwise (fun x x_1 => x ≠ x_1) l
IH : List.erase l b = List.filter (fun x => decide (x ≠ b)) l
⊢ List.erase (b :: l) b = List.filter (fun x => decide (x ≠ b)) (b :: l)
[PROOFSTEP]
rw [erase_cons_head, filter_cons_of_neg _ (by simp)]
[GOAL]
α : Type u
β : Type v
l✝¹ l₁ l₂ : List α
r : α → α → Prop
a b✝ : α
inst✝ : DecidableEq α
l✝ : List α
b : α
l : List α
m : ∀ (a' : α), a' ∈ l → b ≠ a'
a✝ : Pairwise (fun x x_1 => x ≠ x_1) l
IH : List.erase l b = List.filter (fun x => decide (x ≠ b)) l
⊢ ¬decide (b ≠ b) = true
[PROOFSTEP]
simp
[GOAL]
case pos
α : Type u
β : Type v
l✝¹ l₁ l₂ : List α
r : α → α → Prop
a b✝ : α
inst✝ : DecidableEq α
l✝ : List α
b : α
l : List α
m : ∀ (a' : α), a' ∈ l → b ≠ a'
a✝ : Pairwise (fun x x_1 => x ≠ x_1) l
IH : List.erase l b = List.filter (fun x => decide (x ≠ b)) l
⊢ l = List.filter (fun x => decide (x ≠ b)) l
[PROOFSTEP]
symm
[GOAL]
case pos
α : Type u
β : Type v
l✝¹ l₁ l₂ : List α
r : α → α → Prop
a b✝ : α
inst✝ : DecidableEq α
l✝ : List α
b : α
l : List α
m : ∀ (a' : α), a' ∈ l → b ≠ a'
a✝ : Pairwise (fun x x_1 => x ≠ x_1) l
IH : List.erase l b = List.filter (fun x => decide (x ≠ b)) l
⊢ List.filter (fun x => decide (x ≠ b)) l = l
[PROOFSTEP]
rw [filter_eq_self]
[GOAL]
case pos
α : Type u
β : Type v
l✝¹ l₁ l₂ : List α
r : α → α → Prop
a b✝ : α
inst✝ : DecidableEq α
l✝ : List α
b : α
l : List α
m : ∀ (a' : α), a' ∈ l → b ≠ a'
a✝ : Pairwise (fun x x_1 => x ≠ x_1) l
IH : List.erase l b = List.filter (fun x => decide (x ≠ b)) l
⊢ ∀ (a : α), a ∈ l → decide (a ≠ b) = true
[PROOFSTEP]
simpa [@eq_comm α] using m
[GOAL]
case neg
α : Type u
β : Type v
l✝¹ l₁ l₂ : List α
r : α → α → Prop
a✝¹ b✝ : α
inst✝ : DecidableEq α
l✝ : List α
a b : α
l : List α
m : ∀ (a' : α), a' ∈ l → b ≠ a'
a✝ : Pairwise (fun x x_1 => x ≠ x_1) l
IH : List.erase l a = List.filter (fun x => decide (x ≠ a)) l
h : ¬b = a
⊢ List.erase (b :: l) a = List.filter (fun x => decide (x ≠ a)) (b :: l)
[PROOFSTEP]
rw [erase_cons_tail _ h, filter_cons_of_pos, IH]
[GOAL]
case neg.pa
α : Type u
β : Type v
l✝¹ l₁ l₂ : List α
r : α → α → Prop
a✝¹ b✝ : α
inst✝ : DecidableEq α
l✝ : List α
a b : α
l : List α
m : ∀ (a' : α), a' ∈ l → b ≠ a'
a✝ : Pairwise (fun x x_1 => x ≠ x_1) l
IH : List.erase l a = List.filter (fun x => decide (x ≠ a)) l
h : ¬b = a
⊢ decide (b ≠ a) = true
[PROOFSTEP]
simp [h]
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
d : Nodup l
⊢ a ∈ List.erase l b ↔ a ≠ b ∧ a ∈ l
[PROOFSTEP]
rw [d.erase_eq_filter, mem_filter, and_comm, decide_eq_true_iff]
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
L : List (List α)
⊢ Nodup (join L) ↔ (∀ (l : List α), l ∈ L → Nodup l) ∧ Pairwise Disjoint L
[PROOFSTEP]
simp only [Nodup, pairwise_join, disjoint_left.symm, forall_mem_ne]
[GOAL]
α : Type u
β : Type v
l l₁✝ l₂ : List α
r : α → α → Prop
a b : α
l₁ : List α
f : α → List β
⊢ Nodup (List.bind l₁ f) ↔ (∀ (x : α), x ∈ l₁ → Nodup (f x)) ∧ Pairwise (fun a b => Disjoint (f a) (f b)) l₁
[PROOFSTEP]
simp only [List.bind, nodup_join, pairwise_map, and_comm, and_left_comm, mem_map, exists_imp, and_imp]
[GOAL]
α : Type u
β : Type v
l l₁✝ l₂ : List α
r : α → α → Prop
a b : α
l₁ : List α
f : α → List β
⊢ (Pairwise (fun a b => Disjoint (f a) (f b)) l₁ ∧ ∀ (l : List β) (x : α), f x = l → x ∈ l₁ → Nodup l) ↔
    Pairwise (fun a b => Disjoint (f a) (f b)) l₁ ∧ ∀ (x : α), x ∈ l₁ → Nodup (f x)
[PROOFSTEP]
rw [show (∀ (l : List β) (x : α), f x = l → x ∈ l₁ → Nodup l) ↔ ∀ x : α, x ∈ l₁ → Nodup (f x) from
    forall_swap.trans <| forall_congr' fun _ => forall_eq']
[GOAL]
α : Type u
β : Type v
l l₁ l₂✝ : List α
r : α → α → Prop
a b : α
l₂ : List β
d₁ : Nodup l₁
d₂ : Nodup l₂
a₁ a₂ : α
n : a₁ ≠ a₂
x : α × β
h₁ : x ∈ map (Prod.mk a₁) l₂
h₂ : x ∈ map (Prod.mk a₂) l₂
⊢ False
[PROOFSTEP]
rcases mem_map.1 h₁ with ⟨b₁, _, rfl⟩
[GOAL]
case intro.intro
α : Type u
β : Type v
l l₁ l₂✝ : List α
r : α → α → Prop
a b : α
l₂ : List β
d₁ : Nodup l₁
d₂ : Nodup l₂
a₁ a₂ : α
n : a₁ ≠ a₂
b₁ : β
left✝ : b₁ ∈ l₂
h₁ : (a₁, b₁) ∈ map (Prod.mk a₁) l₂
h₂ : (a₁, b₁) ∈ map (Prod.mk a₂) l₂
⊢ False
[PROOFSTEP]
rcases mem_map.1 h₂ with ⟨b₂, mb₂, ⟨⟩⟩
[GOAL]
case intro.intro.intro.intro.refl
α : Type u
β : Type v
l l₁ l₂✝ : List α
r : α → α → Prop
a b : α
l₂ : List β
d₁ : Nodup l₁
d₂ : Nodup l₂
a₁ : α
b₁ : β
left✝ : b₁ ∈ l₂
h₁ : (a₁, b₁) ∈ map (Prod.mk a₁) l₂
n : a₁ ≠ a₁
h₂ : (a₁, b₁) ∈ map (Prod.mk a₁) l₂
mb₂ : b₁ ∈ l₂
⊢ False
[PROOFSTEP]
exact n rfl
[GOAL]
α : Type u
β : Type v
l l₁ l₂✝ : List α
r : α → α → Prop
a✝ b✝ : α
σ : α → Type u_1
l₂ : (a : α) → List (σ a)
d₁ : Nodup l₁
d₂ : ∀ (a : α), Nodup (l₂ a)
a : α
x✝ : a ∈ l₁
b b' : (fun a => σ a) a
h : { fst := a, snd := b } = { fst := a, snd := b' }
⊢ b = b'
[PROOFSTEP]
injection h with _ h
[GOAL]
α : Type u
β : Type v
l l₁ l₂✝ : List α
r : α → α → Prop
a b : α
σ : α → Type u_1
l₂ : (a : α) → List (σ a)
d₁ : Nodup l₁
d₂ : ∀ (a : α), Nodup (l₂ a)
a₁ a₂ : α
n : a₁ ≠ a₂
x : (a : α) × σ a
h₁ : x ∈ map (Sigma.mk a₁) (l₂ a₁)
h₂ : x ∈ map (Sigma.mk a₂) (l₂ a₂)
⊢ False
[PROOFSTEP]
rcases mem_map.1 h₁ with ⟨b₁, _, rfl⟩
[GOAL]
case intro.intro
α : Type u
β : Type v
l l₁ l₂✝ : List α
r : α → α → Prop
a b : α
σ : α → Type u_1
l₂ : (a : α) → List (σ a)
d₁ : Nodup l₁
d₂ : ∀ (a : α), Nodup (l₂ a)
a₁ a₂ : α
n : a₁ ≠ a₂
b₁ : σ a₁
left✝ : b₁ ∈ l₂ a₁
h₁ : { fst := a₁, snd := b₁ } ∈ map (Sigma.mk a₁) (l₂ a₁)
h₂ : { fst := a₁, snd := b₁ } ∈ map (Sigma.mk a₂) (l₂ a₂)
⊢ False
[PROOFSTEP]
rcases mem_map.1 h₂ with ⟨b₂, mb₂, ⟨⟩⟩
[GOAL]
case intro.intro.intro.intro.refl
α : Type u
β : Type v
l l₁ l₂✝ : List α
r : α → α → Prop
a b : α
σ : α → Type u_1
l₂ : (a : α) → List (σ a)
d₁ : Nodup l₁
d₂ : ∀ (a : α), Nodup (l₂ a)
a₁ : α
b₁ : σ a₁
left✝ : b₁ ∈ l₂ a₁
h₁ : { fst := a₁, snd := b₁ } ∈ map (Sigma.mk a₁) (l₂ a₁)
n : a₁ ≠ a₁
h₂ : { fst := a₁, snd := b₁ } ∈ map (Sigma.mk a₁) (l₂ a₁)
mb₂ : b₁ ∈ l₂ a₁
⊢ False
[PROOFSTEP]
exact n rfl
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a✝ b✝ : α
f : α → Option β
h : ∀ (a a' : α) (b : β), b ∈ f a → b ∈ f a' → a = a'
a a' : α
n : a ≠ a'
b : β
bm : b ∈ f a
b' : β
bm' : b' ∈ f a'
e : b = b'
⊢ b' ∈ f a
[PROOFSTEP]
rw [← e]
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a✝ b✝ : α
f : α → Option β
h : ∀ (a a' : α) (b : β), b ∈ f a → b ∈ f a' → a = a'
a a' : α
n : a ≠ a'
b : β
bm : b ∈ f a
b' : β
bm' : b' ∈ f a'
e : b = b'
⊢ b ∈ f a
[PROOFSTEP]
exact bm
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
h : ¬a ∈ l
h' : Nodup l
⊢ Nodup (concat l a)
[PROOFSTEP]
rw [concat_eq_append]
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
h : ¬a ∈ l
h' : Nodup l
⊢ Nodup (l ++ [a])
[PROOFSTEP]
exact h'.append (nodup_singleton _) (disjoint_singleton.2 h)
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
h : Nodup l
h' : a ∈ l
⊢ Nodup (List.insert a l)
[PROOFSTEP]
rw [insert_of_mem h']
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
h : Nodup l
h' : a ∈ l
⊢ Nodup l
[PROOFSTEP]
exact h
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
h : Nodup l
h' : ¬a ∈ l
⊢ Nodup (List.insert a l)
[PROOFSTEP]
rw [insert_of_not_mem h', nodup_cons]
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
h : Nodup l
h' : ¬a ∈ l
⊢ ¬a ∈ l ∧ Nodup l
[PROOFSTEP]
constructor
[GOAL]
case left
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
h : Nodup l
h' : ¬a ∈ l
⊢ ¬a ∈ l
[PROOFSTEP]
assumption
[GOAL]
case right
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
h : Nodup l
h' : ¬a ∈ l
⊢ Nodup l
[PROOFSTEP]
assumption
[GOAL]
α : Type u
β : Type v
l l₁✝ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
l₁ : List α
h : Nodup l₂
⊢ Nodup (l₁ ∪ l₂)
[PROOFSTEP]
induction' l₁ with a l₁ ih generalizing l₂
[GOAL]
case nil
α : Type u
β : Type v
l l₁ l₂✝ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
h✝ : Nodup l₂✝
l₂ : List α
h : Nodup l₂
⊢ Nodup ([] ∪ l₂)
[PROOFSTEP]
exact h
[GOAL]
case cons
α : Type u
β : Type v
l l₁✝ l₂✝ : List α
r : α → α → Prop
a✝ b : α
inst✝ : DecidableEq α
h✝ : Nodup l₂✝
a : α
l₁ : List α
ih : ∀ {l₂ : List α}, Nodup l₂ → Nodup (l₁ ∪ l₂)
l₂ : List α
h : Nodup l₂
⊢ Nodup (a :: l₁ ∪ l₂)
[PROOFSTEP]
exact (ih h).insert
[GOAL]
α : Type u
β : Type v
l l₁✝ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
l₁ : List α
x✝ : Nodup l₁
⊢ List.diff l₁ [] = List.filter (fun x => decide ¬x ∈ []) l₁
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
l l₁✝ l₂✝ : List α
r : α → α → Prop
a✝ b : α
inst✝ : DecidableEq α
l₁ : List α
a : α
l₂ : List α
hl₁ : Nodup l₁
⊢ List.diff l₁ (a :: l₂) = List.filter (fun x => decide ¬x ∈ a :: l₂) l₁
[PROOFSTEP]
rw [diff_cons, (hl₁.erase _).diff_eq_filter, hl₁.erase_eq_filter, filter_filter]
[GOAL]
α : Type u
β : Type v
l l₁✝ l₂✝ : List α
r : α → α → Prop
a✝ b : α
inst✝ : DecidableEq α
l₁ : List α
a : α
l₂ : List α
hl₁ : Nodup l₁
⊢ List.filter (fun a_1 => decide ((decide ¬a_1 ∈ l₂) = true ∧ decide (a_1 ≠ a) = true)) l₁ =
    List.filter (fun x => decide ¬x ∈ a :: l₂) l₁
[PROOFSTEP]
simp only [decide_not, Bool.not_eq_true', decide_eq_false_iff_not, ne_eq, and_comm, Bool.decide_and, find?, mem_cons,
  not_or]
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
hl₁ : Nodup l₁
⊢ a ∈ List.diff l₁ l₂ ↔ a ∈ l₁ ∧ ¬a ∈ l₂
[PROOFSTEP]
rw [hl₁.diff_eq_filter, mem_filter, decide_eq_true_iff]
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
l : List α
hl : Nodup l
f : α → β
x : α
y : β
⊢ map (update f x y) l = if x ∈ l then set (map f l) (indexOf x l) y else map f l
[PROOFSTEP]
induction' l with hd tl ihl
[GOAL]
case nil
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
l : List α
hl✝ : Nodup l
f : α → β
x : α
y : β
hl : Nodup []
⊢ map (update f x y) [] = if x ∈ [] then set (map f []) (indexOf x []) y else map f []
[PROOFSTEP]
simp
[GOAL]
case cons
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
l : List α
hl✝ : Nodup l
f : α → β
x : α
y : β
hd : α
tl : List α
ihl : Nodup tl → map (update f x y) tl = if x ∈ tl then set (map f tl) (indexOf x tl) y else map f tl
hl : Nodup (hd :: tl)
⊢ map (update f x y) (hd :: tl) =
    if x ∈ hd :: tl then set (map f (hd :: tl)) (indexOf x (hd :: tl)) y else map f (hd :: tl)
[PROOFSTEP]
rw [nodup_cons] at hl 
[GOAL]
case cons
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
l : List α
hl✝ : Nodup l
f : α → β
x : α
y : β
hd : α
tl : List α
ihl : Nodup tl → map (update f x y) tl = if x ∈ tl then set (map f tl) (indexOf x tl) y else map f tl
hl : ¬hd ∈ tl ∧ Nodup tl
⊢ map (update f x y) (hd :: tl) =
    if x ∈ hd :: tl then set (map f (hd :: tl)) (indexOf x (hd :: tl)) y else map f (hd :: tl)
[PROOFSTEP]
simp only [mem_cons, map, ihl hl.2]
[GOAL]
case cons
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
l : List α
hl✝ : Nodup l
f : α → β
x : α
y : β
hd : α
tl : List α
ihl : Nodup tl → map (update f x y) tl = if x ∈ tl then set (map f tl) (indexOf x tl) y else map f tl
hl : ¬hd ∈ tl ∧ Nodup tl
⊢ (update f x y hd :: if x ∈ tl then set (map f tl) (indexOf x tl) y else map f tl) =
    if x = hd ∨ x ∈ tl then set (f hd :: map f tl) (indexOf x (hd :: tl)) y else f hd :: map f tl
[PROOFSTEP]
by_cases H : hd = x
[GOAL]
case pos
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
l : List α
hl✝ : Nodup l
f : α → β
x : α
y : β
hd : α
tl : List α
ihl : Nodup tl → map (update f x y) tl = if x ∈ tl then set (map f tl) (indexOf x tl) y else map f tl
hl : ¬hd ∈ tl ∧ Nodup tl
H : hd = x
⊢ (update f x y hd :: if x ∈ tl then set (map f tl) (indexOf x tl) y else map f tl) =
    if x = hd ∨ x ∈ tl then set (f hd :: map f tl) (indexOf x (hd :: tl)) y else f hd :: map f tl
[PROOFSTEP]
subst hd
[GOAL]
case pos
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
l : List α
hl✝ : Nodup l
f : α → β
x : α
y : β
tl : List α
ihl : Nodup tl → map (update f x y) tl = if x ∈ tl then set (map f tl) (indexOf x tl) y else map f tl
hl : ¬x ∈ tl ∧ Nodup tl
⊢ (update f x y x :: if x ∈ tl then set (map f tl) (indexOf x tl) y else map f tl) =
    if x = x ∨ x ∈ tl then set (f x :: map f tl) (indexOf x (x :: tl)) y else f x :: map f tl
[PROOFSTEP]
simp [set, hl.1]
[GOAL]
case neg
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
l : List α
hl✝ : Nodup l
f : α → β
x : α
y : β
hd : α
tl : List α
ihl : Nodup tl → map (update f x y) tl = if x ∈ tl then set (map f tl) (indexOf x tl) y else map f tl
hl : ¬hd ∈ tl ∧ Nodup tl
H : ¬hd = x
⊢ (update f x y hd :: if x ∈ tl then set (map f tl) (indexOf x tl) y else map f tl) =
    if x = hd ∨ x ∈ tl then set (f hd :: map f tl) (indexOf x (hd :: tl)) y else f hd :: map f tl
[PROOFSTEP]
simp [Ne.symm H, H, set, ← apply_ite (cons (f hd))]
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r✝ : α → α → Prop
a b : α
l : List α
r : α → α → Prop
hl : Nodup l
h : ∀ (a : α), a ∈ l → ∀ (b : α), b ∈ l → a ≠ b → r a b
⊢ Pairwise r l
[PROOFSTEP]
classical
refine' pairwise_of_reflexive_on_dupl_of_forall_ne _ h
intro x hx
rw [nodup_iff_count_le_one] at hl 
exact absurd (hl x) hx.not_le
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r✝ : α → α → Prop
a b : α
l : List α
r : α → α → Prop
hl : Nodup l
h : ∀ (a : α), a ∈ l → ∀ (b : α), b ∈ l → a ≠ b → r a b
⊢ Pairwise r l
[PROOFSTEP]
refine' pairwise_of_reflexive_on_dupl_of_forall_ne _ h
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r✝ : α → α → Prop
a b : α
l : List α
r : α → α → Prop
hl : Nodup l
h : ∀ (a : α), a ∈ l → ∀ (b : α), b ∈ l → a ≠ b → r a b
⊢ ∀ (a : α), 1 < count a l → r a a
[PROOFSTEP]
intro x hx
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r✝ : α → α → Prop
a b : α
l : List α
r : α → α → Prop
hl : Nodup l
h : ∀ (a : α), a ∈ l → ∀ (b : α), b ∈ l → a ≠ b → r a b
x : α
hx : 1 < count x l
⊢ r x x
[PROOFSTEP]
rw [nodup_iff_count_le_one] at hl 
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r✝ : α → α → Prop
a b : α
l : List α
r : α → α → Prop
hl✝ : Nodup l
hl : ∀ (a : α), count a l ≤ 1
h : ∀ (a : α), a ∈ l → ∀ (b : α), b ∈ l → a ≠ b → r a b
x : α
hx : 1 < count x l
⊢ r x x
[PROOFSTEP]
exact absurd (hl x) hx.not_le
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : IsSymm α r
hl : Nodup l
⊢ Set.Pairwise {a | a ∈ l} r ↔ Pairwise r l
[PROOFSTEP]
induction' l with a l ih
[GOAL]
case nil
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : IsSymm α r
hl✝ : Nodup l
hl : Nodup []
⊢ Set.Pairwise {a | a ∈ []} r ↔ Pairwise r []
[PROOFSTEP]
simp
[GOAL]
case cons
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a✝ b : α
inst✝ : IsSymm α r
hl✝ : Nodup l✝
a : α
l : List α
ih : Nodup l → (Set.Pairwise {a | a ∈ l} r ↔ Pairwise r l)
hl : Nodup (a :: l)
⊢ Set.Pairwise {a_1 | a_1 ∈ a :: l} r ↔ Pairwise r (a :: l)
[PROOFSTEP]
rw [List.nodup_cons] at hl 
[GOAL]
case cons
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a✝ b : α
inst✝ : IsSymm α r
hl✝ : Nodup l✝
a : α
l : List α
ih : Nodup l → (Set.Pairwise {a | a ∈ l} r ↔ Pairwise r l)
hl : ¬a ∈ l ∧ Nodup l
⊢ Set.Pairwise {a_1 | a_1 ∈ a :: l} r ↔ Pairwise r (a :: l)
[PROOFSTEP]
have : ∀ b ∈ l, ¬a = b → r a b ↔ r a b := fun b hb => imp_iff_right (ne_of_mem_of_not_mem hb hl.1).symm
[GOAL]
case cons
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a✝ b : α
inst✝ : IsSymm α r
hl✝ : Nodup l✝
a : α
l : List α
ih : Nodup l → (Set.Pairwise {a | a ∈ l} r ↔ Pairwise r l)
hl : ¬a ∈ l ∧ Nodup l
this : ∀ (b : α), b ∈ l → (¬a = b → r a b ↔ r a b)
⊢ Set.Pairwise {a_1 | a_1 ∈ a :: l} r ↔ Pairwise r (a :: l)
[PROOFSTEP]
simp [Set.setOf_or, Set.pairwise_insert_of_symmetric (@symm_of _ r _), ih hl.2, and_comm, forall₂_congr this]
[GOAL]
α : Type u
β : Type v
l l₁ l₂ : List α
r : α → α → Prop
a b : α
inst✝ : DecidableEq α
n : ℕ
x✝ : Nodup []
⊢ take n [] = List.filter (fun x => decide (x ∈ take n [])) []
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b✝ : α
inst✝ : DecidableEq α
b : α
l : List α
x✝ : Nodup (b :: l)
⊢ take 0 (b :: l) = List.filter (fun x => decide (x ∈ take 0 (b :: l))) (b :: l)
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b✝ : α
inst✝ : DecidableEq α
b : α
l : List α
n : ℕ
hl : Nodup (b :: l)
⊢ take (n + 1) (b :: l) = List.filter (fun x => decide (x ∈ take (n + 1) (b :: l))) (b :: l)
[PROOFSTEP]
rw [take_cons, Nodup.take_eq_filter_mem (Nodup.of_cons hl), List.filter_cons_of_pos _ (by simp)]
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b✝ : α
inst✝ : DecidableEq α
b : α
l : List α
n : ℕ
hl : Nodup (b :: l)
⊢ decide (b ∈ b :: List.filter (fun x => decide (x ∈ take n l)) l) = true
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b✝ : α
inst✝ : DecidableEq α
b : α
l : List α
n : ℕ
hl : Nodup (b :: l)
⊢ b :: List.filter (fun x => decide (x ∈ take n l)) l =
    b :: List.filter (fun x => decide (x ∈ b :: List.filter (fun x => decide (x ∈ take n l)) l)) l
[PROOFSTEP]
congr 1
[GOAL]
case e_tail
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b✝ : α
inst✝ : DecidableEq α
b : α
l : List α
n : ℕ
hl : Nodup (b :: l)
⊢ List.filter (fun x => decide (x ∈ take n l)) l =
    List.filter (fun x => decide (x ∈ b :: List.filter (fun x => decide (x ∈ take n l)) l)) l
[PROOFSTEP]
refine' List.filter_congr' _
[GOAL]
case e_tail
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b✝ : α
inst✝ : DecidableEq α
b : α
l : List α
n : ℕ
hl : Nodup (b :: l)
⊢ ∀ (x : α),
    x ∈ l → (decide (x ∈ take n l) = true ↔ decide (x ∈ b :: List.filter (fun x => decide (x ∈ take n l)) l) = true)
[PROOFSTEP]
intro x hx
[GOAL]
case e_tail
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b✝ : α
inst✝ : DecidableEq α
b : α
l : List α
n : ℕ
hl : Nodup (b :: l)
x : α
hx : x ∈ l
⊢ decide (x ∈ take n l) = true ↔ decide (x ∈ b :: List.filter (fun x => decide (x ∈ take n l)) l) = true
[PROOFSTEP]
have : x ≠ b := fun h => (nodup_cons.1 hl).1 (h ▸ hx)
[GOAL]
case e_tail
α : Type u
β : Type v
l✝ l₁ l₂ : List α
r : α → α → Prop
a b✝ : α
inst✝ : DecidableEq α
b : α
l : List α
n : ℕ
hl : Nodup (b :: l)
x : α
hx : x ∈ l
this : x ≠ b
⊢ decide (x ∈ take n l) = true ↔ decide (x ∈ b :: List.filter (fun x => decide (x ∈ take n l)) l) = true
[PROOFSTEP]
simp (config := { contextual := true }) [List.mem_filter, this, hx]
