Inevitability of ordering products

Inevitability of ordering products

[Charles Wells]

Vaughn Pratt made some valid points about my earlier remarks on the
inevitably of binary product projections being ordered.  For the most part,
I agree with him (but see below), since my (unclearly made) point was that
it is inevitable in our current mathematical culture, not that it was
mathematically inevitable.  

However, I am stuck on one point:  Sometimes one needs to refer to one of
the projections, and that involves giving the projections names.  I
mentioned "red" and "blue" as examples of names that do not introduce a
spurious ordering. But in practice, we must occasionally give names.  This
is not only for computation, either.  For example, one sometimes needs to
assume that an n-ary operation factors through one of the projections, and
then deduce consequences from that (Peter Johnstone did something like that
in his study of varieties that are ccc's).  In the proof one must give a
name to the projection it factors through.

So I argue that naming the projections is sometimes a practical necessity,
and given current mathematical habits the names are likely to have some
intrinsic (culturally intrinsic!) ordering.  But we could use red and blue.
 Or vanilla and chocolate.




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

Re: Inevitability of ordering products

[Eduardo Dubuc]

ordering is not inevitable

naming is inevitable

how do you refer to a proyection withot naming it ?

of course naming a proyection by the object it proyects is the mother of
all evil

have you delt with actions of the symetric group, say, on polynomials on
several variables   ?
There is a related (if not the same) confusion here.

what sense has the concept of unlabeled graph ?

try to put an unlabeled graph inside a computer  ?

well, unlabeled graph has to be a quotient by an equivalent relation ...


and so on ...

Re: Inevitability of ordering products

[Dusko Pavlovic]

Eduardo Dubuc wrote:

> what sense has the concept of unlabeled graph ?
>
> try to put an unlabeled graph inside a computer  ?

you mean unordered? i would implement it as an ordered graph, with an
additional involutive map on the edges, ie

        Edges <--inv-- Edges ==dom,cod==> Nodes
        dom.inv = cod
        inv.inv = id

--- which, in a way, confirms that

> well, unlabeled graph has to be a quotient by an equivalent relation ...

isn't the "ordering" of the components of a product AxB (by the names,
colors A and B), in a similar way, "factored out" by the canonical
isomorphism with BxA? isn't coherence theory the way we can always factor
out such arbitrary annotations on objects?

(SORRY i am posting too much.)

-- dusko

Re: Inevitability of ordering products

[Eduardo Dubuc]

This is concerning the mail of Dusko in reply to my mail:

> 
> Eduardo Dubuc wrote:
> 
> > what sense has the concept of unlabeled graph ?
> >
> > try to put an unlabeled graph inside a computer  ?
> 
> you mean unordered? i would implement it as an ordered graph, with an
> additional involutive map on the edges, ie
> 
>         Edges <--inv-- Edges ==dom,cod==> Nodes
>         dom.inv = cod
>         inv.inv = id
> 
> --- which, in a way, confirms that
>


yours is not an answer to my question, which I shall explain now (I
thought that it needed no explanations)

by an unlabeled graph i mean the drawing of a graph, in paper, say, or a
graph buildt in space, the skeleton of a building for example. It has
vertices and edges, and everybody knows what it is. Mathematically you
could say a symetric relation on its (finete) set of vertices. But not
quite so ...

If you have n vertices, you have n! different labeling. Each labeling
gives you a different labeled graph.

The minute you have a set (in the mathematical sense) of vertices, you
have a labeling. Namely, the elements of that set are the labels!. So,
with a symetric relation (in the mathematical sense) what you got is a
labeled  graph. Not an unlabeled graph !.

And you become well aware of this fact when you want to put a concrete
unlabeled graph (say, the skeleton of a  building) inside a computer !!

REMEMBER I rise the question on unlabeled graph related to the question
that we were discussing:

INEVITABILITY OF NAMING (IN MATHEMATICS) 
 (naming is not the same as labeling ?)  

>> well, unlabeled graph has to be a quotient by an equivalent relation 
...

I said that. It seems possible. I explain now the  ...

  Given two graphs R, S (symetric relations) on a finite set X (of 
vertices), consider the natural action of the symetric group of X on the
power set of X x X. Then, R =~ S iff they are in the same orbit. The
elements of the quotient set are the unlabeled graphs.

    e.d.

Re: Unlabeled graphs

[Charles Wells]

This is in reply to Eduardo Dubuc (quoted after the reply).  I have a major
point and a minor point.

Minor point: The phrase "labeled graph" usually allows different nodes to have
the same label.  Eduardo clearly intends, however, that the labeling be
injective.  (In the usual sense there are n^n labels, not n!).  This is only a
matter of terminology.  My answer refers to injective labeling as he intended. 
(Better terminology for his purposes would be to call them NAMED nodes.)

