The symmetric square #
This file defines the symmetric square, which is α × α
modulo
swapping. This is also known as the type of unordered pairs.
More generally, the symmetric square is the second symmetric power
(see Data.Sym.Basic
). The equivalence is Sym2.equivSym
.
From the point of view that an unordered pair is equivalent to a
multiset of cardinality two (see Sym2.equivMultiset
), there is a
Mem
instance Sym2.Mem
, which is a Prop
-valued membership
test. Given h : a ∈ z
for z : Sym2 α
, then Mem.other h
is the other
element of the pair, defined using Classical.choice
. If α
has
decidable equality, then h.other'
computably gives the other element.
The universal property of Sym2
is provided as Sym2.lift
, which
states that functions from Sym2 α
are equivalent to symmetric
two-argument functions from α
.
Recall that an undirected graph (allowing self loops, but no multiple
edges) is equivalent to a symmetric relation on the vertex type α
.
Given a symmetric relation on α
, the corresponding edge set is
constructed by Sym2.fromRel
which is a special case of Sym2.lift
.
Notation #
The element Sym2.mk (a, b)
can be written as s(a, b)
for short.
Tags #
symmetric square, unordered pairs, symmetric powers
One can use attribute [local instance] Sym2.Rel.setoid
to temporarily
make Quotient
functionality work for α × α
.
Equations
- Sym2.Rel.setoid α = { r := Sym2.Rel α, iseqv := ⋯ }
Instances For
s(x, y)
is an unordered pair,
which is to say a pair modulo the action of the symmetric group.
It is equal to Sym2.mk (x, y)
.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Pretty printer defined by notation3
command.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependent recursion principal for Sym2
when the target is a Subsingleton
type.
See Quot.recOnSubsingleton
.
Equations
Instances For
The universal property of Sym2
; symmetric functions of two arguments are equivalent to
functions from Sym2
. Note that when β
is Prop
, it can sometimes be more convenient to use
Sym2.fromRel
instead.
Equations
- One or more equations did not get rendered due to their size.
Instances For
A two-argument version of Sym2.lift
.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Membership and set coercion #
This is a predicate that determines whether a given term is a member of a term of the
symmetric square. From this point of view, the symmetric square is the subtype of
cardinality-two multisets on α
.
Instances For
Given an element of the unordered pair, give the other element using Classical.choose
.
See also Mem.other'
for the computable version.
Equations
Instances For
Equations
- Sym2.Mem.decidable x z = Sym2.recOnSubsingleton z fun (x_1 : α × α) => match x_1 with | (fst, snd) => decidable_of_iff' (x = fst ∨ x = snd) ⋯
Note: Sym2.map_id
will not simplify Sym2.map id z
due to Sym2.map_congr
.
Diagonal #
Equations
- Sym2.IsDiag.decidablePred α z = Sym2.recOnSubsingleton z fun (a : α × α) => decidable_of_iff' (a.1 = a.2) ⋯
Declarations about symmetric relations #
Equations
- Sym2.fromRel.decidablePred sym z = Sym2.recOnSubsingleton z fun (x : α × α) => h x.1 x.2
The inverse to Sym2.fromRel
. Given a set on Sym2 α
, give a symmetric relation on α
(see Sym2.toRel_symmetric
).
Equations
- Sym2.ToRel s x y = (s(x, y) ∈ s)
Instances For
Equivalence to the second symmetric power #
The symmetric square is equivalent to length-2 vectors up to permutations.
Equations
Instances For
The symmetric square is equivalent to the second symmetric power.
Equations
- Sym2.equivSym α = Sym2.sym2EquivSym'.trans Sym.symEquivSym'.symm
Instances For
Given [DecidableEq α]
and [Fintype α]
, the following instance gives Fintype (Sym2 α)
.
Equations
- Sym2.instDecidableRel x✝ x = decidable_of_iff' (x✝.1 = x.1 ∧ x✝.2 = x.2 ∨ x✝.1 = x.2 ∧ x✝.2 = x.1) ⋯
Equations
- Sym2.instDecidableRel' = Sym2.instDecidableRel
Equations
- Sym2.instDecidableEq = inferInstanceAs (DecidableEq (Quotient (Sym2.Rel.setoid α)))
The other element of an element of the symmetric square #
Get the other element of the unordered pair using the decidable equality.
This is the computable version of Mem.other
.
Equations
- Sym2.Mem.other' h = Sym2.rec (motive := fun (x : Sym2 α) => a ∈ x → α) (fun (s : α × α) (x : a ∈ Sym2.mk s) => Sym2.pairOther a s) ⋯ z h
Instances For
Equations
- ⋯ = ⋯
Equations
- Sym2.instUnique = Unique.mk' (Sym2 α)