Linear--structure or property?
Bill Lawvere uses "linear" for a category enriched over commutative semigroups. Obviously, if the category has finite products, this is a property. What about in the absence of finite products (or sums)? Could you have two (semi)ring structures on the same set with the same associative multiplication? Robin Houston's startling (to me, anyway) proof that a compact *-autonomous category with finite products is linear starts by proving that 0 = 1. Suppose the category has only binary products? Well, I have an example of one that is not linear: Lawvere's category that is the ordered set of real numbers has a compact *-autonomous structure. Tensor is + and internal hom is -. Product is inf and sum is sup, but there are no initial or terminal objects and the category is not linear.
Dear Michael, I have a trivial comment to the first paragraph of your message. You ask: "...Could you have two (semi)ring structures on the same set with the same associative multiplication?" Take any (semi)ring R with a multiplicative automorphism f that is not an additive automorphism, and transport the structure along f. For instance, both in the semiring of natural numbers and in the ring of integers, any non-identity permutation of (positive) prime numbers determines such an f. An example for students: take, say, f(2) = 3, f(3) = 2, and f(p) = p for all primes p different from 2 and 3. Then, denoting the new addition by *, we calculate (usung the fact that f coincides with its inverse) 1*1 = f(f(1)+f(1)) = f(2+2) = f(2x2) = f(2)xf(2) = 3x3 = 9. Best regards, George ----- Original Message ----- From: "Michael Barr" <mbarr@math.mcgill.ca> To: "Categories list" <categories@mta.ca> Sent: Thursday, August 10, 2006 10:14 PM Subject: categories: Linear--structure or property?
Bill Lawvere uses "linear" for a category enriched over commutative semigroups. Obviously, if the category has finite products, this is a property. What about in the absence of finite products (or sums)? Could you have two (semi)ring structures on the same set with the same associative multiplication?
Robin Houston's startling (to me, anyway) proof that a compact *-autonomous category with finite products is linear starts by proving that 0 = 1. Suppose the category has only binary products? Well, I have an example of one that is not linear: Lawvere's category that is the ordered set of real numbers has a compact *-autonomous structure. Tensor is + and internal hom is -. Product is inf and sum is sup, but there are no initial or terminal objects and the category is not linear.
It's a structure. Consider the following category C. Two objects x and y, with hom-categories C(x,x)=C(y,y)={0,1} C(y,x)={0} C(x,y)=M with composition defined so that each 1 is an identity morphism and each 0 a zero morphism, and with M an arbitrary set. Any commutative monoid structure on M makes C into a linear category. Steve. -----Original Message----- From: cat-dist@mta.ca on behalf of Michael Barr Sent: Fri 8/11/2006 6:14 AM To: Categories list Subject: categories: Linear--structure or property? Bill Lawvere uses "linear" for a category enriched over commutative semigroups. Obviously, if the category has finite products, this is a property. What about in the absence of finite products (or sums)? Could you have two (semi)ring structures on the same set with the same associative multiplication? Robin Houston's startling (to me, anyway) proof that a compact *-autonomous category with finite products is linear starts by proving that 0 = 1. Suppose the category has only binary products? Well, I have an example of one that is not linear: Lawvere's category that is the ordered set of real numbers has a compact *-autonomous structure. Tensor is + and internal hom is -. Product is inf and sum is sup, but there are no initial or terminal objects and the category is not linear.
Sorry Mike, I believe you misunderstood my definition of "Linear category". It is in my paper "Categories of Space and of Quantity" International Symposium on Structures in Mathematical Theories, San Sebastian (1990), published in the Book "The Space of Mathamtics. Philosophical, Epistemological and Historical Explorations. DeGruyter, Berlin (1992), 14-30. Namely, because "additive" was already established standard usage that included negatives, and because the importance in algebraic geometry etc. of rigs other than rings and distributive lattices had been historically underestimated, I chose the name "linear" because it would at least have an intuitive resonance with physicists and computer scientists and others who routinely apply linear algebra to positive and other contexts. Thus, the definition is simply a category with finite products and coproducts which agree (i.e. there is a zero object which permits the definition of identity matrices, which are required to be invertible). Of course this implies enrichment in additive monoids. However, the question of whether a multiplicative monoid has a unique addition is of interest. I believe it was resolved in the negative by the Tarski school of universal algebra, although I cannot recall the reference, nor whether their examples were as straightforward as Steve Lack's. In ambient categories other than abstract sets, that question has been of interest to me in particular in connection with the foundations of smooth geometry and calculus. Euler's definition of real numbers as ratios of infinitesimals leads immediately to a definition of multiplication as composition of pointed endomorphisms of an infinitesimal object T. This endomorphism monoid R of course has a zero element and hence there are two canonical injections from it into R x R and the requirement on an addition is that it be R-homogeneous and restrict to the identity along both those injections. In classical algebraic geometry, where T is coordinatized as the spectrum of the dual numbers, this addition is unique. In a forthcoming paper I try to approach that result from a conceptual standpoint, by invoking expected functorial properties of integration or differentiation. The matter still needs to be clarified. Concerning Mike's example of the real numbers as a *-autonomous category under addition, I found it useful to note, in my 1983 Minnesota Report on the existence of semi-continuous entropy functions, that the system of extended real numbers, including both positive and negative infinity, is also a closed monoidal category (even though not all objects are reflexive). There are actually two such structures, depending on which sense of the ordering one takes as the arrows of the category; the definition of addition (which is to be the tensor product) must preserve colimits in each variable (where colimits has the two possible meanings). Besides its utility in freely performing certain operations in analysis, this structure strikingly illustrates a point often made to young students: subtraction is just addition of negatives, provided one is in a group like the real numbers; however, in general the binary operation of subtraction can be merely adjoint to addition and, in fact, the condition that A is a "compact" object in a SMC for all B, A* @ B --> hom(A,B)is invertible precisely characterizes the finite real numbers. Best wishes, Bill ------------------------------------------ On Fri, 11 Aug 2006, Stephen Lack wrote:
It's a structure.
Consider the following category C. Two objects x and y, with hom-categories C(x,x)=C(y,y)={0,1} C(y,x)={0} C(x,y)=M with composition defined so that each 1 is an identity morphism and each 0 a zero morphism, and with M an arbitrary set. Any commutative monoid structure on M makes C into a linear category.
Steve.
-----Original Message----- From: cat-dist@mta.ca on behalf of Michael Barr Sent: Fri 8/11/2006 6:14 AM To: Categories list Subject: categories: Linear--structure or property?
Bill Lawvere uses "linear" for a category enriched over commutative semigroups. Obviously, if the category has finite products, this is a property. What about in the absence of finite products (or sums)? Could you have two (semi)ring structures on the same set with the same associative multiplication?
Robin Houston's startling (to me, anyway) proof that a compact *-autonomous category with finite products is linear starts by proving that 0 = 1. Suppose the category has only binary products? Well, I have an example of one that is not linear: Lawvere's category that is the ordered set of real numbers has a compact *-autonomous structure. Tensor is + and internal hom is -. Product is inf and sum is sup, but there are no initial or terminal objects and the category is not linear.
Dear Steve, It is true that constructing such examples with more than one object is even easier in a sense. However your example needs a minor correction: What is 1+1 in C(x,x) and in C(y,y)? If it is 0, them M must be a Z/2Z-module, since for every element u in M we have u+u = 1u+1u = (1+1)u = 0u = 0. If it is 1, them M must be idempotent (as before: u+u = 1u+1u = (1+1)u = 1u = u). If it is 1 in C(x,x) and 0 in C(y,y), then M becomes trivial, which destroys the example. And... why did not you and I just take the monoid {0,1}, which becomes a commutative semiring for both additions?! More generally, take any non-degenerated Boolean algebra. It has multiplication=intersection=meet, and at least two additions (symmetric difference and union=join) both good for that multiplication. George ----- Original Message ----- From: "Stephen Lack" <S.Lack@uws.edu.au> To: "Categories list" <categories@mta.ca> Sent: Friday, August 11, 2006 12:49 PM Subject: categories: RE: Linear--structure or property? It's a structure. Consider the following category C. Two objects x and y, with hom-categories C(x,x)=C(y,y)={0,1} C(y,x)={0} C(x,y)=M with composition defined so that each 1 is an identity morphism and each 0 a zero morphism, and with M an arbitrary set. Any commutative monoid structure on M makes C into a linear category. Steve. -----Original Message----- From: cat-dist@mta.ca on behalf of Michael Barr Sent: Fri 8/11/2006 6:14 AM To: Categories list Subject: categories: Linear--structure or property? Bill Lawvere uses "linear" for a category enriched over commutative semigroups. Obviously, if the category has finite products, this is a property. What about in the absence of finite products (or sums)? Could you have two (semi)ring structures on the same set with the same associative multiplication? Robin Houston's startling (to me, anyway) proof that a compact *-autonomous category with finite products is linear starts by proving that 0 = 1. Suppose the category has only binary products? Well, I have an example of one that is not linear: Lawvere's category that is the ordered set of real numbers has a compact *-autonomous structure. Tensor is + and internal hom is -. Product is inf and sum is sup, but there are no initial or terminal objects and the category is not linear.
FW: categories: Re: Linear--structure or property?Dear Florian,
1*2 = f(f(1)+f(2)) = f(1+3) = f(4) = f(2x2) = f(2)xf(2) = 3x3 = 9.
You are right, and thank you the correction (I think I thought of 3*3 = f(f(3)+f(3)) = f(2+2) =..., but does not matter of course). Dear Bill, Having two structures in {0,1} (with 1+1 = 0 and with 1+1 = 1) makes what you say about the Tarski school funny (sorry!) Best regards to all- George
Beyond simple counter examples to general statements, the Tarski school also pursued conditions on particular monoids which might imply uniqueness of a ring structure, or a definite range of ring structures. As I suggested, that open problem takes on a deeper significance if we consider it within categories of cohesion, not just within the category of abstract sets. Best wishes to all. Bill ************************************************************ On Fri, 11 Aug 2006, George Janelidze wrote:
FW: categories: Re: Linear--structure or property?Dear Florian,
1*2 = f(f(1)+f(2)) = f(1+3) = f(4) = f(2x2) = f(2)xf(2) = 3x3 = 9.
You are right, and thank you the correction (I think I thought of 3*3 = f(f(3)+f(3)) = f(2+2) =..., but does not matter of course).
Dear Bill,
Having two structures in {0,1} (with 1+1 = 0 and with 1+1 = 1) makes what you say about the Tarski school funny (sorry!)
Best regards to all-
George
George Janelidze and others answer affirmatively the question
Could you have two (semi)ring structures on the same set with the same associative multiplication?
(attributed to Mike Barr) without ever noticing that the related question, of having two (semi)ring structures on the same set, with the same addition, also has answer YES. For instance, take the additive group of 2x2 matrices with integer entries (or entries from any semiring) and notice that, apart from the usual matrix multiplication, there is also the sophomoric, or pointwise, multiplication (so called since it is generally only sophomores in the first week of their first linear algebra course who, following the analogous pointwise definition of matrix addition, would wish to multiply two matrices by multiplying their corresponding entries). Not quite sure though how this impacts the situation with more than one object. -- Fred ------ Original Message ------ Received: Fri, 11 Aug 2006 01:06:56 PM EDT From: "George Janelidze" <janelg@telkomsa.net> To: "Categories list" <categories@mta.ca> Subject: categories: Re: Linear--structure or property?
Dear Steve,
It is true that constructing such examples with more than one object is ...
When a Boolean algebra B is treated as a Boolean ring in the usual manner, the meet is the multiplication. In his little-known thesis, Herbrand noted that a BA could also be construed as a ring with the join as the multiplication (see Church's tome on logic). Gian-Carlo Rota noted that both these Boolean rings were "opposite" quotients of what he called a "valuation ring" V(B,Z_2) which carries *both* multiplications and one addition. What is usually called "Boolean duality" (e.g., DeMorgan's law) is an anti-isomorphism of the valuation ring that swaps the two multiplications and leaves addition the same. The "trick" in constructing such rings was to see that the bottom element z (representing the null set) should be a separate element than the 0 of the ring. The usual Boolean ring constructed from a BA is really the quotient of the valuation ring that identifies z and 0, i.e., V(B,Z_2)/(z). The Boolean ring noted by Herbrand is the quotient of the valuation ring that identifies the element representing the top u with 0, i.e., V(B,Z_2)/(u). Remarkably, the valuation ring construction V(L,A) works for any distributive lattice L and any commutative ring A, not just a BA B and Z_2 and the anti-isomorphism works just as well. Thus we have "Boolean duality" over arbitrary commutative rings A; it has nothing to do with 0-1 nature of Z_2. This general theory of Boolean duality was developed in a series of papers by Geissinger in Arch. Math. 1973. See Rota's book "Finite Operator Calculus" for material on valuation rings. For the opposite question of two additions and one multiplication in a semi-ring, the natural setting is the algebraic treatment of series addition a+b and parallel addition a:b = 1/((1/a)+(1/b)) (e.g., from electrical circuit theory) in what might be called a "series-parallel algebra." Every commutative group G (written multiplicatively) generates a series-parallel division algebra SP(G) (think of all series-parallel circuits of resistors that could be generated with the elements of G as the resistors). It is a "division algebra" in the sense that the SP algebra is also a multiplicative group where the inverse of any SP circuit is obtained by taking the series-parallel conjugate circuit (see any circuit theory book) with the atomic resistances from G replaced by their inverses in G. Then "taking reciprocals" is the anti-isomorphism of the SP algebra that swaps the two additions leaving multiplication the same, and it algebraically captures series-parallel duality just as the anti-isomorphisms of the valuation rings captured Boolean duality. The SP algebra SP({1}) of the trivial group is just the positive rationals Q^+ (i.e., any rational resistance can be obtained as a series-parallel circuit with unit resistances) and the anti-isomorphism that swaps the two additions is just "taking the reciprocal" r-->1/r. There is an 1892 paper by the great combinatorist Percy MacMahon published in "The Electrician" that explains the notion of a conjugate of a series-parallel circuit and shows that if each resistence is 1 (i.e., G = {1}) and the compound resistance of an SP circuit is R, then the resistance of the conjugate SP circuit is 1/R (in case your library does not carry "The Electrician" from 1892, see the Collected Papers of MacMahon). Paying attention to the duality of series and parallel addition on the positive rationals or reals gives some cute dualities. For instance, instead of saying that the geometric series 1+x+x^2+... converges to 1/(1-x) for any positive x<1, it is easier to say that 1+(1:x)+(1:x)^2+... converges to 1+x for any positive x. And dually, the parallel sum infinte series 1:(1+x):(1+x)^2:... converges to 1:x for any positive x. Both Rota's valuation rings and the series-parallel algebras are explained in two chapters of my book: "Intellectual Trespassing as a Way of Life: Essays in Philosophy, Economics, and Mathematics" (Rowman-Littlefield, 1995). Cheers, David __________________ David Ellerman Visiting Scholar University of California at Riverside Email: david@ellerman.org Webpage: www.ellerman.org View my research on my SSRN Author page: http://ssrn.com/author=294049 Now out in paperback: Helping People Help Themselves: From the World Bank to an Alternative Philosophy of Development Assistance. University of Michigan Press. 2006. For more information, see my website: www.ellerman.org . Book available at better booksellers online. -----Original Message----- From: cat-dist@mta.ca [mailto:cat-dist@mta.ca] On Behalf Of Fred E.J. Linton Sent: Sunday, September 03, 2006 2:27 AM To: Categories list Subject: categories: Re: Linear--structure or property? George Janelidze and others answer affirmatively the question
Could you have two (semi)ring structures on the same set with the same associative multiplication?
(attributed to Mike Barr) without ever noticing that the related question, of having two (semi)ring structures on the same set, with the same addition, also has answer YES. For instance, take the additive group of 2x2 matrices with integer entries (or entries from any semiring) and notice that, apart from the usual matrix multiplication, there is also the sophomoric, or pointwise, multiplication (so called since it is generally only sophomores in the first week of their first linear algebra course who, following the analogous pointwise definition of matrix addition, would wish to multiply two matrices by multiplying their corresponding entries). Not quite sure though how this impacts the situation with more than one object. -- Fred ------ Original Message ------ Received: Fri, 11 Aug 2006 01:06:56 PM EDT From: "George Janelidze" <janelg@telkomsa.net> To: "Categories list" <categories@mta.ca> Subject: categories: Re: Linear--structure or property?
Dear Steve,
It is true that constructing such examples with more than one object is ...
David Ellerman begins,
When a Boolean algebra B is treated as a Boolean ring in the usual ...
Boolean algebras actually have the additional surprise that, because their multiplication (meet) is idempotent (as well as commutative and associative), it distributes over itself ( a(bc) = (ab)(ac) ) so that one can use multiplication as a third addition candidate (the first two having been the more usual symmetric difference and join, of course). Cheers, and Happy Labor Day (in the US, anyway), -- Fred
Three items with which to follow up on my earlier note,
For instance, take the additive group of 2x2 matrices with integer entries (or entries from any semiring) and notice that, apart from the usual matrix multiplication, there is also the sophomoric, or pointwise, multiplication ...:
1. In one of the poster sessions at the recent Madrid ICM2006, Camarero, Etayo, Rovira, and Santamaria remind us that the ordinary real plane R^2 (with usual vector addition) admits at least
three distinguished real algebras ... as follows: the set {a+bi: a, b {/element} R} with i^2 = -1, +1, 0, i.e., the complex, double, and dual numbers.
(ICM2006 Abstracts, p. 42) 2. Yefim Katsov (in a telephone conversation) has pointed out that in any reasonable lattice-ordered (semi-)group, where a + (b ^ c) = (a+b) ^ (a+c) and a + (b v c) = (a+b) v (a+c), one gets two different (semi-)ring structures by using: as product, the (semi-)group composition + ; and as sum, in one case the lattice meet ^ , alternatively, the join v . 3. A many-objects version can be concocted from example 2 above by stirring it up with a variant form of Lawvere's observations about metric spaces being categories enriched over an appropriately structured closed monoidal version of the poset R+ of nonnegative real numbers ( order relation > , tensor product + , unit 0 , internal hom the positive part of b-a ). In detail, if X is a metric space with metric d, consider the ordinary category _X_ whose objects are the points of X while its homsets _X_(p, q) are given by the principal filter (in (R, </= ) ) generated by d(p, q): _X_(p, q) = { x {/element} R: x >/= d(p, q) } . Composition _X_(p, q) x _X_(q, r) can clearly be given by sending (x, y) to x+y : for identity map is always the number 0, and whenever x >/= d(p, q) and y >/= d(q, r) we must also have x+y >/= d(p, q) + d(q, r) >/= d(p, r) . Thus, arithmetic addition provides a composition rule for _X_ , and both real sup and real inf can serve as commutative semigroup structures (across which composition distributes) on the homsets. Of course no one will claim _X_ has any finite (co)products; but, anyway, here any enrichment of _X_ over semigroups is clearly an added item of structure, and not a property of _X_ . -- Fred (and pardon, please, the crude ASCII/TeX symbology) PS: Katsov has also pointed out that a marvelous little New Yorker piece of Fields Medal gossip, turning around Yau, Perelman, Hamilton, and the Poincare conjecture, can be found on the web (for those who don't take the New Yorker, or even those who do) at: http://www.newyorker.com/printables/fact/060828fa_fact2 . -- F.
participants (6)
-
David Ellerman -
F W Lawvere -
Fred E.J. Linton -
George Janelidze -
Michael Barr -
Stephen Lack