Hash set lemmas

This module contains lemmas about Std.Data.HashSet. Most of the lemmas require EquivBEq α and LawfulHashable α for the key type α. The easiest way to obtain these instances is to provide an instance of LawfulBEq α.

@[simp]

theorem Std.HashSet.isEmpty_emptyWithCapacity {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {c : Nat} : (emptyWithCapacity c).isEmpty = true

@[simp]

theorem Std.HashSet.isEmpty_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} : ∅.isEmpty = true

@[simp]

theorem Std.HashSet.isEmpty_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a : α} : (m.insert a).isEmpty = false

theorem Std.HashSet.mem_iff_contains {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {a : α} : a ∈ m ↔ m.contains a = true

@[simp]

theorem Std.HashSet.contains_iff_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {a : α} : m.contains a = true ↔ a ∈ m

@[simp]

theorem Std.HashSet.contains_eq_false_iff_not_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {k : α} : m.contains k = false ↔ ¬k ∈ m

theorem Std.HashSet.contains_congr {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a b : α} (hab : (a == b) = true) : m.contains a = m.contains b

theorem Std.HashSet.mem_congr {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a b : α} (hab : (a == b) = true) : a ∈ m ↔ b ∈ m

@[simp]

theorem Std.HashSet.contains_emptyWithCapacity {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} {c : Nat} : (emptyWithCapacity c).contains a = false

@[simp]

theorem Std.HashSet.not_mem_emptyWithCapacity {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} {c : Nat} : ¬a ∈ emptyWithCapacity c

@[simp]

theorem Std.HashSet.contains_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} : ∅.contains a = false

@[simp]

theorem Std.HashSet.not_mem_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} : ¬a ∈ ∅

theorem Std.HashSet.contains_of_isEmpty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a : α} : m.isEmpty = true → m.contains a = false

theorem Std.HashSet.not_mem_of_isEmpty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a : α} : m.isEmpty = true → ¬a ∈ m

theorem Std.HashSet.isEmpty_eq_false_iff_exists_contains_eq_true {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] : m.isEmpty = false ↔ ∃ (a : α), m.contains a = true

theorem Std.HashSet.isEmpty_eq_false_iff_exists_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] : m.isEmpty = false ↔ ∃ (a : α), a ∈ m

theorem Std.HashSet.isEmpty_iff_forall_contains {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] : m.isEmpty = true ↔ ∀ (a : α), m.contains a = false

theorem Std.HashSet.isEmpty_iff_forall_not_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] : m.isEmpty = true ↔ ∀ (a : α), ¬a ∈ m

@[simp]

theorem Std.HashSet.insert_eq_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {a : α} : Insert.insert a m = m.insert a

@[simp]

theorem Std.HashSet.singleton_eq_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} : {a} = ∅.insert a

@[simp]

theorem Std.HashSet.contains_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} : (m.insert k).contains a = (k == a || m.contains a)

@[simp]

theorem Std.HashSet.mem_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} : a ∈ m.insert k ↔ (k == a) = true ∨ a ∈ m

theorem Std.HashSet.contains_of_contains_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} : (m.insert k).contains a = true → (k == a) = false → m.contains a = true

theorem Std.HashSet.mem_of_mem_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} : a ∈ m.insert k → (k == a) = false → a ∈ m

theorem Std.HashSet.contains_of_contains_insert' {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} : (m.insert k).contains a = true → ¬((k == a) = true ∧ m.contains k = false) → m.contains a = true

This is a restatement of contains_insert that is written to exactly match the proof obligation in the statement of get_insert.

theorem Std.HashSet.mem_of_mem_insert' {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} : a ∈ m.insert k → ¬((k == a) = true ∧ ¬k ∈ m) → a ∈ m

This is a restatement of mem_insert that is written to exactly match the proof obligation in the statement of get_insert.

theorem Std.HashSet.contains_insert_self {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : (m.insert k).contains k = true

theorem Std.HashSet.mem_insert_self {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : k ∈ m.insert k

theorem Std.HashSet.mem_of_get_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {k v : α} {w : k ∈ m} : m.get k w = v → k ∈ m

@[simp]

theorem Std.HashSet.size_emptyWithCapacity {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {c : Nat} : (emptyWithCapacity c).size = 0

@[simp]

theorem Std.HashSet.size_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} : ∅.size = 0

theorem Std.HashSet.isEmpty_eq_size_eq_zero {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} : m.isEmpty = (m.size == 0)

@[simp]

theorem Std.HashSet.toList_emptyWithCapacity {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {c : Nat} : (emptyWithCapacity c).toList = []

@[simp]

theorem Std.HashSet.toList_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} : ∅.toList = []

theorem Std.HashSet.size_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : (m.insert k).size = if k ∈ m then m.size else m.size + 1

theorem Std.HashSet.size_le_size_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : m.size ≤ (m.insert k).size

theorem Std.HashSet.size_insert_le {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : (m.insert k).size ≤ m.size + 1

@[simp]

theorem Std.HashSet.erase_emptyWithCapacity {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} {c : Nat} : (emptyWithCapacity c).erase a = emptyWithCapacity c

@[simp]

theorem Std.HashSet.erase_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} : ∅.erase a = ∅

@[simp]

theorem Std.HashSet.isEmpty_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : (m.erase k).isEmpty = (m.isEmpty || m.size == 1 && m.contains k)

@[simp]

theorem Std.HashSet.contains_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} : (m.erase k).contains a = (!k == a && m.contains a)

@[simp]

theorem Std.HashSet.mem_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} : a ∈ m.erase k ↔ (k == a) = false ∧ a ∈ m

theorem Std.HashSet.contains_of_contains_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} : (m.erase k).contains a = true → m.contains a = true

theorem Std.HashSet.mem_of_mem_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} : a ∈ m.erase k → a ∈ m

theorem Std.HashSet.size_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : (m.erase k).size = if k ∈ m then m.size - 1 else m.size

theorem Std.HashSet.size_erase_le {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : (m.erase k).size ≤ m.size

theorem Std.HashSet.size_le_size_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : m.size ≤ (m.erase k).size + 1

@[simp]

theorem Std.HashSet.get?_emptyWithCapacity {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} {c : Nat} : (emptyWithCapacity c).get? a = none

@[simp]

theorem Std.HashSet.get?_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} : ∅.get? a = none

theorem Std.HashSet.get?_of_isEmpty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a : α} : m.isEmpty = true → m.get? a = none

