Subject: categories: Re: Why binary products are ordered

From: Vaughan Pratt <[email-masked]>
Date: Wed, 07 Feb 2001 17:17:19 -0800

(Just back from Australia, where I was able to combine my mum's 90th
birthday with the annual Australian Computer Society meeting which by
pure luck turned out to be only a 20 minute drive away, in the process
running into Bob Walters and Mike Johnson as well as some other friends
I hadn't seen for ages.  The following arrived right on Mum's birthday.)

>From: Charles Wells <[email-masked]>
>
>One might say that the ordering of binary products, with a first projection
>and a second projection, is spurious but inevitable.  
>
>The two components of a binary product must be distinguished, as Colin
>McLarty explained, but they must be allowed to be isomorphic.  The usual
>way we handle a situation like this in mathematics is to index them, in
>this case by a two-element set.  One could use {red,blue}.  As far as I
>know, in Western culture, this set has no canonical ordering, but
>nevertheless one knows that there is a redth component and a blueth
>component and they might or might not be different objects.  
>
>However, in practice the index set is {0,1}, {1,2} or {x,y} (the latter in
>analytic geometry).  All of these are canonically totally ordered in our
>culture, so inevitably binary products do have an order in practice.

I confess to some confusion as to what Charles is insisting is inevitable
here.  A binary product in C is a limit of a diagram 1+1->C (1+1 the
two-object discrete category), and 1+1 has two automorphisms.  This much
and its mathematical consequences are surely inevitable.

But woven into Charles' argument is what Bill has called the "totally
arbitrary singleton operation of Peano."  It appears implicitly at the
beginning when Charles names the projections, and then (after an indirect
reference to the automorphisms of the binary product) more explicitly
when he collects the names as a set.

Surely anyone insisting on names like 1 and 2 or red and blue for the
projections of binary product is backsliding into the ZFvN tarpit of
spurious rigidified membership.  If this backsliding really is inevitable
as Charles seems to be saying, how does one reconcile this with Bill's
view of "rigidified membership" as "mathematically spurious"?

Must mathematics accept the spurious, in this or any other case?

Vaughan

---

From: Michael Barr <[email-masked]>
Date: Thu, 8 Feb 2001 12:44:59 -0500 (EST)

As I said in an earlier post, the whole thing is a figment of the linear
way we write (and speak, for that matter).  Products are over unordered
sets and any ordering is purely irrelevant.

On Wed, 7 Feb 2001, Vaughan Pratt wrote:

...

---

From: Colin McLarty <[email-masked]>
Date: Thu, 08 Feb 2001 10:14:28

Charles Wells and Steve Vickers both made the point that, for
example, in a record of type (height in inches age, in years) you have to
be able to identify the height entry, and the age entry, but you do not
have to identify either one as the "first" entry or the "second". Yet, as
Charles points out, the usual ways of identifying the two entries all
carry a culturally-canonical ordering--as we say "one, two" usually in

>>culture, so inevitably binary products do have an order in practice.

	Then Vaughan Pratt weighs in, in his rhinocerean way. (For those
who do not read FOM, or at least Ionesco, Vaughan had a terrific post on
FOM about categorists as kind of rhinoceros, and by the end he began
transforming into one.)

>view of "rigidified membership" as "mathematically spurious"?

	I think Charles is not tarred by this pit. 

	The Peano/ZFvN idea is to say that, given 0 and 1, and some one
among all the two-element sets is actually the set {0,1}.

	Charles is merely saying that when we pick a two element set, and
name its elements, we tend to use names with specific (helpful or
spurious) connotations.

	The naming here is "local", a choice of how to talk about two objects we
assme we have. It involves no idea that the two element set has any
objective features making it the set of 0 and 1.

best, Colin

---

From: Dusko Pavlovic <[email-masked]>
Date: Sat, 10 Feb 2001 16:10:42 -0800

Hi.

I am also trying to catch up, perhaps belatedly, with the "spurious
ingredients" thread, but I am quite lost in some parts.

> arbitrary singleton operation of Peano."

To begin embarassing myself --- I am not sure what Peano's singleton operation
is. Is it the map x|-->{x}?

If it is --- why is this operation totally arbitrary, like Bill says? In
particular, why is it more arbitrary than the successor operation in arithmetic
(which Peano used)? It comes about as a part of the initial algebra structure
on Godel's cumulative hierarchy, just like the successor comes about in NNO.
Aren't all our inductive constructions based on such operations, including the
software we are using to run this conversation?

I would really appreciate help with this.

