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 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 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 internal-categories k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure 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).

Atrium: Number of Adjunctions between two Finite Categories

Bottom of Page

1 to 22 of 22

  1.  
    • CommentRowNumber1.
    • CommentAuthorConflictTheory
    • CommentTimeAug 6th 2012

    I was considering the question of how many adjunctions there are between two fixed finite categories C and D. The reason for my querry is to try to better understand the meaning and nature of adjunctions by studying them explicitly in a finite setting.

    I have looked online, and have not found the question of how many adjunctions there are between two finite categories. Considering the number of papers touting the importance of adjunctions to category theory, it seems like this would be a natural question to ask.

    My question is: Is there a philosophical reason why this question is not asked?

    Some additional back-ground on the question…

    I have read an

    article

    that stated it is not good to ask the question of whether an adjunction exists between two categories, but rather to ask whether a particular functor has a left, or right, adjoint.

    It just seems to me that if we could construct every adjunction between two arbitrary finite categories, that this might reap a great deal of concrete knowledge about adjunctions and perhaps make their real-world applications more obvious to the applied mathematician, engineer, physicists, etc.

    Any thoughts are most appreciated. Thanks!

    • CommentRowNumber2.
    • CommentAuthorTobyBartels
    • CommentTimeAug 7th 2012

    I don’t agree with that article. The author writes

    it is not the relation on categories “there exists an adjunction,” but rather “this functor has an adjoint” that we are concerned with.

    to contrast adjunctions with equivalences. But one might as well write

    it is not the relation on categories “there exists an equivalence,” but rather “this functor has a pseudo-inverse” that we are concerned with.

    I think that looking that the totality of adjunctions between two categories is quite reasonable, just like looking at the totality of equivalences between two categories.

    However, notice that there is not just a set but a category of adjunctions (and the same for equivalences), so it’s not just the number of them (or even the number up to isomorphism) but the entire structure of this (also finite) category.

    I have never considered this, so I’d like to know if you find anything interesting!

    • CommentRowNumber3.
    • CommentAuthorTodd_Trimble
    • CommentTimeAug 7th 2012

    There are some cases where one is very interested in understanding when an adjunction exists between two categories. For example, if one of the categories is XX and the other has just one object and one morphism (viz. the identity morphism), then whether an adjunction exists between these two categories is the same as whether XX has an initial or terminal object. And just about any fundamental question in category theory can be phrased as asking whether some category XX has an initial object!

    My guess is that given two finite categories, it will in general be very hard to classify or enumerate all adjunctions between them (or to understand up to equivalence the category of adjunctions between them). But in some special cases, depending on what sorts of categories one has, it could be interesting. For example, if one of the categories is the two-element ordinal, what can you say? Off hand, I don’t know!

    • CommentRowNumber4.
    • CommentAuthorDavidRoberts
    • CommentTimeAug 7th 2012

    Even if we can only get inequalities, that would be interesting. There are clearly very weak bounds given by the bound on the number of functors in one direction and some data as specified in Street’s paper http://www.tac.mta.ca/tac/volumes/27/4/27-04abs.html.

    As a first step, we’d need to estimate the number of functors from one finite category to another. It would be interesting to see what effect choosing a source category has on the estimate of the number of adjunctions - whether starting with functors from the smaller to the larger is a better bound or not than functors from the larger to the smaller - and looking at left/right adjoints to the given functors.

    • CommentRowNumber5.
    • CommentAuthorRodMcGuire
    • CommentTimeAug 7th 2012

    Since only smallish categories are being considered, as a wild guess it might be good to consider their underlying quivers and associated things.

    For category AA, call the underlying quiver U(A)U(A), the free category F(U(A))F(U(A)), and the (unique?) binding? functor f A:F(U(A))→Af_A : F(U(A)) \to A. (does this type of functor which I called binding have a name in the literature?)

    It may be that any adjunctions between AA and BB can be derived from adjunctions between F(U(A))F(U(A)) and F(U(B))F(U(B)), in which case there may be some independently determinable pre-adjunction relation between U(A)U(A) and U(B)U(B).

    As I said above, this is just a wild guess.

    • CommentRowNumber6.
    • CommentAuthorDavidRoberts
    • CommentTimeAug 7th 2012

    does this type of functor which I called binding have a name in the literature?)

    it’s the counit of the forget-free adjunction between CatCat and QuiverQuiver (aka GrphGrph, DiGrphDiGrph Set •⇉•Set^{\bullet \rightrightarrows\bullet} etc).

    • CommentRowNumber7.
    • CommentAuthorConflictTheory
    • CommentTimeAug 7th 2012
    • (edited Aug 7th 2012)

    Rod:

    If we look at the underlying quivers U(A)U(A) and U(B)U(B) for finite categories AA and BB, I wonder if it would be useful to restrict to categories AA and BB whose underlying quiver representations are of finite type? I am wondering if the complications associated with quiver representations of the "wild type", mentioned in the link above, would lead to complications with classifying the adjoint functors between the corresponding finite categories AA and BB if either U(A)U(A) or U(B)U(B) has an underlying quiver representation of the wild type. If so, this could lead to a connection between the theory of adjoints between finite categories and the representation theory of quiver categories.

    Following Todd and Roberts’ ideas: in the category of finite categories, there is at most one adjunction between any finite category X to category 1 consisting of one object and the identity morphism since the one object category with identity morphism is the terminal category in the category of finite categories with functors as morphisms. It would seem that it might be easier to work with a sequence of finite ordinal categories to start with, and try to work out the structure of the corresponding categories of adjunctions (between two arbitrary finite ordinal categories) in accordance with Toby’s suggestion.

    Thanks for all your input on this! These look like very interesting ideas!

    • CommentRowNumber8.
    • CommentAuthorDavidRoberts
    • CommentTimeAug 7th 2012

    there is at most one adjunction between any finite category X to category 1

    or rather, up to equivalence, there is at most one adjunction. Consider a groupoid equivalent to 1.

    • CommentRowNumber9.
    • CommentAuthorConflictTheory
    • CommentTimeAug 8th 2012
    • (edited Aug 8th 2012)

    If we let Sk(C)Sk(C) and Sk(D)Sk(D) denote the skeletons of locally small categories CC, and DD, respectively, then

    The uniqueness up to equivalence of adjunctions would suggest that we can study the category of adjunctions between two categories CC and DD by studying the category of adjunctions between the skeletons Sk(C)Sk(C) and Sk(D)Sk(D) of the categories CC and DD, respectively, since for each adjunction FF left adjoint to GG from CC to DD, there exists an adjunction from Sk(C)Sk(C) to Sk(D)Sk(D) obtained by composition of FF and GG with the respective halves of the equivalence adjunctions between CC and Sk(C)Sk(C) and between DD and Sk(D)Sk(D), and conversely.

    • CommentRowNumber10.
    • CommentAuthorTodd_Trimble
    • CommentTimeAug 8th 2012

    One thing to do is just start playing around with examples. For example, suppose one of the categories is the two-element ordinal 22. Then adjoint pairs (F:2→X,G:X→2,F⊣G)(F: 2 \to X, G: X \to 2, F \dashv G) amount to epimorphisms 0→x0 \to x where 00 is initial in XX. Similarly, adjoint pairs (F:n→X,G:X→n,F⊣G)(F: n \to X, G: X \to n, F \dashv G) amount to chains of epimorphisms 0→x 1→…→x n−10 \to x_1 \to \ldots \to x_{n-1} in XX. (Remark that in a poset PP, every arrow is an epimorphism, and left adjoints preserve epimorphisms.)

    • CommentRowNumber11.
    • CommentAuthorConflictTheory
    • CommentTimeAug 8th 2012
    • (edited Aug 8th 2012)

    From Todd’s example, it seems like then that left adjoints from n to the X just picks out the ordered subcategories of XX with initial object of nn being mapped to the initial object of XX.

    From this, then there would be exactly two adjoints between the two-ordinal category 22 and itself, namely, the functor FF that sends 0→00 \to 0 and 1→11 \to 1 in 22, with right adjoint RR that sends 0→00 \to 0 and 1→11 \to 1 in 22. Then the other adjoint is F ′F^{'} that sends 0→00 \to 0 and 1→01 \to 0 in 22 with right adjoint G ′G^{'} that sends 1→11 \to 1 and 0→10 \to 1 in 22. So the total number of adjoints from 2→22 \to 2 is equal to 2 ord#−1=2 2−1=22^{ord#-1} =2^{2-1}=2. It seems like this generalizes: if mm is the m-ordinal category, m a positive integer, then the number of adjunctions from mm to itself (or from mm to nn with nn greater than or equal to mm) is just 2 m−12^{m-1}.

    For small integers m, there appears to be an easy way to enumerate explicitly all the left adjoints from mm to itself, and from this enumeration, it is easy to read off the respective right adjoints.

    For 22, the binary number 00, and 01 encode the two distinct left adjoints from 22 to 22: the first position in the binary string _ x represents the first element in 22 as the source category, and the second position in the binary string x _ represents the second element in 22 as the source category. The first digit 0 in the binary string 01 tells us to send the identity morphism of the object 0∈20 \in 2 to the identity morphism of 0∈20 \in 2, and the second digit 1 in the binary string 01 tells us to send the identity morphism of the object 1∈21 \in 2 to the identity morphism of 1∈21 \in 2. The right adjoint is found by taking the string 01, and subtracting from each digit the number 1 to obtain the string (1-0,1-1)=10, and then reversing the digits in the string 10 to get 01. By telling where to map the identity morphisms, functorality of FF tells us how to map the non-identity morphisms (and objects) between 22 and itself so as to preserve composition in 22 (and I believe this generalizes to arbitrary functors between ordinal categories mm and nn, but I could be wrong).

    For the ordinal category 33, the left adjoints are represented by a subset of the 3 digit numbers of base 3 (instead of binary numbers): the left adjoints from 33 to 33 are encoded by 000, 001, 011, and 012, with the right adjoint for 000 given by 222, the right adjoint for 001 given by 122 (= 221 in reverse order, that is 122 is obtained by 2-0 2-0 2-1 = 221 and then reversing the string to get 122), the right adjoint for 011 is given by 112, and the right adjoint for 012 given by 012.

    Example of this encodeing: Let x 0,x 1,x 2x_0, x_1, x_2 denote the identity morphisms of 0, 1, and 2 of 33 as a the source category, and y 0,y 1,y 3y_0, y_1, y_3 denote the identity morphisms of 0, 1, and 2, respectively, of 33 viewed as the target category.

    Then 011 gives a left adjoint from 3→33 \to 3 by suggesting the following map: FF defined by sending x 0→y 0x_0 \to y_0, x 1→y 1x_1 \to y_1 and x 2→y 1x_2 \to y_1 with 112 giving the right adjoint by suggesting the map GG defined by sending y 0→x 1y_0 \to x_1, y 1→x 1y_1 \to x_1 and y 2→x 2y_2 \to x_2.

    Note that each digit in the four trinary numbers 000, 001, 011, and 012 have the property that the digits are non-decreasing from left to right, and that adjacent digits are either 0 units apart or 1 unit apart and that the first digit is always 0 (to ensure that FF sends the initial object of 33 to the initial object in 33). I think this suggests a general algorithm to test whether a functor HH from the ordinal category m→mm \to m (or from m→nm \to n with nn greater than or equal to mm) is a left adjoint.

    • CommentRowNumber12.
    • CommentAuthorTobyBartels
    • CommentTimeAug 8th 2012

    it seems like then that left adjoints from n to the X just picks out the ordered subcategories of XX with initial object of nn being mapped to the initial object of XX

    Also, the morphisms in these ‘ordered subcategories’ need to be epic. But since your examples of XX are all posets, that’s automatic.

    that the digits are non-decreasing from left to right, and that adjacent digits are either 0 units apart or 1 unit apart and that the first digit is always 0

    Based on Todd’s result, the possibilities are more general. There’s no reason that the step size needs to be 00 or 11. For example, 0→20 \to 2 is an epimorphism so gives us an adjunction from 22 to 33.

    if mm is the m-ordinal category, m a positive integer, then the number of adjunctions from mm to itself (or from mm to nn with nn greater than or equal to mm) is just 2 (m−1)2^{(m-1)}

    I would agree with this if the previous quotation were correct. But instead, we want the number of nondecreasing sequences of length m−1m - 1 from a sequence of nn digits. If we tack on a 00 at the beginning (which in fact we already have) and an n−1n - 1 on the end (which we don’t already have), then we have mm steps where the step sizes total to n−1n - 1. That is, count ordered partitions of n−1n - 1 into mm parts, except in partition theory they usually don’t accept parts of size 00, so count ordered partitions of n−1n - 1 into at most mm inhabited parts. I found this in the OEIS as A026820.

    • CommentRowNumber13.
    • CommentAuthorTodd_Trimble
    • CommentTimeAug 8th 2012
    • (edited Aug 8th 2012)

    There’s a “stars and bars” trick for counting the number of left adjoints from the ordinal mm to the ordinal n={0,…,n−1}n = \{0, \ldots, n-1\}, or what is the same, the number of functors = nondecreasing functions from m−1m-1 to nn. The number of stars is n−1n-1 and the number of bars is m−1m-1; for each nondecreasing f:m−1→nf \colon m-1 \to n, imagine all the stars and bars lined up in a row, so that if f(i)=jf(i) = j, then the i thi^{th} bar is placed just after jj stars.

    Thus the function ff is specified by saying which m−1m-1 items, among (m−1)+(n−1)(m-1) + (n-1) items in a row, are to serve as bars, or in other words we are trying to count the number of (m−1)(m-1)-element subsets of a set with m+n−2m+n-2 elements. This is the binomial coefficient (m+n−2m−1)\binom{m+n-2}{m-1}. As a spot check, this gives nn in the case m=2m=2 (which is correct).

    • CommentRowNumber14.
    • CommentAuthorConflictTheory
    • CommentTimeAug 9th 2012
    • (edited Aug 9th 2012)

    Toby, thanks for correcting my error and for the clarification! Todd, thanks for your assistance and star and bar combinatorics approach (that helps for visualizing a lot!) as well. Todd’s formula looks correct: I was able to test the result for m=3=n.

    (3+3−23−1)=(42)=6\binom{3+3-2}{3-1} =\binom{4}{2} = 6

    More explicitly, the six adjoints pairs from 3→33 \to 3 are

    1) f(i)=0f(i)=0, and g(i)=2−f(2−i)=2g(i)=2-f(2-i)=2 for i=0,1,2i=0,1,2,

    2) f(0)=0f(0)=0, f(1)=0f(1)=0, f(2)=2f(2)=2 whose right adjoint is given by g(0)=1=g(1)g(0)=1=g(1), and g(2)=2g(2)=2.

    3) f(0)=0f(0)=0, f(1)=0f(1)=0, and f(2)=1f(2)=1 with right adjoint g(0)=1g(0)=1, g(1)=2g(1)=2, g(2)=2g(2)=2

    4) f(0)=0f(0)=0, f(1)=1f(1)=1, and f(2)=1f(2)=1 with right adjoint g(0)=0g(0)=0, g(1)=2g(1)=2, g(2)=2g(2)=2

    5) f(0)=0f(0)=0, f(1)=1f(1)=1, and f(2)=2f(2)=2 with right adjoint g(0)=0g(0)=0, g(1)=1g(1)=1, g(2)=2g(2)=2

    6) f(0)=0f(0)=0, f(1)=2f(1)=2, and f(2)=2f(2)=2 with right adjoint g(0)=0=g(1)g(0)=0=g(1), g(2)=2g(2)=2.

    I am not sure if there is a nice closed form formula for gg given ff, other than the well known brute force one f(i)≤j↔i≤g(j)f(i) \leq j \leftrightarrow i \leq g(j), but even for this, it generates only O(mn)O(mn) inequalities to check for a given f.

    • CommentRowNumber15.
    • CommentAuthorConflictTheory
    • CommentTimeAug 9th 2012
    • (edited Aug 11th 2012)

    In the notation below,f(0:3)=f(0)f(1)f(2)f(3)f(0:3)=f(0)f(1)f(2)f(3) represents the values of f evaluated at the integers 0 to 3 concatenated together to yield a string.

    f 0(0:3)=0000⊣3333=g 0(0:3)f_{0}(0:3) = 0000 \dashv 3333 = g_{0}(0:3) f 1(0:3)=0001⊣2333=g 1(0:3)f_{1}(0:3) = 0001 \dashv 2333 = g_{1}(0:3) f 2(0:3)=0002⊣2233=g 2(0:3)f_{2}(0:3) = 0002 \dashv 2233 = g_{2}(0:3) f 3(0:3)=0003⊣2223=g 3(0:3)f_{3}(0:3) = 0003 \dashv 2223 = g_{3}(0:3) f 4(0:3)=0011⊣1333=g 4(0:3)f_{4}(0:3) = 0011 \dashv 1333 = g_{4}(0:3) .. .. .. f 15(0:3)=0133⊣0113=g 15(0:3)f_{15}(0:3) = 0133 \dashv 0113 = g_{15}(0:3) f 16(0:3)=0222⊣0033=g 16(0:3)f_{16}(0:3) = 0222 \dashv 0033 = g_{16}(0:3) f 17(0:3)=0223⊣0023=g 17(0:3)f_{17}(0:3) = 0223 \dashv 0023 = g_{17}(0:3) f 18(0:3)=0233⊣0013=g 18(0:3)f_{18}(0:3) = 0233 \dashv 0013 = g_{18}(0:3) f 19(0:3)=0333⊣0003=g 19(0:3)f_{19}(0:3) = 0333 \dashv 0003 = g_{19}(0:3)

    From the pattern above, it appears that each left adjoint
    f k:4→4f_{k} : 4 \to 4 yields f k(1:3)3=f k(1)f k(2)f k(3)3f_{k}(1:3) 3 = f_{k}(1) f_{k}(2) f_{k}(3) 3 as a right adjoint for f n−k(0:3)f_{n-k}(0:3) where n=19n=19 is the number of left adjoints between the ordinal categories 4→44 \to 4 minus 1.

    This same pattern holds for left adjoint endofunctors between the the ordinal categories 22, 33 also, and so the pattern may be proved for left adjoint endofunctors between ordinal categories n→nn \to n by induction on n, with n=2 the base case.

    This also suggests there is a natural ordering on the adjoint pairs between ordinal categories n→nn \to n such that f k⊣g lf_{k} \dashv g_{l} iff l=kl=k in the given ordering of the family of left adjoints as above. The formula Todd derived for the number of left adjoints between two ordinal categories m→nm \to n gets large pretty quick for m and n much bigger than 4: following Toby’s suggestion, studying an appropriate abstract category of adjunctions for the case of m=nm=n and n =5,6,… might yield additional knowledge of the structure of adjoint pairs in a way that is tractable.

    • CommentRowNumber16.
    • CommentAuthorTodd_Trimble
    • CommentTimeAug 9th 2012

    A necessary and sufficient condition for f:m→nf: m \to n to be a left adjoint is that f(0)=0f(0) = 0. (This is related to the fact that the ordinal mm is the “free cocompletion” of m−1m-1 in the 2-category of posets.) Given ff such that f(0)=0f(0) = 0, let’s work out the formula for the right adjoint gg.

    There are a number of ways to think about this. One is to use the adjoint functor theorem, in its simple form for posets. Using the fact that f(i)≤jf(i) \leq j iff i≤g(j)i \leq g(j), we have the formula

    g(j)=max{i:f(i)≤j}=maxf −1({0,…,j})g(j) = \max \{i: f(i) \leq j\} = \max f^{-1}(\{0, \ldots, j\})

    (If ff is surjective, we can just write g(j)=max{i:f(i)=j}=maxf −1(j)g(j) = \max \{i: f(i) = j\} = \max f^{-1}(j).)

    But in some sense this is not a very satisfying formula (even if it is succinct), because it’s a little more computation-intensive than it should be. An alternative is to visualize an ordinal map as a string diagram, or what is more or less the same, think of the category of finite ordinals (aka the simplex category) as a monoidal category, where the monoidal product is written ++ and pictured as horizontal juxtaposition. The string diagram picture suggests how to decompose an ordinal map as a juxtaposition of pieces of the form 1 k1_k (the identity on the kk-element ordinal), m k:k→1m_k: k \to 1 for k>0k \gt 0 (there is only one such ordinal map), and u k:0→ku_k: 0 \to k (again, there is only one). We have u 0=1 0u_0 = 1_0 and m 1=1 1m_1 = 1_1. (We point out that the string diagram for u 0u_0 is empty, but for the purposes of the formula below, it is convenient to consider this case.)

    If f 1⊣g 1f_1 \dashv g_1 and f 2⊣g 2f_2 \dashv g_2, then f 1+f 2⊣g 1+g 2f_1 + f_2 \dashv g_1 + g_2. Also, one may compute 1+u k⊣m k+1⊣u k+11 + u_k \dashv m_{k+1} \dashv u_k + 1. Of course, 1 k⊣1 k1_k \dashv 1_k.

    Now, any ff such that f(0)=0f(0) = 0 can be written in the form

    v j 1+u k 1+v j 2+u k 2+…+v j n+u k nv_{j_1} + u_{k_1} + v_{j_2} + u_{k_2} + \ldots + v_{j_n} + u_{k_n}

    where the symbol ’vv’ may be either mm or 11, and we suppose j i>0j_i \gt 0 for all ii. Define the symbol v′v' by 1′=11' = 1, m′=um' = u. Then the right adjoint of ff is given by the formula

    g=v j 1−1 ′+m k 1+1+v j 2−1 ′+m k 2+1+…+v j n−1 ′+m k n+1g = v_{j_1 - 1}^' + m_{k_1 + 1} + v_{j_2 - 1}^' + m_{k_2 + 1} + \ldots + v_{j_n - 1}^' + m_{k_n + 1}

    For example, suppose f:8→7f: 8 \to 7 is, in the notation of ConflictTheory, 01144466. Write this out as a string diagram, and use this to see that

    f=1 1+u 0+m 2+u 2+m 3+u 1+m 2+u 0f = 1_1 + u_0 + m_2 + u_2 + m_3 + u_1 + m_2 + u_0

    (notice the insertions of empty diagrams). The right adjoint is accordingly

    g=1 0+m 1+u 1+m 3+u 2+m 2+u 1+m 1g = 1_0 + m_1 + u_1 + m_3 + u_2 + m_2 + u_1 + m_1

    which is the map g:7→8g: 7 \to 8 given, in ConflictTheory’s notation, by 0222557 (if I haven’t made a mistake).

    I should mention that all this is related to the observation that the simplex category carries a natural structure of monoidal 2-category, and indeed is the “walking lax idempotent monad” (to use nLab argot), where u 1u_1 the monad unit and m 2m_2 the monad multiplication.

    • CommentRowNumber17.
    • CommentAuthorConflictTheory
    • CommentTimeAug 11th 2012
    • (edited Aug 11th 2012)

    A necessary and sufficient condition for f:m→n to be a left adjoint is that f(0)=0.

    I think this may not be correct: I think the following is a counter-example.

    Let f:3→3f: 3 \to 3 be defined by f(0)=0f(0)=0, f(1)=1f(1)=1, and f(2)=0f(2)=0. Then the necessary and sufficient condition that f be a left adjoint f(i)≤j⇔i≤g(j)f(i) \leq j \Leftrightarrow i \leq g(j) for i,j=0,1,2i,j = 0,1,2 yields the following system of 9 inequalities:

    (1) $0=f(0)≤0⇔0≤g(0)0=f(0) \leq 0 \Leftrightarrow 0 \leq g(0)$

    (2) $0=f(0)≤1⇔0≤g(1)0=f(0) \leq 1 \Leftrightarrow 0 \leq g(1)$

    (3) $0=f(0)≤2⇔0≤g(2)0=f(0) \leq 2 \Leftrightarrow 0 \leq g(2)$

    (4) $1=f(1)≤0⇔1≤g(0)1=f(1) \leq 0 \Leftrightarrow 1 \leq g(0)$

    (5) $1=f(1)≤1⇔1≤g(1)1=f(1) \leq 1 \Leftrightarrow 1 \leq g(1)$

    (6) $1=f(1)≤2⇔1≤g(2)1=f(1) \leq 2 \Leftrightarrow 1 \leq g(2)$

    (7) $0=f(2)≤0⇔2≤g(0)0=f(2) \leq 0 \Leftrightarrow 2 \leq g(0)$

    (8) $0=f(2)≤1⇔2≤g(1)0=f(2) \leq 1 \Leftrightarrow 2 \leq g(1)$

    (9) $0=f(2)≤2⇔2≤g(2)0=f(2) \leq 2 \Leftrightarrow 2 \leq g(2)$

    From (4), 1=f(1)≤01=f(1) \leq 0 is false implies that 1≤g(0) 1 \leq g(0) must be false, which in turn, implies that g(0)g(0) < 11.

    On the other hand, from (7), 0=f(2)≤00=f(2) \leq 0 is true implies that 2≤g(0)2 \leq g(0) must also be true. That is, (4) implies that g(0)g(0) < 11, and (7) implies that 2≤g(0)2 \leq g(0), a contradiction.

    Thus there can exist no function g that satisfies f(i)≤j⇔i≤g(j)f(i) \leq j \Leftrightarrow i \leq g(j) for i,j=0,1,2i,j = 0,1,2 for the f defined above even though that given ff satisfies f(0)=0f(0)=0. I think the result you discovered earlier, as Toby pointed out, implies that the left adjoints from from the ordinal categories m→nm \to n are precisely the non-decreasing functions from m→nm \to n. I could have made a mistake above, please let me know if you see an obvious error in my reasoning above. Thanks for all of your guys work on this! It has been helpful to me, and I hope to you as well, in getting some concrete familiarity with adjoints.

    • CommentRowNumber18.
    • CommentAuthorConflictTheory
    • CommentTimeAug 11th 2012
    • (edited Aug 11th 2012)

    This is somewhat of an aside, but I noticed from the previous example,

    f 0(0:3)=0000⊣3333=g 0(0:3)f_{0}(0:3) = 0000 \dashv 3333 = g_{0}(0:3) f 1(0:3)=0001⊣2333=g 1(0:3)f_{1}(0:3) = 0001 \dashv 2333 = g_{1}(0:3) f 2(0:3)=0002⊣2233=g 2(0:3)f_{2}(0:3) = 0002 \dashv 2233 = g_{2}(0:3)

    That the sum of the digits of the left adjoint f 0(0:3)=0000f_{0}(0:3) = 0000 plus the digits of the right adjoint 3333=g 0(0:3)3333 = g_{0}(0:3) add up to 12 = 4*3 = cardinality of the set {0,1,2,3} times 3=the maximal element in the set {0,1,2,3}. This holds for all the adjoint pairs in this example: 0+0+0+1+2+3+3+3=12.

    Is it generally true that if f:m→m⊣g:m→mf: m \to m \dashv g: m \to m, then ∑ i=0 m−1f(i)\sum_{i=0}^{m-1}f(i) + ∑ i=0 m−1g(i)=m(m−1)\sum_{i=0}^{m-1}g(i) = m(m-1) holds true?

    • CommentRowNumber19.
    • CommentAuthorTobyBartels
    • CommentTimeAug 11th 2012

    @CT #17:

    Todd was taking for granted that ff is at least monotone (non-decreasing).

    • CommentRowNumber20.
    • CommentAuthorConflictTheory
    • CommentTimeAug 11th 2012

    Oh, okay. Thanks for the clarification Toby!

    • CommentRowNumber21.
    • CommentAuthorTodd_Trimble
    • CommentTimeAug 11th 2012
    • (edited Aug 11th 2012)

    Todd was taking for granted that f is at least monotone (non-decreasing).

    Indeed, and I do not regard my not mentioning this as some kind of oversight, for the following reason.

    Throughout this discussion, nn has been representing the ordinal {0,…,n−1}\{0, \ldots, n-1\}, regarded as a finite category (as in the subject of this thread). When we category theorists write an arrow between two categories, such as m→nm \to n, we mean a functor (at least, that’s the default meaning; in fancier contexts, it might mean for example a profunctor). A functor between posets (as categories) is the same as a monotone map.

    • CommentRowNumber22.
    • CommentAuthorConflictTheory
    • CommentTimeAug 11th 2012

    Oh, okay.

    Todd, I apologize about that: I am still a bit new at category theory, and so am still learning the language, so to speak. Thank you for taking your time to work on all of this, and for your patience to be willing to go and explain this.

    In any case, it is interesting that you mention profunctors, as Ellerman mentions those in one of his papers Adjoint Functors and Heteromorphisms, which is what got me interested in the theory of adjoint functors.

    Thanks again everyone, for your assistance and insights above and knowledge!

1 to 22 of 22

  1.