theorem Std.HashSet.get?_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} : (m.insert k).get? a = if (k == a) = true ∧ ¬k ∈ m then some k else m.get? a

theorem Std.HashSet.contains_eq_isSome_get? {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a : α} : m.contains a = (m.get? a).isSome

@[simp]

theorem Std.HashSet.isSome_get?_eq_contains {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a : α} : (m.get? a).isSome = m.contains a

theorem Std.HashSet.mem_iff_isSome_get? {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a : α} : a ∈ m ↔ (m.get? a).isSome = true

@[simp]

theorem Std.HashSet.isSome_get?_iff_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a : α} : (m.get? a).isSome = true ↔ a ∈ m

theorem Std.HashSet.get?_eq_some_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k k' : α} : m.get? k = some k' ↔ ∃ (h : k ∈ m), m.get k h = k'

theorem Std.HashSet.mem_of_get?_eq_some {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k k' : α} (h : m.get? k = some k') : k' ∈ m

theorem Std.HashSet.get?_eq_none_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a : α} : m.contains a = false → m.get? a = none

theorem Std.HashSet.get?_eq_none {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a : α} : ¬a ∈ m → m.get? a = none

theorem Std.HashSet.get?_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} : (m.erase k).get? a = if (k == a) = true then none else m.get? a

@[simp]

theorem Std.HashSet.get?_erase_self {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : (m.erase k).get? k = none

theorem Std.HashSet.get?_beq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : Option.all (fun (x : α) => x == k) (m.get? k) = true

theorem Std.HashSet.get?_congr {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k k' : α} (h : (k == k') = true) : m.get? k = m.get? k'