Also, I somehow came to think of set theory as *tree representations of
abstract sets*, much like vector spaces are used for group representations. Is
this wrong? It seems to me that introducing the external, "spurious" elements
(eg vectors) is the whole point of representations. And more than that, the
essence of our thinking: Isn't every metaphor, as a deviation from the abstract
view, built of spurious elements? Isn't every novel a bunch of lies, things
that never happened, put together to tell some truth? Can we really define
cartesian product without the spurious elements?

I am sure we can, but it would be good to know more precisely how to
distinguish the spurious from the authentic elements. Otherwise, we may end up
"slinging back and forth ill-defined epithets", like i am probably doing now.

With apologies, and best wishes,
-- Dusko

---

From: "zdiskin" <[email-masked]>
Date: Sun, 11 Feb 2001 11:40:37 -0800

OOPS! In my previous posting i've made some mixed-up and talked mainly about
notation for diagrams while the actual question is whether product  is
commutative (symmetric) operation in Sets. Below is a sketch of possible
solution.

First of all, product is a diagram operation and explicit presentation of
their syntax would be useful; so, let me present a bit of technicalities.

Let G be some base category (think of the category of graphs). The arity of
a diagram operation F (think of  products, push-outs...) is a G-morphism s:
S^in --> S with S the shape of the operation and S^in the input shape.

For example, for binary products, S is the graph    [x] <--p-- [u] --q-->
[y]
where [ ]'s denote nodes and arrows'  names are  written right on the
arrows,
S^in is the two-node discrete graph  [x]  [y],  and morphism s is its
embedding  into S.

A G-object C (think of a category)  is an F-algebra if for any diagram d:
S^in --> C there is a unique diagram  F^C(d): S-->C such that s;F^C(d) = d
(input data are preserved); below i'll write just F for F^C.

Well, categorically we normally have many isomorphic F(d)'s,  let's skip
this  for a while. And as for products of sets (ie, F is Prod, C is Sets),
by using names p and q that are already given in the shape, we really have a
canonical choice. Namely, for any d: [x]  [y] --> Sets with x.d=A, y.d=B, we
define
u.Prod(d) = { t: {p,q} -->  A \cup B |  p.t \in A, q.t \in B } with evident
p.Prod(d) and q.Prod(d).

F is called commutative on algebra C if  any isomorphism i: S^in --> S^in
has an isomorphic extension i+: S --> S with s;i+ = i;s  s.t. for any d:
S^in --> C,   F(i;d)  =  i+ ; F(d)

Now it is seen that Prod is commutative in Sets because any isomorphism i:
S^in --> S^in  has an evident required extension i+, i+(u) = u and i+ acts
on the arrows p,q, . exactly like i acts on their targets x,y,.. The
illusion of non-commutativity of products in Sets arises because of
disregarding the diagrammatic nature of the operation: isomorphism i on the
nodes in the shape acts on d but the corresponding i+ acting on the arrows
is not taken into consideration.

 A peculiarity of what was described above is that  names of items in the
shape are used in the definition of the operation. So, for example, the
following two shapes
[x] <-- weight -- [u] -- height --> [y]   and  [x] <-- red -- [u] -
blue -->[y]
though isomorphic yet different and determine the two different product
operations producing isomorphic yet different results from the same input.
Thus, what we usually call the product operation is  something like
operation schema parameterized by pairs of names. Then expressions like
Prod[weight:A, height:B] denote a concrete instance of the shape schema and,
simultaneously, a diagram d in Sets with
weight.codom.d = A and height.codom.d = B.

Now back to AxB vs. BxA. The writing AxB is normally unambiguous, it means
[1st:A] x [2nd:B] and  encodes
(i) the standard shape instance [x] <-- 1st -- [u] -- 2nd --> [y] and
(ii) the diagram d: [x]  [y] --> Sets,  x.d = A, y.d=B.

In contrast, the writing  BxA is really ambiguous: it may mean either
(a) [1st:B] x [2nd:A] that encodes the same standard shape instance
     [x] <-- 1st -- [u] -- 2nd --> [y] but now the diagram is x.d = B,
y.d=A;
or it may mean
(b) [2nd:A] x [1st:B] that encodes the non-standard shape instance
[x] <-- 2nd-- [u] -- 1st  --> [y] and again the diagram x.d = B, y.d=A.

It seems that  thinking naïvely-set-theoretically people tend to see in
writing BxA the case (a) and then, of course, BxA is not equal to AxB. And
thinking categorically, people tend to see in writing BxA the case (b) and
then BxA is the same as AxB. So, the problem 'ordered vs. unordered products
' is a  problem of poor notation for product operation like BxA  while the
operation itself is a *commutative*  diagram operation as defined above.
Actually it was already said in early postings but now it became more
transparent.

Finally, some speculation. It seems that parameterization of (shapes of )
operations by names, and use of these names in operation's definitions,  is
applicable to other standard categorical operations and can be considered in
a general setting. Probably,  it could be made precise by some kind of
internalization ...?

