Documentation

Std.Data.ExtHashSet.Lemmas

Extensional hash set lemmas #

This module contains lemmas about Std.ExtHashSet.

source
@[simp]
theorem Std.ExtHashSet.isEmpty_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] :
m.isEmpty = true ↔ m = ∅
source
@[simp]
theorem Std.ExtHashSet.isEmpty_eq_false_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] :
m.isEmpty = false ↔ ¬m = ∅
source
@[simp]
theorem Std.ExtHashSet.empty_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} :
∅ = m ↔ m = ∅
source
@[simp]
theorem Std.ExtHashSet.emptyWithCapacity_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {c : Nat} :
emptyWithCapacity c = ∅
source
@[simp]
theorem Std.ExtHashSet.not_insert_eq_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} :
¬m.insert k = ∅
source
theorem Std.ExtHashSet.mem_iff_contains {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a : α} :
a ∈ m ↔ m.contains a = true
source
@[simp]
theorem Std.ExtHashSet.contains_iff_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a : α} :
m.contains a = true ↔ a ∈ m
source
theorem Std.ExtHashSet.contains_congr {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a b : α} (hab : (a == b) = true) :
m.contains a = m.contains b
source
theorem Std.ExtHashSet.mem_congr {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a b : α} (hab : (a == b) = true) :
a ∈ m ↔ b ∈ m
source
@[simp]
theorem Std.ExtHashSet.contains_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {a : α} :
∅.contains a = false
source
@[simp]
theorem Std.ExtHashSet.not_mem_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {a : α} :
¬a ∈ ∅
source
theorem Std.ExtHashSet.eq_empty_iff_forall_contains {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] :
m = ∅ ↔ ∀ (a : α), m.contains a = false
source
theorem Std.ExtHashSet.eq_empty_iff_forall_not_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] :
m = ∅ ↔ ∀ (a : α), ¬a ∈ m
source
@[simp]
theorem Std.ExtHashSet.insert_eq_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a : α} :
Insert.insert a m = m.insert a
source
@[simp]
theorem Std.ExtHashSet.singleton_eq_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {a : α} :
{a} = ∅.insert a
source
@[simp]
theorem Std.ExtHashSet.contains_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} :
(m.insert k).contains a = (k == a || m.contains a)
source
@[simp]
theorem Std.ExtHashSet.mem_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} :
a ∈ m.insert k ↔ (k == a) = true ∨ a ∈ m
source
theorem Std.ExtHashSet.contains_of_contains_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} :
(m.insert k).contains a = true → (k == a) = false → m.contains a = true
source
theorem Std.ExtHashSet.mem_of_mem_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} :
a ∈ m.insert k → (k == a) = false → a ∈ m
source
theorem Std.ExtHashSet.contains_of_contains_insert' {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [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.

source
theorem Std.ExtHashSet.mem_of_mem_insert' {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [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.

