Why binary products are ordered
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
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.
(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
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
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
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
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
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
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/
Dusko Pavlovic <dusko@kestrel.edu> wrote:
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.
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.
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.
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
Colin McLarty wrote:
It comes about as a part of the initial algebra structure 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.
[snip]
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.
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?)
Also, I somehow came to think of set theory as *tree representations of abstract sets*, much like vector spaces are used for group 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.
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 plays no role in ordinary math practice.
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
Dusko Pavlovic points out that various data types representing the natural numbers by posets are useful. That is true but hardly related to tree representations in set theory. (For example, these posets are generally not "extensional" in the sense of membership trees.) When I remarked that the operation x|--> {x} has no role in mathematical practice and does not exist in categorical set theory, Dusko replied:
but didn't joyal and moerdijk actually write a book about it?
Joyal and Moerdijk wrote a book on algebraic characterization of models of ZF. They use an operation with formal properties like Peano's singleton. So I have to admit the singleton operation does figure in practice, when the "practice" is to describe ZF and related set theories. Not otherwise. When I said membership trees "obviously play no role in ordinary math practice" he replied
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
Membership trees are hardly the same as the study of large cardinals. The large cardinals I know of are all described by isomorphism invariant properties (measurable: an uncountable set k which admits a non-principle k-complete ultrafilter). So the definitions that ZF set theorists give do not rely on membership, they are already definitions in categorical set theory. As to "obvious", we might wish that everything about practice was obscure. It would free up 'debate' wonderfully. But it is obvious right now that membership trees in set theory are used only for a handful of technical theorems in the foundations of set theory. Categorical set theorists also use them, for equiconsistency results with ZF. I don't claim to *prove* they will never have any other use. Perhaps one day they will be central to work in PDEs. Perhaps one day (as Philip Johnson predicts) Bible based biology will produce far greater advances than materialist science as practiced in recent centuries. I only say such claims are arbitrary. best regards, Colin
participants (8)
-
Charles Wells -
Colin McLarty -
Dusko Pavlovic -
Michael Barr -
Nick Rossiter -
S.J.Vickers＠open.ac.uk -
Vaughan Pratt -
zdiskin