## Not signed in

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

## Site Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

• CommentRowNumber1.
• CommentAuthorDavid_Corfield
• CommentTimeOct 31st 2018
• (edited Dec 23rd 2021)

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)?

• CommentRowNumber2.
• CommentAuthormaxsnew
• CommentTimeOct 31st 2018

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.

• CommentRowNumber3.
• CommentAuthorDavid_Corfield
• CommentTimeOct 31st 2018

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)

• CommentRowNumber4.
• CommentAuthormaxsnew
• CommentTimeOct 31st 2018
• (edited Oct 31st 2018)

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.

• CommentRowNumber5.
• CommentAuthorMike Shulman
• CommentTimeOct 31st 2018

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
• CommentRowNumber6.
• CommentAuthorDavid_Corfield
• CommentTimeDec 22nd 2021
• (edited Dec 22nd 2021)

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?