Zinovy Diskin

---

From: "zdiskin" <[email-masked]>
Date: Sat, 10 Feb 2001 17:54:58 -0800

> sets and any ordering is purely irrelevant.
It's right of course but maybe some explanation of what is meant would be
useful.

Even if we work in naive set theory, products are defined for diagrams d:
I -> Set and thus expressions
Prod(A,B,C) or AxBxC are, strictly speaking, incorrect because we don't see
diagrams. When we use such expressions we actually use the following
convention:
(i)  the source of any  diagram is an initinal fragment of natural numbers,
I={1,2,3,...n}
(ii) the very mapping d is defined by the correspondence of the natural
ordering  I={1,2,...} and  the list of sets in the expressions above in
their reading from left to right, eg, AxBxC encodes the diagram d1=A, d2=B,
d3=C.

Quite similarly, we may use colored inks for writing AxBxC... and state
another convention:
(i)'  the source of any diagram is a set of colors, I={red, yellow,
blue,...}
(ii)' the very mapping d is defined by correspondence between semantic
meaning of these labels 'red', 'yellow', .... and colors of inks with which
symbols 'A', 'B', 'C' are written, eg, A(written in yellow) x B(in greeen) x
C(in red) encodes the diagram
d: {yellow, green, red} --> Set with yellow.d=A, green.d=B, red.d =C.
Does it mean that pdoducts are colored? :)

So, back to the "problem of ordered vs. unordered products": ordering is not
more than a notational tip for encoding diagrams having nothing to do with
the construct of product as such. In applications, where we need to deal
with semantically meaningful indexes -- elements of I, the convention of
having I={1,2,..} is irrelevant and another notational tip was invented. To
designate the product of diagram d: {red, blue}-> Set with red.d=A,
blue.d=B, we write Prod(red:A, blue:B) or  (red:A) x (blue:B) or just
[red:A, blue:B] and it's really convenient.

Thus, expression AxB denotes Prod(1:A, 2:B) while BxA denotes Prod(1:B, 2:A)
which are different just becausse these are products of the *different*
diagrams.

So, heavy use of convention (i),(ii) and the corresponding notation in
classical math may be misleading (notational peculiarity is attributed to
the notion as such) and thus, as Mike Barr wrote in his early posting, is
its disadvantage. It became an *annoying*  disadvantage when you start to
work in applications (say, relational database theory) with your old habit
to consider relations as sets of ordered tuples.

================
Actually, a similar problem we have in categorical products and other
categroical operations producing multiple items and so  we need a convention
how to name/denote them. For example, having a diagram d: I--> C, we need to
agree how to denote (name)  projections. There is no such a problem with
usual operations over sets because there is a single result and we usually
denote it by the very term built with the symbol of the operation, say, 8+3.
Let's imagine now that we have a  binary operation * on integers producing
two results: their difference and product, so that 8*3=(5,24). Of course,
the latter notation is ambiguous and actually we need to write say [1st:8] *
[2nd:3]  = [1ST: 5,  2ND:24]. Thus, a really unambiguous format for writing
arity-coarity shape of the operation * is
      [1st:_] * [2nd:_] = [1ST:_ , 2ND:_ ]
where _'s denote placeholders. Well, this notation is still using, though
inesentially, some ordering flavor and so let's suppose that the two
operands of our operation are distingusihed by some meaningful (semantic)
roles they play, say, one operand is considered to be 'principal' while the
other is 'auxiliary'; as for the two results, we may use the underlying
procedures for naming them.  Then the arity-coarity shape might be written
as
      [princ:_ ]  *  [aux:_ ] = [diff:_ , prod:_ ]
and no any ordeirng used. Note, names of the results are included in the
syntax of the operation from the very beginning and not taken on the sky.
Probably, Colin McLarty wrote about the same.
=======================

After all, it seems that in this (indeed somewhat figment) debate
(initiated, i remind, by a Todd Wilson's question about comparative pluses
and minuses of the two ways of treating products w.r.t. applications) the
actual principle difference between them, that really matters for
applications, was lost, i mean not articulated explicitly and hence lost by
the applied domains part of the audience. I will sketch it for the case of
relations  because in application we normally deal with relations rather
than products.

In ST, you first define tuples (actually, as we've seen,  mappings defined
on unordered sets) and *then* a relation is a set of tuples of the
corresponding type. In CT, you *first* define a relation as a set equipped
with a jointly monic family of outgoing mappings (that is, in fact, declare
a special predicate for the corresponding diagram of arrows with common
source) and then, if you need, define a tuple as an element of that set.