Major point:  Any way you store an unlabeled graph in a computer will involve a
memory location for each node, and so introduces a labeling, indeed a total
ordering, on the nodes.  However, a high level language with pointers such as C
can be used to describe the structure without any names being given
explicitly.  The structure head will point to a node, which will have a pointer
to another node, etc, and the program text will not mention all the nodes
directly.  For the purpose of computing with the graph, you can have the
program traverse the nodes without naming them.  This is a commonly used
technique.  (There will have to be pointer structures for the edges with
pointers to the two nodes each is incident on.)  When the program is compiled,
the nodes are made to correspond to memory locations but the locations are
hidden from the user.  It seems to me that this preserves the psychology of a
drawing with no labels on the nodes.

You can respond that each node has an implicit label, essentially an integer,
which is the number of pointers you have to dereference to get to the node. 
But that is just like saying that in the drawing of the graph on a piece of
paper, each node has an implicit label, namely its location on the paper.  If
you allow implicit labels like this the drawing has them and so does the graph
in the computer.  If you don't allow them then neither has labels.

Let me forestall someone bringing up a red herring:  The coordinates of the
node on the paper depend on an arbitrary choice of coordinate system, unlike
the number of pointers you need to get to the stored node in the computer. 
This argument, if someone makes it, is based on a misreading of what I said.  I
said each node is labeled by its location on the paper.  I didn't say the
coordinates of the location.  The location itself is the label.  (But how do
you talk about it?  You POINT to it!)

--Charles Wells


>by an unlabeled graph i mean the drawing of a graph, in paper, say, or a
>graph buildt in space, the skeleton of a building for example. It has
>vertices and edges, and everybody knows what it is. Mathematically you
>could say a symetric relation on its (finete) set of vertices. But not
>quite so ...
>
>If you have n vertices, you have n! different labeling. Each labeling
>gives you a different labeled graph.
>
>The minute you have a set (in the mathematical sense) of vertices, you
>have a labeling. Namely, the elements of that set are the labels!. So,
>with a symetric relation (in the mathematical sense) what you got is a
>labeled  graph. Not an unlabeled graph !.
>
>And you become well aware of this fact when you want to put a concrete
>unlabeled graph (say, the skeleton of a  building) inside a computer !!
>
>REMEMBER I rise the question on unlabeled graph related to the question
>that we were discussing:
>
>INEVITABILITY OF NAMING (IN MATHEMATICS) 
> (naming is not the same as labeling ?)  
>
>>> well, unlabeled graph has to be a quotient by an equivalent relation 
>...
>
>I said that. It seems possible. I explain now the  ...
>
>  Given two graphs R, S (symetric relations) on a finite set X (of 
>vertices), consider the natural action of the symetric group of X on the
>power set of X x X. Then, R =~ S iff they are in the same orbit. The
>elements of the quotient set are the unlabeled graphs.
>
>    e.d.
>
>
>
>
>
>



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

Re: Unlabeled graphs

[Eduardo Dubuc]

this is in reply to Charles Wells, I quote in between  ' " '

" Major point:  Any way you store an unlabeled graph in a computer will
involve a memory location for each node, and so introduces a labeling,
indeed a total ordering, on the nodes.  However, a high level language
with pointers such as C can be used to describe the structure without any
names being given explicitly.  The structure head will point to a node,
which will have a pointer
to another node, etc, and the program text will not mention all the nodes
directly.  For the purpose of computing with the graph, you can have the
program traverse the nodes without naming them.  This is a commonly used
technique.  (There will have to be pointer structures for the edges with
pointers to the two nodes each is incident on.)  When the program is
compiled, the nodes are made to correspond to memory locations but the
locations are hidden from the user.  It seems to me that this preserves
the psychology of a drawing with no labels on the nodes. "

quite wright, i agree that the technique you describe "preserves the
psychology of a drawing with no labels on the nodes. ".

 i had no thought about the pointer technique  !!!

but then, try to put an unlabeled graph in a computer using assembler
languge  !

is what i should have said !

" You can respond that each node has an implicit label, essentially an
integer, which is the number of pointers you have to dereference to get to
the node. But that is just like saying that in the drawing of the graph on
a piece of paper, each node has an implicit label, namely its location on
the paper. If you allow implicit labels like this the drawing has them and
so does the graph in the computer.  If you don't allow them then neither
has labels.

Let me forestall someone bringing up a red herring:  The coordinates of
the node on the paper depend on an arbitrary choice of coordinate system,
unlike the number of pointers you need to get to the stored node in the
computer. This argument, if someone makes it, is based on a misreading of
what I said.  I said each node is labeled by its location on the paper.  I
didn't say the coordinates of the location.  The location itself is the
label. "

the final conclusion of your arguing : " The location itself is the label" 
means that there is no such a thing as an unlabeled graph.

interesting . . . 

but what about permutation of the labels ? 

en fin !  we should perhaps leave this problem to the philosophers, if
they would be able to understand it 

e.d.