Documentation

PolyFun.PFunctor.Equiv.Basic

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:

Main definitions #

Main results #

instance PSigma.isEmpty_left {α : Sort u} {β : α → Sort v} [inst : IsEmpty α] :
IsEmpty ((a : α) ×' β a)
@[deprecated PSigma.isEmpty_left (since := "2026-10-19")]
instance instIsEmptySigma {α : Sort u} {β : α → Sort v} [inst : IsEmpty α] :
IsEmpty ((a : α) ×' β a)

A dependent pair over an empty first component is empty.

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
    @[simp]
    theorem PFunctor.Equiv.sumZero_equivB (P : PFunctor.{uA₁, uB}) (x✝ : (P + 0).A) :
    (sumZero P).equivB x✝ = Sum.casesOn x✝ (fun (x : P.A) => _root_.Equiv.refl ((P + 0).B (Sum.inl x))) fun (a : A 0) => PEmpty.elim a

    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
      @[simp]
      theorem PFunctor.Equiv.zeroSum_equivB (P : PFunctor.{uA₁, uB}) (x✝ : (0 + P).A) :
      (zeroSum P).equivB x✝ = Sum.casesOn x✝ (fun (a : A 0) => PEmpty.elim a) fun (x : P.A) => _root_.Equiv.refl ((0 + P).B (Sum.inr x))

      Sum of polynomial functors is commutative up to equivalence

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        @[simp]
        theorem PFunctor.Equiv.sumComm_equivB (P : PFunctor.{uA₁, uB}) (Q : PFunctor.{uA₂, uB}) (x✝ : (P + Q).A) :
        (sumComm P Q).equivB x✝ = Sum.casesOn x✝ (fun (x : P.A) => _root_.Equiv.refl ((P + Q).B (Sum.inl x))) fun (x : Q.A) => _root_.Equiv.refl ((P + Q).B (Sum.inr x))

        Sum of polynomial functors is associative up to equivalence

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For
          @[simp]
          theorem PFunctor.Equiv.sumAssoc_equivB (P : PFunctor.{uA₁, uB}) (Q : PFunctor.{uA₂, uB}) (R : PFunctor.{uA₃, uB}) (x✝ : (P + Q + R).A) :
          (sumAssoc P Q R).equivB x✝ = Sum.casesOn x✝ (fun (x : (P + Q).A) => Sum.casesOn x (fun (x : P.A) => _root_.Equiv.refl ((P + Q + R).B (Sum.inl (Sum.inl x)))) fun (x : Q.A) => _root_.Equiv.refl ((P + Q + R).B (Sum.inl (Sum.inr x)))) fun (x : R.A) => _root_.Equiv.refl ((P + Q + R).B (Sum.inr x))
          def PFunctor.Equiv.sumCongr {P Q : PFunctor.{u_1, u_2}} {R : PFunctor.{uA₃, uB₁}} {S : PFunctor.{uA₄, uB₁}} (e₁ : P.Equiv R) (e₂ : Q.Equiv S) :
          (P + Q).Equiv (R + S)

          If P ≃ₚ R and Q ≃ₚ S, then P + Q ≃ₚ R + S

          Equations
          Instances For
            @[simp]
            theorem PFunctor.Equiv.sumCongr_equivB {P Q : PFunctor.{u_1, u_2}} {R : PFunctor.{uA₃, uB₁}} {S : PFunctor.{uA₄, uB₁}} (e₁ : P.Equiv R) (e₂ : Q.Equiv S) (x✝ : (P + Q).A) :
            (e₁.sumCongr e₂).equivB x✝ = Sum.casesOn x✝ (fun (x : P.A) => e₁.equivB x) fun (x : Q.A) => e₂.equivB x

            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
              Instances For

                Product with 0 on the left is 0

                Equations
                Instances For

                  Product with the unit functor on the right is equivalent to the original functor

                  Equations
                  Instances For

                    Product with the unit functor on the left is equivalent to the original functor

                    Equations
                    Instances For

                      Product of polynomial functors is commutative up to equivalence

                      Equations
                      Instances For

                        Product of polynomial functors is associative up to equivalence

                        Equations
                        Instances For
                          def PFunctor.Equiv.prodCongr {P Q : PFunctor.{u_1, u_2}} {R : PFunctor.{uA₃, uB₃}} {S : PFunctor.{uA₄, uB₄}} (e₁ : P.Equiv R) (e₂ : Q.Equiv S) :
                          (P * Q).Equiv (R * S)

                          Equivalence is preserved under product: if P ≃ₚ R and Q ≃ₚ S, then P * Q ≃ₚ R * S

                          Equations
                          Instances For
                            @[simp]
                            theorem PFunctor.Equiv.prodCongr_equivB {P Q : PFunctor.{u_1, u_2}} {R : PFunctor.{uA₃, uB₃}} {S : PFunctor.{uA₄, uB₄}} (e₁ : P.Equiv R) (e₂ : Q.Equiv S) (a : (P * Q).A) :
                            (e₁.prodCongr e₂).equivB a = (e₁.equivB a.1).sumCongr (e₂.equivB a.2)

                            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
                                  @[simp]
                                  theorem PFunctor.Equiv.prodSumDistrib_equivB (P : PFunctor.{uA₁, uB₁}) (Q : PFunctor.{uA₂, uB₂}) (R : PFunctor.{uA₃, uB₂}) (a : (P * (Q + R)).A) :
                                  (prodSumDistrib P Q R).equivB a = match a with | (fst, Sum.inl val) => _root_.Equiv.refl ((P * (Q + R)).B (fst, Sum.inl val)) | (fst, Sum.inr val) => _root_.Equiv.refl ((P * (Q + R)).B (fst, Sum.inr val))
                                  def PFunctor.Equiv.emptySigma {I : Type v} (F : I → PFunctor.{uA₂, uB₂}) [inst : IsEmpty I] :
                                  (sigma F).Equiv 0

                                  Sigma of an empty family is the zero functor.

                                  Equations
                                  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
                                        def PFunctor.Equiv.sumSigmaDistrib (P : PFunctor.{uA₁, uB₁}) {I : Type v} (F : I → PFunctor.{uA₂, uB₁}) [Unique I] :
                                        (P + sigma F).Equiv (sigma fun (i : I) => P + F i)

                                        Left distributivity of sum over sigma.

                                        Equations
                                        • One or more equations did not get rendered due to their size.
                                        Instances For
                                          def PFunctor.Equiv.sigmaSumDistrib (P : PFunctor.{uA₁, uB₁}) {I : Type v} (F : I → PFunctor.{uA₂, uB₁}) [Unique I] :
                                          (sigma F + P).Equiv (sigma fun (i : I) => F i + P)

                                          Right distributivity of sum over sigma.

                                          Equations
                                          • One or more equations did not get rendered due to their size.
                                          Instances For
                                            def PFunctor.Equiv.prodSigmaDistrib (P : PFunctor.{uA₁, uB₁}) {I : Type v} (F : I → PFunctor.{uA₂, uB₂}) :
                                            (P * sigma F).Equiv (sigma fun (i : I) => P * F i)

                                            Left distributivity of product over sigma.

                                            Equations
                                            • One or more equations did not get rendered due to their size.
                                            Instances For
                                              def PFunctor.Equiv.sigmaProdDistrib (P : PFunctor.{uA₁, uB₁}) {I : Type v} (F : I → PFunctor.{uA₂, uB₂}) :
                                              (sigma F * P).Equiv (sigma fun (i : I) => F i * P)

                                              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
                                                    def PFunctor.Equiv.sigmaCompDistrib {I : Type v} (F : I → PFunctor.{uA₁, uB₁}) (P : PFunctor.{uA₂, uB₂}) :
                                                    ((sigma F).comp P).Equiv (sigma fun (i : I) => (F i).comp P)

                                                    Right distributivity of composition over sigma.

                                                    Equations
                                                    • One or more equations did not get rendered due to their size.
                                                    Instances For
                                                      def PFunctor.Equiv.piCompDistrib {I : Type v} (F : I → PFunctor.{uA₁, uB₁}) (P : PFunctor.{uA₂, uB₂}) :
                                                      ((pi F).comp P).Equiv (pi fun (i : I) => (F i).comp P)

                                                      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
                                                          Instances For
                                                            @[deprecated PFunctor.Equiv.ulift (since := "2026-10-19")]

                                                            P is equivalent to its universe lift; the inverse direction of Equiv.ulift.

                                                            Equations
                                                            Instances For

                                                              Universe lifting is idempotent up to equivalence

                                                              Equations
                                                              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
                                                                    Instances For

                                                                      Tensor product with 0 on the left is 0

                                                                      Equations
                                                                      Instances For

                                                                        Tensor product with 1 on the right is equivalent to the constant functor

                                                                        Equations
                                                                        Instances For

                                                                          Tensor product with 1 on the left is equivalent to the constant functor

                                                                          Equations
                                                                          Instances For

                                                                            Tensor product with the functor Y on the right

                                                                            Equations
                                                                            Instances For

                                                                              Tensor product with the functor Y on the left

                                                                              Equations
                                                                              Instances For

                                                                                Tensor product of polynomial functors is commutative up to equivalence

                                                                                Equations
                                                                                Instances For

                                                                                  Tensor product of polynomial functors is associative up to equivalence

                                                                                  Equations
                                                                                  Instances For

                                                                                    Tensor product preserves equivalences: if P ≃ₚ R and Q ≃ₚ S, then P ⊗ Q ≃ₚ R ⊗ S

                                                                                    Equations
                                                                                    Instances For
                                                                                      @[simp]
                                                                                      theorem PFunctor.Equiv.tensorCongr_equivB {P : PFunctor.{uA₁, uB₁}} {Q : PFunctor.{uA₂, uB₂}} {R : PFunctor.{uA₃, uB₃}} {S : PFunctor.{uA₄, uB₄}} (e₁ : P.Equiv R) (e₂ : Q.Equiv S) (a : (P.tensor Q).A) :
                                                                                      (e₁.tensorCongr e₂).equivB a = (e₁.equivB a.1).prodCongr (e₂.equivB a.2)

                                                                                      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
                                                                                            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
                                                                                                  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.
                                                                                                        Instances For