theorem Std.HashSet.get?_eq_some_of_contains {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [LawfulBEq α] {k : α} (h : m.contains k = true) : m.get? k = some k

theorem Std.HashSet.get?_eq_some {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [LawfulBEq α] {k : α} (h : k ∈ m) : m.get? k = some k

theorem Std.HashSet.get_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} {h₁ : a ∈ m.insert k} : (m.insert k).get a h₁ = if h₂ : (k == a) = true ∧ ¬k ∈ m then k else m.get a ⋯

theorem Std.HashSet.toList_insert_perm {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : (m.insert k).toList.Perm (if k ∈ m then m.toList else k :: m.toList)

@[simp]

theorem Std.HashSet.get_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} {h' : a ∈ m.erase k} : (m.erase k).get a h' = m.get a ⋯

theorem Std.HashSet.get?_eq_some_get {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a : α} (h' : a ∈ m) : m.get? a = some (m.get a h')

theorem Std.HashSet.get_eq_get_get? {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} {h : k ∈ m} : m.get k h = (m.get? k).get ⋯

theorem Std.HashSet.get_get? {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} {h : (m.get? k).isSome = true} : (m.get? k).get h = m.get k ⋯

theorem Std.HashSet.get_beq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (h : k ∈ m) : (m.get k h == k) = true

theorem Std.HashSet.get_congr {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k₁ k₂ : α} (h : (k₁ == k₂) = true) (h₁ : k₁ ∈ m) : m.get k₁ h₁ = m.get k₂ ⋯

@[simp]

theorem Std.HashSet.get_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [LawfulBEq α] {k : α} (h : k ∈ m) : m.get k h = k

@[simp]

theorem Std.HashSet.get!_emptyWithCapacity {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [Inhabited α] {a : α} {c : Nat} : (emptyWithCapacity c).get! a = default

@[simp]

theorem Std.HashSet.get!_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [Inhabited α] {a : α} : ∅.get! a = default

theorem Std.HashSet.get!_of_isEmpty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [Inhabited α] [EquivBEq α] [LawfulHashable α] {a : α} : m.isEmpty = true → m.get! a = default

theorem Std.HashSet.get!_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [Inhabited α] [EquivBEq α] [LawfulHashable α] {k a : α} : (m.insert k).get! a = if (k == a) = true ∧ ¬k ∈ m then k else m.get! a

theorem Std.HashSet.get!_eq_default_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [Inhabited α] [EquivBEq α] [LawfulHashable α] {a : α} : m.contains a = false → m.get! a = default

theorem Std.HashSet.get!_eq_default {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [Inhabited α] [EquivBEq α] [LawfulHashable α] {a : α} : ¬a ∈ m → m.get! a = default

theorem Std.HashSet.get!_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [Inhabited α] [EquivBEq α] [LawfulHashable α] {k a : α} : (m.erase k).get! a = if (k == a) = true then default else m.get! a

@[simp]

theorem Std.HashSet.get!_erase_self {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [Inhabited α] [EquivBEq α] [LawfulHashable α] {k : α} : (m.erase k).get! k = default

theorem Std.HashSet.get?_eq_some_get!_of_contains {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} : m.contains a = true → m.get? a = some (m.get! a)

theorem Std.HashSet.get?_eq_some_get! {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} : a ∈ m → m.get? a = some (m.get! a)

theorem Std.HashSet.get!_eq_get!_get? {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} : m.get! a = (m.get? a).get!

theorem Std.HashSet.get_eq_get! {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} {h' : a ∈ m} : m.get a h' = m.get! a

theorem Std.HashSet.get!_congr {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k k' : α} (h : (k == k') = true) : m.get! k = m.get! k'

theorem Std.HashSet.get!_eq_of_contains {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [LawfulBEq α] [Inhabited α] {k : α} (h : m.contains k = true) : m.get! k = k

theorem Std.HashSet.get!_eq_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [LawfulBEq α] [Inhabited α] {k : α} (h : k ∈ m) : m.get! k = k

@[simp]

theorem Std.HashSet.getD_emptyWithCapacity {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {a fallback : α} {c : Nat} : (emptyWithCapacity c).getD a fallback = fallback

@[simp]

theorem Std.HashSet.getD_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {a fallback : α} : ∅.getD a fallback = fallback

theorem Std.HashSet.getD_of_isEmpty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a fallback : α} : m.isEmpty = true → m.getD a fallback = fallback

theorem Std.HashSet.getD_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k a fallback : α} : (m.insert k).getD a fallback = if (k == a) = true ∧ ¬k ∈ m then k else m.getD a fallback

theorem Std.HashSet.getD_eq_fallback_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a fallback : α} : m.contains a = false → m.getD a fallback = fallback

theorem Std.HashSet.getD_eq_fallback {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a fallback : α} : ¬a ∈ m → m.getD a fallback = fallback

theorem Std.HashSet.getD_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k a fallback : α} : (m.erase k).getD a fallback = if (k == a) = true then fallback else m.getD a fallback

@[simp]

theorem Std.HashSet.getD_erase_self {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k fallback : α} : (m.erase k).getD k fallback = fallback

theorem Std.HashSet.get?_eq_some_getD_of_contains {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a fallback : α} : m.contains a = true → m.get? a = some (m.getD a fallback)

theorem Std.HashSet.get?_eq_some_getD {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a fallback : α} : a ∈ m → m.get? a = some (m.getD a fallback)

theorem Std.HashSet.getD_eq_getD_get? {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a fallback : α} : m.getD a fallback = (m.get? a).getD fallback

theorem Std.HashSet.get_eq_getD {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {a fallback : α} {h' : a ∈ m} : m.get a h' = m.getD a fallback

theorem Std.HashSet.get!_eq_getD_default {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} : m.get! a = m.getD a default

theorem Std.HashSet.getD_congr {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k k' fallback : α} (h : (k == k') = true) : m.getD k fallback = m.getD k' fallback

theorem Std.HashSet.getD_eq_of_contains {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [LawfulBEq α] {k fallback : α} (h : m.contains k = true) : m.getD k fallback = k

theorem Std.HashSet.getD_eq_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [LawfulBEq α] {k fallback : α} (h : k ∈ m) : m.getD k fallback = k

@[simp]

theorem Std.HashSet.containsThenInsert_fst {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {k : α} : (m.containsThenInsert k).fst = m.contains k

@[simp]

theorem Std.HashSet.containsThenInsert_snd {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {k : α} : (m.containsThenInsert k).snd = m.insert k

@[simp]

theorem Std.HashSet.length_toList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] : m.toList.length = m.size

@[simp]

theorem Std.HashSet.isEmpty_toList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] : m.toList.isEmpty = m.isEmpty

@[simp]

theorem Std.HashSet.contains_toList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : m.toList.contains k = m.contains k

@[simp]

theorem Std.HashSet.mem_toList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [LawfulBEq α] {k : α} : k ∈ m.toList ↔ k ∈ m

theorem Std.HashSet.mem_of_mem_toList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : k ∈ m.toList → k ∈ m

theorem Std.HashSet.distinct_toList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] : List.Pairwise (fun (a b : α) => (a == b) = false) m.toList

@[simp]

theorem Std.HashSet.toArray_toList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} : m.toList.toArray = m.toArray

@[simp]

theorem Std.HashSet.toList_toArray {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} : m.toArray.toList = m.toList

@[simp]

theorem Std.HashSet.size_toArray {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] : m.toArray.size = m.size

@[simp]

theorem Std.HashSet.isEmpty_toArray {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] : m.toArray.isEmpty = m.isEmpty

@[simp]

theorem Std.HashSet.contains_toArray {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : m.toArray.contains k = m.contains k

@[simp]

theorem Std.HashSet.mem_toArray {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [LawfulBEq α] {k : α} : k ∈ m.toArray ↔ k ∈ m

theorem Std.HashSet.forall_mem_toArray_iff_forall_mem_get {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {p : α → Prop} : (∀ (k : α), k ∈ m.toArray → p k) ↔ ∀ (k : α) (h : k ∈ m), p (m.get k h)

theorem Std.HashSet.contains_of_mem_toArray {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (h' : k ∈ m.toArray) : m.contains k = true

theorem Std.HashSet.foldM_eq_foldlM_toList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {δ : Type v} {m' : Type v → Type w} [Monad m'] [LawfulMonad m'] {f : δ → α → m' δ} {init : δ} : foldM f init m = List.foldlM f init m.toList

theorem Std.HashSet.fold_eq_foldl_toList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {δ : Type v} {f : δ → α → δ} {init : δ} : fold f init m = List.foldl f init m.toList

@[simp]

theorem Std.HashSet.forM_eq_forM {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {m' : Type v → Type w} [Monad m'] [LawfulMonad m'] {f : α → m' PUnit} : forM f m = ForM.forM m f

theorem Std.HashSet.forM_eq_forM_toList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {m' : Type v → Type w} [Monad m'] [LawfulMonad m'] {f : α → m' PUnit} : ForM.forM m f = ForM.forM m.toList f

@[simp]

theorem Std.HashSet.forIn_eq_forIn {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {δ : Type v} {m' : Type v → Type w} [Monad m'] [LawfulMonad m'] {f : α → δ → m' (ForInStep δ)} {init : δ} : ForIn.forIn m init f = ForIn.forIn m init f

theorem Std.HashSet.forIn_eq_forIn_toList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {δ : Type v} {m' : Type v → Type w} [Monad m'] [LawfulMonad m'] {f : α → δ → m' (ForInStep δ)} {init : δ} : ForIn.forIn m init f = ForIn.forIn m.toList init f

@[simp]

theorem Std.HashSet.forIn_toList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} (c : HashSet α) : ForIn.toList c = c.toList

instance Std.HashSet.instPureForInOfLawfulMonad {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m' : Type v → Type w} [Monad m'] [LawfulMonad m'] : Internal.PureForIn m' (HashSet α) α

theorem Std.HashSet.foldM_eq_foldlM_toArray {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {δ : Type v} {m' : Type v → Type w} [Monad m'] [LawfulMonad m'] {f : δ → α → m' δ} {init : δ} : foldM (fun (d : δ) (a : α) => f d a) init m = Array.foldlM f init m.toArray

theorem Std.HashSet.fold_eq_foldl_toArray {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {δ : Type v} {f : δ → α → δ} {init : δ} : fold (fun (d : δ) (a : α) => f d a) init m = Array.foldl f init m.toArray

theorem Std.HashSet.forM_eq_forM_toArray {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {m' : Type v → Type w} [Monad m'] [LawfulMonad m'] {f : α → m' PUnit} : forM (fun (a : α) => f a) m = Array.forM f m.toArray

theorem Std.HashSet.forIn_eq_forIn_toArray {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {δ : Type v} {m' : Type v → Type w} [Monad m'] [LawfulMonad m'] {f : α → δ → m' (ForInStep δ)} {init : δ} : forIn (fun (a : α) (d : δ) => f a d) init m = ForIn.forIn m.toArray init f

theorem Std.HashSet.all_eq_not_any_not {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {p : α → Bool} : m.all p = !m.any fun (a : α) => !p a

theorem Std.HashSet.any_eq_not_all_not {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {p : α → Bool} : m.any p = !m.all fun (a : α) => !p a

@[simp]

theorem Std.HashSet.any_toList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [LawfulHashable α] [EquivBEq α] {p : α → Bool} : m.toList.any p = m.any p

theorem Std.HashSet.any_eq_true_iff_exists_mem_get {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [LawfulHashable α] [EquivBEq α] {p : α → Bool} : m.any p = true ↔ ∃ (a : α), ∃ (h : a ∈ m), p (m.get a h) = true

theorem Std.HashSet.any_eq_true_iff_exists_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [LawfulBEq α] {p : α → Bool} : m.any p = true ↔ ∃ (a : α), a ∈ m ∧ p a = true

theorem Std.HashSet.any_eq_false_iff_forall_mem_get {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [LawfulHashable α] [EquivBEq α] {p : α → Bool} : m.any p = false ↔ ∀ (a : α) (h : a ∈ m), p (m.get a h) = false

theorem Std.HashSet.any_eq_false_iff_forall_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [LawfulBEq α] {p : α → Bool} : m.any p = false ↔ ∀ (a : α), a ∈ m → p a = false

@[simp]

theorem Std.HashSet.all_toList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [LawfulHashable α] [EquivBEq α] {p : α → Bool} : m.toList.all p = m.all p

theorem Std.HashSet.all_eq_true_iff_forall_mem_get {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {p : α → Bool} : m.all p = true ↔ ∀ (a : α) (h : a ∈ m), p (m.get a h) = true

theorem Std.HashSet.all_eq_true_iff_forall_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [LawfulBEq α] {p : α → Bool} : m.all p = true ↔ ∀ (a : α), a ∈ m → p a = true

theorem Std.HashSet.all_eq_false_iff_exists_mem_get {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {p : α → Bool} : m.all p = false ↔ ∃ (a : α), ∃ (h : a ∈ m), p (m.get a h) = false

theorem Std.HashSet.all_eq_false_iff_exists_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [LawfulBEq α] {p : α → Bool} : m.all p = false ↔ ∃ (a : α), a ∈ m ∧ p a = false

@[simp]

theorem Std.HashSet.insertMany_nil {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} : m.insertMany [] = m

@[simp]

theorem Std.HashSet.insertMany_list_singleton {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {k : α} : m.insertMany [k] = m.insert k

theorem Std.HashSet.insertMany_cons {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {l : List α} {k : α} : m.insertMany (k :: l) = (m.insert k).insertMany l

theorem Std.HashSet.insertMany_append {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {l₁ l₂ : List α} : m.insertMany (l₁ ++ l₂) = (m.insertMany l₁).insertMany l₂

theorem Std.HashSet.insertMany_ind {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {ρ : Type v} [ForIn Id ρ α] {motive : HashSet α → Prop} (m : HashSet α) {l : ρ} (init : motive m) (insert : ∀ (m : HashSet α) (a : α), motive m → motive (m.insert a)) : motive (m.insertMany l)

@[simp]

theorem Std.HashSet.contains_insertMany_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} : (m.insertMany l).contains k = (m.contains k || l.contains k)

@[simp]

theorem Std.HashSet.mem_insertMany_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} : k ∈ m.insertMany l ↔ k ∈ m ∨ l.contains k = true

theorem Std.HashSet.mem_of_mem_insertMany_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} (contains_eq_false : l.contains k = false) : k ∈ m.insertMany l → k ∈ m

theorem Std.HashSet.mem_insertMany_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {ρ : Type v} [ForIn Id ρ α] [EquivBEq α] [LawfulHashable α] {l : ρ} {k : α} : k ∈ m → k ∈ m.insertMany l

theorem Std.HashSet.get?_insertMany_list_of_not_mem_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} (not_mem : ¬k ∈ m) (contains_eq_false : l.contains k = false) : (m.insertMany l).get? k = none

theorem Std.HashSet.get?_insertMany_list_of_not_mem_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k k' : α} (k_beq : (k == k') = true) (not_mem : ¬k ∈ m) (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) (mem : k ∈ l) : (m.insertMany l).get? k' = some k

theorem Std.HashSet.get?_insertMany_list_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} (mem : k ∈ m) : (m.insertMany l).get? k = m.get? k

theorem Std.HashSet.get_insertMany_list_of_not_mem_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k k' : α} (k_beq : (k == k') = true) (not_mem : ¬k ∈ m) (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) (mem : k ∈ l) {h : k' ∈ m.insertMany l} : (m.insertMany l).get k' h = k

theorem Std.HashSet.get_insertMany_list_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} (mem : k ∈ m) {h : k ∈ m.insertMany l} : (m.insertMany l).get k h = m.get k mem

theorem Std.HashSet.get!_insertMany_list_of_not_mem_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {l : List α} {k : α} (not_mem : ¬k ∈ m) (contains_eq_false : l.contains k = false) : (m.insertMany l).get! k = default

theorem Std.HashSet.get!_insertMany_list_of_not_mem_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {l : List α} {k k' : α} (k_beq : (k == k') = true) (not_mem : ¬k ∈ m) (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) (mem : k ∈ l) : (m.insertMany l).get! k' = k

theorem Std.HashSet.get!_insertMany_list_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {l : List α} {k : α} (mem : k ∈ m) : (m.insertMany l).get! k = m.get! k

theorem Std.HashSet.getD_insertMany_list_of_not_mem_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k fallback : α} (not_mem : ¬k ∈ m) (contains_eq_false : l.contains k = false) : (m.insertMany l).getD k fallback = fallback

theorem Std.HashSet.getD_insertMany_list_of_not_mem_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k k' fallback : α} (k_beq : (k == k') = true) (not_mem : ¬k ∈ m) (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) (mem : k ∈ l) : (m.insertMany l).getD k' fallback = k

theorem Std.HashSet.getD_insertMany_list_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k fallback : α} (mem : k ∈ m) : (m.insertMany l).getD k fallback = m.getD k fallback

theorem Std.HashSet.size_insertMany_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) : (∀ (a : α), a ∈ m → l.contains a = false) → (m.insertMany l).size = m.size + l.length

theorem Std.HashSet.size_le_size_insertMany_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} : m.size ≤ (m.insertMany l).size

theorem Std.HashSet.size_le_size_insertMany {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {ρ : Type v} [ForIn Id ρ α] [EquivBEq α] [LawfulHashable α] {l : ρ} : m.size ≤ (m.insertMany l).size

theorem Std.HashSet.size_insertMany_list_le {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} : (m.insertMany l).size ≤ m.size + l.length

@[simp]

theorem Std.HashSet.isEmpty_insertMany_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} : (m.insertMany l).isEmpty = (m.isEmpty && l.isEmpty)

theorem Std.HashSet.isEmpty_of_isEmpty_insertMany {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {ρ : Type v} [ForIn Id ρ α] [EquivBEq α] [LawfulHashable α] {l : ρ} : (m.insertMany l).isEmpty = true → m.isEmpty = true

theorem Std.HashSet.Equiv.beq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] (h : m₁.Equiv m₂) : (m₁ == m₂) = true

theorem Std.HashSet.equiv_of_beq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [LawfulBEq α] (h : (m₁ == m₂) = true) : m₁.Equiv m₂

theorem Std.HashSet.beq_iff_equiv {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [LawfulBEq α] : (m₁ == m₂) = true ↔ m₁.Equiv m₂

theorem Std.HashSet.Equiv.beq_congr {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {m₃ m₄ : HashSet α} (h₁ : m₁.Equiv m₃) (h₂ : m₂.Equiv m₄) : (m₁ == m₂) = (m₃ == m₄)

@[simp]

theorem Std.HashSet.union_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} : m₁.union m₂ = m₁ ∪ m₂

@[simp]

theorem Std.HashSet.contains_union {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : (m₁ ∪ m₂).contains k = (m₁.contains k || m₂.contains k)

theorem Std.HashSet.mem_union_of_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : k ∈ m₁ → k ∈ m₁ ∪ m₂

theorem Std.HashSet.mem_union_of_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : k ∈ m₂ → k ∈ m₁ ∪ m₂

@[simp]

theorem Std.HashSet.mem_union_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : (m₁ ∪ m₂).contains k = true ↔ m₁.contains k = true ∨ m₂.contains k = true

theorem Std.HashSet.mem_of_mem_union_of_not_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : k ∈ m₁ ∪ m₂ → ¬k ∈ m₂ → k ∈ m₁

theorem Std.HashSet.mem_of_mem_union_of_not_mem_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : k ∈ m₁ ∪ m₂ → ¬k ∈ m₁ → k ∈ m₂

theorem Std.HashSet.Equiv.union_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ m₃ : HashSet α} [EquivBEq α] [LawfulHashable α] (equiv : m₁.Equiv m₂) : (m₁ ∪ m₃).Equiv (m₂ ∪ m₃)

theorem Std.HashSet.Equiv.union_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ m₃ : HashSet α} [EquivBEq α] [LawfulHashable α] (equiv : m₂.Equiv m₃) : (m₁ ∪ m₂).Equiv (m₁ ∪ m₃)

theorem Std.HashSet.Equiv.union_congr {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ m₃ m₄ : HashSet α} [EquivBEq α] [LawfulHashable α] (equiv₁ : m₁.Equiv m₃) (equiv₂ : m₂.Equiv m₄) : (m₁ ∪ m₂).Equiv (m₃ ∪ m₄)

theorem Std.HashSet.get?_union {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : (m₁ ∪ m₂).get? k = (m₂.get? k).or (m₁.get? k)

theorem Std.HashSet.get?_union_of_not_mem_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (not_mem : ¬k ∈ m₁) : (m₁ ∪ m₂).get? k = m₂.get? k

theorem Std.HashSet.get?_union_of_not_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (not_mem : ¬k ∈ m₂) : (m₁ ∪ m₂).get? k = m₁.get? k

theorem Std.HashSet.get_union_of_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (mem : k ∈ m₂) : (m₁ ∪ m₂).get k ⋯ = m₂.get k mem

theorem Std.HashSet.get_union_of_not_mem_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (not_mem : ¬k ∈ m₁) {h' : k ∈ m₁ ∪ m₂} : (m₁ ∪ m₂).get k h' = m₂.get k ⋯

theorem Std.HashSet.get_union_of_not_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (not_mem : ¬k ∈ m₂) {h' : k ∈ m₁ ∪ m₂} : (m₁ ∪ m₂).get k h' = m₁.get k ⋯

theorem Std.HashSet.getD_union {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k fallback : α} : (m₁ ∪ m₂).getD k fallback = m₂.getD k (m₁.getD k fallback)

theorem Std.HashSet.getD_union_of_not_mem_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k fallback : α} (not_mem : ¬k ∈ m₁) : (m₁ ∪ m₂).getD k fallback = m₂.getD k fallback

theorem Std.HashSet.getD_union_of_not_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k fallback : α} (not_mem : ¬k ∈ m₂) : (m₁ ∪ m₂).getD k fallback = m₁.getD k fallback

theorem Std.HashSet.get!_union {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} : (m₁ ∪ m₂).get! k = m₂.getD k (m₁.get! k)

theorem Std.HashSet.get!_union_of_not_mem_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [Inhabited α] [EquivBEq α] [LawfulHashable α] {k : α} (not_mem : ¬k ∈ m₁) : (m₁ ∪ m₂).get! k = m₂.get! k

theorem Std.HashSet.get!_union_of_not_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [Inhabited α] [EquivBEq α] [LawfulHashable α] {k : α} (not_mem : ¬k ∈ m₂) : (m₁ ∪ m₂).get! k = m₁.get! k

theorem Std.HashSet.size_union_of_not_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] : (∀ (a : α), a ∈ m₁ → ¬a ∈ m₂) → (m₁ ∪ m₂).size = m₁.size + m₂.size

theorem Std.HashSet.size_left_le_size_union {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] : m₁.size ≤ (m₁ ∪ m₂).size

theorem Std.HashSet.size_right_le_size_union {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] : m₂.size ≤ (m₁ ∪ m₂).size

theorem Std.HashSet.size_union_le_size_add_size {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] : (m₁ ∪ m₂).size ≤ m₁.size + m₂.size

@[simp]

theorem Std.HashSet.isEmpty_union {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] : (m₁ ∪ m₂).isEmpty = (m₁.isEmpty && m₂.isEmpty)

@[simp]

theorem Std.HashSet.inter_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} : m₁.inter m₂ = m₁ ∩ m₂

@[simp]

theorem Std.HashSet.contains_inter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : (m₁ ∩ m₂).contains k = (m₁.contains k && m₂.contains k)

@[simp]

theorem Std.HashSet.mem_inter_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : (m₁ ∩ m₂).contains k = true ↔ m₁.contains k = true ∧ m₂.contains k = true

theorem Std.HashSet.not_mem_inter_of_not_mem_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (not_mem : ¬k ∈ m₁) : ¬k ∈ m₁ ∩ m₂

theorem Std.HashSet.not_mem_inter_of_not_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (not_mem : ¬k ∈ m₂) : ¬k ∈ m₁ ∩ m₂

theorem Std.HashSet.Equiv.inter_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ m₃ : HashSet α} [EquivBEq α] [LawfulHashable α] (equiv : m₁.Equiv m₂) : (m₁ ∩ m₃).Equiv (m₂ ∩ m₃)

theorem Std.HashSet.Equiv.inter_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ m₃ : HashSet α} [EquivBEq α] [LawfulHashable α] (equiv : m₂.Equiv m₃) : (m₁ ∩ m₂).Equiv (m₁ ∩ m₃)

theorem Std.HashSet.Equiv.inter_congr {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ m₃ m₄ : HashSet α} [EquivBEq α] [LawfulHashable α] (equiv₁ : m₁.Equiv m₃) (equiv₂ : m₂.Equiv m₄) : (m₁ ∩ m₂).Equiv (m₃ ∩ m₄)

theorem Std.HashSet.get?_inter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : (m₁ ∩ m₂).get? k = if k ∈ m₂ then m₁.get? k else none

theorem Std.HashSet.get?_inter_of_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (mem : k ∈ m₂) : (m₁ ∩ m₂).get? k = m₁.get? k

theorem Std.HashSet.get?_inter_of_not_mem_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (not_mem : ¬k ∈ m₁) : (m₁ ∩ m₂).get? k = none

theorem Std.HashSet.get?_inter_of_not_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (not_mem : ¬k ∈ m₂) : (m₁ ∩ m₂).get? k = none

@[simp]

theorem Std.HashSet.get_inter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} {h_mem : k ∈ m₁ ∩ m₂} : (m₁ ∩ m₂).get k h_mem = m₁.get k ⋯

theorem Std.HashSet.getD_inter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k fallback : α} : (m₁ ∩ m₂).getD k fallback = if k ∈ m₂ then m₁.getD k fallback else fallback

theorem Std.HashSet.getD_inter_of_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k fallback : α} (mem : k ∈ m₂) : (m₁ ∩ m₂).getD k fallback = m₁.getD k fallback

theorem Std.HashSet.getD_inter_of_not_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k fallback : α} (not_mem : ¬k ∈ m₂) : (m₁ ∩ m₂).getD k fallback = fallback

theorem Std.HashSet.getD_inter_of_not_mem_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k fallback : α} (not_mem : ¬k ∈ m₁) : (m₁ ∩ m₂).getD k fallback = fallback

