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
I guess that the point I was trying to make in my post was missed in my telegraphic submission. I'll try to make what I was trying to say clearer. If you take the "representable functor" definition of a product of a object A with an object B, you say that an object P together with an ordered pair of arrows (p_A:P--->A,p_B:P-->B) is a product of A with B if for all objects T , the mapping Hom(T,P)--->Hom(T,A)xHom(T,B), defined by f |---> (p_A.f,p_B.f) is a bijection. This makes it clear that P together with (p_A,p_B) represents the product of A with B and P together with (p_B,p_A) represents the product B with A and that these are not representations of the same functor but that there is a natural isomorphism of such an object with itself which "interchanges the two projections". Note also that this distinction remains even for a product of A with itself which leads a pr_1 and pr_2 notation for the two "projections". Now, as with all such bijections, one can eliminate all reference to sets of morphisms by a "for all x there exists a unique y such that..." statement which here becomes: for all ordered pairs of arrows of the form (x:T--->A,y:T--->B) , there exists a unique arrow f:T--->P, such that (p_A.x,p_B.y)=(x,y), and the distinction made in in set theory between AxB and BxA," that they are not equal, but there is a 'canonical' bijection between them", is perfectly maintained entirely within category theory... or is it? The use of the ordered pair term "(x,y)" still appears in the replacement first order statement, and if the only way that one can use "ordered pair" is through von Neumann's clever but rather grotesque (x,y)={x,{x,y}}, one has to pull in "Peano's entirely spurious singletons" , as Bill Lawvere referred to them. Now if the purpose of an "underlying logic" us to "codify by making explicit the normal habits of reasoning that all mathematicians will accept" and that "an object P and arrows p_A:P--->A and p_B:P--->B" is equivalent to "an object P and arrows p_B:P-->B and p_A:P-->A", or more starkly, the logical equivalence of,"p_A and p_B" and "p_B and p_A". Then there would seem to be no way that a purely first order category theory could make the distinctions that we teach in every elementary math course about the distinction between (x,y) and (y,x), unless we appeal to informal aspects of everyday language where "and" is sometimes commutative and sometimes not, and thus in this case rely on "everybody's having met (x,y) long before they have ever heard of a 'category' ". Apparently this subtlety has surfaced before: In the beginning of Bourbaki's Theorie des Ensembles,\footnote{which, remember, was written by "working mathematicians" who did not consider themselves "professional logicians or professional set-theorists", and may even have had some contempt for them (among others) if we are to judge from a certain fronts piece photograph inserted by Andre Weil into the Fascicule de Resultats.} they introduced as "specific signs", in addition to those of equality and membership, another sign of weight 2, \couple xy, ultimately written as (x,y) together with the Axiom (A3) : (for all x)(for all y)(for all x')(for all y' ) (x,y)=(x',y') implies x=x' and y=y'. They then define "z is an ordered pair (couple)" by "(there exists x)(there exists y)(z=(x,y))", which then gives (x,y) its first and second projections because of the way that "there exists " is constructed (using their "\tau operator"). The existence of the cartesian product of the set A with the set B then follows, as usual, as the set of ordered pairs,since the presence of (x,y) allows them to describe formal "relations" R|x,y| as properties of the ordered pair z=(x,y). Only later do they observe, in an exercise, that the little von Neumann nest of singletons has the property of the axiom A3, but they use this only to show that \couple xy together with A3 is relatively consistent with their other axioms for set theory. It is clear, however, that \couple xy and A3 could have been introduced immediately after they had done quantification and long before any of the axioms for \epsilon were introduced. But, after all, they were trying to use their "Theory of Sets" as a foundation for all of mathematics, so most people have considered this whole business of adding \couple xy and A3 at so fundamental a level an eccentric and superfluous curiosity, and it has all but been completely forgotten. My point is not to pull category theorists back into the intricacies of Bourbaki 's treatment of logic, but rather to point out that the idea of an ordered pair has at least once before been considered a notion that properly belongs somewhere anterior to set theory and can be used in category theory without fear of the latter suffering from any "set-theoretic contamination". In any case, to my eyes, the use of "lists and addresses" with their attendant ordering seems to be pretty fundamental in computer science. Amusingly, Grothendieck "pushed" representability in the forlorn hope that it would convince working mathematicians that they did not have to give up their Cantorian Paradise of " set-theory" in order to make use of the unique insights provided by "category theory", but then had to (re-)invent "universes" when the old paradoxes of set-theory and the category of all sets, all groups, etc. carpingly resurfaced. Bill Lawvere, in contrast, noticed that when the working axioms of set-theory were rephrased in purely "category-theoretic" terms, that they, amazingly, all became "first order" statements , thereby raising the question of an entirely new way to look at foundational questions in which the pesky membership paradoxes could not arise nor even be formally expressible. He, in contrast to Grothendieck, "pushed" the much more radical move of, effectively, "banning all use of Hom-sets" and thereby made the divide crystal clear.
On Sun, 11 Feb 2001, John Duskin wrote:
Bill Lawvere, in contrast, noticed that when the working axioms of set-theory were rephrased in purely "category-theoretic" terms, that they, amazingly, all became "first order" statements , thereby raising the question of an entirely new way to look at foundational questions in which the pesky membership paradoxes could not arise nor even be formally expressible. He, in contrast to Grothendieck, "pushed" the much more radical move of, effectively, "banning all use of Hom-sets" and thereby made the divide crystal clear.
Can someone give a reference to an elaboration of this point of view? Since I am not a real category theorist and have at best a weak understanding of foundations, something written for the mainstream mathematician would be even better. Thanks in advance. Jim Borger
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
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.
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
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.
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 ...
participants (5)
-
Charles Wells -
Dusko Pavlovic -
Eduardo Dubuc -
James Borger -
John Duskin