The CT-way is a really abstract specification applicable in any context
where objects of interest are organized into a category (say, we may define
what is a relation between the two database schemas). In ST-way,  we have
just a particular specification, in fact, an elementwise implementation of
the categorical specification. In sofware engineering terms, one might say
that the CT-way is object-oriented (though actually it's arrow orineted)
since relation appears as a set of objects  while the ST-way is
value-oriented since relation is just a table of values.

Also, these two ways induce the two different logics. In the CT-treatment,
relations appear as new (derived) sorts to which basic sorts of other
theories can be mapped when we deal with interpretaions of theories. In
applications (say, consider the famous ER-diagrams),  this phenomenon is not
exotics and well known under the name of 'semantic relativism' (what is an
entity -- basic sort -- for one user, may be a relationship for another
user).  In the logic naturally induced by the ST-treatment (Tarsky's
first-order structures), a theory  interpretation can map a basic relation
to a derived relation but mapping a basic sort to relation (either basic or
derived) is not legitimate. An essential difference!

Zinovy Diskin

---

From: Colin McLarty <[email-masked]>
Date: Sun, 11 Feb 2001 18:24:55

>on Godel's cumulative hierarchy, just like the successor comes about in NNO.

	Well, something *like* Peano's operation occurs in that initial algebra
structure, but that is not much to the point.

	The point is: successor did not have to wait for NNOs to be defined. It
occurs throughout arithmetic for nearly as long as we have records of
systematic thought. And it is central to all uses of arithmetic today.

	The *singleton subset* idea is also very old: A geometric condition can
define a subset of points in the plane, and perhaps a singleton subset. And
singleton subsets are all over math today for the same reason.

	It is a recent idea that given any set x there is some set {x}. Bill
traces it to Peano. It plays no role in ordinary mathematical practice, and
is unnecessary in set theory. It does not exist in categorical set theory.

>(eg vectors) is the whole point of representations.

	The whole point of group representations is that each group has many of
them. The classical Lie groups are given as groups of linear
transformations in the first place. The power of representation theory is
to relate these with *other* representations of the same groups. 

	Each ZF set has exactly one membership tree. Thus the "representation"
cannot do anything like what group representations do. And obviously it
plays no role in ordinary math practice.

	I hope no one believes that singletons, or trees, or vectors are
"spurious" per se. Some uses of the ideas are "arbitrary", and some claims
about them are "spurious". 

best, Colin

---

From: Dusko Pavlovic <[email-masked]>
Date: Mon, 12 Feb 2001 20:34:37 -0800

Colin McLarty wrote:

> >It comes about as a part of the initial algebra structure

[snip]

> is unnecessary in set theory. It does not exist in categorical set theory.

but didn't joyal and moerdijk actually write a book about it? i think they call it
successor, but the standard model is x|-->{x}. (or did i mix it all up?)

> >abstract sets*, much like vector spaces are used for group
> >representations.
>
> cannot do anything like what group representations do.

i didn't say that set theory provides tree representations of ZF sets; ZF sets
*are* trees (or acyclic rooted graphs). i said that set theory provides tree
representation of *abstract* sets. think of lazy natural numbers, flat natural
numbers, finite chains, all of them different *and useful* representations of the
same abstract set.

> And obviously it

the words "obviously" and "practice" don't go together well. 20 years ago, it
seemed obvious that complexity theory was mostly an academic whim. nowadays, the
security infrastructure built upon it is a critical part of the engineering
practices, and the very life of the net. large cardinals may still find unexpected
applications, say in establishing the new tax policies =;0

all the best,
-- dusko

---

From: Nick Rossiter <[email-masked]>
Date: Tue, 13 Feb 2001 18:17:59 +0000

At 05:54 PM 2/10/01 -0800, Zinovy Diskin wrote:

>  It became an *annoying*  disadvantage when you start to

Relational database theory is actually more subtle than this.  The 
extension indeed is a set of ordered n-tuples but this is linked to an 
intension specifying attribute names and types.  The extension is 
effectively indexed by names in the intension so that ordering of columns 
is immaterial.  Since the ordering of tuples in the extension is also 
immateial, the model is very flexible. The indexing is in effect from 
another level.

>source) and then, if you need, define a tuple as an element of that set.

Cannot  such relations be better represented as pullbacks?  Limits and 
colimits then appear to emerge naturally as keys (product thereof) and 
non-keys (sums) respectively.

>value-oriented since relation is just a table of values.

CT certainly appears more powerful at handling object modelling than 
ST.  But I am not sure the relational model is simply value-oriented. The 
user view is such but the underlying theory (dependencies, normalization, 
intension-extension mapping, integrity rules) is very much arrow-based and 
hence also amenable to CT.

Regards ... Nick
http://www.cs.ncl.ac.uk/people/b.n.rossiter/home.informal/