theorem Std.HashSet.get!_inter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} : (m₁ ∩ m₂).get! k = if k ∈ m₂ then m₁.get! k else default

theorem Std.HashSet.get!_inter_of_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} (mem : k ∈ m₂) : (m₁ ∩ m₂).get! k = m₁.get! k

theorem Std.HashSet.get!_inter_of_not_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} (not_mem : ¬k ∈ m₂) : (m₁ ∩ m₂).get! k = default

theorem Std.HashSet.get!_inter_of_not_mem_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} (not_mem : ¬k ∈ m₁) : (m₁ ∩ m₂).get! k = default

theorem Std.HashSet.size_inter_le_size_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] : (m₁ ∩ m₂).size ≤ m₁.size

theorem Std.HashSet.size_inter_le_size_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] : (m₁ ∩ m₂).size ≤ m₂.size

theorem Std.HashSet.size_inter_eq_size_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] (h : ∀ (a : α), a ∈ m₁ → a ∈ m₂) : (m₁ ∩ m₂).size = m₁.size

theorem Std.HashSet.size_inter_eq_size_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] (h : ∀ (a : α), a ∈ m₂ → a ∈ m₁) : (m₁ ∩ m₂).size = m₂.size

theorem Std.HashSet.size_add_size_eq_size_union_add_size_inter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] : m₁.size + m₂.size = (m₁ ∪ m₂).size + (m₁ ∩ m₂).size

