Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

• Username
• Password
• Remember me

• Sign in using OpenID
• Remember me

• Forgot your password?
• Apply for membership

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology definitions deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nlab nonassociative noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

1. • CommentRowNumber1.
   • CommentAuthorDavid_Corfield
   • CommentTimeOct 31st 2018
   • (edited Dec 23rd 2021)
   • PermaLink
   Author: David_Corfield
   Format: MarkdownItexI only just noticed: Taking coproduct and product as adjoints to duplication, $\Delta: \mathcal{C} \to \mathcal{C} \times \mathcal{C}$, then the pair of introduction rules for coproduct amounts to the unit of the monad, $(A, B) \to (A+B, A+B)$, and the pair of elimination rules for product the counit of the comonad, $(A \times B, A \times B) \to (A, B)$. The other (co)unit gives, $C + C \to C$ and $C \to C \times C$. Is there anything useful and general to say about introduction/elimination and co(units)?

   I only just noticed:

   Taking coproduct and product as adjoints to duplication, $\Delta: \mathcal{C} \to \mathcal{C} \times \mathcal{C}$, then the pair of introduction rules for coproduct amounts to the unit of the monad, $(A, B) \to (A+B, A+B)$, and the pair of elimination rules for product the counit of the comonad, $(A \times B, A \times B) \to (A, B)$.

   The other (co)unit gives, $C + C \to C$ and $C \to C \times C$.

   Is there anything useful and general to say about introduction/elimination and co(units)?

2. • CommentRowNumber2.
   • CommentAuthormaxsnew
   • CommentTimeOct 31st 2018
   • PermaLink
   Author: maxsnew
   Format: MarkdownItexYes, this is some of the fundamental dogma of type theory's relationship with categories: When a type former models a right adjoint $G$ with $F \dashv G$, its elimination rule(s) are modeled by the counit of the adjunction $FGA \to A$ and its introduction rule is given by one direction of the Hom isomorphism: $(F A \to B) \to (A \to G B)$. For products we have the counit is a morphism in $C^2$: $(A\times B);(A\times B) \to (A;B)$ modeling the two projections and the introduction rule gives a natural transformation that takes a morphism in $C^2$ of the form $(\Gamma;\Gamma) \to (A;B)$ and constructs a $\Gamma \to A \times B$ in $C$. The naturality on the left is the definition of substitution. And then you have the dual which is that for types that model a left adjoint the introduction rule is modeled by the unit and the elimination rule is given by the opposite direction of the Hom isomorphism. As for general theorems there's not much to say since there's so little structure except maybe what's on this page: https://ncatlab.org/nlab/show/representability+determines+functoriality which says that the presentation in type theory is enough to define the functorial action, which is just a categorification of the fact that you can prove that the functions in a galois connection are monotone from the galois connection data.

   Yes, this is some of the fundamental dogma of type theory’s relationship with categories: When a type former models a right adjoint $G$ with $F \dashv G$, its elimination rule(s) are modeled by the counit of the adjunction $FGA \to A$ and its introduction rule is given by one direction of the Hom isomorphism: $(F A \to B) \to (A \to G B)$. For products we have the counit is a morphism in $C^2$: $(A\times B);(A\times B) \to (A;B)$ modeling the two projections and the introduction rule gives a natural transformation that takes a morphism in $C^2$ of the form $(\Gamma;\Gamma) \to (A;B)$ and constructs a $\Gamma \to A \times B$ in $C$. The naturality on the left is the definition of substitution.

   And then you have the dual which is that for types that model a left adjoint the introduction rule is modeled by the unit and the elimination rule is given by the opposite direction of the Hom isomorphism.

   As for general theorems there’s not much to say since there’s so little structure except maybe what’s on this page: https://ncatlab.org/nlab/show/representability+determines+functoriality which says that the presentation in type theory is enough to define the functorial action, which is just a categorification of the fact that you can prove that the functions in a galois connection are monotone from the galois connection data.

