Set

This file introduces a very basic Set type, which is merely a function from the element type into Prop.

@[implicit_reducible]

def CustomBasicDatastructures.Set (α : Type u) : Type u

Equations

• CustomBasicDatastructures.Set α = (α → Prop)

@[instance_reducible]

instance CustomBasicDatastructures.instEmptyCollectionSet {α : Type u_1} : EmptyCollection (Set α)

Equations

• CustomBasicDatastructures.instEmptyCollectionSet = { emptyCollection := fun (x : α) => False }

@[instance_reducible]

instance CustomBasicDatastructures.instMembershipSet {α : Type u_1} : Membership α (Set α)

Equations

• CustomBasicDatastructures.instMembershipSet = { mem := fun (S : CustomBasicDatastructures.Set α) (a : α) => S a }

@[instance_reducible]

instance CustomBasicDatastructures.instUnionSet {α : Type u_1} : Union (Set α)

Equations

• CustomBasicDatastructures.instUnionSet = { union := fun (A B : CustomBasicDatastructures.Set α) (e : α) => e ∈ A ∨ e ∈ B }

@[instance_reducible]

instance CustomBasicDatastructures.instHasSubsetSet {α : Type u_1} : HasSubset (Set α)

Equations

• CustomBasicDatastructures.instHasSubsetSet = { Subset := fun (A B : CustomBasicDatastructures.Set α) => ∀ (e : α), e ∈ A → e ∈ B }

@[instance_reducible]

instance CustomBasicDatastructures.instHasSSubsetSet {α : Type u_1} : HasSSubset (Set α)

Equations

• CustomBasicDatastructures.instHasSSubsetSet = { SSubset := fun (A B : CustomBasicDatastructures.Set α) => A ⊆ B ∧ ¬B ⊆ A }

theorem CustomBasicDatastructures.Set.ext {α : Type u_1} (X Y : Set α) : (∀ (e : α), e ∈ X ↔ e ∈ Y) → X = Y

Two sets are the same if they feature the same elements.

theorem CustomBasicDatastructures.Set.ext_iff {α : Type u_1} {X Y : Set α} : X = Y ↔ ∀ (e : α), e ∈ X ↔ e ∈ Y

theorem CustomBasicDatastructures.Set.not_empty_contains_element {α : Type u_1} (X : Set α) : X ≠ ∅ → ∃ (e : α), e ∈ X

A non-empty set contains at least one element.

theorem CustomBasicDatastructures.Set.mem_of_subset_of_mem {α : Type u_1} {e : α} {A B : Set α} : A ⊆ B → e ∈ A → e ∈ B

If A is a subset of B and e is in A, then e is in B. This is essentially the subset definition.

theorem CustomBasicDatastructures.Set.mem_union_iff {α : Type u_1} {e : α} {A B : Set α} : e ∈ A ∪ B ↔ e ∈ A ∨ e ∈ B

Unfolds the definition of set union.

theorem CustomBasicDatastructures.Set.mem_union_of_mem_left {α : Type u_1} {e : α} {A B : Set α} : e ∈ A → e ∈ A ∪ B

If e is in A, then e is in A ∪ B.

theorem CustomBasicDatastructures.Set.mem_union_of_mem_right {α : Type u_1} {e : α} {A B : Set α} : e ∈ B → e ∈ A ∪ B

If e is in B, then e is in A ∪ B.

def CustomBasicDatastructures.Set.map {α : Type u_1} {β : Type u_2} (X : Set α) (f : α → β) : Set β

Apply a mapping function to each member of a set yielding a new set; think of List.map.

Equations

• X.map f e = ∃ (e' : α), e' ∈ X ∧ f e' = e

@[simp]

theorem CustomBasicDatastructures.Set.mem_map {α : Type u_1} {β : Type u_2} {X : Set α} {f : α → β} {e : β} : e ∈ X.map f ↔ ∃ (e' : α), e' ∈ X ∧ f e' = e

This is essentially the definition of map.

theorem CustomBasicDatastructures.Set.mem_map_of_mem {α : Type u_1} {β : Type u_2} {e : α} {X : Set α} {f : α → β} : e ∈ X → f e ∈ X.map f

For a set element, the mapped version of the element is in the mapped set.

theorem CustomBasicDatastructures.Set.subset_refl {α : Type u_1} {X : Set α} : X ⊆ X

The subset relation on sets is reflexive.

theorem CustomBasicDatastructures.Set.subset_trans {α : Type u_1} {a b c : Set α} : a ⊆ b → b ⊆ c → a ⊆ c

The subset relation on sets is transitive.

theorem CustomBasicDatastructures.Set.subset_union_of_subset_left {α : Type u_1} {a b c : Set α} : a ⊆ b → a ⊆ b ∪ c

When a is a subset of b, then a is still a subset of the union of b with c.

theorem CustomBasicDatastructures.Set.subset_union_of_subset_right {α : Type u_1} (a b c : Set α) : a ⊆ c → a ⊆ b ∪ c

When a is a subset of c, then a is still a subset of the union of b with c.

@[simp]

theorem CustomBasicDatastructures.Set.union_subset_iff_both_subset {α : Type u_1} (a b c : Set α) : a ∪ b ⊆ c ↔ a ⊆ c ∧ b ⊆ c

The union of a and b is a subset of c if and only if a and b are both subsets of c.