source
theorem Std.ExtHashSet.contains_insert_self {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} :
(m.insert k).contains k = true
source
theorem Std.ExtHashSet.mem_insert_self {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} :
k ∈ m.insert k
source
@[simp]
theorem Std.ExtHashSet.size_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] :
∅.size = 0
source
theorem Std.ExtHashSet.eq_empty_iff_size_eq_zero {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] :
m = ∅ ↔ m.size = 0
source
theorem Std.ExtHashSet.size_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} :
(m.insert k).size = if k ∈ m then m.size else m.size + 1
source
theorem Std.ExtHashSet.size_le_size_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} :
m.size ≤ (m.insert k).size
source
theorem Std.ExtHashSet.size_insert_le {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} :
(m.insert k).size ≤ m.size + 1
source
@[simp]
theorem Std.ExtHashSet.erase_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {a : α} :
∅.erase a = ∅
source
@[simp]
theorem Std.ExtHashSet.erase_eq_empty_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} :
m.erase k = ∅ ↔ m = ∅ ∨ m.size = 1 ∧ k ∈ m
source
@[simp]
theorem Std.ExtHashSet.contains_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} :
(m.erase k).contains a = (!k == a && m.contains a)
source
@[simp]
theorem Std.ExtHashSet.mem_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} :
a ∈ m.erase k ↔ (k == a) = false ∧ a ∈ m
source
theorem Std.ExtHashSet.contains_of_contains_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} :
(m.erase k).contains a = true → m.contains a = true
source
theorem Std.ExtHashSet.mem_of_mem_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} :
a ∈ m.erase k → a ∈ m
source
theorem Std.ExtHashSet.size_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} :
(m.erase k).size = if k ∈ m then m.size - 1 else m.size
source
theorem Std.ExtHashSet.size_erase_le {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} :
(m.erase k).size ≤ m.size
source
theorem Std.ExtHashSet.size_le_size_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} :
m.size ≤ (m.erase k).size + 1
source
@[simp]
theorem Std.ExtHashSet.get?_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {a : α} :
∅.get? a = none
source
theorem Std.ExtHashSet.get?_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} :
(m.insert k).get? a = if (k == a) = true ∧ ¬k ∈ m then some k else m.get? a
source
theorem Std.ExtHashSet.contains_eq_isSome_get? {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a : α} :
m.contains a = (m.get? a).isSome
source
@[simp]
theorem Std.ExtHashSet.isSome_get?_eq_contains {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a : α} :
(m.get? a).isSome = m.contains a
source
theorem Std.ExtHashSet.mem_iff_isSome_get? {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a : α} :
a ∈ m ↔ (m.get? a).isSome = true
source
@[simp]
theorem Std.ExtHashSet.isSome_get?_iff_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a : α} :
(m.get? a).isSome = true ↔ a ∈ m
source
theorem Std.ExtHashSet.get?_eq_none_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a : α} :
m.contains a = false → m.get? a = none
source
theorem Std.ExtHashSet.get?_eq_none {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a : α} :
¬a ∈ m → m.get? a = none
source
theorem Std.ExtHashSet.get?_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} :
(m.erase k).get? a = if (k == a) = true then none else m.get? a
source
@[simp]
theorem Std.ExtHashSet.get?_erase_self {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} :
(m.erase k).get? k = none
source
theorem Std.ExtHashSet.get?_beq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} :
Option.all (fun (x : α) => x == k) (m.get? k) = true
source
theorem Std.ExtHashSet.get?_congr {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k k' : α} (h : (k == k') = true) :
m.get? k = m.get? k'
source
theorem Std.ExtHashSet.get?_eq_some_of_contains {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [LawfulBEq α] {k : α} (h : m.contains k = true) :
m.get? k = some k
source
theorem Std.ExtHashSet.get?_eq_some {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [LawfulBEq α] {k : α} (h : k ∈ m) :
m.get? k = some k
source
theorem Std.ExtHashSet.get_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [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 ⋯
source
@[simp]
theorem Std.ExtHashSet.get_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k a : α} {h' : a ∈ m.erase k} :
(m.erase k).get a h' = m.get a ⋯
source
theorem Std.ExtHashSet.get?_eq_some_get {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a : α} (h' : a ∈ m) :
m.get? a = some (m.get a h')
source
theorem Std.ExtHashSet.get_eq_get_get? {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} {h : k ∈ m} :
m.get k h = (m.get? k).get ⋯
source
theorem Std.ExtHashSet.get_get? {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} {h : (m.get? k).isSome = true} :
(m.get? k).get h = m.get k ⋯
source
theorem Std.ExtHashSet.get_beq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} (h : k ∈ m) :
(m.get k h == k) = true
source
theorem Std.ExtHashSet.get_congr {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k₁ k₂ : α} (h : (k₁ == k₂) = true) (h₁ : k₁ ∈ m) :
m.get k₁ h₁ = m.get k₂ ⋯
source
theorem Std.ExtHashSet.get_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [LawfulBEq α] {k : α} (h : k ∈ m) :
m.get k h = k
source
@[simp]
theorem Std.ExtHashSet.get!_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} :
∅.get! a = default
source
theorem Std.ExtHashSet.get!_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [Inhabited α] [EquivBEq α] [LawfulHashable α] {k a : α} :
(m.insert k).get! a = if (k == a) = true ∧ ¬k ∈ m then k else m.get! a
source
theorem Std.ExtHashSet.get!_eq_default_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [Inhabited α] [EquivBEq α] [LawfulHashable α] {a : α} :
m.contains a = false → m.get! a = default
source
theorem Std.ExtHashSet.get!_eq_default {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [Inhabited α] [EquivBEq α] [LawfulHashable α] {a : α} :
¬a ∈ m → m.get! a = default
source
theorem Std.ExtHashSet.get!_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [Inhabited α] [EquivBEq α] [LawfulHashable α] {k a : α} :
(m.erase k).get! a = if (k == a) = true then default else m.get! a
source
@[simp]
theorem Std.ExtHashSet.get!_erase_self {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [Inhabited α] [EquivBEq α] [LawfulHashable α] {k : α} :
(m.erase k).get! k = default
source
theorem Std.ExtHashSet.get?_eq_some_get!_of_contains {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} :
m.contains a = true → m.get? a = some (m.get! a)
source
theorem Std.ExtHashSet.get?_eq_some_get! {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} :
a ∈ m → m.get? a = some (m.get! a)
source
theorem Std.ExtHashSet.get!_eq_get!_get? {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} :
m.get! a = (m.get? a).get!
source
theorem Std.ExtHashSet.get_eq_get! {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} {h' : a ∈ m} :
m.get a h' = m.get! a
source
theorem Std.ExtHashSet.get!_congr {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k k' : α} (h : (k == k') = true) :
m.get! k = m.get! k'
source
theorem Std.ExtHashSet.get!_eq_of_contains {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [LawfulBEq α] [Inhabited α] {k : α} (h : m.contains k = true) :
m.get! k = k
source
theorem Std.ExtHashSet.get!_eq_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [LawfulBEq α] [Inhabited α] {k : α} (h : k ∈ m) :
m.get! k = k
source
@[simp]
theorem Std.ExtHashSet.getD_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {a fallback : α} :
∅.getD a fallback = fallback
source
theorem Std.ExtHashSet.getD_insert {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k a fallback : α} :
(m.insert k).getD a fallback = if (k == a) = true ∧ ¬k ∈ m then k else m.getD a fallback
source
theorem Std.ExtHashSet.getD_eq_fallback_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a fallback : α} :
m.contains a = false → m.getD a fallback = fallback
source
theorem Std.ExtHashSet.getD_eq_fallback {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a fallback : α} :
¬a ∈ m → m.getD a fallback = fallback
source
theorem Std.ExtHashSet.getD_erase {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k a fallback : α} :
(m.erase k).getD a fallback = if (k == a) = true then fallback else m.getD a fallback
source
@[simp]
theorem Std.ExtHashSet.getD_erase_self {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k fallback : α} :
(m.erase k).getD k fallback = fallback
source
theorem Std.ExtHashSet.get?_eq_some_getD_of_contains {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a fallback : α} :
m.contains a = true → m.get? a = some (m.getD a fallback)
source
theorem Std.ExtHashSet.get?_eq_some_getD {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a fallback : α} :
a ∈ m → m.get? a = some (m.getD a fallback)
source
theorem Std.ExtHashSet.getD_eq_getD_get? {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a fallback : α} :
m.getD a fallback = (m.get? a).getD fallback
source
theorem Std.ExtHashSet.get_eq_getD {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {a fallback : α} {h' : a ∈ m} :
m.get a h' = m.getD a fallback
source
theorem Std.ExtHashSet.get!_eq_getD_default {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} :
m.get! a = m.getD a default
source
theorem Std.ExtHashSet.getD_congr {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k k' fallback : α} (h : (k == k') = true) :
m.getD k fallback = m.getD k' fallback
source
theorem Std.ExtHashSet.getD_eq_of_contains {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [LawfulBEq α] {k fallback : α} (h : m.contains k = true) :
m.getD k fallback = k
source
theorem Std.ExtHashSet.getD_eq_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [LawfulBEq α] {k fallback : α} (h : k ∈ m) :
m.getD k fallback = k
source
@[simp]
theorem Std.ExtHashSet.containsThenInsert_fst {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} :
(m.containsThenInsert k).fst = m.contains k
source
@[simp]
theorem Std.ExtHashSet.containsThenInsert_snd {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} :
(m.containsThenInsert k).snd = m.insert k
source
@[simp]
theorem Std.ExtHashSet.insertMany_nil {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] :
m.insertMany [] = m
source
@[simp]
theorem Std.ExtHashSet.insertMany_list_singleton {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {k : α} :
m.insertMany [k] = m.insert k
source
theorem Std.ExtHashSet.insertMany_cons {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} :
m.insertMany (k :: l) = (m.insert k).insertMany l
source
theorem Std.ExtHashSet.insertMany_append {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {l₁ l₂ : List α} :
m.insertMany (l₁ ++ l₂) = (m.insertMany l₁).insertMany l₂
source
theorem Std.ExtHashSet.insertMany_ind {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {ρ : Type v} [ForIn Id ρ α] [EquivBEq α] [LawfulHashable α] {motive : ExtHashSet α → Prop} (m : ExtHashSet α) {l : ρ} (init : motive m) (insert : ∀ (m : ExtHashSet α) (a : α), motive m → motive (m.insert a)) :
motive (m.insertMany l)
source
@[simp]
theorem Std.ExtHashSet.contains_insertMany_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} :
(m.insertMany l).contains k = (m.contains k || l.contains k)
source
@[simp]
theorem Std.ExtHashSet.mem_insertMany_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} :
k ∈ m.insertMany l ↔ k ∈ m ∨ l.contains k = true
source
theorem Std.ExtHashSet.mem_of_mem_insertMany_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} (contains_eq_false : l.contains k = false) :
k ∈ m.insertMany l → k ∈ m
source
theorem Std.ExtHashSet.mem_insertMany_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} {ρ : Type v} [ForIn Id ρ α] [EquivBEq α] [LawfulHashable α] {l : ρ} {k : α} :
k ∈ m → k ∈ m.insertMany l
source
theorem Std.ExtHashSet.get?_insertMany_list_of_not_mem_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} (not_mem : ¬k ∈ m) (contains_eq_false : l.contains k = false) :
(m.insertMany l).get? k = none
source
theorem Std.ExtHashSet.get?_insertMany_list_of_not_mem_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [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
source
theorem Std.ExtHashSet.get?_insertMany_list_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} (mem : k ∈ m) :
(m.insertMany l).get? k = m.get? k
source
theorem Std.ExtHashSet.get_insertMany_list_of_not_mem_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [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
source
theorem Std.ExtHashSet.get_insertMany_list_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} (mem : k ∈ m) {h : k ∈ m.insertMany l} :
(m.insertMany l).get k h = m.get k mem
source
theorem Std.ExtHashSet.get!_insertMany_list_of_not_mem_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {l : List α} {k : α} (not_mem : ¬k ∈ m) (contains_eq_false : l.contains k = false) :
(m.insertMany l).get! k = default
source
theorem Std.ExtHashSet.get!_insertMany_list_of_not_mem_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [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
source
theorem Std.ExtHashSet.get!_insertMany_list_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {l : List α} {k : α} (mem : k ∈ m) :
(m.insertMany l).get! k = m.get! k
source
theorem Std.ExtHashSet.getD_insertMany_list_of_not_mem_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k fallback : α} (not_mem : ¬k ∈ m) (contains_eq_false : l.contains k = false) :
(m.insertMany l).getD k fallback = fallback
source
theorem Std.ExtHashSet.getD_insertMany_list_of_not_mem_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [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
source
theorem Std.ExtHashSet.getD_insertMany_list_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} {k fallback : α} (mem : k ∈ m) :
(m.insertMany l).getD k fallback = m.getD k fallback
source
theorem Std.ExtHashSet.size_insertMany_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [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
source
theorem Std.ExtHashSet.size_le_size_insertMany_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} :
m.size ≤ (m.insertMany l).size
source
theorem Std.ExtHashSet.size_le_size_insertMany {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} {ρ : Type v} [ForIn Id ρ α] [EquivBEq α] [LawfulHashable α] {l : ρ} :
m.size ≤ (m.insertMany l).size
source
theorem Std.ExtHashSet.size_insertMany_list_le {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} :
(m.insertMany l).size ≤ m.size + l.length
source
@[simp]
theorem Std.ExtHashSet.insertMany_list_eq_empty_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {l : List α} :
m.insertMany l = ∅ ↔ m = ∅ ∧ l = []
source
theorem Std.ExtHashSet.eq_empty_of_insertMany_eq_empty {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} {ρ : Type v} [ForIn Id ρ α] [EquivBEq α] [LawfulHashable α] {l : ρ} :
m.insertMany l = ∅ → m = ∅
source
@[simp]
theorem Std.ExtHashSet.ofList_nil {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] :
ofList [] = ∅
source
@[simp]
theorem Std.ExtHashSet.ofList_singleton {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {k : α} :
ofList [k] = ∅.insert k
source
theorem Std.ExtHashSet.ofList_cons {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {hd : α} {tl : List α} :
ofList (hd :: tl) = (∅.insert hd).insertMany tl
source
@[simp]
theorem Std.ExtHashSet.contains_ofList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} :
(ofList l).contains k = l.contains k
source
@[simp]
theorem Std.ExtHashSet.mem_ofList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} :
k ∈ ofList l ↔ l.contains k = true
source
theorem Std.ExtHashSet.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
source
theorem Std.ExtHashSet.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
source
theorem Std.ExtHashSet.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
source
theorem Std.ExtHashSet.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
source
theorem Std.ExtHashSet.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
source
theorem Std.ExtHashSet.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
source
theorem Std.ExtHashSet.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
source
theorem Std.ExtHashSet.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
source
theorem Std.ExtHashSet.size_ofList_le {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} :
(ofList l).size ≤ l.length
source
@[simp]
theorem Std.ExtHashSet.ofList_eq_empty_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} :
ofList l = ∅ ↔ l = []
source
theorem Std.ExtHashSet.ext_get? {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {m₁ m₂ : ExtHashSet α} (h : ∀ (k : α), m₁.get? k = m₂.get? k) :
m₁ = m₂
source
theorem Std.ExtHashSet.ext_get?_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {m₁ m₂ : ExtHashSet α} :
m₁ = m₂ ↔ ∀ (k : α), m₁.get? k = m₂.get? k
source
theorem Std.ExtHashSet.ext_contains {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [LawfulBEq α] {m₁ m₂ : ExtHashSet α} (h : ∀ (k : α), m₁.contains k = m₂.contains k) :
m₁ = m₂
source
theorem Std.ExtHashSet.ext_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [LawfulBEq α] {m₁ m₂ : ExtHashSet α} (h : ∀ (k : α), k ∈ m₁ ↔ k ∈ m₂) :
m₁ = m₂
source
theorem Std.ExtHashSet.ext_mem_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [LawfulBEq α] {m₁ m₂ : ExtHashSet α} :
m₁ = m₂ ↔ ∀ (k : α), k ∈ m₁ ↔ k ∈ m₂
source
theorem Std.ExtHashSet.filter_eq_empty_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} :
filter f m = ∅ ↔ ∀ (k : α) (h : k ∈ m), f (m.get k h) = false
source
@[simp]
theorem Std.ExtHashSet.mem_filter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} {k : α} :
k ∈ filter f m ↔ ∃ (h : k ∈ m), f (m.get k h) = true
source
theorem Std.ExtHashSet.contains_of_contains_filter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} {k : α} :
(filter f m).contains k = true → m.contains k = true
source
theorem Std.ExtHashSet.mem_of_mem_filter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} {k : α} :
k ∈ filter f m → k ∈ m
source
theorem Std.ExtHashSet.size_filter_le_size {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} :
(filter f m).size ≤ m.size
source
theorem Std.ExtHashSet.size_filter_eq_size_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} :
(filter f m).size = m.size ↔ ∀ (k : α) (h : k ∈ m), f (m.get k h) = true
source
theorem Std.ExtHashSet.filter_eq_self_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} :
filter f m = m ↔ ∀ (k : α) (h : k ∈ m), f (m.get k h) = true
source
@[simp]
theorem Std.ExtHashSet.get?_filter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} {k : α} :
(filter f m).get? k = Option.filter f (m.get? k)
source
@[simp]
theorem Std.ExtHashSet.get_filter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} {k : α} {h : k ∈ filter f m} :
(filter f m).get k h = m.get k ⋯
source
theorem Std.ExtHashSet.get!_filter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {f : α → Bool} {k : α} :
(filter f m).get! k = (Option.filter f (m.get? k)).get!
source
theorem Std.ExtHashSet.getD_filter {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : ExtHashSet α} [EquivBEq α] [LawfulHashable α] {f : α → Bool} {k fallback : α} :
(filter f m).getD k fallback = (Option.filter f (m.get? k)).getD fallback