@[simp]

theorem Std.HashSet.isEmpty_inter_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] (h : m₁.isEmpty = true) : (m₁ ∩ m₂).isEmpty = true

@[simp]

theorem Std.HashSet.isEmpty_inter_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] (h : m₂.isEmpty = true) : (m₁ ∩ m₂).isEmpty = true

theorem Std.HashSet.isEmpty_inter_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] : (m₁ ∩ m₂).isEmpty = true ↔ ∀ (k : α), k ∈ m₁ → ¬k ∈ m₂

theorem Std.HashSet.isEmpty_inter_comm {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] : (m₁ ∩ m₂).isEmpty = (m₂ ∩ m₁).isEmpty

@[simp]

theorem Std.HashSet.diff_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} : m₁.diff m₂ = m₁ \ m₂

@[simp]

theorem Std.HashSet.contains_diff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : (m₁ \ m₂).contains k = (m₁.contains k && !m₂.contains k)

@[simp]

theorem Std.HashSet.mem_diff_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : k ∈ m₁ \ m₂ ↔ k ∈ m₁ ∧ ¬k ∈ m₂

theorem Std.HashSet.not_mem_diff_of_not_mem_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (not_mem : ¬k ∈ m₁) : ¬k ∈ m₁ \ m₂

theorem Std.HashSet.not_mem_diff_of_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (mem : k ∈ m₂) : ¬k ∈ m₁ \ m₂

