Equivalences of Polynomial Functors #
This file defines equivalences between polynomial functors and proves basic properties about them.
An equivalence between two polynomial functors P and Q, written P ≃ₚ Q, is given by an
equivalence of the A types and an equivalence between the B types for each a : A.
We provide various canonical equivalences for operations on polynomial functors, such as:
- Sum operations:
P + 0 ≃ₚ P,0 + P ≃ₚ P - Product operations and their properties
- Equivalences for sigma and pi constructions
- Universe lifting equivalences
- Tensor product equivalences
- Composition equivalences
Main definitions #
PFunctor.Equiv: An equivalence between two polynomial functors≃ₚ: Notation for polynomial functor equivalences
Main results #
- Basic equivalence properties: reflexivity, symmetry, transitivity
- Canonical equivalences for sum, product, and other constructions on polynomial functors
Adding the zero functor on the right is equivalent to the original functor.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Adding the zero functor on the left is equivalent to the original functor.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Sum of polynomial functors is commutative up to equivalence
Equations
- One or more equations did not get rendered due to their size.
Instances For
Sum of polynomial functors is associative up to equivalence
Equations
- One or more equations did not get rendered due to their size.
Instances For
If P ≃ₚ R and Q ≃ₚ S, then P + Q ≃ₚ R + S
Equations
Instances For
Rearrangement of nested sums: (P + Q) + (R + S) ≃ₚ (P + R) + (Q + S)
Equations
- One or more equations did not get rendered due to their size.
Instances For
Product with 0 on the right is 0
Equations
- PFunctor.Equiv.prodZero P = { equivA := Equiv.prodPEmpty P.A, equivB := fun (a : (P * 0).A) => PEmpty.elim a.2 }
Instances For
Product with 0 on the left is 0
Equations
- PFunctor.Equiv.zeroProd P = { equivA := Equiv.pemptyProd P.A, equivB := fun (a : (0 * P).A) => PEmpty.elim a.1 }
Instances For
Product with the unit functor on the right is equivalent to the original functor
Equations
- PFunctor.Equiv.prodOne P = { equivA := Equiv.prodPUnit P.A, equivB := fun (a : (P * 1).A) => Equiv.sumEmpty (P.B a.1) PEmpty.{?u.1 + 1} }
Instances For
Product with the unit functor on the left is equivalent to the original functor
Equations
- PFunctor.Equiv.oneProd P = { equivA := Equiv.punitProd P.A, equivB := fun (a : (1 * P).A) => Equiv.emptySum PEmpty.{?u.1 + 1} (P.B a.2) }
Instances For
Product of polynomial functors is commutative up to equivalence
Equations
- PFunctor.Equiv.prodComm P Q = { equivA := Equiv.prodComm P.A Q.A, equivB := fun (a : (P * Q).A) => Equiv.sumComm (P.B a.1) (Q.B a.2) }
Instances For
Product of polynomial functors is associative up to equivalence
Equations
- PFunctor.Equiv.prodAssoc P Q R = { equivA := Equiv.prodAssoc P.A Q.A R.A, equivB := fun (a : (P * Q * R).A) => Equiv.sumAssoc (P.B a.1.1) (Q.B a.1.2) (R.B a.2) }
Instances For
Equivalence is preserved under product: if P ≃ₚ R and Q ≃ₚ S, then P * Q ≃ₚ R * S
Equations
Instances For
Rearrangement of nested products: (P * Q) * (R * S) ≃ₚ (P * R) * (Q * S)
Equations
- One or more equations did not get rendered due to their size.
Instances For
Sum distributes over product: (P + Q) * R ≃ₚ (P * R) + (Q * R)
Equations
- One or more equations did not get rendered due to their size.
Instances For
Product distributes over sum: P * (Q + R) ≃ₚ (P * Q) + (P * R)
Equations
- One or more equations did not get rendered due to their size.
Instances For
Sigma of an empty family is the zero functor.
Equations
- PFunctor.Equiv.emptySigma F = { equivA := Equiv.equivPEmpty (PFunctor.sigma F).A, equivB := fun (a : (PFunctor.sigma F).A) => inst.elim a.fst }
Instances For
Sigma over a subsingleton index type is the single functor F default.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Sigma of a PUnit-indexed family is equivalent to the functor itself.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Left distributivity of sum over sigma.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Right distributivity of sum over sigma.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Left distributivity of product over sigma.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Right distributivity of product over sigma.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Left distributivity of tensor product over sigma.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Right distributivity of tensor product over sigma.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Right distributivity of composition over sigma.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Composition distributes over an indexed product on the left
(Niu–Spivak (6.51)):
(Π i, F i) ◃ P ≃ₚ Π i, (F i ◃ P).
A position on the left chooses all F i positions and one continuation on
their dependent sum of directions. The equivalence curries that continuation
one index at a time; directions are reassociated dependent pairs.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Pi over a PUnit-indexed family is equivalent to the functor itself.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The universe lift of a polynomial functor is equivalent to the polynomial functor.
Equations
- PFunctor.Equiv.ulift P = { equivA := Equiv.ulift, equivB := fun (x : P.ulift.A) => Equiv.ulift }
Instances For
P is equivalent to its universe lift; the inverse direction of Equiv.ulift.
Equations
- PFunctor.Equiv.uliftEquiv P = { equivA := Equiv.ulift.symm, equivB := fun (x : P.A) => Equiv.ulift.symm }
Instances For
Universe lifting is idempotent up to equivalence
Equations
- PFunctor.Equiv.uliftUliftEquiv P = { equivA := Equiv.ulift, equivB := fun (x : P.ulift.ulift.A) => Equiv.ulift }
Instances For
Universe lifting commutes with sum
Equations
- One or more equations did not get rendered due to their size.
Instances For
Universe lifting commutes with product.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Tensor product with 0 on the right is 0
Equations
- PFunctor.Equiv.tensorZero P = { equivA := Equiv.prodPEmpty P.A, equivB := fun (a : (P.tensor 0).A) => Equiv.prodPEmpty (P.B a.1) }
Instances For
Tensor product with 0 on the left is 0
Equations
- PFunctor.Equiv.zeroTensor P = { equivA := Equiv.pemptyProd P.A, equivB := fun (a : (PFunctor.tensor 0 P).A) => Equiv.pemptyProd (P.B a.2) }
Instances For
Tensor product with 1 on the right is equivalent to the constant functor
Equations
- PFunctor.Equiv.tensorOne P = { equivA := Equiv.prodPUnit P.A, equivB := fun (x : (P.tensor 1).A) => Equiv.equivPEmpty ((P.tensor 1).B x) }
Instances For
Tensor product with 1 on the left is equivalent to the constant functor
Equations
- PFunctor.Equiv.oneTensor P = { equivA := Equiv.punitProd P.A, equivB := fun (x : (PFunctor.tensor 1 P).A) => Equiv.equivPEmpty ((PFunctor.tensor 1 P).B x) }
Instances For
Tensor product with the functor Y on the right
Equations
- PFunctor.Equiv.tensorY P = { equivA := Equiv.prodPUnit P.A, equivB := fun (a : (P.tensor PFunctor.y).A) => Equiv.prodPUnit (P.B a.1) }
Instances For
Tensor product with the functor Y on the left
Equations
- PFunctor.Equiv.yTensor P = { equivA := Equiv.punitProd P.A, equivB := fun (a : (PFunctor.y.tensor P).A) => Equiv.punitProd (P.B a.2) }
Instances For
Tensor product of polynomial functors is commutative up to equivalence
Equations
- PFunctor.Equiv.tensorComm P Q = { equivA := Equiv.prodComm P.A Q.A, equivB := fun (a : (P.tensor Q).A) => Equiv.prodComm (P.B a.1) (Q.B a.2) }
Instances For
Tensor product of polynomial functors is associative up to equivalence
Equations
- PFunctor.Equiv.tensorAssoc P Q R = { equivA := Equiv.prodAssoc P.A Q.A R.A, equivB := fun (a : ((P.tensor Q).tensor R).A) => Equiv.prodAssoc (P.B a.1.1) (Q.B a.1.2) (R.B a.2) }
Instances For
Tensor product preserves equivalences: if P ≃ₚ R and Q ≃ₚ S, then P ⊗ Q ≃ₚ R ⊗ S
Equations
Instances For
Rearrangement of nested tensor products: (P ⊗ Q) ⊗ (R ⊗ S) ≃ₚ (P ⊗ R) ⊗ (Q ⊗ S)
Equations
- One or more equations did not get rendered due to their size.
Instances For
Sum distributes over tensor product: (P + Q) ⊗ R ≃ₚ (P ⊗ R) + (Q ⊗ R)
Equations
- One or more equations did not get rendered due to their size.
Instances For
Tensor product distributes over sum: P ⊗ (Q + R) ≃ₚ (P ⊗ Q) + (P ⊗ R)
Equations
- One or more equations did not get rendered due to their size.
Instances For
Composing the zero functor with P yields the zero functor.
Equations
- PFunctor.Equiv.zeroComp P = { equivA := Equiv.equivPEmpty (PFunctor.comp 0 P).A, equivB := fun (a : (PFunctor.comp 0 P).A) => PEmpty.elim a.fst }
Instances For
Composing the unit functor with P yields the unit functor.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Associativity of composition
Equations
- One or more equations did not get rendered due to their size.
Instances For
Composition with y is identity (right)
Equations
- PFunctor.Equiv.compY P = { equivA := Equiv.sigmaUnique P.A fun (a : P.A) => P.B a → PUnit.{?u.2 + 1}, equivB := fun (x : (P.comp PFunctor.y).A) => Equiv.sigmaPUnit (P.B x.fst) }
Instances For
Composition with y is identity (left)
Equations
- One or more equations did not get rendered due to their size.
Instances For
Right distributivity of composition over sum (Niu–Spivak Prop 6.47).
Equations
- One or more equations did not get rendered due to their size.
Instances For
Composition distributes over product on the left.
Equations
- One or more equations did not get rendered due to their size.