Documentation

Std.Data.HashSet.RawLemmas

Hash set lemmas #

This module contains lemmas about Std.Data.HashSet.Raw. 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 α.

source
@[simp]
theorem Std.HashSet.Raw.size_empty {α : Type u} {c : Nat} :
(Std.HashSet.Raw.empty c).size = 0
source
@[simp]
theorem Std.HashSet.Raw.size_emptyc {α : Type u} :
∅.size = 0
source
theorem Std.HashSet.Raw.isEmpty_eq_size_eq_zero {α : Type u} {m : Std.HashSet.Raw α} :
m.isEmpty = (m.size == 0)
source
@[simp]
theorem Std.HashSet.Raw.isEmpty_empty {α : Type u} [BEq α] [Hashable α] {c : Nat} :
(Std.HashSet.Raw.empty c).isEmpty = true
source
@[simp]
theorem Std.HashSet.Raw.isEmpty_emptyc {α : Type u} [BEq α] [Hashable α] :
∅.isEmpty = true
source
@[simp]
theorem Std.HashSet.Raw.isEmpty_insert {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} :
(m.insert a).isEmpty = false
source
theorem Std.HashSet.Raw.mem_iff_contains {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] {a : α} :
a ∈ m ↔ m.contains a = true
source
theorem Std.HashSet.Raw.contains_congr {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} {b : α} (hab : (a == b) = true) :
m.contains a = m.contains b
source
theorem Std.HashSet.Raw.mem_congr {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} {b : α} (hab : (a == b) = true) :
a ∈ m ↔ b ∈ m
source
@[simp]
theorem Std.HashSet.Raw.contains_empty {α : Type u} [BEq α] [Hashable α] {a : α} {c : Nat} :
(Std.HashSet.Raw.empty c).contains a = false
source
@[simp]
theorem Std.HashSet.Raw.not_mem_empty {α : Type u} [BEq α] [Hashable α] {a : α} {c : Nat} :
¬a ∈ Std.HashSet.Raw.empty c
source
@[simp]
theorem Std.HashSet.Raw.contains_emptyc {α : Type u} [BEq α] [Hashable α] {a : α} :
∅.contains a = false
source
@[simp]
theorem Std.HashSet.Raw.not_mem_emptyc {α : Type u} [BEq α] [Hashable α] {a : α} :
¬a ∈ ∅
source
theorem Std.HashSet.Raw.contains_of_isEmpty {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} :
m.isEmpty = true → m.contains a = false
source
theorem Std.HashSet.Raw.not_mem_of_isEmpty {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} :
m.isEmpty = true → ¬a ∈ m
source
theorem Std.HashSet.Raw.isEmpty_eq_false_iff_exists_contains_eq_true {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) :
m.isEmpty = false ↔ ∃ (a : α), m.contains a = true
source
theorem Std.HashSet.Raw.isEmpty_eq_false_iff_exists_mem {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) :
m.isEmpty = false ↔ ∃ (a : α), a ∈ m
source
theorem Std.HashSet.Raw.isEmpty_iff_forall_contains {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) :
m.isEmpty = true ↔ ∀ (a : α), m.contains a = false
source
theorem Std.HashSet.Raw.isEmpty_iff_forall_not_mem {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) :
m.isEmpty = true ↔ ∀ (a : α), ¬a ∈ m
source
@[simp]
theorem Std.HashSet.Raw.insert_eq_insert {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] {a : α} :
insert a m = m.insert a
source
@[simp]
theorem Std.HashSet.Raw.singleton_eq_insert {α : Type u} [BEq α] [Hashable α] {a : α} :
{a} = ∅.insert a
source
@[simp]
theorem Std.HashSet.Raw.contains_insert {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} {a : α} :
(m.insert k).contains a = (k == a || m.contains a)
source
@[simp]
theorem Std.HashSet.Raw.mem_insert {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} {a : α} :
a ∈ m.insert k ↔ (k == a) = true ∨ a ∈ m
source
theorem Std.HashSet.Raw.contains_of_contains_insert {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} {a : α} :
(m.insert k).contains a = true → (k == a) = false → m.contains a = true
source
theorem Std.HashSet.Raw.mem_of_mem_insert {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} {a : α} :
a ∈ m.insert k → (k == a) = false → a ∈ m
source
theorem Std.HashSet.Raw.contains_of_contains_insert' {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {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.HashSet.Raw.mem_of_mem_insert' {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {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_insertIfNew.

source
@[simp]
theorem Std.HashSet.Raw.contains_insert_self {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} :
(m.insert k).contains k = true
source
@[simp]
theorem Std.HashSet.Raw.mem_insert_self {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} :
k ∈ m.insert k
source
theorem Std.HashSet.Raw.size_insert {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} :
(m.insert k).size = if k ∈ m then m.size else m.size + 1
source
theorem Std.HashSet.Raw.size_le_size_insert {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} :
m.size ≤ (m.insert k).size
source
theorem Std.HashSet.Raw.size_insert_le {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} :
(m.insert k).size ≤ m.size + 1
source
@[simp]
theorem Std.HashSet.Raw.erase_empty {α : Type u} [BEq α] [Hashable α] {k : α} {c : Nat} :
(Std.HashSet.Raw.empty c).erase k = Std.HashSet.Raw.empty c
source
@[simp]
theorem Std.HashSet.Raw.erase_emptyc {α : Type u} [BEq α] [Hashable α] {k : α} :
∅.erase k = ∅
source
@[simp]
theorem Std.HashSet.Raw.isEmpty_erase {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} :
(m.erase k).isEmpty = (m.isEmpty || m.size == 1 && m.contains k)
source
@[simp]
theorem Std.HashSet.Raw.contains_erase {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} {a : α} :
(m.erase k).contains a = (!k == a && m.contains a)
source
@[simp]
theorem Std.HashSet.Raw.mem_erase {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} {a : α} :
a ∈ m.erase k ↔ (k == a) = false ∧ a ∈ m
source
theorem Std.HashSet.Raw.contains_of_contains_erase {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} {a : α} :
(m.erase k).contains a = true → m.contains a = true
source
theorem Std.HashSet.Raw.mem_of_mem_erase {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} {a : α} :
a ∈ m.erase k → a ∈ m
source
theorem Std.HashSet.Raw.size_erase {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} :
(m.erase k).size = if k ∈ m then m.size - 1 else m.size
source
theorem Std.HashSet.Raw.size_erase_le {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} :
(m.erase k).size ≤ m.size
source
theorem Std.HashSet.Raw.size_le_size_erase {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} :
m.size ≤ (m.erase k).size + 1
source
@[simp]
theorem Std.HashSet.Raw.get?_empty {α : Type u} [BEq α] [Hashable α] {a : α} {c : Nat} :
(Std.HashSet.Raw.empty c).get? a = none
source
@[simp]
theorem Std.HashSet.Raw.get?_emptyc {α : Type u} [BEq α] [Hashable α] {a : α} :
∅.get? a = none
source
theorem Std.HashSet.Raw.get?_of_isEmpty {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} :
m.isEmpty = true → m.get? a = none
source
theorem Std.HashSet.Raw.get?_insert {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} {a : α} :
(m.insert k).get? a = if (k == a) = true ∧ ¬k ∈ m then some k else m.get? a
source
theorem Std.HashSet.Raw.contains_eq_isSome_get? {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} :
m.contains a = (m.get? a).isSome
source
theorem Std.HashSet.Raw.get?_eq_none_of_contains_eq_false {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} :
m.contains a = false → m.get? a = none
source
theorem Std.HashSet.Raw.get?_eq_none {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} :
¬a ∈ m → m.get? a = none
source
theorem Std.HashSet.Raw.get?_erase {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} {a : α} :
(m.erase k).get? a = if (k == a) = true then none else m.get? a
source
theorem Std.HashSet.Raw.get_insert {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {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.HashSet.Raw.get_erase {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} {a : α} {h' : a ∈ m.erase k} :
(m.erase k).get a h' = m.get a ⋯
source
theorem Std.HashSet.Raw.get?_eq_some_get {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} {h' : a ∈ m} :
m.get? a = some (m.get a h')
source
@[simp]
theorem Std.HashSet.Raw.get?_erase_self {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} :
(m.erase k).get? k = none
source
@[simp]
theorem Std.HashSet.Raw.get!_empty {α : Type u} [BEq α] [Hashable α] [Inhabited α] {a : α} {c : Nat} :
(Std.HashSet.Raw.empty c).get! a = default
source
@[simp]
theorem Std.HashSet.Raw.get!_emptyc {α : Type u} [BEq α] [Hashable α] [Inhabited α] {a : α} :
∅.get! a = default
source
theorem Std.HashSet.Raw.get!_of_isEmpty {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [Inhabited α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} :
m.isEmpty = true → m.get! a = default
source
theorem Std.HashSet.Raw.get!_insert {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [Inhabited α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} {a : α} :
(m.insert k).get! a = if (k == a) = true ∧ ¬k ∈ m then k else m.get! a
source
theorem Std.HashSet.Raw.get!_eq_default_of_contains_eq_false {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [Inhabited α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} :
m.contains a = false → m.get! a = default
source
theorem Std.HashSet.Raw.get!_eq_default {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [Inhabited α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} :
¬a ∈ m → m.get! a = default
source
theorem Std.HashSet.Raw.get!_erase {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [Inhabited α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} {a : α} :
(m.erase k).get! a = if (k == a) = true then default else m.get! a
source
@[simp]
theorem Std.HashSet.Raw.get!_erase_self {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [Inhabited α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} :
(m.erase k).get! k = default
source
theorem Std.HashSet.Raw.get?_eq_some_get!_of_contains {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] [Inhabited α] (h : m.WF) {a : α} :
m.contains a = true → m.get? a = some (m.get! a)
source
theorem Std.HashSet.Raw.get?_eq_some_get! {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] [Inhabited α] (h : m.WF) {a : α} :
a ∈ m → m.get? a = some (m.get! a)
source
theorem Std.HashSet.Raw.get!_eq_get!_get? {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] [Inhabited α] (h : m.WF) {a : α} :
m.get! a = (m.get? a).get!
source
theorem Std.HashSet.Raw.get_eq_get! {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] [Inhabited α] (h : m.WF) {a : α} {h' : a ∈ m} :
m.get a h' = m.get! a
source
@[simp]
theorem Std.HashSet.Raw.getD_empty {α : Type u} [BEq α] [Hashable α] {a : α} {fallback : α} {c : Nat} :
(Std.HashSet.Raw.empty c).getD a fallback = fallback
source
@[simp]
theorem Std.HashSet.Raw.getD_emptyc {α : Type u} [BEq α] [Hashable α] {a : α} {fallback : α} :
∅.getD a fallback = fallback
source
theorem Std.HashSet.Raw.getD_of_isEmpty {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} {fallback : α} :
m.isEmpty = true → m.getD a fallback = fallback
source
theorem Std.HashSet.Raw.getD_insert {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {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.HashSet.Raw.getD_eq_fallback_of_contains_eq_false {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} {fallback : α} :
m.contains a = false → m.getD a fallback = fallback
source
theorem Std.HashSet.Raw.getD_eq_fallback {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} {fallback : α} :
¬a ∈ m → m.getD a fallback = fallback
source
theorem Std.HashSet.Raw.getD_erase {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} {a : α} {fallback : α} :
(m.erase k).getD a fallback = if (k == a) = true then fallback else m.getD a fallback
source
@[simp]
theorem Std.HashSet.Raw.getD_erase_self {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {k : α} {fallback : α} :
(m.erase k).getD k fallback = fallback
source
theorem Std.HashSet.Raw.get?_eq_some_getD_of_contains {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} {fallback : α} :
m.contains a = true → m.get? a = some (m.getD a fallback)
source
theorem Std.HashSet.Raw.get?_eq_some_getD {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} {fallback : α} :
a ∈ m → m.get? a = some (m.getD a fallback)
source
theorem Std.HashSet.Raw.getD_eq_getD_get? {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} {fallback : α} :
m.getD a fallback = (m.get? a).getD fallback
source
theorem Std.HashSet.Raw.get_eq_getD {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (h : m.WF) {a : α} {fallback : α} {h' : a ∈ m} :
m.get a h' = m.getD a fallback
source
theorem Std.HashSet.Raw.get!_eq_getD_default {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] [Inhabited α] (h : m.WF) {a : α} :
m.get! a = m.getD a default
source
@[simp]
theorem Std.HashSet.Raw.containsThenInsert_fst {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] (h : m.WF) {k : α} :
(m.containsThenInsert k).fst = m.contains k
source
@[simp]
theorem Std.HashSet.Raw.containsThenInsert_snd {α : Type u} {m : Std.HashSet.Raw α} [BEq α] [Hashable α] (h : m.WF) {k : α} :
(m.containsThenInsert k).snd = m.insert k