theorem Std.HashSet.Equiv.diff_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ m₃ : HashSet α} [EquivBEq α] [LawfulHashable α] (equiv : m₁.Equiv m₂) : (m₁ \ m₃).Equiv (m₂ \ m₃)

theorem Std.HashSet.Equiv.diff_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ m₃ : HashSet α} [EquivBEq α] [LawfulHashable α] (equiv : m₂.Equiv m₃) : (m₁ \ m₂).Equiv (m₁ \ m₃)

theorem Std.HashSet.Equiv.diff_congr {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ m₃ m₄ : HashSet α} [EquivBEq α] [LawfulHashable α] (equiv₁ : m₁.Equiv m₃) (equiv₂ : m₂.Equiv m₄) : (m₁ \ m₂).Equiv (m₃ \ m₄)

theorem Std.HashSet.get?_diff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} : (m₁ \ m₂).get? k = if k ∈ m₂ then none else m₁.get? k

theorem Std.HashSet.get?_diff_of_not_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (not_mem : ¬k ∈ m₂) : (m₁ \ m₂).get? k = m₁.get? k

theorem Std.HashSet.get?_diff_of_not_mem_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (not_mem : ¬k ∈ m₁) : (m₁ \ m₂).get? k = none

theorem Std.HashSet.get?_diff_of_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (mem : k ∈ m₂) : (m₁ \ m₂).get? k = none

