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] where
(carrier : Set X)
(op_mem' : ∀ {x : X}, x ∈ carrier → sorry ∈ carrier)
namespace MySubobject
variable {X : Type*} [ObjectTypeclass X] {x : X}
instance : SetLike (MySubobject X) X :=
⟨MySubobject.carrier, fun 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 α β where
(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
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.
- coe : A → Set B
- coe_injective' : Function.Injective SetLike.coe
Instances
The coercion from a term of a SetLike to its corresponding Set is injective.
For terms that match the CoeSort instance's body, pretty print as ↥S
rather than as { x // x ∈ S }. The discriminating feature is that membership
uses the SetLike.instMembership instance.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
- SetLike.instPartialOrder = PartialOrder.mk ⋯
Alias of the reverse direction of SetLike.coe_subset_coe.
Alias of the reverse direction of SetLike.coe_ssubset_coe.