RE: Why binary products are ordered

RE: Why binary products are ordered

[S.J.Vickers]

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

Two points.

First, even in computer programming, one can lose the need for an ordering
by using what are often called "record types", so that

  <your age in years=99, your height in inches=70>

denotes the same record as

   <your height in inches=70, your age in years=99>

I don't think there's anything mysterious about this. A pair of sets can be
described as a function f: X -> 2, and we can quite happily replace 2 by any
isomorphic set (but we don't have to choose the isomorphism) such as

   M = {"your height in inches", "your age in years"}

The product of f: X -> M is then a universal solution to the problem of
finding

   g: YxM -> X  over M

and this is equivalent to the usual characterization once you have chosen
the isomorphism between M and 2.

A second, and deeper, point is that constructively there are unorderable
2-element sets, so there is a kind of binary product in which the ordering
first vs. second projection is impossible. It uses the same "record type"
construction.

An example in sheaves over the circle O is the twisted double cover M (edge
of a Mobius band). It is finite decidable set with cardinality 2. It is
isomorphic to 2 (i.e. 2xO) locally but not globally. It has no global
elements and no global total ordering. If you have a sheaf X with a map f: X
-> M, then locally it falls into two parts whose product you can take. It
can be expressed as

  Pi f = {(i,x,j,y) in MxXxX | f(x) = i and f(y) = j and j = s(i)} / ~

where s: M -> M swaps the two elements and ~ is the equivalence relation
generated by (i,x,j,y) ~ (j,y,i,x).

Globally, Pi f is the equalizer of two maps from X^M to M^M, namely f^M and
the constant identity map: so set theoretically it is the set of sections,

   {g: M -> X | g;f = Id_M}

The universal property is that for any YxM -> X over M you get a unique
corresponding Y -> Pi f.

The second description with X^M probably looks more natural to a topos
theorist, but the first one has the advantage of being geometric.
 

Steve.

RE: Why binary products are ordered

[S Vickers]

[David Benson asked me:
>This looks extremely useful...  Where might I read more about this
>formulation of limits?
>
>> The product of f: X -> M is then a universal solution to the problem of
>> finding
>> 
>>    g: YxM -> X  over M
>> 
>> and this is equivalent to the usual characterization once you have chosen
>> the isomorphism between M and 2.
>
Perhaps readers of the list can suggest sources I'd overlooked.] 


Dear David,

The underlying idea is a very broad one, namely to look for limits of
internal diagrams. You will find these described in Johnstone's "Topos
Theory" and (I think - I haven't got it to hand) Mac Lane and Moerdijk.

Suppose, working in a suitable category S (let's say a topos), you have an
internal category C. Then you can define a notion of internal diagram over
C (C-shaped diagram of S-objects) and they are the objects of an external
category S^C, another topos.

If D is another internal category in S and F: C -> D is a functor, then
there is a functor F^*: S^D -> S^C defined using pullbacks in S and it has
both right and left adjoints. In fact it defines an essential (if I
remember the right word) geometric morphism from S^C to S^D.

Now consider the situation when D is the terminal category, one object and
one morphism. S^D is just S. The the right and left adjoints of F^*
calculate internal limits and colimits of internal diagrams. This is easy
to see, since F^*(X) is just the constant diagram, X everywhere, and a
morphism (natural transformation) between an internal diagram D and F^*(X)
is just a cone or cocone over D from or to X. The adjunctions then express
exactly the universal properties of limits and colimits.

I was describing situations where C was a discrete category, so the
internal limit is an internal product.

I also considered the question of whether the construction of the internal
limit was geometric - preserved under inverse image functors of geometric
morphisms. I have written about this kind of question in my own work, for
instance "Topical Categories of Domains". (See my website,
http://mcs.open.ac.uk/sjv22 .) Geometricity in general rules out the use of
exponentiation in the topos, but exponentiation Y^X is geometric if X is
finite with decidable equality (Johnstone and Wraith, ??"Algebraic theories
in a topos"). My proposal is that the record type construction should be
seen as a solution to the problem of internal products, but that it relies
on finite decidability of the set of field names - hence it's related to
geometricity of the internal product.

In a different direction, note that internal products make sense in
categories other than toposes, even if they don't always exist. For
instance, if f: X -> Y is a continuous map of spaces, then the internal
product, if it exists, is a space of continuous sections of f. I bet that's
explored somewhere in the literature, but I don't know where.

Best regards,

Steve.

Re: Why binary products are ordered

[Nick Rossiter]

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

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

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.

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

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.

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

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/

Re: Why binary products are ordered

[zdiskin]

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

Re: Why binary products are ordered

[zdiskin]

Michael Barr <barr@barrs.org>  wrote:
> 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.
>
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

Re: Why binary products are ordered

[Dusko Pavlovic]

Hi.

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

> But woven into Charles' argument is what Bill has called the "totally
> 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

> 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

Re: Why binary products are ordered

[Michael Barr]

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:

...

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

Re: Why binary products are ordered

[Colin McLarty]

	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
that order and "left, right" most often in that order. As he puts it:

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

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


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

	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

Re: Why binary products are ordered

[Vaughan Pratt]

(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 <charles@freude.com>
>
>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

Why binary products are ordered

[Charles Wells]

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.


Charles Wells, 105 South Cedar St., Oberlin, Ohio 44074, USA.
email: charles@freude.com. 
home phone: 440 774 1926.  
professional website: http://www.cwru.edu/artsci/math/wells/home.html
personal website: http://www.oberlin.net/~cwells/index.html
NE Ohio Sacred Harp website: http://www.oberlin.net/~cwells/sh.htm