7
$\begingroup$

In his answer link to the question whether $a|m$ and $a+1|m$ implies $a(a+1)|m$, Bill Dubuque takes a detour to derive the equality $$ \gcd(a,b)=ab/\mathrm{lcm}(a,b) $$ from the universal property of $\gcd$ and $\mathrm{lcm}$. Since they have a universal property, the natural question is: is $\gcd$ the right adjoint of something and is $\mathrm{lcm}$ the left adjoint of something?


A note about the answers below

Originally, the question was meant as: does the functor $\gcd:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ has a left adjoint. This was answered by Qiaochu Yuan by observing that $\gcd$ is a categorical product.

Hurkyl had interpreted my question as: does the functor $\gcd(-,b):\mathbb{N}\to\mathbb{N}$ have a left adjoint for each $b\in\mathbb{N}$? This is not the case, but interestingly the functor $\mathrm{lcm}(-,b):\mathbb{N}\to\mathbb{N}$ has a left adjoint. This shows that if we reverse the ordering of divisibility, the category $\mathbb{N}$ becomes cartesian closed.

  • 2
    I don't have time to give a good answer now, but to get you started google "Yoneda's Lemma" and posets, etc, which, e.g. yields an introduction here by Tott Trimble: [Toward Stone Duality: Posets and Meets](http://topologicalmusings.wordpress.com/2008/04/02/toward-stone-duality-posets-and-meets/). I'd be very grateful if others could post here links on this and related topics, since it would be useful to have an answer to link to when related questions touch on these *universal* ideas.2012-05-21
  • 1
    Note: readers may also find of interest the [universal view of the *floor* function](http://math.stackexchange.com/a/147832) (which I suspect inspired this question). See also [this question](http://math.stackexchange.com/questions/149376) on Yoneda's Lemma.2012-05-24
  • 2
    In one sentence: gcd is supremum in poset $(\mathbb N, |)$, and suprema in posets are products in categories, and products are limits, and limits are adjoints to diagonal functors.2012-06-02

2 Answers 2

7

Well, as far as category theory goes, it is a categorical product (and $\text{lcm}$ is a categorical coproduct) in the category whose objects are the natural numbers where there is a single arrow $a \to b$ if $a | b$.

All limits and colimits are adjoints. If $C$ is a category and $J$ a diagram category, then the diagonal inclusion $C \to C^J$ sending every object $c \in C$ to the constant functor $J \to C$ with value $c$ potentially has a left and right adjoint, and these are the limit and colimitcolimit and limit respectively when they exist.

  • 3
    It is indeed the other way around. The mnemonic is, right adjoints preserve limits – so the formation of colimits can't be a right adjoint, since those don't usually commute with limits!2012-05-21
3

Here's an explicit left adjoint $L$ to lcm in the poset of natural numbers ordered by divisibility.

I define $L(a,b)$ in terms of its valuation at each prime: $$ v_p(L(a,b)) = \begin{cases} 0 & v_p(a) \leq v_p(b) \\ v_p(a) & v_p(b) < v_p(a) \end{cases}$$

To verify it is a left adjoint:

  • $L(a,b) \mid c$
  • iff $\forall p: v_p(a) \leq v_p(b) \vee v_p(a) \leq v_p(c)$
  • iff $a \mid \mathop{\mathrm{lcm}}(b,c)$

It's sort of a weird function, and I don't think I've seen it before, but there it is!

I computed it by fixing $a,b$ and looking at the requirement

  • $L(a,b) \mid c$ if and only if $a \mid \mathop{\mathrm{lcm}}(b,c)$

I picked the smallest value for $c$ that made the right hand side true, which gives an upper bound on $L(a,b)$. Then, I checked that actually defining that upper bound to be $L(a,b)$ works.

There isn't a right adjoint to $\mathop{\mathrm{gcd}}$; my intuition attributes that to the fact that there is no upper bound on things. The proof is short: the condition is

  • $\mathop{\mathrm{gcd}}(a,b) \mid c$ if and only if $a \mid R(b,c)$

For a fixed $b,c$, we can pick arbitrarily large values of $a$ relatively prime to $b$, which makes the left hand side true. This contradicts the fact that $R(b,c)$ would be an upper bound on the set of values for $a$, and so $R(b,c)$ cannot exist.

  • 0
    I think I don't fully understand the functions $v_p$ and how you construct $L$ in terms of it. So you proved that $\mathrm{lcm}(-,b)$ has a left adjoint; in other words, that the dual of $(\mathbb{N},|)$ is cartesian closed?2012-05-22
  • 0
    Is $L(a,b)=\mathrm{lcm}(a,b)/b$?2012-05-22
  • 1
    $v_p(x)$ is the number of times the prime $p$ divides $x$. So, $v_2(18) = 1$ and $v_3(18) = 2$. A sample value of $L$ is $L(12,18) = 4$. It has this value because $2$ is the only prime that divides $12$ more than it does $18$, and it does so twice.2012-05-22
  • 0
    Ok, I get it. But I believe that the assertion in the second item should read: iff $\forall p: v_p(a)\leq v_p(b)\vee v_p(a)\leq v_p(c)$.2012-05-22
  • 0
    I've made the fix.2012-05-22
  • 0
    I still think that it should be disjunction, because in the conjunction case you'd get $L(a,b)=1$. Or I'm still misunderstanding it...2012-05-22
  • 0
    Whoops, I had missed that I made *two* typos! :(2012-05-22
  • 0
    @Hurkyl Is there a standard name for $v_p$ ?2012-05-23
  • 0
    @magma: $v_p(x)$ is the "valuation of $x$ at $p$".2012-05-23
  • 0
    @Hurkyl Thank you. In wikipedia I only found http://en.wikipedia.org/wiki/Valuation_%28algebra%29 . Does it relate to your valuation function?2012-05-23
  • 0
    @magma Yes: it's the "P-adic valuation". But really, you should think of it in terms of "the exponent of $p$ in the factorization of $x$" -- one point of the notion of valuation is to generalize this simpler notion.2012-05-23