Linear--structure or property?

Linear--structure or property?

[Michael Barr]

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.

Re: Linear--structure or property?

[Fred E.J. Linton]

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.

Re: Linear--structure or property?

[Fred E.J. Linton]

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

Re: Linear--structure or property?

[David Ellerman]

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
...

Re: Linear--structure or property?

[Fred E.J. Linton]

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 ...

Re: Linear--structure or property?

[F W Lawvere]

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

Re: Linear--structure or property?

[George Janelidze]

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

Re: Linear--structure or property?

[George Janelidze]

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.

RE: Linear--structure or property?

[F W Lawvere]

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.
>
>
>
>
>
>
>
>

RE: Linear--structure or property?

[Stephen Lack]

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.

Re: Linear--structure or property?

[George Janelidze]

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.
>
>
>
>