Documentation

Mathlib.Data.SetLike.Basic

Typeclass for types with a set-like extensionality property #

The Membership typeclass is used to let terms of a type have elements. Many instances of Membership have a set-like extensionality property: things are equal iff they have the same elements. The SetLike typeclass provides a unified interface to define a Membership that is extensional in this way.

The main use of SetLike is for algebraic subobjects (such as Submonoid and Submodule), whose non-proof data consists only of a carrier set. In such a situation, the projection to the carrier set is injective.

In general, a type A is SetLike with elements of type B if it has an injective map to Set B. This module provides standard boilerplate for every SetLike: a coe_sort, a coe to set, a PartialOrder, and various extensionality and simp lemmas.

A typical subobject should be declared as:

structure MySubobject (X : Type*) [ObjectTypeclass X] :=
  (carrier : Set X)
  (op_mem' : ∀ {x : X}, x ∈ carrier → sorry ∈ carrier)

namespace MySubobject

variables {X : Type*} [ObjectTypeclass X] {x : X}

instance : SetLike (MySubobject X) X :=
  ⟨MySubobject.carrier, λ p q h, by cases p; cases q; congr'⟩

@[simp] lemma mem_carrier {p : MySubobject X} : x ∈ p.carrier ↔ x ∈ (p : Set X) := Iff.rfl

@[ext] theorem ext {p q : MySubobject X} (h : ∀ x, x ∈ p ↔ x ∈ q) : p = q := SetLike.ext h

/-- Copy of a `MySubobject` with a new `carrier` equal to the old one. Useful to fix definitional
equalities. See Note [range copy pattern]. -/
protected def copy (p : MySubobject X) (s : Set X) (hs : s = ↑p) : MySubobject X :=
  { carrier := s,
    op_mem' := hs.symm ▸ p.op_mem' }

@[simp] lemma coe_copy (p : MySubobject X) (s : Set X) (hs : s = ↑p) :
  (p.copy s hs : Set X) = s := rfl

lemma copy_eq (p : MySubobject X) (s : Set X) (hs : s = ↑p) : p.copy s hs = p :=
  SetLike.coe_injective hs

end MySubobject

An alternative to SetLike could have been an extensional Membership typeclass:

class ExtMembership (α : out_param $ Type u) (β : Type v) extends Membership α β :=
  (ext_iff : ∀ {s t : β}, s = t ↔ ∀ (x : α), x ∈ s ↔ x ∈ t)

While this is equivalent, SetLike conveniently uses a carrier set projection directly.

Tags #

subobjects

class SetLike (A : Type u_1) (B : outParam (Type u_2)) :
Type (max u_1 u_2)

A class to indicate that there is a canonical injection between A and Set B.

This has the effect of giving terms of A elements of type B (through a Membership instance) and a compatible coercion to Type* as a subtype.

Note: if SetLike.coe is a projection, implementers should create a simp lemma such as

@[simp] lemma mem_carrier {p : MySubobject X} : x ∈ p.carrier ↔ x ∈ (p : Set X) := Iff.rfl

to normalize terms.

If you declare an unbundled subclass of SetLike, for example:

class MulMemClass (S : Type*) (M : Type*) [Mul M] [SetLike S M] where
  ...

Then you should not repeat the outParam declaration so SetLike will supply the value instead. This ensures your subclass will not have issues with synthesis of the [Mul M] parameter starting before the value of M is known.

Instances
    instance SetLike.instCoeTCSet {A : Type u_1} {B : Type u_2} [i : SetLike A B] :
    CoeTC A (Set B)
    Equations
    • SetLike.instCoeTCSet = { coe := SetLike.coe }
    instance SetLike.instMembership {A : Type u_1} {B : Type u_2} [i : SetLike A B] :
    Equations
    • SetLike.instMembership = { mem := fun x p => x p }
    instance SetLike.instCoeSortType {A : Type u_1} {B : Type u_2} [i : SetLike A B] :
    CoeSort A (Type u_2)
    Equations
    • SetLike.instCoeSortType = { coe := fun p => { x // x p } }
    @[simp]
    theorem SetLike.coe_sort_coe {A : Type u_1} {B : Type u_2} [i : SetLike A B] (p : A) :
    p = { x // x p }
    theorem SetLike.exists {A : Type u_1} {B : Type u_2} [i : SetLike A B] {p : A} {q : { x // x p }Prop} :
    (x, q x) x h, q { val := x, property := h }
    theorem SetLike.forall {A : Type u_1} {B : Type u_2} [i : SetLike A B] {p : A} {q : { x // x p }Prop} :
    ((x : { x // x p }) → q x) (x : B) → (h : x p) → q { val := x, property := h }
    theorem SetLike.coe_injective {A : Type u_1} {B : Type u_2} [i : SetLike A B] :
    Function.Injective SetLike.coe
    @[simp]
    theorem SetLike.coe_set_eq {A : Type u_1} {B : Type u_2} [i : SetLike A B] {p : A} {q : A} :
    p = q p = q
    theorem SetLike.ext' {A : Type u_1} {B : Type u_2} [i : SetLike A B] {p : A} {q : A} (h : p = q) :
    p = q
    theorem SetLike.ext'_iff {A : Type u_1} {B : Type u_2} [i : SetLike A B] {p : A} {q : A} :
    p = q p = q
    theorem SetLike.ext {A : Type u_1} {B : Type u_2} [i : SetLike A B] {p : A} {q : A} (h : ∀ (x : B), x p x q) :
    p = q

    Note: implementers of SetLike must copy this lemma in order to tag it with @[ext].

    theorem SetLike.ext_iff {A : Type u_1} {B : Type u_2} [i : SetLike A B] {p : A} {q : A} :
    p = q ∀ (x : B), x p x q
    @[simp]
    theorem SetLike.mem_coe {A : Type u_1} {B : Type u_2} [i : SetLike A B] {p : A} {x : B} :
    x p x p
    @[simp]
    theorem SetLike.coe_eq_coe {A : Type u_1} {B : Type u_2} [i : SetLike A B] {p : A} {x : { x // x p }} {y : { x // x p }} :
    x = y x = y
    @[simp]
    theorem SetLike.coe_mem {A : Type u_1} {B : Type u_2} [i : SetLike A B] {p : A} (x : { x // x p }) :
    x p
    theorem SetLike.eta {A : Type u_1} {B : Type u_2} [i : SetLike A B] {p : A} (x : { x // x p }) (hx : x p) :
    { val := x, property := hx } = x
    instance SetLike.instPartialOrder {A : Type u_1} {B : Type u_2} [i : SetLike A B] :
    Equations
    theorem SetLike.le_def {A : Type u_1} {B : Type u_2} [i : SetLike A B] {S : A} {T : A} :
    S T ∀ ⦃x : B⦄, x Sx T
    @[simp]
    theorem SetLike.coe_subset_coe {A : Type u_1} {B : Type u_2} [i : SetLike A B] {S : A} {T : A} :
    S T S T
    theorem SetLike.coe_mono {A : Type u_1} {B : Type u_2} [i : SetLike A B] :
    Monotone SetLike.coe
    @[simp]
    theorem SetLike.coe_ssubset_coe {A : Type u_1} {B : Type u_2} [i : SetLike A B] {S : A} {T : A} :
    S T S < T
    theorem SetLike.coe_strictMono {A : Type u_1} {B : Type u_2} [i : SetLike A B] :
    StrictMono SetLike.coe
    theorem SetLike.not_le_iff_exists {A : Type u_1} {B : Type u_2} [i : SetLike A B] {p : A} {q : A} :
    ¬p q x, x p ¬x q
    theorem SetLike.exists_of_lt {A : Type u_1} {B : Type u_2} [i : SetLike A B] {p : A} {q : A} :
    p < qx, x q ¬x p
    theorem SetLike.lt_iff_le_and_exists {A : Type u_1} {B : Type u_2} [i : SetLike A B] {p : A} {q : A} :
    p < q p q x, x q ¬x p