@[simp]

theorem Std.HashSet.get_diff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} {h_mem : k ∈ m₁ \ m₂} : (m₁ \ m₂).get k h_mem = m₁.get k ⋯

theorem Std.HashSet.getD_diff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k fallback : α} : (m₁ \ m₂).getD k fallback = if k ∈ m₂ then fallback else m₁.getD k fallback

theorem Std.HashSet.getD_diff_of_not_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k fallback : α} (not_mem : ¬k ∈ m₂) : (m₁ \ m₂).getD k fallback = m₁.getD k fallback

theorem Std.HashSet.getD_diff_of_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k fallback : α} (mem : k ∈ m₂) : (m₁ \ m₂).getD k fallback = fallback

theorem Std.HashSet.getD_diff_of_not_mem_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k fallback : α} (not_mem : ¬k ∈ m₁) : (m₁ \ m₂).getD k fallback = fallback

theorem Std.HashSet.get!_diff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} : (m₁ \ m₂).get! k = if k ∈ m₂ then default else m₁.get! k

theorem Std.HashSet.get!_diff_of_not_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} (not_mem : ¬k ∈ m₂) : (m₁ \ m₂).get! k = m₁.get! k

theorem Std.HashSet.get!_diff_of_mem_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} (mem : k ∈ m₂) : (m₁ \ m₂).get! k = default

theorem Std.HashSet.get!_diff_of_not_mem_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} (not_mem : ¬k ∈ m₁) : (m₁ \ m₂).get! k = default

theorem Std.HashSet.size_diff_le_size_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] : (m₁ \ m₂).size ≤ m₁.size

theorem Std.HashSet.size_diff_eq_size_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] (h : ∀ (a : α), a ∈ m₁ → ¬a ∈ m₂) : (m₁ \ m₂).size = m₁.size

theorem Std.HashSet.size_diff_add_size_inter_eq_size_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] : (m₁ \ m₂).size + (m₁ ∩ m₂).size = m₁.size

@[simp]

theorem Std.HashSet.isEmpty_diff_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] (h : m₁.isEmpty = true) : (m₁ \ m₂).isEmpty = true

theorem Std.HashSet.isEmpty_diff_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] : (m₁ \ m₂).isEmpty = true ↔ ∀ (k : α), k ∈ m₁ → k ∈ m₂

@[simp]

theorem Std.HashSet.ofArray_eq_ofList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} (a : Array α) : ofArray a = ofList a.toList

@[simp]

theorem Std.HashSet.ofList_nil {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} : ofList [] = ∅

@[simp]

theorem Std.HashSet.ofList_singleton {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {k : α} : ofList [k] = ∅.insert k

theorem Std.HashSet.ofList_cons {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {hd : α} {tl : List α} : ofList (hd :: tl) = (∅.insert hd).insertMany tl

theorem Std.HashSet.ofList_eq_insertMany_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {l : List α} : ofList l = ∅.insertMany l

@[simp]

theorem Std.HashSet.contains_ofList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} : (ofList l).contains k = l.contains k

@[simp]

theorem Std.HashSet.mem_ofList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} : k ∈ ofList l ↔ l.contains k = true

theorem Std.HashSet.get?_ofList_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} (contains_eq_false : l.contains k = false) : (ofList l).get? k = none

theorem Std.HashSet.get?_ofList_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} {k k' : α} (k_beq : (k == k') = true) (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) (mem : k ∈ l) : (ofList l).get? k' = some k

theorem Std.HashSet.get_ofList_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} {k k' : α} (k_beq : (k == k') = true) (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) (mem : k ∈ l) {h : k' ∈ ofList l} : (ofList l).get k' h = k

theorem Std.HashSet.get!_ofList_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {l : List α} {k : α} (contains_eq_false : l.contains k = false) : (ofList l).get! k = default

theorem Std.HashSet.get!_ofList_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {l : List α} {k k' : α} (k_beq : (k == k') = true) (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) (mem : k ∈ l) : (ofList l).get! k' = k

theorem Std.HashSet.getD_ofList_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} {k fallback : α} (contains_eq_false : l.contains k = false) : (ofList l).getD k fallback = fallback

theorem Std.HashSet.getD_ofList_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} {k k' fallback : α} (k_beq : (k == k') = true) (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) (mem : k ∈ l) : (ofList l).getD k' fallback = k

theorem Std.HashSet.size_ofList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) : (ofList l).size = l.length

theorem Std.HashSet.size_ofList_le {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} : (ofList l).size ≤ l.length

@[simp]

theorem Std.HashSet.isEmpty_ofList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} : (ofList l).isEmpty = l.isEmpty

@[simp]

theorem Std.HashSet.Equiv.refl {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} (m : HashSet α) : m.Equiv m

theorem Std.HashSet.Equiv.rfl {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} : m.Equiv m

theorem Std.HashSet.Equiv.symm {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} : m₁.Equiv m₂ → m₂.Equiv m₁

theorem Std.HashSet.Equiv.trans {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ m₃ : HashSet α} : m₁.Equiv m₂ → m₂.Equiv m₃ → m₁.Equiv m₃

@[instance_reducible]

instance Std.HashSet.Equiv.instTrans {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} : Trans Equiv Equiv Equiv

Equations

• Std.HashSet.Equiv.instTrans = { trans := ⋯ }

theorem Std.HashSet.Equiv.comm {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} : m₁.Equiv m₂ ↔ m₂.Equiv m₁

theorem Std.HashSet.Equiv.congr_left {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ m₃ : HashSet α} (h : m₁.Equiv m₂) : m₁.Equiv m₃ ↔ m₂.Equiv m₃

theorem Std.HashSet.Equiv.congr_right {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ m₃ : HashSet α} (h : m₁.Equiv m₂) : m₃.Equiv m₁ ↔ m₃.Equiv m₂

