Not signed in (Sign In)

Not signed in

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

  • Sign in using OpenID

Site Tag Cloud

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 comma complex complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration finite 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 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

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

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • 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)(A+B,A+B)(A, B) \to (A+B, A+B), and the pair of elimination rules for product the counit of the comonad, (A×B,A×B)(A,B)(A \times B, A \times B) \to (A, B).

    The other (co)unit gives, C+CCC + C \to C and CC×CC \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 GG with FGF \dashv G, its elimination rule(s) are modeled by the counit of the adjunction FGAAFGA \to A and its introduction rule is given by one direction of the Hom isomorphism: (FAB)(AGB)(F A \to B) \to (A \to G B). For products we have the counit is a morphism in C 2C^2: (A×B);(A×B)(A;B)(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 2C^2 of the form (Γ;Γ)(A;B)(\Gamma;\Gamma) \to (A;B) and constructs a ΓA×B\Gamma \to A \times B in CC. 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×BA,w 2:A×BBw_1 : A \times B \to A, w_2 : A \times B \to B, and they add the unit, i.e., the diagonal c:AA×Ac : A \to A \times A, but then they also need to add the functorial action of the product which is t 1×t 2:A 1×A 2B 1×B 2t_1 \times t_2 : A_1 \times A_2 \to B_1 \times B_2 when t i:A iB it_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 GG with FGF \dashv G, its elimination rule(s) are modeled by the counit of the adjunction FGAAF G A \to A and its introduction rule is given by one direction of the Hom isomorphism: (FAB)(AGB)(F A \to B) \to (A \to G B). For products we have the counit is a morphism in C 2C^2: (A×B);(A×B)(A;B)(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 2C^2 of the form (Γ;Γ)(A;B)(\Gamma;\Gamma) \to (A;B) and constructs a ΓA×B\Gamma \to A \times B in CC. 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:BAp: B \to A, we want Hom 𝒞(C,B)Hom_{\mathcal{C}}(C, B) to be equivalent to maps from CC to AA factoring through p:BAp: B \to A. So that’s maps in the arrow category Arr(𝒞)Arr(\mathcal{C}) between id C:CCid_C: C \to C and p:BAp: 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:𝒞Arr(𝒞)Id: \mathcal{C} \to Arr(\mathcal{C}).

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