3. • CommentRowNumber3.
   • CommentAuthorDavid_Corfield
   • CommentTimeOct 31st 2018
   • PermaLink
   Author: David_Corfield
   Format: MarkdownItexThanks. By the way to get a link to the nLab page, just enclose the name in double square parentheses, so [[representability determines functoriality]]. I found a paper, [An Algorithmic Interpretation of a Deep Inference System](https://link.springer.com/chapter/10.1007/978-3-540-89439-1_34), which claims to prefer going the whole way and using both units and counits ("this improvement over the situation in natural deduction", p. 495). > Our system corresponds to the more symmetric specification of an adjunction based on two functors and unit and counit. (p. 494)

   Thanks. By the way to get a link to the nLab page, just enclose the name in double square parentheses, so representability determines functoriality.

   I found a paper, An Algorithmic Interpretation of a Deep Inference System, which claims to prefer going the whole way and using both units and counits (“this improvement over the situation in natural deduction”, p. 495).

   Our system corresponds to the more symmetric specification of an adjunction based on two functors and unit and counit. (p. 494)

4. • CommentRowNumber4.
   • CommentAuthormaxsnew
   • CommentTimeOct 31st 2018
   • (edited Oct 31st 2018)
   • PermaLink
   Author: maxsnew
   Format: MarkdownItexI don't know if they "prefer" it but they have some specific goal of modeling this "Deep Inference" system. That style of system is a kind of "categorical combinator" calculus. The big differences between their system and natural deduction are 1. They make composition an explicit constructor on terms (which they call "sequential composition"), whereas in natural deduction it is an admissible construction. The downside here is you also need to add associativity and unitality of composition, whereas those are just properties of substitution in natural deduction. 2. To present a connective, they add 3 term constructors: unit, counit and functorial action (which they call "parallel composition"). 3. Because they are not using variables, but are presenting implication anyway, they need to add equalities that use both implication and product, whereas in natural deduction all constructions are "modular" in that every type is defined independently of every other type. For products, they add the counit in the form of the two destructors $w_1 : A \times B \to A, w_2 : A \times B \to B$, and they add the unit, i.e., the diagonal $c : A \to A \times A$, but then they also need to add the functorial action of the product which is $t_1 \times t_2 : A_1 \times A_2 \to B_1 \times B_2$ when $t_i : A_i \to B_i$. You need to add functoriality explicitly because it's not definable from the unit and counit, whereas it is definable from the counit and one direction of the hom isomorphism.

   I don’t know if they “prefer” it but they have some specific goal of modeling this “Deep Inference” system. That style of system is a kind of “categorical combinator” calculus.

   The big differences between their system and natural deduction are

   1. They make composition an explicit constructor on terms (which they call “sequential composition”), whereas in natural deduction it is an admissible construction. The downside here is you also need to add associativity and unitality of composition, whereas those are just properties of substitution in natural deduction.
   2. To present a connective, they add 3 term constructors: unit, counit and functorial action (which they call “parallel composition”).
   3. Because they are not using variables, but are presenting implication anyway, they need to add equalities that use both implication and product, whereas in natural deduction all constructions are “modular” in that every type is defined independently of every other type.

   For products, they add the counit in the form of the two destructors $w_1 : A \times B \to A, w_2 : A \times B \to B$, and they add the unit, i.e., the diagonal $c : A \to A \times A$, but then they also need to add the functorial action of the product which is $t_1 \times t_2 : A_1 \times A_2 \to B_1 \times B_2$ when $t_i : A_i \to B_i$. You need to add functoriality explicitly because it’s not definable from the unit and counit, whereas it is definable from the counit and one direction of the hom isomorphism.

5. • CommentRowNumber5.
   • CommentAuthorMike Shulman
   • CommentTimeOct 31st 2018
   • PermaLink
   Author: Mike Shulman
   Format: MarkdownItexBTW, to make a numbered list display as a list, you need a paragraph break (blank line) before it: 1. one 2. two 3. three

   BTW, to make a numbered list display as a list, you need a paragraph break (blank line) before it:

   1. one
   2. two
   3. three
6. • CommentRowNumber6.
   • CommentAuthorDavid_Corfield
   • CommentTimeDec 22nd 2021
   • (edited Dec 22nd 2021)
   • PermaLink
   Author: David_Corfield
   Format: MarkdownItexI hadn't thought of this before: In view of the fact that product appears as the non-dependent dependent sum, it's unsurprising that both [[product type]] and [[dependent sum type]] are given via both positive and negative polarities. Now for the negative polarity, as above > When a type former models a right adjoint $G$ with $F \dashv G$, its elimination rule(s) are modeled by the counit of the adjunction $F G A \to A$ and its introduction rule is given by one direction of the Hom isomorphism: $(F A \to B) \to (A \to G B)$. For products we have the counit is a morphism in $C^2$: $(A\times B);(A\times B) \to (A;B)$ modeling the two projections and the introduction rule gives a natural transformation that takes a morphism in $C^2$ of the form $(\Gamma;\Gamma) \to (A;B)$ and constructs a $\Gamma \to A \times B$ in $C$. The naturality on the left is the definition of substitution. How then to think of dependent sum as a right adjoint? For a dependent type given by $p: B \to A$, we want $Hom_{\mathcal{C}}(C, B)$ to be equivalent to maps from $C$ to $A$ factoring through $p: B \to A$. So that's maps in the arrow category $Arr(\mathcal{C})$ between $id_C: C \to C$ and $p: B \to A$. So the negative presentation of dependent sum type is rendering the counit and Hom isomorphism of the domain cofibration as right adjoint to $Id: \mathcal{C} \to Arr(\mathcal{C})$. Are there conditions to add to provide a setting where this works?

   I hadn’t thought of this before:

   In view of the fact that product appears as the non-dependent dependent sum, it’s unsurprising that both product type and dependent sum type are given via both positive and negative polarities. Now for the negative polarity, as above

   When a type former models a right adjoint $G$ with $F \dashv G$, its elimination rule(s) are modeled by the counit of the adjunction $F G A \to A$ and its introduction rule is given by one direction of the Hom isomorphism: $(F A \to B) \to (A \to G B)$. For products we have the counit is a morphism in $C^2$: $(A\times B);(A\times B) \to (A;B)$ modeling the two projections and the introduction rule gives a natural transformation that takes a morphism in $C^2$ of the form $(\Gamma;\Gamma) \to (A;B)$ and constructs a $\Gamma \to A \times B$ in $C$. The naturality on the left is the definition of substitution.

   How then to think of dependent sum as a right adjoint?

   For a dependent type given by $p: B \to A$, we want $Hom_{\mathcal{C}}(C, B)$ to be equivalent to maps from $C$ to $A$ factoring through $p: B \to A$. So that’s maps in the arrow category $Arr(\mathcal{C})$ between $id_C: C \to C$ and $p: B \to A$.

   So the negative presentation of dependent sum type is rendering the counit and Hom isomorphism of the domain cofibration as right adjoint to $Id: \mathcal{C} \to Arr(\mathcal{C})$.

   Are there conditions to add to provide a setting where this works?