theorem Std.HashSet.Equiv.isEmpty_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] (h : m₁.Equiv m₂) : m₁.isEmpty = m₂.isEmpty

theorem Std.HashSet.Equiv.size_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] (h : m₁.Equiv m₂) : m₁.size = m₂.size

theorem Std.HashSet.Equiv.contains_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (h : m₁.Equiv m₂) : m₁.contains k = m₂.contains k

theorem Std.HashSet.Equiv.mem_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (h : m₁.Equiv m₂) : k ∈ m₁ ↔ k ∈ m₂

theorem Std.HashSet.Equiv.toList_perm {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} (h : m₁.Equiv m₂) : m₁.toList.Perm m₂.toList

theorem Std.HashSet.Equiv.of_toList_perm {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} (h : m₁.toList.Perm m₂.toList) : m₁.Equiv m₂

theorem Std.HashSet.Equiv.get?_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (h : m₁.Equiv m₂) : m₁.get? k = m₂.get? k

theorem Std.HashSet.Equiv.get_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (hk : k ∈ m₁) (h : m₁.Equiv m₂) : m₁.get k hk = m₂.get k ⋯

theorem Std.HashSet.Equiv.get!_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} (h : m₁.Equiv m₂) : m₁.get! k = m₂.get! k

theorem Std.HashSet.Equiv.getD_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] {k fallback : α} (h : m₁.Equiv m₂) : m₁.getD k fallback = m₂.getD k fallback

theorem Std.HashSet.Equiv.insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] (k : α) (h : m₁.Equiv m₂) : (m₁.insert k).Equiv (m₂.insert k)

theorem Std.HashSet.Equiv.erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] (k : α) (h : m₁.Equiv m₂) : (m₁.erase k).Equiv (m₂.erase k)

theorem Std.HashSet.Equiv.insertMany_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] (l : List α) (h : m₁.Equiv m₂) : (m₁.insertMany l).Equiv (m₂.insertMany l)

theorem Std.HashSet.Equiv.filter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} (f : α → Bool) (h : m₁.Equiv m₂) : (HashSet.filter f m₁).Equiv (HashSet.filter f m₂)

theorem Std.HashSet.Equiv.of_forall_get?_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] (h : ∀ (k : α), m₁.get? k = m₂.get? k) : m₁.Equiv m₂

theorem Std.HashSet.Equiv.of_forall_contains_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [LawfulBEq α] (h : ∀ (k : α), m₁.contains k = m₂.contains k) : m₁.Equiv m₂

theorem Std.HashSet.Equiv.of_forall_mem_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [LawfulBEq α] (h : ∀ (k : α), k ∈ m₁ ↔ k ∈ m₂) : m₁.Equiv m₂

@[simp]

theorem Std.HashSet.equiv_emptyWithCapacity_iff_isEmpty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {c : Nat} : m.Equiv (emptyWithCapacity c) ↔ m.isEmpty = true

@[simp]

theorem Std.HashSet.equiv_empty_iff_isEmpty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] : m.Equiv ∅ ↔ m.isEmpty = true

theorem Std.HashSet.inter_equiv_empty_comm {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {m₁ m₂ : HashSet α} : (m₁ ∩ m₂).Equiv ∅ ↔ (m₂ ∩ m₁).Equiv ∅

@[simp]

theorem Std.HashSet.emptyWithCapacity_equiv_iff_isEmpty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {c : Nat} : (emptyWithCapacity c).Equiv m ↔ m.isEmpty = true

@[simp]

theorem Std.HashSet.empty_equiv_iff_isEmpty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] : ∅.Equiv m ↔ m.isEmpty = true

theorem Std.HashSet.equiv_iff_toList_perm {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [EquivBEq α] [LawfulHashable α] : m₁.Equiv m₂ ↔ m₁.toList.Perm m₂.toList

theorem Std.HashSet.equiv_iff_forall_mem_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashSet α} [LawfulBEq α] : m₁.Equiv m₂ ↔ ∀ (k : α), k ∈ m₁ ↔ k ∈ m₂

theorem Std.HashSet.insertMany_list_equiv_foldl {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {l : List α} : (m.insertMany l).Equiv (List.foldl (fun (acc : HashSet α) (a : α) => acc.insert a) m l)

theorem Std.HashSet.ofList_equiv_foldl {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {l : List α} : (ofList l).Equiv (List.foldl (fun (acc : HashSet α) (a : α) => acc.insert a) ∅ l)

theorem Std.HashSet.toList_filter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} {f : α → Bool} : (filter f m).toList.Perm (List.filter f m.toList)

theorem Std.HashSet.isEmpty_filter_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} : (filter f m).isEmpty = true ↔ ∀ (k : α) (h : k ∈ m), f (m.get k h) = false

theorem Std.HashSet.isEmpty_filter_eq_false_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} : (filter f m).isEmpty = false ↔ ∃ (k : α), ∃ (h : k ∈ m), f (m.get k h) = true

@[simp]

theorem Std.HashSet.mem_filter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} {k : α} : k ∈ filter f m ↔ ∃ (h : k ∈ m), f (m.get k h) = true

theorem Std.HashSet.contains_of_contains_filter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} {k : α} : (filter f m).contains k = true → m.contains k = true

theorem Std.HashSet.mem_of_mem_filter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} {k : α} : k ∈ filter f m → k ∈ m

theorem Std.HashSet.size_filter_le_size {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} : (filter f m).size ≤ m.size

theorem Std.HashSet.size_filter_eq_size_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} : (filter f m).size = m.size ↔ ∀ (k : α) (h : k ∈ m), f (m.get k h) = true

theorem Std.HashSet.filter_equiv_self_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} : (filter f m).Equiv m ↔ ∀ (k : α) (h : k ∈ m), f (m.get k h) = true

@[simp]

theorem Std.HashSet.get?_filter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} {k : α} : (filter f m).get? k = Option.filter f (m.get? k)

@[simp]

theorem Std.HashSet.get_filter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} {k : α} {h : k ∈ filter f m} : (filter f m).get k h = m.get k ⋯

theorem Std.HashSet.get!_filter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {f : α → Bool} {k : α} : (filter f m).get! k = (Option.filter f (m.get? k)).get!

theorem Std.HashSet.getD_filter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} {k fallback : α} : (filter f m).getD k fallback = (Option.filter f (m.get? k)).getD fallback