# 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)
• coe : ASet B

The coercion from a term of a SetLike to its corresponding Set.

• coe_injective' : Function.Injective SetLike.coe

The coercion from a term of a SetLike to its corresponding Set is injective.

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)
instance SetLike.instMembership {A : Type u_1} {B : Type u_2} [i : SetLike A B] :
instance SetLike.instCoeSortType {A : Type u_1} {B : Type u_2} [i : SetLike A B] :
CoeSort A (Type u_2)
@[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] :
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