Talk:Finitary relation/Archive 1

Untitled

I think this article should be moved to relation (mathematics), for the same reason for which the ill-named mathematical group was moved to group (mathematics). Michael Hardy 20:12, 1 Mar 2004 (UTC)

• Agree. Isomorphic 20:15, 1 Mar 2004 (UTC)
  • Done. -- Walt Pohl 18:20, 16 Mar 2004 (UTC)

Inconsistent

First a relation is defined as a tuple with its graph as the last element. Then later the relation is used in a way its graph could be used in the latex formulas. -MarSch 15:25, 20 Apr 2005 (UTC)

The "inconsistency" has to do with the fact that, as mentioned in the article, a relation is often identified with its graph. I've edited the article so as to minimize the inconsistency in the article. But, unfortunately, there is an inherent inconsistentcy in standard usage. Paul August ☎ 20:47, Apr 20, 2005 (UTC)

Varied & sundried articles on relations & relatives

JA: I'm presently working on co-ordinating numerous articles and sub-articles that have to do with the logical and mathematical aspects of relations, relative terms, predicates, propositions, boolean functions, and so on. Not for the fun of it, but because intelligent discussion of these topics has simply become impossible of late, especially between the communities of mathematical, philosophical, and programming folks. The big cloud at the beginning of talking about any given thing is whether it's a "signlike" thing or an "objectlike" thing. For instance, "predicate" -- signoid or objectoid!? -- take your pick, Gimli. Here I've found that the strategic discipline used in computer science is very beneficial for cross-cultural communication, namely, to append the word "name" or "expression" to any substantive or adjective that you intend to be taken as a name or expression. For example, we can use the short form "predicate" for the formal object, and use the longer forms "predicate name", "predicate expression", "predicate formula", etc. for the semiotic-syntactic entity that denotes the corresponding object. So I'll adopt that as clarifying principle to begin. Jon Awbrey 15:36, 16 January 2006 (UTC)

JA: Bad example. We could do that for "predicate", but I will try to avoid applying the rule there, mostly just for historical reasons. A better example would be "proposition", where we can let that term denote the abstract, formal, or mathematical object, even in some contexts identifying it as a boolean-valued function, while using "propositional expression" for any signlike thing that denotes the proposition proper.

JA: I am concerned about the accessibility and utility axes of encyclopedia articles, by which I mean making useful ideas useful to readers who might have a use for them. In this connection, one of the other expositional problems that I would like to mull over for a while is the distinction between the relation and the graph of the relation. On one hand I understand the importance of getting this distinction across one way or another -- on the other hand, I know from a lot of adverse experience that a definition that begins "a k-place relation is a (k+1)-tuple ..." will have already lost 90% of the readership that is most in need of understanding what a k-place relation really is. What is wanted here is something like the arrow notation for functions f : X -> Y, that subtly forces us to regard the source X and the target Y as inherent parts of what f is. (I use to use a concept of "relational arrow", but that again is for later.) So I will think a bit on how to ease the exposition here. Jon Awbrey 18:08, 16 January 2006 (UTC)

Ramping up to relations in general

JA: I'll be trying to write several levels of exposition that ramp up in stages to a moderately general concept of relations. I'm not sure I can get to "relations without arity" in this article, but will keep it in the back of my mind as I go. I made a few cosmetic changes, subbing k for n mostly just because I always save n for some sort of ambient dimension rather than just the number of variables in a particular predicate form. I would also use the term "finitary" instead of "k-ary" if nobody thinks anybody would take it as meaning "computable". Jon Awbrey 06:26, 17 January 2006 (UTC)

JA: Well, off to dreamland for now, but tomorrow I will try to tackle that protean polymorphism issue, as I think that is one of the things that is most likely to drive a novice to despair. Jon Awbrey 06:40, 17 January 2006 (UTC)

JA: I will also make an effort to remove the reference to k's and n's from the thrust of the definition, relegating it to a parameter (that may or may not be defined for a given relation of the most general sort). This may take a few tries. Jon Awbrey 13:36, 17 January 2006 (UTC)

Which concept nests in which?

If relations have frames, then a binary relation is a specific case of the more general concept of k-ary relation. However, if a relation is identified with its graph, then k-ary relations are special cases of binary relations (in fact, a (k+1)-ary relation is a species of k-ary relation...) I am myself an unregenerate advocate of simplicity: the relation is its graph. Adding the frame to the relation as a component is analogous to sticking type-labels to things: objects should not have to carry type labels around with them, as the context in which they appear should provide cues sufficient to tell what type we are currently assigning to them. This is not a proposal to change the article (the usage described is unfortunately common), just a philosophical comment... Randall Holmes 23:46, 20 January 2006 (UTC)

• JA: Randall, before we get started, look at the history, and where I came in, so that I don't have to take undeserved blame and/or credit for things that I did not contribute:

• Relation 22 December 2005

Did I mention you? I was simply talking about the general difference between the two styles of defining a relation. I guess the "frame" terminology is yours (?), but the general practice of incorporating domains of relations as components is just that -- a general (though not universal) practice. No reference to any individual was intended. I have already figured out from the function (mathematics) war that it is difficult to tell when someone advocates a position and when they are simply trying to edit something already present into a better form... Randall Holmes 00:24, 23 January 2006 (UTC)

I now note (as I say at more length below) that your definition is actually apparently nonstandard in a way I had not noticed. It is not the same concept (or to be precise, not the same set theoretical implementation of the concept) that was defined in the original article! Randall Holmes 04:20, 23 January 2006 (UTC)

• JA: In casual discussion, I always speak of a k-adic relation as being something of the form L c X_1 x ... x X_k, and never run into trouble myself -- not until somebody asks a question that's symptomatic of the fact that something I took for granted in so writing is really not understood in so reading. And this is the factor of context, frame, setting, or whatchamacallit that is reflected in specifying the cartesian product X_1 x ... x X_k.

• JA: And if we make that context explicit, what we get is the definition of a k-adic relation as a pair (L, X_1 x ... x X_k) where L c X_1 x ... x X_k. (Notice that the relation itself is not yet name in this formulation.) That is probably how I'd express it if I started from scratch today. (As it happens, this is actually a notion that I explored during one of my decade-ent Wanderjahren all through the 80's under the heading of "relational arrows" and "intermediate categories", but that's an arrow of another quiver.)

• JA: I was also tempted to call the subset the "figure" and the sequence of domains, or product over it the "ground", making the relation a "gestalt, I guess, but that would have imposed too radical a novelty on what's in place, plus reversing the F and the G, so I resisted that impulse. Like it or not "graph" is standard, and "frame" is pretty close to standard usage, as in "frame of reference". So I think that's about as good as I can do, as far as non-demolition continuity of improvement goes.

I actually like your terminology; but I prefer to identify relations with their graphs. Randall Holmes 00:24, 23 January 2006 (UTC)

The rewrite of this article by Jon Awbrey

Hi Jon. Thank you for your work on that article. Now, I am not an expert on the thing, but from reading what you wrote, it looks to me that the current version of the article is so much more complicated and hard to follow than the original version before your rewrite.

I would suggest the article flow in a different manner. First one defines what a relation is. In spite of all the text you wrote in that article, and all those definitions, a relation is no big deal, it is just a subset of a cartezian product. So that could be made clear.

Then, one could give a very simple example. After that, you could enter into all those complications, which are frame, arity, adicity, and all that.

In short, I would suggest you keep the old introduction, then give examples, then write all that which is the current introduction you wrote. Wonder what people think. Oleg Alexandrov (talk) 17:00, 22 January 2006 (UTC)

• JA: Hi Oleg. I am still working on this article and will take your comments into account over the next few days, weeks? This is a fundamental and important topic, and it will be incumbent on us to make it both accurate and accessible to whomever might have a need for clarity about the concept. In the meantime, please review the entire history of the article and especially what's gone before on the discussion page, as some of what you say — for instance, "a relation is no big deal, it is just a subset of a cartezian product" — seems to reflect a lack of appreciation for both the substantive and the expository problems at hand. Time for lunch, so I'll comment more fully later in the day. Jon Awbrey 17:12, 22 January 2006 (UTC)

Yeah, but you don't need to start with the complicated stuff right away, that's my point. Start simple, give example, move on to complications later. :) Oleg Alexandrov (talk) 17:20, 22 January 2006 (UTC)

And more

• JA: I get too confused by trying to follow 1-sided conversations at user talk pages, so I copy your remarks here.

• OA: You wrote at talk:relation (mathematics):
• JA: I'm presently working on co-ordinating numerous articles and sub-articles that have to do with the logical and mathematical aspects of relations, relative terms, predicates, propositions, boolean functions, and so on. Not for the fun of it, but because intelligent discussion of these topics has simply become impossible of late, especially between the communities of mathematical, philosophical, and programming folks.

• OA: Well, I would suggest you don't rush. Contributions are always welcome of course, but I would like to say that from my experience grand schemes of things usually fail, especially if undertaken by somewhat new users. That is, maybe some caution, slowing the pace, and lot of discussion may be in order. :) Oleg Alexandrov (talk) 17:04, 22 January 2006 (UTC)

• JA: I'm in no rush if you aren't. Though born again but lately as a WikiPeon, I am an old veteran of Relations. Jon Awbrey 17:28, 22 January 2006 (UTC)

OA: Great sir! Oleg Alexandrov (talk) 17:37, 22 January 2006 (UTC)

Discussion of Relation 2006

• JA: Here is where I came in:

Relation (mathematics) — 22 December 2005 In mathematics, an n-ary relation (or n-place relation or often simply relation) is a generalization of binary relations such as "=" and "<" which occur in statements such as "5 < 6" or "2 + 2 = 4". It is also the fundamental notion in the relational model for databases. Definition A relation over the sets X1, ..., Xn is an (n + 1)-tuple R=(X1, ..., Xn, G(R)) where G(R) is a subset of X1 × ... × Xn (the Cartesian product of these sets). If X=X1=X2=...=Xn, R is simply called a relation over X. G(R) is called the graph of R and, similar to the case of binary relations, R is often identified with its graph. An n-ary predicate is a truth-valued function of n variables.

Jon Awbrey 23:23, 22 January 2006 (UTC)

• JA: Despite its deceptive simplicity, the first sentence is nothing like a definition of "relation" in mathematics, but merely states one of the things of which a relation in mathematics is supposed to be a generalization. Without some hint of the intended direction of generalization, since there are always many directions of possible generalization for any significant concept, that remark provides very little service to the reader. It's more like a "build your own definition" (BYOD) pot-luck party kit". The multitude of use-mention confusions in the examples given next pretty much guarantee that only a reader who already understands what a relation is better than the writer of this "definition" would be able to negotiate what the writer — no doubt a distributed committee of writers — was trying to say in the first place. Jon Awbrey 23:44, 22 January 2006 (UTC)

As I said in other places, I find this definition perfectly acceptable. Next thing to do is give an example of a nontrivial relation. After that, you may delve into all those complications you now put front and center in the introduction. Oleg Alexandrov (talk) 01:34, 23 January 2006 (UTC)

• JA: Are we still talking about that first sentence? That you are personally content with it does not suffice as a criterion of definition. I can think of no mathematical source that would even dignify it as a definition in form, much less a definition of relations in general. It is at best a "description", something that one might say is true of relations, but a vague description at that, and simply not definitive of their substance. If you have some sort of stylistic preference for beginning WP articles that way, fine, I guess, but please do not misinform readers or distort what is a universal mathematical practice by calling it a definition. That may be okay for "defining" Doctor Seuss or Doctor Who, but it does not qualify as a definition in mathematics. Jon Awbrey 04:02, 23 January 2006 (UTC)

• I think that the text in the box above is much better than the current text. The opening sentence is not a definition, but it does reveal what kind of thing a relation is supposed to be. The second paragraph gives the exact mathematical definition (not my favorite one, but a commonly accepted one). In the current version, one has to read rather farther before getting the whole story in any form. Also, the definition given here is nonstandard (and the text is muddy enough that I didn't really see it until now, though I have looked at it before): the first component of the k-ary relation is here said to be the cartesian product of its domains rather than the k-tuple of its domains, and this is not the way it is usually done. This, at least, is probably not acceptable, any more than it would be accepable for me to follow my preference and stipulate that the relation is its graph, period. [I could change my mind about this if given concrete references to works which define relation this way] Randall Holmes 04:15, 23 January 2006 (UTC)

It is very encouraging to start an article with an informal description. This is a general purpose encyclopedia, so let's keep things simple. Good reads are by the way the math style manual and Wikipedia:Make technical articles accessible. Oleg Alexandrov (talk) 04:46, 23 January 2006 (UTC)

• JA: I am perfectly happy starting an article with an informal description, so long as you don't, by commission or omission, mislead the reader by advertising it as something else. My current version, as of 2 minutes ago, begins with an informal wedge that advises the reader of its nature as such. The main problem with the article as I found it on or about the solstice last year was neither the informal level of the introduction nor the sophistication of the bolded definition, where only the bold would be emboldened to go — it was simply that there was no way of getting from one to the other, no escalator between them, as it were. I know very well the sort of glazed eye that would turn away from a definition that begins "a k-ary relation is a (k+1)-tuple ...", going away with only what was in that first paragraph as somehow a sufficient idea of "what's a relation". That is the problem that I've been working on — perfect success is no doubt unrealistic to expect, but I will keep at it a bit longer. Jon Awbrey 05:14, 23 January 2006 (UTC)

The definition using the cartesian product has a technical defect: the whole purpose of adding extra components over and above the graph is to be able to extract the domains from the relation, and with the definition using the cartesian product of the domains, one cannot determine the domains if one of them happens to be empty. This is a weird limiting case, true, but the best definitions also work in weird limiting cases. Randall Holmes 05:25, 23 January 2006 (UTC)

• JA: The relation is defined as L = (F(L), G(L)), so there is no problem about extracting the domains from the relation, since the relation L determines F(L). Jon Awbrey 05:54, 23 January 2006 (UTC)

Evidence that the old definition is still dominant

I've been doing web searches on the definition of relation and the definition of n-ary relation. It appears that I'm being too diffident about my preference. With the exception of this article in Wikipedia, the dominant definition of a relation from A to B on the web is simply "subset of $A\times B$; I have yet to find a definition with the additional adornment of domain and codomain other than the one in this article. Similarly, the web consensus definition of n-ary relation with domains A_i is "subset of the cartesian product of the A_i's". I will keep looking, and I'm sure I'll find definitions adorned with domain and codomain, but this definition is a technical refinement (motivated by category theory originally, I believe) and could perhaps better be presented as a technical refinement... Randall Holmes 05:48, 23 January 2006 (UTC)

• JA: I have already commented on this particular style of loose talk, so please see above. I talk loosely, too, at times, so what? And we've already seen with respect to the Funk Mat mess what reduces to a "Who needs WP when we already have Webster" argument.

• It's not loose talk. It's sometimes necessary in the context of set theory. Look at a clean set of axioms for Von Neumann-Bernays-Gödel set theory without choice, in which the axiom of replacement uses a function rather than a property as in ZF. (I'll need to fix that article.) Arthur Rubin | (talk) 06:16, 23 January 2006 (UTC)

• It is as a matter of hard historical fact the original and perhaps still the dominant formal definition of relation. It is not "loose talk". The definition adorned with domain and codomain is a relative novelty. I'm well aware that it is getting more and more common (for reasons which I consider misguided, but that in itself shouldn't affect what appears in the encyclopedia); but evidence that the older definition remains dominant is of interest. Randall Holmes 13:26, 23 January 2006 (UTC)

Discussion of Relation by a Logician User:Arthur Rubin

This is where I came in.

Relation (mathematics) — 20 January 2005 A relation is a mathematical object of a very general type, the generality of which is best approached in several stages, as will be carried out below. The basic idea, however, is to generalize the concept of a binary relation, such as the binary relation of 'equality' that is denoted by the sign "=" in a statement like "5 + 7 = 12" or the binary relation of 'order' that is denoted by the sign "<" in a statement like "5 < 12". In order to approach the mathematical definition of a relation, it is useful to introduce a few preliminary notions that can serve as stepping stones to the general idea. A relation in mathematics is defined as an object that has its existence as such within a definite context or setting. It is literally the case that to change this setting is to change the relation that is being defined. The particular type of context that is needed here is formalized as an encompasing collection from which the elements of the relation in question are chosen. A relation L is defined by specifying two mathematical objects as its constituent parts: The first part is called the frame of L, written frame(L) or F(L). The second part is called the graph of L, written graph(L) or G(L). In the special case of a finitary relation, for concreteness a k-place relation, the concepts of frame and graph are defined as follows: The frame of L is specified by giving a sequence of k sets, X1,…, Xk, called the domains of the relation L, and taking the frame of L to be their set-theoretic product or cartesian product F(L) = X1 × … × Xk. The graph of L is given by specifying a subset of this cartesian product, and taking the graph of L to be this subset, G(L) ⊆ F(L) = X1 × … × Xk. Strictly speaking, then, the relation L consists of a couple of things, L = (F(L), G(L)), but it is customary in loose speech to use the single name L in a systematically equivocal fashion, taking it to denote either the couple L = (F(L), G(L)) or the graph G(L). There is usually no confusion about this so long as the frame of the relation can be gathered from context.

I, too think think the version of 22 December is better. To avoid edit conflicts with JA, may I propose yet another alternate version of the introduction, although I'm not happy with the first paragraph, based on the version of 20 January referred to above.

A relation is a mathematical object of a very general type, the generality of which is best approached in several stages, as will be carried out below. The basic idea, however, is to generalize the concept of a binary relation, such as the binary relation of 'equality' that is denoted by the sign "=" in a statement like "5 + 7 = 12" or the binary relation of 'order' that is denoted by the sign "<" in a statement like "5 < 12". In it's most abstract sense, a k-ary relation (where k is a positive integer) on sets X1, …, Xk represents a property that may or may not hold between elements x1 of X1, …, xk of Xk. For a more precise definition, it is useful to introduce a few preliminary notions. A relation L is defined by specifying two mathematical objects as its constituent parts: The first part is called the frame of L, written frame(L) or F(L). The second part is called the graph of L, written graph(L) or G(L), which is an arbitrary subset of the product domain, constructed from the frame. Comment I can define a finitary relation without using the concept of function, but for an infinitary relation, the concept of function without a frame is required, or more advanced set theory than normally used to construct the frame of the domain function. I'll provide a formal definition of a framed relation using an unframed function, and we'll see whether there is any way of saving it, later. The frame of L is specified by a function X from an arbitrary set A (called the -arity of the the relation), which, for any α in A, chooses a set Xα, called a domain. The product domain is the formal product of the domains; the collection of all functions f on A such that, for all α in A, f(α) is in Xα. In the special case of a finitary relation, for concreteness a k-place relation, the concepts of frame and product domain are defined as follows: The frame of L is specified by giving a sequence of k sets, X1,…, Xk, called the domains of the relation L. The product domain is their set-theoretic product or cartesian product F(L) = X1 × … × Xk. Strictly speaking, then, the relation L consists of a couple of things, L = (F(L), G(L)), but it is customary in loose speech to use the single name L in a systematically equivocal fashion, taking it to denote either the couple L = (F(L), G(L)) or the graph G(L). There is usually no confusion about this so long as the frame of the relation can be gathered from context.

Infinite arity relations, Relations without arity, etc.

• JA: Really folks, this is not a game of aleph-one-upmanship. I am not trying to impress anyone. I am trying to provide the reader with a workable, moderately general and powerful concept of relations. I am quite familiar with these supersized sorts of generalizations, and I have taken pains that my treatment leaves the space open to them, but without distracting the novice reader with their mention at the outset. Later, Dude. Jon Awbrey 06:14, 23 January 2006 (UTC)

• Your definition is wrong. The frame is not the product domain, but the sequence of domains. Arthur Rubin | (talk) 06:19, 23 January 2006 (UTC)

• JA: If you take the time to read the revision history and the play-by-play commentary that I maintained on the talk page when I started this -- does anybody ever do that, I wonder? -- you will see that I began by defining the frame as the sequence of domains, but put it aside for the current purpose simply because it adds an extra complication that impedes the reader at this point in the game. I just don't think that it's helpful to raise the AC spectre at this point, for the current ends. Jon Awbrey 06:30, 23 January 2006 (UTC)

• I'm willing to defer the definition for infinitary operations to the body of the article, provided that you accept the fact that the frame is the sequence of domains, rather than the product of the domains. Arthur Rubin | (talk) 06:24, 23 January 2006 (UTC)

• The issue is not AC. If one of the domains is empty, it is impossible to recover the domains from your form of the frame. Randall Holmes 13:23, 23 January 2006 (UTC)

• Further, the definition "a relation is a set of ordered pairs" is not "loose talk". It is the exact definition of relation which has been dominant for most of the century, and which a web search on the quoted string "a relation is" (for example) suggests is still dominant. I am a mathematicial logician and set theorist; I generally know when I am talking loosely. Randall Holmes 13:23, 23 January 2006 (UTC)

Try the web searches "a relation is a set of ordered pairs" versus "a relation is a tuple" or "a relation is a triple". The results are instructive (and I have tried various variations). Then go read mathematical sources (I'm sufficiently interested to do a library search in QA today). I think at the very least the unadorned definition should be given equal time (as I do in function (set theory). Randall Holmes 13:32, 23 January 2006 (UTC)

a concrete example of the error in Awbrey's definition

Under Awbrey's definition, the unique relation with first domain A, second domain the empty set, and third domain C is exactly the same object as the unique relation with first domain A, second domain B, and third domain the empty set, because $A\times \emptyset \times C=A\times B\times \emptyset$: the frames of these two relations are the same set (and they both have the empty graph). Thus it is impossible to determine the domains of these relations from Awbrey's definition. The whole point of this kind of definition is that it should be possible to extract the domains from the relation. So Awbrey's definition is an unsatisfactory middle ground between the correct "category-theoretic" definition (which will draw all distinctions of this kind) and the classical definition (which would of course identify these empty relations but also makes many other identifications). If there is to be a frame at all, it must be the tuple of the domains, not their cartesian product. Randall Holmes 14:48, 23 January 2006 (UTC)

Logic & Rhetoric

• JA: Ladies & Gentlemen of De Jure, I know that it's difficult to balance the complementary claims of logic and rhetoric, where I always invoke the latter in its classical good sense of 'forms of discussion that are considerate toward their interpreters', but we have to maintain an equanimous perspective in this work. If you can tell me a good reason why we should bewilder the reader at this early point with punctilios about cartesian products over empty or infinite sequences of proper classes with possibly empty sets among those sequences, then I'm perfectly happy to listen to your reasons. But frankly some oracles are talking out of both sides of their mouths in this regard, quibbling about the very mention of sets in one place and quibbling about the slighting of proper classes and trifling borderline cases in another. Jon Awbrey 14:56, 23 January 2006 (UTC)

Actual mathematical errors should be avoided (we don't need to discuss the reasons for using the tuple of domains instead of the cartesian product of domains, we just need to use the tuple -- if we are to use a "frame" at all). I think that the definition of the infinitary product should be deferred to the body of the article (late), and I was the one who introduced proper classes, and I was convinced by the other members of the jury that this should be moved to the body of the article and not mentioned in the intro. Randall Holmes 15:12, 23 January 2006 (UTC)

• JA: Things like the empty algebra, empty geometry, empty graph, empty group, ad nullum infinitum, all got their 15 minutes of fame at the outset of every graduate math class — no, not that kind of class — that I ever took, and there is actually a notorious paper by these two notables: Harary, F. and Read, R. "Is the Null Graph a Pointless Concept?", Graphs and Combinatorics Conference, George Washington University, Springer-Verlag, New York, 1973. So what say you all if we simply deploy the usual hedge and stipulate "nonempty" at the appropriate loco loci? Jon Awbrey

• RH: I do not understand what the problem is with replacing the cartesian product of the domains with the tuple and never saying anything about the limiting case in the article: it is just that we then know that the definition has full generality. There is no particular advantage of the cartesian product as a "frame" over the tuple of domains that I can see (of course I am biased since I regard adding a frame at all as almost pure loss). Randall Holmes 17:16, 23 January 2006 (UTC)

• JA: This is naturally what I wrote write out of the box:

Relation (mathematics) — 17 December 2005 A relation $L$ is defined by specifying two mathematical objects as its constituent parts: The first part is called the frame of $L$, written $frame\,(L)$ or $F(L).$ The second part is called the graph of $L$, written $graph\,(L)$ or $G(L).$ In the special case of a finitary relation, for concreteness a k-place relation, the concepts of its frame and its graph are defined as follows: The frame of $L$ is specified by giving a sequence of $k$ sets, $X_{1},\ldots ,X_{k}$, called the domains of the relation $L,$ with the understanding that their set-theoretic or cartesian product $X_{1}\times \ldots \times X_{k}$is to be taken. Under these circumstances, then, a reference to the frame of $L$ can mean either the sequence of sets or their cartesian product, since it's the same information for all practical purposes in this context.

• JA: The reason that I revised this to use the product rather than the sequence was simply that the first version put a couple of distracting rhetorical kinks in discussion that I judged to be more impediment to first time readers than they were worth. There is a limit to how far a complex subject can be simplified, of course, but I'm accustomed to stepwise refinement, and we can always add yet another lamina later.

"loose talk"

In this note, I give concrete examples of "loose talk", taken from discrete math texts (I've seen examples on web sites while doing my recent survey, too). It is loose talk to define a relation as a set of ordered pairs, define the domain as the set of first coordinates of elements of the relation, define the range as the set of second coordinates of the relation, define a function as a special case of relation in the usual way, and then say that a function is surjective if it maps onto the whole of its range. It is also loose talk to define a relation as a tuple (A,B,G) and then identify xRy with "(x,y) is an element of R". This does not make it loose talk to define a relation as a set of ordered pairs: the way I deal with this in discrete math class, when students are given the simple definition of relation and function and the (now wrong) definition of "surjective", is to point out both possible solutions: I say that one can (but I don't) deal with this by defining a function as a triple containing its domain and intended range (I do not say "codomain"; it is never in the book), but one also can (as I do) fix the problem by saying "onto B" rather than simply "onto": one defines "surjective function from A to B rather than "surjective function". This works without the baroque complication of the structure of relations and functions entailed by the "category-theoretic definition".

An additional comment: I have never seen an undergraduate discrete math book actually get this completely right, in either style. This is annoying, because it isn't really that hard.

There is a powerful philosophical reason to avoid the category theoretical definition. Mathematical definitions should have as few obviously artificial features as possible. In the definition of relation as a set of ordered pairs, the only artificial feature is the detail of the definition of ordered pair (which can be ignored: it is as it were encapsulated). Consider the definition of function as conditioned by these two definitions of relation, and the definition of function application:

• a function is a set of ordered pairs no two of which have the same first coordinate.

versus

• a function is an ordered triple whose third coordinate is a set of ordered pairs all of which have first coordinate in the first coordinate of the function, second coordinate in the second coordinate of the function, and in which no two first coordinates of elements are the same.

and

• f(x), where f is a function, is the unique y (if there is one) such that (x,y) belongs to f

versus

• f(x), where f is a function, is the unique y (if there is one) such that (x,y) belongs to the third coordinate of f.

The complication of the definition of "surjective" in the classical approach is much cheaper in terms of philosophical (or even pedagogical) bother than the complication of the definition of every relation and function in the category theoretical approach. Randall Holmes 15:09, 23 January 2006 (UTC)

Epigraphs

• JA: The following is what is generally called an "epigraph":

	All rising to Great Place is by a Winding Staire
	Francis Bacon, Essays, Civil and Moral (1625)

• JA: It is hardly "inappropriate", but to the contrary quite aptly telegraphs one of the themes that is more formally developed in the text. It is customary to employ such epigraphs even in the most severe of mathematical treatises, even especially in the most severe of mathematical treatises, to relieve the very severity thereof. Jon Awbrey 17:06, 23 January 2006 (UTC)

• RH: an epigraph is a personal reflection on the content (an authorial touch) and an encyclopedia article is impersonal. Randall Holmes 17:24, 23 January 2006 (UTC)

• JA: Not of necessity purely personal, as any reading of semi-literate math lit amply demonstates. There's a clear and apt logical relationship between the epigraph and the more severe issues of the text. I see nothing about writing encyclopedia articles per se that dictates being dull. Jon Awbrey 18:18, 23 January 2006 (UTC)

There is a difference between a mathematical treatise or a textbook (where epigrams are appropriate) and an encyclopedia article. They are written with different purposes, and in different styles. An encyclopedia is a reference work, it is not primarily intended to be didactic. Paul August ☎ 22:01, 24 January 2006 (UTC)

Epitaphs

• JA: If by non-didactic you mean you do not intend anybody to learn much from reading your articles, then what I have seen in my first month here tells me that you are at great risk of a smashing success. But I read all those fine sentiments at the Math Project page about making math more accessible, and I just wonder what that really means in practice, if not something that would dare to be didactic by any word. Maybe you don't see the contradiction lurking in your system there, but I doubt if I can be the only onlooker who does. Jon Awbrey 22:58, 24 January 2006 (UTC)

Well maybe I'm all wet about how all this should work, and maybe I'm going to hell in a hand basket, but I hope not ;-) Yes, of course I want people to be able to learn from reading these articles, and yes of course I want mathematics to be accessible. But the fact remains that we are still writing an encyclopedia not a textbook. A frequent problem that new editors have is that while that may have considerable expertise in the subject matter, they have (not surprisingly) little experience in encyclopedia writing style. You might want to consider if it is possible that through lack of experience (I'm assuming you haven't written for an encyclopedia before) you might not be aproaching the article in the most appropriate way. You do think that that there is a difference between encyclopedic writing and textbook writing, don't you? How would you describe it? Paul August ☎ 00:20, 25 January 2006 (UTC)

the continuing error

The definition is now not wrong in the sense of mathematical error, but wrong in the sense that it is not the definition anyone uses. This makes it inappropriate as an encyclopedia definition. This definition may have some merits (I can even see some); but it should not be the main definition in an encyclopedia article. Evidence that this is anyone's official definition of relation (in print) is required for this to stand. Randall Holmes 18:30, 23 January 2006 (UTC)

Results of literature search

Looking at books in our library, in all subjects (going down the shelf and looking for set-theoretical preliminaries sections, if any) I found the following distribution. (And I did skew against old books): Seventy-five percent give the old definition (a relation is a set of ordered pairs, and a function likewise); of the remaining twenty-five percent, some just make vague cautionary noises, some define the graph of a relation or function and do not say what a relation or function actually is, and a few give the category theoretic definition (only one gives it explicitly in my sample). I may continue this through some more shelves (to make sure there isn't a prejudice determined by which branches of mathematics I went through) but this, along with web surveys, strongly suggests that the dominant definition is "a relation is a set of ordered pairs". An encyclopedia is not a vehicle for reform of mathematics: it should report what the definition of a concept actually is. The dominant definition is the classical, simple one, at least from the evidence I can see. The category-theoretic definition has a significant following and should be explained -- after the simpler one (which is also easier to explain!) is given. Randall Holmes 22:11, 23 January 2006 (UTC)

My current (draft) thinking

One can look at my current draft if one is interested. Randall Holmes 02:28, 24 January 2006 (UTC)

Relation (mathematics)

I will eventually edit out the cartesian product frame and keep editing. I would rather that you do it. Please listen to Rubin and myself; this definition is wrong. Further, space must be given to what is in fact the dominant definition, even though you do not like it (a relation is a set of ordered pairs) [hint: this is called neutral point of view]. (Added: even in terms of category theory, your definition is wrong: one does not want to exclude the empty set from the category of sets and functions (or the category of sets and relations), where it plays a significant role). Randall Holmes 00:11, 24 January 2006 (UTC)

Take a look at my current draft. Notice that (whatever I have said in discussions about the relative merits of the two definitions) I cover them neutrally. I present the one that I actually prefer earlier not because I prefer it but because it is (1) simpler and (2) is actually the commonest definition. Randall Holmes 02:35, 24 January 2006 (UTC)

• JA: [ad hom deleted] Jon Awbrey 12:34, 26 January 2006 (UTC)

• JA: I apologize for the pique in what I wrote, but there is something in the substance that I want you (and others) to understand. I will work on that a while and try again later in the day. Jon Awbrey 11:40, 24 January 2006 (UTC)

I am rather more widely educated than you think (I am not going to learn anything from your article that I do not already know). I also have to watch my own postings lest some personal annoyance creep in; I will not take personal offense and I also apologize if I have given any. But you must remember that this is a mathematics article, not a computer science nor a philosophy article. Moreover, you do appear to be attempting to impose a special POV of your own, and in the long run this simply won't work. Randall Holmes 16:52, 24 January 2006 (UTC)

Further, I observe that the formal definition of relation that you give is correct (for the "category-theoretic form") and does not agree with the definition you give in the intro. Further, you say in the formal definition that you are recapitulating what is in the intro -- but you haven't. You really need to change the intro to agree with the formal definition; I don't understand why this is such a sticking point (those who have trouble with abstractions will not find the cartesian product any friendlier than the sequence of domains). You must in addition give a full and much less dismissive place to the view which identifies the relation with its graph -- or I will. Randall Holmes 16:52, 24 January 2006 (UTC)

• JA: I've already said that the front-end version is the way it is for pedagogical-rhetorical reasons, as I started the other way and found myself slouching forward on 3 feet rather than running on 2 -- Shades of the Sphynx! Except for the scruples about null factors, it's the same information, and I already know a better way to handle those exceptions, as it's something that arises in real-life database practice all the time, there under the heading of "missing values". But the best way to handle that is in terms of what is actually a more general concept than a relation, to wit, a so-dubbed "relational complex", dubbed-so by analogy with a "simplicial complex" (q.v.) But it's become too much of a distraction to mention out of order all of the things that you are simply not foreseeing, since these talk pages are not really set up for interactive discussion, what with the edit conflicts and all. So try to have some patience. Jon Awbrey 17:16, 24 January 2006 (UTC)

This is not the place for a discussion of better implementations of mathematical concepts; it is a place for a discussion of the implementations which are actually in use. (in later sections of the article one could introduce possible variations). The actual definitions in use are Definitions I and II as in my sandbox article. These can be introduced briefly (and introducing I first actually helps to introduce II, since the object introduced in I is a component of the object introduced in II). Randall Holmes 06:08, 25 January 2006 (UTC)

Example !!!!!!!!!!!!

Things are looking up for the article. But come on people, there's got to be a simple example somewhere! :) And the intro is too big now, I moved the heading up a bit for that. Ideally, there would be the intro, then a short def, then an example, then the more serious definitions. How's that? Oleg Alexandrov (talk) 05:06, 24 January 2006 (UTC)

• JA: So who's in a rush, now!? Really, Oleg, there's only so many hours in a day. Sufficient unto the complexity of the subject is the introduction thereof. I am sweating blood here because this is such a low plate in the global architectonics of logic and mathematics both. But there's a very delicate balance between article adequacy and article accessibility -- we've got cheer-leaders stumping for inaccessible cardinals or some team of that stripe, and we've got boo-leaders grousing because it's not the story of Gödel-Lockes the way they heard it as a child. Examples? -- I got a gadshillion of em. Gimme time. Jon Awbrey 05:26, 24 January 2006 (UTC)

You have no idea what my motivations are. These remarks are offensive. Randall Holmes 17:28, 24 January 2006 (UTC)

• JA: Sorry for lack of clarity, but I had you in with the cheerleaders for higher cardinals. I was not speculating on the motives there, and you are correct that I should not do that for either side, but I was merely describing what you were arguing for at one point. Jon Awbrey 15:45, 26 January 2006 (UTC)

• JA: And I'm going to put my epigraph back, because I think that folks really need to muse on the wisdom of it. Difficult ascents simply must be approached in multiple stages. Jon Awbrey 05:30, 24 January 2006 (UTC)

• JA: Oleg and All: This article is key to many doors. It needs to have the right heft and shape to it. As to length, I think that it's best to let it develop a while and then think about what to do with the excess. There are already a number of spinoff stubs that have been prepared to take up the slack and to refine some of the many-splendored aspects of the subject in their own rights. So please hold your horses on that. It will work out in time. Jon Awbrey 12:14, 24 January 2006 (UTC)

corrected the definition of the frame

I have dealt with one of my non-negotiable points (I corrected the definition of the frame). Now negotiations might be opened on the other question: the definition of a relation which identifies it with its graph MUST be given respectful consideration -- and this is not covered by saying that in loose talk we can identify them. There is a rigorous, long-attested (in fact, still dominant) approach under which the relation really is "just" a subset of the cartesian product (admittedly, there are careless usages associated with this approach, which should be highlighted, as I do in function (set theory) and in my sandbox article). This must be said, up front where it can be seen. I suggest, again, looking at the article in my sandbox to see how this can be done (though I don't insist on using my writing, which admittedly can get convoluted). Randall Holmes 17:19, 24 January 2006 (UTC)

Sources

• JA: Randall, If you have questions about sources, then ask them on the talk page. Jon Awbrey 17:32, 24 January 2006 (UTC)

No, I know what is a common usage and what is an eccentric one out of left field. Give references to justify this usage or it does not appear. It certainly should not appear first. Randall Holmes 17:40, 24 January 2006 (UTC)

• JA: Take a number and sit down. I'm trying to work on Examples today, in accordance with a prior request. It's not all that important at this point in the text, but merely introduces in passing a bit of useful language, quite handy since the days of DeMorgan and Peirce, that has the added benefit of making sense for the aritiless case that some folks are so fond of, whereas "tuple" is slightly more forced. Jon Awbrey 17:54, 24 January 2006 (UTC)

Please stop using condescending language. You have already given personal offense with your remarks to Alexandrov. This article is not yours, and it is not going to end up looking exactly the way you want it. Please listen. Randall Holmes 18:04, 24 January 2006 (UTC)

A cheeky but honest opinion

The was little indication in the lay-intro that a n-place relation, unlike a function with n arguments, maps only to the values TRUE and FALSE. I would imagine that the formal definition is more concrete in its extensional form, however in this case the concept is somewhat obscured from the layman, like myself. The comparison and the contrast with the concept of a function is not brought clearly to the fore.

If I am wrong, then please set me right - but clarification would be most enlightening. Oh and feel free to edit this away.

;-DanielB

Seconded - it would be very nice if the introduction could make it clear that a relation defines a property that either is or isn't true. I came to this page looking to clarify the use of the term 'unary relation', and had to delve quite deeply to confirm that I had that right idea. —Preceding unsigned comment added by 81.98.250.250 (talk) 12:00, 30 October 2007 (UTC)

I have requested intervention

I copy postings I have recently made to Oleg Alexandrov.

Relation (mathematics)

Dear Oleg,

I would not say that things are looking up for the relation (mathematics) article. The actual situation is that I (and I think Arthur Rubin, though I can't speak for him) are reluctant to start an edit war like the recent one in function (mathematics). But I will start one shortly if Awbrey does not listen to us. Please read the discussion. The definition of relation given in the intro is incorrect and does not agree with the formal definition given subsequently (which is correct for one style). Respectful consideration must be given to the definition which identifies the relation with its graph, which remains the dominant definition of this concept (and which is also simpler and so should be given first). For content rather than style (it is a draft and it needs examples and certainly some rewriting) see my User: Randall Holmes/Sandbox/relation (mathematics), in which both styles of definition are discussed from a neutral point of view. Randall Holmes 17:00, 24 January 2006 (UTC)

I request mediation on relation (mathematics)

Dear Oleg,

I request mediation on relation (mathematics). Jon Awbrey [...cut out severe language...RH] needs to listen to others, and he needs to be disabused of the idea that he can impose a program of his on the whole field of relations and related entities. Randall Holmes 17:48, 24 January 2006 (UTC)

I suggest going back to the version of 22 December 2005, supported by the current set of references, though. The additions to the technical discussion seem to me to be of little value to the exposition. Charles Matthews 19:07, 24 January 2006 (UTC)

I am amenable to that, though I would like a slight rephrase to indicate that some mathematicians really do identify the relation with its graph (it is not just a facon de parler). Randall Holmes 19:59, 24 January 2006 (UTC)

Sure - I meant only that that old text seems a better jumping-off point than the current text. Charles Matthews 20:10, 24 January 2006 (UTC)

My preference would be to return to the Dec 22 version, and to add some decent baby examples, of which there are presently none, i.e. the kind of things one sees in a first course on "discrete mathematics". The current revision is a bit weird. Sorry, Jon, I think your edits complicate the topic unecessarily. Dmharvey 21:40, 24 January 2006 (UTC)

And I stick with my comment at #The rewrite of this article by Jon Awbrey, several sections above, which agrees with what Charles and Dmharvey say. Oleg Alexandrov (talk) 01:46, 25 January 2006 (UTC)

JA: Dear Oleg, For the record, I did nothing to change the substance of the definition that was already present in this article on 22 December 2005. I repeat once again that I am not the one seeking to modify that definition. After reading that definition already in place and spending three days getting accustomed to it, I realized that it really did express the concept of relation that is most commonly used in mathematics. And anyone who actually takes the time to read it will see that it does not say that a relation is just a subset of a cartesian product. What I did realize is that the audience that I was at that time meaning to refer to a standard definition of mathematical relations would simply not be able to make use of it without doing something to make it more accessible to them. What I tried to do was nothing more than a bit of conceptual chunking and explanation of the more formidable parts of the definition that was there. If I did not succeed, no biggie, that is hardly a new experience, but I did give it a good faith try. Being asked to add to add examples, I promptly set about writing up examples, and immediately got heckled for needing several sittings to write them up. Jon Awbrey 03:44, 25 January 2006 (UTC)

As I said before, I am willing to return to something close to the text of 22 Dec (exactly to that, to begin with -- it would be an improvement). I stick to my assertion that a search of definitions found on the web, in books, and for that matter a poll of people I stop in the halls in the math department finds that most mathematicians define a relation as a set of ordered pairs. A strong minority define it in the way given in the article. I don't believe that the 22 Dec version would have to be rephrased at too much length to give a reasonable (brief) account of both definitions. This would still involve more space being given to the more complicated definition because it takes longer to explain :-) Randall Holmes 06:02, 25 January 2006 (UTC)

Examples?

Awbrey's new examples section does not give any examples! (It brings in a class of examples but doesn't exhibit one of them.) I don't think that the particular philosophical musings appearing in this section actually belong in an encyclopedia article on this subject. Randall Holmes 20:07, 24 January 2006 (UTC)

Literature on relations

Poizat (2000)

• 1. Poizat, B., A Course in Model Theory: An Introduction to Contemporary Mathematical Logic, Moses Klein (trans.), Springer-Verlag, New York, NY, 2000.

• If E is a set and m a positive integer, we call a subset R of E^m an m-ary relation with universe E. If the m-tuple ${\vec {a}}$ = (a₁, …, a_m) in E belongs to R, we say that it satisfies the relation R; otherwise, ${\vec {a}}$ does not satisfy R. The integer m is called the arity of the relation. (Poizat, p. 1).

• JA: This is definition of m-ary relation with universe E, and not a definition of m-ary relation. Jon Awbrey 04:34, 25 January 2006 (UTC)

Chang & Keisler (1973)

• 2. Chang, C.C., and Keisler, H.J., Model Theory, North-Holland, Amsterdam, Netherlands, 1973.

• An n-ary relation over X is a subset of Xⁿ, and a function is a binary many-one relation. (Chang & Keisler, p. 494).

• JA: This is a definition of n-ary relation over X, and not a definition of n-ary relation. Jon Awbrey 05:20, 25 January 2006 (UTC)

How do you imagine that this is a problem for me? Note that if X is a subset of Y, all relations with universe X are also relations with universe Y under this definition. I have no problem with "relation on X" as a subtype of "relation" in general (in fact, of course, being sane, I know that such subconcepts of general concepts are important). Relations with the same graph are identified under the definitions you cite here no matter what universe they are considered under. I myself might start a definition of binary relation with the sentence "A binary relation from A to B is a subset of $A\times B$". This is perfectly consistent with the definition "A binary relation (unqualified) is a set of ordered pairs". Think about it. (In CS terms, types do not have to be disjoint). Randall Holmes 06:28, 25 January 2006 (UTC)

Styazhkin (1969) on De Morgan

• 3. Styazhkin, N.I., History of Mathematical Logic from Leibniz to Peano, MIT Press, Cambridge, MA, 1969.

• De Morgan's algebra of relations included the following six fundamental operations:

1. $MN'\,$ (the logical sum of the relations M and N);
2. $MN\,$ (the logical product of these relations);
3. $n\,$ (the operation of obtaining the complementary relation to N; literally not-N; De Morgan called n the contrary relation);
4. $N^{-1}\,$ (the operation of obtaining the converse relation or the converse of N);
5. $M)\!(N$ (the operation of generating the relative sum of the relations M and N);
6. $M(N)\,$ (the operation of generating the relative product of the relations M and N or the "composition" of those relations). (Styazhkin, p. 165).

• JA: The complement of a relation (no. 3) makes no sense if the relation is taken out of the context of a product domain. Jon Awbrey 06:45, 25 January 2006 (UTC)

De Morgan was working before modern set theory, so this is an entirely anachronistic objection. One specifies one's product domain in a given context and uses the relative complement with respect to the product domain. Again, how do you imagine that this is a problem for me? I have already remarked in published text on Wikipedia that I recognize that some concepts must be relativized to an intended domain if this is not incorporated into the definition of relation: one must say "onto Y" rather than "onto", for example (and Cieselski in a current "set theory for mathematicians" book makes exactly the same point). It's also not true that the complement makes no sense, necessarily; some of us work in NBG or Morse-Kelley set theory. Moreover, since my preferred set theory NFU has a universal set, I really have no problem with complements of relations at all :-) Randall Holmes 06:43, 25 January 2006 (UTC)

This is a dangerous argument: should I then appeal to Boole and Venn to support the position that every set A must actually have the structure (A,V), where V is the "intended universe", so that we can support the complement operation on such "framed sets"? This takes us back to type theory, and mathematicians have rejected type theory as the foundation of mathematics (and this is one of my reasons for (personally) rejecting Definition II: it amounts to using the theory of functions of Church's simple type theory in the context of untyped set theory: why?). [not to say that I don't like type theory; but everything in its place]

Are you aware that I work in alternative set theory and automated theorem proving? I think about nonstandard implementations of mathematical concepts all the time. [Look at my home page. Consider the implementation of "function" described in the slides for the talk titled "Mathematics in Three Types".] My motivation is not that the definitions you are presenting are not ones I'm used to; I have principled reasons for supporting particular definitions. But I'm not even acting as an advocate for definitions because I like them; I'm advocating presenting the definitions in use; both of them. I am entirely willing to discuss the pitfalls (of both) too. This is called "neutral point of view". Randall Holmes 06:50, 25 January 2006 (UTC)

You might enjoy the application of relation algebra to the finite axiomatization of NFU in my book. (This is a sincere invitation -- and it carries a very strong hint). Randall Holmes 06:52, 25 January 2006 (UTC)

Ullman (1980)

• 4. Ullman, J.D., Principles of Database Systems, Computer Science Press, Rockville, MD, 1980.

3. The Three Great Data Models 3.1 The Relational Data Model The mathematical concept underlying the relational model is the set-theoretic relation, which is a subset of the Cartesian product of a list of domains. A domain is simply a set of values. … The Cartesian product of domains D1, D2, …, Dk, written D1 × D2 × … × Dk, is the set of all k-tuples (v1, v2, …, vk) such that v1 is in D1, v2 is in D2, and so on. … A relation is any subset of the Cartesian product of one or more domains. As far as databases are concerned, it is pointless to discuss infinite relations, so we shall assume that a relation is finite unless we state otherwise. … The members of a relation are called tuples. Each relation that is a subset of D1 × D2 × … × Dk is said to have arity k. A tuple (v1, v2, …, vk) has k components; the ith component is vi. Often we use the shorthand v1 v2 … vk to denote the tuple (v1, v2, …, vk). It helps to view a relation as a table, where each row is a tuple and each column corresponds to one component. The columns are often given names, called attributes. Example 3.1. In Fig. 3.1 we see a relation whose attributes are CITY, STATE, and POP. The arity of the relation is three. For example, (Miami, Oklahoma, 13880) is a tuple. CITY | STATE | POP ------------o------------o------------ San Diego | Texas | 4490 Miami | Oklahoma | 13880 Pittsburg | Iowa | 509 | | Fig. 3.1. A Relation (Ullman, 1980, pp. 73-74).

• JA: I am presently just collecting examples of usage, but the point about "loose talk" is the divergence between what people say and what they mean, say, on critically examining the implications of what they say. Jon Awbrey 13:18, 25 January 2006 (UTC)

• What exactly is the point of this example? This is the definition I favor (a relation is a set of ordered pairs). Note that any set of ordered pairs is a subset of a product domain. "A relation is a subset of the Cartesian product of one or more domains" is synonymous with "A relation is a set of n-tuples" (and on the usual definition all n-tuples are ordered pairs). There are no sets which are not covered by some product domain (and this continues to be true if one extends to classes). Randall Holmes 13:05, 25 January 2006 (UTC)

To clarify why I am unmoved by these examples, here is a definition by Randall Holmes:

Where A and B are sets, we define a relation graph from A to B  as a 
subset of $A\times B$.  According to one school of thought, a relation is   
defined as a relation graph (and so any set of ordered pairs is a relation).  According to 
another school of thought, a relation is defined as an ordered triple $(A,B,G)$,
where G is a relation graph from A to B.

Of course, this is a definition of binary relation (which subsumes all relations under Definition I but not under Definition II). Note that I do start out by mentioning product domains; but if the product domain is not a feature of the function as an object (as it is not here or in your definitions of this section) then "relation" in general reduces to "set of tuples". Randall Holmes 13:26, 25 January 2006 (UTC)

Did you read my remarks on "loose talk" above? I'm every bit as annoyed by it as you are, and it is prevalent (both among users of Definition I and users of Definition II): each group wants to have their cake and eat it, too. Randall Holmes 13:28, 25 January 2006 (UTC)

Mostow, Sampson, Meyer (1963)

• JA: My college roommate used to call me "Packrat". He said it was because I saved all my textbooks instead of selling them back at the end of the term. Here is a standard bit of liturgy from my sophomore/junior 'Abstract Algebra' book, used at UM A², circa 1970.

• 5. Mostow, G.D., Sampson, J.H., Meyer, J.-P., Fundamental Structures of Algebra, McGraw-Hill, New York, NY, 1963.

One of the most basic notions occurring in mathematics is that of mapping. A mapping of a set S to a set T is a rule, or an operation, which assigns to every element in S a definite element in T. (The sets S and T need not be different.) Mappings are also called functions or, sometimes, operators. Mappings are customarily denoted by letters. If f denotes a mapping of S to T, then the element of T which f assigns to an element x of S is often denoted by f(x); one says that the mapping f sends (or maps) the element x into the element f(x), and f(x) is called the image of x. The notation f : S → T is useful to indicate that f is a mapping from S to T. Some further useful notation is as follows: B being a subset of S, f(B) denotes the subset of T consisting of all f(x) for which x is in B; f(B) is called the image of B under f. C being a subset of T, f−1(C) denotes the subset of S consisting of all elements x such that f(x) is in C. (Mostow, Sampson, Meyer, 1963, p. 2).

• JA: Et sic deinceps ... Jon Awbrey 20:30, 3 February 2006 (UTC)

Minsky & Papert (1969)

• JA: Honestly, folks, I don't lay awake at night making this stuff up. I have people who do that for me. Jon Awbrey 17:34, 8 February 2006 (UTC)

• 6. Minsky, M.L., and Papert, S.A., Perceptrons, An Introduction to Computational Geometry, MIT Press, Cambridge, MA, 1969. Expanded edition, 1988.

0.5 Some Geometric Patterns; Predicates Let R be the ordinary two-dimensional Euclidean plane and let X be a geometric figure drawn on R. X could be a circle, or a pair of circles, or a black-and-white sketch of a face. In general we will think of a figure X as simply a subset of the points of R (that is, the black points). Let ψ(X) be a function (of figures X on R) that can have but two values. We usually think of the two values of ψ as 0 and 1. But by taking them to be FALSE and TRUE we can think of ψ(X) as a predicate, that is, a variable statement whose truth or falsity depends on the choice of X. We now give a few examples of predicates that will be of particular interest in the sequel. $\psi _{\mbox{CIRCLE}}(X)={\begin{cases}1&{\mbox{if the figure }}X{\mbox{ is a circle,}}\\0&{\mbox{if the figure is not a circle.}}\end{cases}}$ ... We will also use some very much simpler predicates.* The very simplest predicate "recognizes" when a particular single point is in X: let p be a point in the plane and define $\phi _{p}(X)={\begin{cases}1&{\mbox{if }}p{\mbox{ is in }}X,\\0&{\mbox{otherwise}}.\end{cases}}$ Finally, we will need the kind of predicate that tells when a particular set A is a subset of X: $\phi _{A}(X)={\begin{cases}1&{\mbox{if }}A\subset X,\\0&{\mbox{otherwise}}.\end{cases}}$ * We will use "φ" instead of ψ for those very simple predicates that will be combined later to make more complicated predicates. No absolute logical distinction is implied. (Minsky & Papert, 1988, 5-7).

Outside opinion on this article

I haven't been a contributor to this article, yet, but I was thinking of working on it, because I can barely understand how what is written here is related to the ordinary notion of a relation... and I'm a professor who teaches discrete math! I got the point eventually, however, I have some remarks: If you look at what links here, a significant number of them are specifically talking about binary relations (for example see Set, Partial function, Topology glossary; some articles, like binary relation or Charles Peirce refer, accurately, to the generalization here, but it appears in the text as something other than "relation"). We could correct those links to go to binary relation, but this would require constant attention, because often people refer to the concept of a binary relation when they say "relation." This article does not do enough to inform the reader that very often "relation" refers to "binary relation." This leads me to propose that this article be renamed to something like "k-ary relation," and move the binary relation article to this title, perhaps with additional prominence of the reference to k-ary relations. I suspect this would be reasonable, as even in the definition here you call the object a 'k-ary relation' rather than a 'relation.'

Second, this article reads like definitions from a graduate text. Particular phrases that pop out at me include the first sentence and "It is literally the case that to change this setting is to change the relation that is being defined." It seems to me that the formal definition of a k-ary relation is actually much clearer if we just put it first, but to make it more clear, I might give the formal definition of a binary relation first, so we can see how simply it generalized. The notions of "frame" and "graph" are obviously less important than the definition and are not, despite what the text says, necessary to understand the definition. As a result, this article is not really accessible to most people who might arrive here.

Third, this article should be expanded to be more informative about things like the history of k-ary relations, and more importantly, the importance of k-ary relations: what areas of mathematics make use of k-ary relations? Are there types of k-ary relations akin to symmetric, reflexive, antisymmetric, etc. relations?

I have limited expertise on the third point, but I can help a lot with the second, and I think the first is very important. I'll be watching the talk page here for your replies, JA and RH. Mangojuice 13:57, 25 January 2006 (UTC)

We'll see what develops. I think that both of the two of us that you have addressed think that the issues you mention are important (as do the other participants). Randall Holmes 14:50, 25 January 2006 (UTC)

It is interesting to note that under the definition I recommend (which remains most common), "k-ary relation" is a special case of "binary relation". Randall Holmes 14:52, 25 January 2006 (UTC)

O Lost

• JA: Mangojuice, I also have a bent or a bias toward discrete math, especially graph theory, being brought up in the MiGhTy school founded by Harary, Palmer, Robinson, et al. So binary relations are especial favorites, partly because they are so readily visualized as graphs, bigraphs, digraphs, and their ilk. We already have an article on binary relations, and this one is supposed to be about the natural generalization of that. How general is general? Well, k-adic (k-ary) relations are the next step up. Some people like to (try to) picture k-adic relations as hypergraphs, but the way I see it, and maybe it's just the keen-ness of my mind's eyes, all the benefit of visual representation is lost in the offing. Jon Awbrey 15:26, 25 January 2006 (UTC)

• JA: There's a POV in philosophical logic (sometimes a paper of Quine is cited) that says that all relations reduce to binary relations. Get it? Everything's just a set, right? So all relations are really about the binary relation of membership. Speaking of something lost in the offing, there's something lost there. But whatever it is, it's not the way that mathematicians in their benighted state actually think, and we are talking about standards and practices here. Jon Awbrey 15:26, 25 January 2006 (UTC)

Anabasis

• JA: As a person with some training in logic and mathematics who is also interested in the history and philosophy of logic and mathematics, and whose so-called career cast him in among a diversity of research practitioners and philosophical interlocutors from a panoply of not of necessity mathematical fields, I frequently find myself trying to explain, say, what some 17th through 20th Century light in logic or mathematics knew about this or that item of mind at the time that he or she knew it. The people that I find myself talking to are intelligent and sohisticated people, the lion's share of them far more subtle than I in their overall thought, but a fair majority of them have had the log-&-math switch turned off at some point in their lives, by what I guess has more to do with faults of nurture than faults of nature.

• JA: That is the sandal that brought me to these shores on this latest occasion, if you can imagine yourself wearing it, and though a few days of earnest cogitation assured me of the accuracy and the aptness of the definition that I found there, on or about the solstice last, and though the math-half of my wit still skips according to its custom on past the foliage at the base of the cliff, up to the bolded head of the real Definition, I know that I've left my fellow castaways still drowning in the surf. And I still feel bad about that. Jon Awbrey 14:36, 25 January 2006 (UTC)

A theoretical presentation, looking at valid motivations for both definitions (looking for common ground, and not to go in the article!)

First, I'm going to talk about "binary relation", not "n-ary relation". The issues are exactly the same, and it's much easier to talk about just the binary case.

Go back to the abstraction being implemented: this is a two-place predicate, such as "x loves y" or x < y.

The underlying issue between the two approaches is whether a predicate has domain and codomain as intrinsic features. Another, very important underlying feature is that the implementation of the concept is (usually) being carried out in set theory. It is important to note that set theory (unlike many application domains) is a one-sorted theory (or at best a two-sorted theory if there are said to be classes and "set" is not a subtype of "class").

In first-order logic as most commonly presented, there is a single domain of discourse; this domain of discourse would then be domain and codomain to all relations in a theory with that domain of discourse. In multi-sorted first-order logic, every two place predicate does have a domain and a codomain as intrinsic features, taken from the available domains of discourse in the current theory. Moreover, multi-sorted logic (a logic with types) is appropriate in practice for most application areas within mathematics. But remember that set theory (in which every application area is ultimately supposed to be implemented) is a one-sorted theory.

For a set theorist, then (and for a mathematician contemplating the implementation of mathematics in set theory in general) it is entirely appropriate to define a (binary) relation as a set of ordered pairs. It is perfectly compatible with this view to remark that a subset of the cartesian product of A and B implements a relation with domain A and codomain B; as long as one notes that concepts which essentially involve domain and codomain (such as "surjective function") must be qualified with an indication of the intended domain and codomain if no such indication is incorporated into the set representing the relation.

For a mathematician who is not a set theorist (and whose viewpoint might be better coded in a type theory) the domain and codomain of a given function might be regarded as vital intrinsic features of the function. For such a mathematician, a relation from A to B might better incorporate the domain and codomain explicitly: it is then a tuple (A,B,G) where G is a subset of the cartesian product of A and B. Further, the viewpoint of category theory includes a category of sets and relations, in which the sets are the objects of the category and the relations are morphisms between the objects: the relations are naturally organized into morphism classes between pairs of objects, and might then naturally be supposed to be labelled with their domain and codomain (this may not be the right category theoretic terminology). From a logical standpoint, such a mathematician could be taken to be working in a multi-sorted logic (which is not the case for a set theorist considering the set theoretical implementation as a piece of set theory; there is an incongruity of viewpoint).

Finally, there is a middle ground: it is not necessarily the case that types in a type theory are disjoint. This is most easily understood using a CS analogy: objects of different types can carry type labels around with them (in which case the types are disjoint) or distinctions of type can be completely determined from context (in which case objects of different types may actually be implemented by the same object from an external standpoint). It is perfectly possible to have a "typed" standpoint (so one regards "relation from A to B" as a different sort of mathematical object when the choice of A and B is varied) and nonetheless view a relation from A to B as being implemented by a subset of $A\times B$; the fact that some relation types are embedded in others then needs to be managed in context (one says "onto B" of a surjective function from A to B rather than just "onto", since the latter locution is ambiguous). Randall Holmes 15:21, 25 January 2006 (UTC)

the point being that both definitions have reasonable motivation. Since both occur in practice, and confusions result from not noticing the difference, both should be presented (and appropriate cautions given against formal errors arising from confusing them). Randall Holmes 15:26, 25 January 2006 (UTC)

coming from the RfC

I saw the RfC so I came over to see what the fuss is about. Before I read this article and talk page, I was kind of wondering how there could be a massive disagreement on the definition of a relation. Now I know ;-)

Caveats: I haven't worked on this article, in fact I hadn't read it before I was pointed here by the RfC. I am a working research mathematician, but not in anything foundational; my research is on PDE and SDE. Allow this to color your impressions of my comments as you will.  ;-)

My impressions: I think the article, as it stands, is pretty inappropriate as an article in Wikipedia. I don't think that topics should be introduced in all generality at first, ever, but that generality should be built up after examples. This should be doubly true for a Wikipedia article. I find it inconceivable that any layman and/or undergrad (much less a high-school student) could read this and get anything out of it. My eyes glazed over sometime in the first few sentences, and I read this kind of thing for a living! Now, I am not saying that this article is wrong, or even bad, for certain contexts. I'm sure the authors put a lot of work into it and I don't want to criticize the text as itself. This would be a quite appropriate definition for a graduate text on set theory or computer science. But assuming I read the policies correctly, the purpose of any article on Wikipedia is that non-experts can find it accessible, not that one can generate the most general possible definition of a topic in the most concise way.

My suggestions: I'd suggest that the article be organized completely differently. Start with the definition of binary relation and send a link to the article on binary relation (FWIW, I read that article and think it is in a much more appropriate style for this community). Then give the definition of a k-tuple relation, and then give several concrete examples. (The examples section as it stands now is not a collection of examples by any means!) Then, finally, at the end, talk about this notion of frame and the issues on whether it needs to be specified.

And since I'm making suggestions, I'm of course willing to contribute some labor to this once concensus is reached.

--Deville 15:01, 25 January 2006 (UTC)

• JA: Deville, I don't know how, but if you know how to do it, you could well begin by making up a $(DIYD)^{2}$ template for this and the many similar "Attention" pages that I've seen hereabouts. Jon Awbrey 17:30, 25 January 2006 (UTC)

I've carried out the revert+addition of reference section. Charles Matthews 15:19, 25 January 2006 (UTC)

• JA: The work that I started on Examples was waylaid by the current acts of intervention. I'll get bak tuit here or elsewhere when the dust settles. Jon Awbrey 16:04, 25 January 2006 (UTC)

added brief alternative definition

As per (endless) discussion, added a description of the older definition. I don't think a discussion of the contrast between them is needed in this article; the difference becomes important for the first time in the discussion of functions. Randall Holmes 16:51, 25 January 2006 (UTC)

Issue clarification

Setting aside my 3 general comments, I want to try to think about the actual disputed issue, but I'm a little confused. Let me try to summarize:

The way I understand it is, we could make one of two definitions, either the "framed" one or the "unframed" one. The "unframed" one says that a k-ary relation is a subset of X_1 \times X_2 \times ... \times X_k, that is, a "graph" only. The "framed" one says that the relation must inherently be tied to its "frame", that is, the sets X_1, ... X_k. The functional difference between these two definitions is, effectively, that a k-ary relation, if defined "unframed," may actually be a relation not only on (X_1, ... , X_k) but also on (X'_1, ..., X'_k) where for each i, X_i \subset X'_i (or indeed, in some cases, where the sets shrink), whereas a k-ary relation if defined "framed" is only a relation for that particular (X_1, ..., X_k), and the relations on larger sets are related via some obvious transformation. To make this specific with an example, consider the 3-ary relation R on (Z, Z, Q) defined by (a, b, c) \in G(R) if a/b=c, and the 3-ary relation R' on (Z, Z, R) defined by (a, b, c) \in G(R') if a/b=c. Note that R and R' have the same graph, as long as we think of Q as included in R in the normal way. In the "framed" definition, R and R' are actually different relations (though you could define R' via an inclusion mapping from R), whereas in the "unframed" definition, R and R' are actually the same relation. Am I on target here, or am I missing something? Mangojuice 19:25, 25 January 2006 (UTC)

That's not about the definition, really, but about some defined equality of relations. I say framed is standard practice in mathematics, and this is relation (mathematics), so we go at it from that end. Charles Matthews 19:40, 25 January 2006 (UTC)

a literature search suggests otherwise: I find the unframed definition much more frequently. But note that I am content to have the older definition as an alternative and go with the framed one as the official first-line definition. Randall Holmes 19:49, 25 January 2006 (UTC)

just to clarify, are you saing that the definition is frequently, specifically unframed, or are you saying that many definitions don't address framed vs. unframed at all, but give a definition that is basically the unframed one? Mangojuice 19:56, 25 January 2006 (UTC)

now that I think about it, that's a bit of an unfair question. I would expect even a textbook that actively embraces the unframed notion wouldn't take the bother to explicitly reject the framed notion.  :) Mangojuice 20:10, 25 January 2006 (UTC)

70 percent of sources in my unscientific survey give the unframed definition (they may say "A relation from A to B is a subset of the cartesian product of A and B", but that is the unframed definition: a relation is still the same as its graph under this definition). The remaining 30 percent mostly define "graph of a relation" as the set of ordered pairs and do not say what the relation itself is at all. Just one of the books I looked at actually gave the framed definition. Now one should look at "surjection": this is a tale of shame. Too many books which officially use the unframed definition then cite "surjective" or "onto" as an unqualified property of functions; this is an error, as under a definition which identifies function and graph, one must say "surjection from A to B or "onto B". I have a very recent set theory book which does this correctly. Randall Holmes 21:33, 25 January 2006 (UTC)

Renaming things?

• FYI, in case anyone is reading this page and not Talk:Relation (mathematics), I have proposed that we consider moving Binary relation to Relation (mathematics) and moving what is currently in Relation (mathematics) to n-ary relation. See the discussion at Talk:Relation (mathematics); in the interest of consolidating, let's have the discussion over there. Mangojuice 19:08, 25 January 2006 (UTC)

You have breached this in a confusing way, by copying text from binary relation to here. Please don't do that kind of thing. And I'm opposed to the moves. Charles Matthews 22:08, 25 January 2006 (UTC)

• JA: Mangojuice, I haven't been messing with the binary relation article -- sufficient unto the day and all -- I only scanned it one or twice, but it seemed more or less okay for the time being. So I'll copy your remark and answer it here. I was getting to this point in my reply above, but got distracted.

• JA: The question was: How general is general? And I mentioned a few things about the finite-place case of k-adic (k-ary) relations -- I use k for the arity of the predicate or relation that I have in mind, always saving n for whatever ambient dimensionality (TBA) comes along, and I'm thinking on analogy with differential forms and such, where there's always an (n choose k) parameter in the works.

• JA: Where was I? Right, general. Well, the finite dim case is nowhere near enough for some folks, count me in on a bad day, as countable and uncountable situations quickly arise. Even more bizarre, it's getting less and less unheard of these days to wrestle with "relations without arity", that is, you can have all different lengths of tuples, with maybe no upper bound on their fiendish tuplicity. What is that? Well, if you stop to think about it, which I made the mistake of doing once a couple of decadent decades back, it's the moral equivalent of a "formal language" in the comb-&-comp sense of a subset of a kleene star of a (finite) alphabet, L c A*. Obviously we don't want to put this kind of air-headedness up front, but we do need to keep it in mind, as some folks out there are really into this stuff. Jon Awbrey 19:40, 25 January 2006 (UTC)

• Since a pointer to binary relation occurs in the very first line of this article, I don't see that there is a problem. I agree with Mangojuice that most uses of relation in mathematics actually refer to binary relations (and under my archaic definition all relations (of finite arity) are binary relations anyway -- for artificial reasons, though :-) but I think that the reader should rapidly be able to find the right concept. I think there is a major divide between the finite and infinite/vague arity cases; the set theoretical implementation is quite different, since we have to use functions to implement infinite "tuples", and moreover the connection with predicates in logic (at least, the logic of languages we can actually write) is lost (though I suppose that finite vague arity might have some applications in logic). [I do know that there is infinitary logic, but it is a different enterprise]. Randall Holmes 19:53, 25 January 2006 (UTC)

• I suppose that those interested in n-ary relations would be directed there from binary relation under this proposal; no one is going to look for that title (which I think is an argument against it). Randall Holmes 19:58, 25 January 2006 (UTC)

The other possibility would be a merge of the two articles. In the merged version, we could appropriately talk about binary relations first and foremost, and then in the same article discuss the generalization of a relation. Now that I think about it, I like that idea better... it has two disadvantages though: (1) it requires more work, and (2) it would be important that the k-ary relation stuff doesn't become so bulky that it overwhelms the bulk of the binary relation stuff. I agree that if we do my proposal we'd have to pick the right title, but I think n-ary relation would do fine; we can put up redirects for any other reasonable titles. Mangojuice 20:08, 25 January 2006 (UTC)

Note that the k-ary article is now quite short. But I still don't see the need. Randall Holmes 20:38, 25 January 2006 (UTC)

So are you neutral on the idea or do you actively object? Mangojuice 20:52, 25 January 2006 (UTC)

I guess that I would have to say that I am actively opposed. A single article could have been written in the beginning, but merging them now would create a lot of trouble. Randall Holmes 21:23, 26 January 2006 (UTC)

A new name for some old ways of relating

• JA: Okay, so let's try to read, as if for the very first time, this new-old or old-new definition of a relation:

A commonly occurring alternative definition (commoner in older sources) is "a relation over the sets X1, ..., Xn is a subset of X1 × ... × Xn (the Cartesian product of these sets)." Under this definition an n-ary relation in general is simply a set of n-tuples, and there is no distinction between a relation and its graph.

• JA: Of course, where it says "commoner in older sources" it means "old but not too old" — you have to hit the era just right to find folks dreaming that they ever talked this way.

• The era during which people talked this way began a long time ago -- and continues. But I am not promoting this definition (in the article), merely reporting that it is used (which is true and important for an encyclopedia article). Randall Holmes 20:41, 25 January 2006 (UTC)
• I could have said (and supported) "the commonest definition of relation continues to be..." but that would be perceived as hostile. I'm not interested in promoting this definition, merely in ensuring that it appears. Did you read what I said above about it (in the section on looking for common ground?) Randall Holmes 20:43, 25 January 2006 (UTC)

• JA: But this is mathematics, where a truly good-beautiful idea just does not have an expiry date, so a more important question to ask of a definition would probably be: What the heck does it define, in the first place?

• There is fashion in mathematics as in other fields, and it is at least formally possible that some fashions may be pernicious. Randall Holmes 20:49, 25 January 2006 (UTC)

• JA: Does the above definition define "relation"? How do we tell, anyway? Well, "lege, lege, lege, ora, relege, labora et invenies" is the usual rule here, And on the re*reading part of that sloggin' we may chance to see that the new rite does not define a relation either. It just cant get over the hedge with which it first set out to qualify itself, to wit, "a relation over" something or other.

• JA: Moral of the story time. If you want to form a notion of a relation detached from context, you have to do a lot or a little more work, abstracting from datasets of more concretely embedded, mathily not mafially speaking, situated relations of the form "relation over this", "relation over that", and so on.
• JA: Jon Awbrey 20:36, 25 January 2006 (UTC)

• I say that, over and over. But it is generally a little extra work; in a context where it is a lot of extra work, one is always free to use the other definition! Randall Holmes 20:45, 25 January 2006 (UTC)

• Oh, I see, you're not saying what I thought. My previous remark was based in understanding you be saying (as I do) that to use the context free version requires one to qualify various predicates of the relation which do depend on intended domain and codomain. You appear to be saying on the second reading that I can't really be defining relation in this way because I chose to define "relation from A to B" first. But I am. For one thing, the general case of relation occurs as an instance of this definition as well as an abstraction from it, if the universal set or class occurs: "relation from V to V" is "binary relation". For another, just read my book, pp. 29-31 (the pagination might be slightly different in the online version). "Domain" and "range" are there defined as the results of operations on relations, which are defined pristinely as sets of pairs. In the function section you can see how I handle "one-to-one", "onto" and "bijection". I'm really quite remorselessly consistent. The only reason that I defined "relation from A to B" first was to make it easy to frame the other definition as an alternative! Randall Holmes 21:05, 25 January 2006 (UTC)

• JA: But we're not talking about the bottle and vintage of axiomatic set theory that U or I or the Mathematician on the Moon has acquired a taste for. We're talking about the boys, er, persons in the hall, what you might call T.A. Mits, the average mathematician in the study, T.C. Mits' less wealthy sister. I already know what T.A. uses for set theory, its her own, her native brand. Jon Awbrey 21:22, 25 January 2006 (UTC)

• JA: The point is that this definition don't hunt. It stays in the hedge that it started from and does nothing that the other doesn't do, except for the confusing people about what's being defined part. And that's a bad thing. Jon Awbrey 20:52, 25 January 2006 (UTC)

• Independently of whether it is good or bad, it is still in use (and in fact, as far as I can tell, still more common than the framed definition). That is enough to settle the question as to whether it should be mentioned in an encyclopedia article. Your assertions about what it does and doesn't do are simply wrong. Randall Holmes 21:07, 25 January 2006 (UTC)

• As an outsider on this debate, let me offer the following. The core of the issue is whether the unframed definition is actually an alternate definition, or just a less precise one. What I'm getting at is, I agree that many books would not be so precise as to define frames when defining relations, but that doesn't mean that they (1) reject the idea, or (2) (equivalently) equate a relation with its graph even when the context is vague. If some significant source actually do expicitly reject the idea, it is "used." But if not, then mentioning the unframed definition as an alternative suggests that there's some disagreement on the point. If in fact virtually all sources that don't give frames don't reject the idea there wouldn't be a disagreement. The difference I'm bringing up is whether the unframed definition is a minority POV vs a fringe POV. Keep in mind, it's not just what the source SAYS, it's the POV they have. Mangojuice 21:18, 25 January 2006 (UTC)

• They are definitely different definitions. Moreover, the unframed definition is dominant, in the sense that it is used far more (try a literature search): it is the majority position, not the minority, and it is the historical implementation of relation in set theory. The new definition is gaining ground, but it still does not hold the field. Randall Holmes 21:24, 25 January 2006 (UTC)

to be more precise: a source that says "A relation is a set of ordered pairs" repudiates the framed definition, because under the framed definition a relation is not a set of ordered pairs. It is as simple as that. Randall Holmes 21:26, 25 January 2006 (UTC)

• JA: This crosses over from "loose" to "sloppy". I find no respectable sources (or targets) that write such a sloppy def as this sort of out-of-context 1-liner. Jon Awbrey 21:38, 25 January 2006 (UTC)

As a precise example -- consider set-class axiomatic set theory (such as Von Neumann-Bernays-Gödel set theory or Morse-Kelly set theory) using the axiom of replacement:

If F is a (class) function whose domain is equal to a set, then its range is equal to a set.

or the alternative formulation

If F is a (class) function and x is a set then F[x] is a set.

This makes no sense if we're talking about framed functions. Arthur Rubin | (talk) 21:35, 25 January 2006 (UTC)

• When I am feeling uncharitable, I think that the whole issue arises from the mathematical community accepting one bad definition: this is to parse "a bijection is a one-to-one and onto function from A to B" as "a bijection is a (one to one and onto function) from A to B rather than the (IMHO correct) "a bijection is a one-to-one and onto (function from A to B). "Surjective" is not a property of functions: functions have unique ranges, but not unique codomains. Without this one misconception, the issue would not arise. Randall Holmes 21:44, 25 January 2006 (UTC)

Re: Spect, Retro: Spect, Pro: Spect

• JA: Yes, the word "respectable" was ill-chosen. I retract that. Halmos and the appendix of Kelley were my first two brushes with set theory, and I get all teary-eyed just looking into them again. But I respect all sorts of people for all sorts of reasons that have nothing to with how much use I can make of their ways of thinking. What's in NST is just no longer adequate for my day-to-day needs. And putting aside the fact that I probably derive a different moral from Kelley, what's in that appendix is a beautiful luxury that hangs on the wall in its golden, er, unframed state and has never helped me with any of the real math problems that I have ever had. As much joy as (axiomatic) sets can be, I know as a practical matter that, in a pinch, I always trust to my own naivete, and not some other book's naivete. I do not try to say why, I am just being honest about the way it is.

• JA: But we're supposed be addressing the sorts of material that is found in "discrete maths", remember? At least for the first hundred kbytes or so. Jon Awbrey 22:34, 25 January 2006 (UTC)

• • So you want me to count occurrences of the sentence "A relation is a set of ordered pairs" in the discrete math texts? It's a common definition there, too. Randall Holmes 22:47, 25 January 2006 (UTC)

A relation is a set of ordered pairs: batting 1000 so far. Many many respectable references.

JA said above: "JA: This crosses over from "loose" to "sloppy". I find no respectable sources (or targets) that write such a sloppy def as this sort of out-of-context 1-liner. Jon Awbrey 21:38, 25 January 2006 (UTC)"

• Sorry, Jon, it's common. [...unkind rhetorical question deleted...RH] Jean Rubin, Set Theory for the Working Mathematician, p. 51. It's written in symbols, but that's what it says. Randall Holmes 21:48, 25 January 2006 (UTC)

• Words, too: "A relation, then, will be defined as a class of ordered pairs". Randall Holmes 21:50, 25 January 2006 (UTC)

• Jech, Thomas, Set Theory (a major authority), p. 8: "An n-ary relation R is a set of n-tuples". [...unkind rhetorical question deleted...RH]Randall Holmes 21:53, 25 January 2006 (UTC)

• Drake and Singh, Intermediate Set Theory, p. 215: "Rel r for r is a relation, i.e., a set of ordered pairs." Do you want more? I've got a shelf full. (this is 1996). Randall Holmes 21:55, 25 January 2006 (UTC)

• Halmos, Naive set theory, p. 26: "We hereby define a relation as a set of ordered pairs". Old but good. [...Unkind rhetorical question deleted...RH]

• Quine, W. v. O., Mathematical Logic, p. 198, "it is thus convenient to think of each relation as a class of pairs of elements". Calling some people unrespectable rebounds on you.

• Handbook of Mathematical Logic, Jon Barwise, ed., in an article by Shoenfeld, p. 329, "Set theory deals not only with sets, but also with relations and functions, which are sets of ordered pairs".

Set theory texts are easily accessible to me. I also have a shelf full of undergraduate discrete math texts (I teach the stuff). Some of them, but only a minority, now use the framed definition. Would you like more page references? Randall Holmes 22:11, 25 January 2006 (UTC)

My library search was not of set theory titles: I looked at set theoretical preliminaries in books on a wide range of mathematical subjects. 70 percent of them (and I avoided the old ratty ones) give this definition (though they sometimes define "relation from A to B"). Randall Holmes 22:13, 25 January 2006 (UTC)

There is a false dichotomy here which people have tried (Awbrey and others) more than once. Axiomatic set theory...is set theory. There is no other set theory. There are some other systems, but they tend to define relations...as sets of ordered pairs! Randall Holmes 22:17, 25 January 2006 (UTC)

All the logic books on my shelves (four, and I'm only counting current ones) define "n-ary relation on A" as "subset of $A^{n}$". You seem to derive some sense of justification from this. However, as soon as one says "binary relation" in general, one is presumably talking about objects which are subsets of some $A^{2}$. It is a theorem of set theory that for any B, there is an A such that $B\subseteq A^{2}$ iff...here it comes...B is a set of ordered pairs... Randall Holmes 22:35, 25 January 2006 (UTC)

I found one example of the framed definition on my shelf so far: it is given (and well-motivated) in K. Joshi, General Topology, 1983.

Is there supposed to be a consersation above? Why does it look like only one person talking? I'm confused. -lethe ^talk 04:00, 26 January 2006 (UTC)

This note is a rant, addressed to JA whose silly statement is quoted above. The gaps were occupied by going to the shelf in my office to get another book... Randall Holmes 21:29, 26 January 2006 (UTC)

There is only one person talking; this talk page has been changing so fast, sometimes people write their comments in multiple chunks. Mangojuice 13:09, 26 January 2006 (UTC)

Predicates as boolean valued functions

I have two problems with that. First, is that true? That's not the way I heard it, when I learned me some mathematical logic. As I learned it, a predicate is just a symbol used in a first (or higher) order language, and in fact it is a structure, which assigns a semantics to the language, which you might call truth assignment, I guess. But anyway, as far as I know, a predicate is not a function. Secondly, it strikes me as quite odd to define a predicate as an n-ary truth valued function as if that were somehow different than an n-ary relation. They're the same, as surely as any map X→2 is just a subset of X, up to notation. -lethe ^talk 04:20, 26 January 2006 (UTC)

• JA: I corrected the heading to something that makes sense. There is a quite common variation in usage — the word to the hip is polymorphism, perverse or otherwise — that I was in the progress of explaining before the ceiling flew away. Maybe I'll get bak tuit when the chat rheum quits humming so NP-hard. It takes a standard brand of categorical factorization diagram by which the predicate p : X -> B, where B = {0, 1}, factors through the k-dimensional coordinate space B^k. I have some old snapshots from Asciiland that I will dig up, or maybe somebody here already has one that will do the trick? Jon Awbrey 13:58, 26 January 2006 (UTC)

Merging proposal (please read)

Hey -- I propose merging this article with binary relation. I have mentioned this idea, and the idea of moving articles around, a couple of times but not gotten direct responses. Randall said he "didn't see the need," but I don't take that as opposition, it seems neutral to me. JA hasn't said anything, and I'm certainly interested in outside opinions. Again, my reason for this is that many times people will come here looking for an article on binary relations, and this article barely mentions them. What's more, I would say that the term "relation" much more often refers to a binary relation than a k-ary relation, while people rarely use the term "binary relation" to refer to binary relations. The more accurate naming would be to have the article on binary relations here and the article on k-ary relations elsewhere.

For clarity, what I propose is that the article under Relation (mathematics) talk first and foremost about binary relations, and introduce k-ary relations in a section, but still define it and give an example. This would be a merge of this article into binary relation. The current article is half as long as the binary relation article, so it would certainly have to be cut down in order to merge it. I propose that we make binary relation redirect here, but make a new main page for k-ary relation where we can have the full text of this article and go into more detail. Mangojuice 13:19, 26 January 2006 (UTC)

• JA: Strong objection. You have apparently just missed the whole point of the article and the level of generality that is appropriate to it. Jon Awbrey 14:04, 26 January 2006 (UTC)

* I totally DO get the idea that this article is about the generalization of a relation. What I'm saying is that, while that definitely is something that belongs on Wikipedia, and in fact probably does deserve its own page, it shouldn't be the "Relation (mathematics)" page, because common usage refers to _binary_ relations, specifically. I'm going to compile a list of links to this page and what they mean, so you can see the evidence here. Mangojuice 14:24, 26 January 2006 (UTC)

• JA: You needn't bother, I am quite familiar with all of the usages, abusages, along with their histories. The circumstance that "relation" defaults to "binary relation" in some people's minds is a historical anomaly that arose in part on account of the fact that (>2)-adic relations are vastly more complex than 2-adic relations and that Frege and Russell in particular gave them very short schrift. Not so with the Peirce-Schröder line of work, however. Jon Awbrey 14:58, 26 January 2006 (UTC)

* Well, I did anyway. Check out User talk:Mangojuice/relation (mathematics). I don't mean to argue that it may be better to use "relation" to refer generally to relations, while using the term "binary relation" specifically to refer to binary ones. However, look at WP:NPOV. That's a point of view, and my evidence is proof that it's not a majority POV. If you look, about half the pages that (1) use the term relation correctly at all and (2) don't list both links in a list -- about half refer to binary relations, and the ones that don't are mostly set theory topics. It's important that wikipedia be NPOV: and it's important in naming as well as in article presentation. (I wrote this earlier. Mangojuice 15:41, 26 January 2006 (UTC))

Mangojuice: On reconsideration, there's no reason this article couldn't be general without being uninformative about binary relations. I'm working on a merged version now that I hope will be satisfactory; just read it imagining that there is no article on "binary relation"... actually I think we can do this without needing a separate article for n-ary relations. I'm working on it in my user space and will post a link here when I'm done with the draft. Mangojuice 15:45, 26 January 2006 (UTC)

Neutral in principle, but not in practice: don't rock the boat!!! Randall Holmes 21:31, 26 January 2006 (UTC)

Roads to mathematics — democratic, dreaming, royal

• JA: Now that a couple of new roads to mathematics have been paved by the good intentions of the WikiWaffle chain gangs, there will be a vote on the Riemann Hypothesis Tuesday next, and we'll put that Bad Boy to bed for good. Jon Awbrey 15:26, 26 January 2006 (UTC)

I strongly advise you not to escalate a point about how to write one (1) article. Charles Matthews 15:30, 26 January 2006 (UTC)

• The metaphor resonates with me. To my colleagues I quote Plato's (or Euclid's) "There is no royal road to geometry" -- then follow it up with my own "There is no democratic road to the calculus, either (alas)". Randall Holmes 21:33, 26 January 2006 (UTC)

i.e., Mathematics is an aristocratic activity. Live with it. Randall Holmes 21:33, 26 January 2006 (UTC)

• JA: I was partly thinking of Freud's description of dreams as the "royal road to the unconscious". I wish we had expressways in mathematics, but it just doesn't seem likely anywhile soon. The association, free or else, to Plato is probably an allusion to the motto about geometry over the door, but the bit about "no royal road" is supposedly Euclid talking to Ptolemy₁.

For Archimedes, who came immediately after the first (Ptolemy), makes mention of Euclid: and, further, they say that Ptolemy once asked him if there was in geometry any shorter way than that of the elements, and he answered that there was no royal road to geometry. (Heath, "Euclid and the Traditions about Him", in Euclid, Elements, Thomas L. Heath (ed.)) — Perseus at Tufts

• JA: I also post here a note that I put at Talk:Topology in case set theorists and topologists no longer hang out at the same intersections:

• JA: I've been noticing this widespread misunderstanding here in WikioPolis as to the general meaning of the word "elementary" in mathematics. It all goes back to Euclid's Stoicheia (singular Stoicheion), a Greek word for many things, from the shadow of a gnomon on a sundial, to letters and numbers, to steppen stones and steps of a stairway to Platos's Heaven, to the stars, but in geometry having the specific senses glossed below:

Stoicheion. 3. the elements of proof, e.g. in general reasoning the prôtoi sullogismoi, Arist.Metaph.1014b1; in Geometry, the propositions whose proof is involved in the proof of other propositions, ib.998a26, 1014a36; title of geometrical works by Hippocrates of Chios, Leon, Theudios, and Euclid, Procl. in Euc.pp.66,67,68F.: hence applied to whatever is one, small, and capable of many uses, Arist.Metaph.1014b3; to whatever is most universal, e.g. the unit and the point, ib.6; the line and the circle, Id.Top.158b35; the topos (argument applicable to a variety of subjects), ib.120b13, al., Rh.1358a35, al.; stoicheia ta genê legousi tines Id.Metaph.1014b10; (Liddell & Scott, A Greek-English Lexicon)

• JA: Incidental Muse — Loreena McKennitt, Elemental Jon Awbrey 14:45, 1 February 2006 (UTC)

My merged version draft

Check here to see my first draft of a merged version between this and binary relation. I was aiming to be general, yet informative about the specifica case of binary relations and their importance. I included the "Sets vs. Classes" section of the binary relation article (which certainly belongs more in a general article anyway) and I grabbed the references and bibliography (which, BTW, probably need to be cut down somewhat) from this article, and generally tried to merge definitions. I added a bunch of examples of my own ... I shied away from using "toy" examples as existed in both articles... though I think the examples section could use some work, and partially repeats stuff in the intro. Some examples (for instance, the example of functions) really work better in the combined article than they would in either separate one. Comments, please! Mangojuice 19:43, 26 January 2006 (UTC)

Actually, the sets/classes issue belongs (near the end, not in the intro) in an elementary binary relations article. The fact that equality, membership, and subsets are not (set) relations unless restricted does need to come in somewhere. It is not really needed in the n-ary relations article (nor is it needed in the function article) because there are no commonly used functions or n-ary relations which are likely to cause confusion. Randall Holmes 21:37, 26 January 2006 (UTC)

What are you planning to do with this article? It does not seem to contain the informal example in the existing relation article (which is currently looking quite nice). It also contains a mathematical error: the connection with characteristic functions is not described correctly. I would leave things as they are. Randall Holmes 21:40, 26 January 2006 (UTC)

I take it back about characteristic functions; I wasn't reading carefully enough... Randall Holmes 21:42, 26 January 2006 (UTC)

Lest the intervening retraction make it unclear, I'm not interested in merging the existing articles; each of them seems to do its own job on its own level fairly well right now. Randall Holmes 21:45, 26 January 2006 (UTC)

Reduction of "relation" to "binary relation"

There are two completely different senses in which "relation" can be reduced to "binary relation". I have implicitly mentioned one and Jon Awbrey has explicitly mentioned another; there might be some confusion as to which is which, so I will spell out the two reductions and the contexts in which they work. I remain on the record as against merging the two articles. Randall Holmes 16:59, 27 January 2006 (UTC)

• Under the old set theoretical implementation of "relation" (a relation is a set of ordered pairs, or a relation from A to B is a subset of the cartesian product of A and B; pace remarks by Awbrey, these are the same definition), all n-ary relations are binary relations. This follows from the purely technical fact that under the usual definition of an n-tuple, all n-tuples are ordered pairs, too, so an n-ary relation (a set of n-tuples) is also a binary relation (a set of ordered pairs). This ceases to be true if one uses the framed definition of relation; it ceases to be true if one changes the definition of n-tuple, too; it is a strictly implementation-dependent (and therefore suspicious) identification. It should also be noted that the logical n-ary relation implemented by a given set of n-tuples is not the same logical relation as the binary relation implemented by the same set of n-tuples (obviously!). Randall Holmes 16:59, 27 January 2006 (UTC)

• It is a further observation (Awbrey seems to ascribe it to Quine, but it may be older) that under certain readily satisfied circumstances logic does not require the use of any n-ary relations with n>2 at all. Namely, if one has ordered pairs as a component of one's logic (a function symbol) there is no need to use any logical n-ary relation (n>2) at all, ever. The relation written $P(a_{1},\ldots a_{n})$ can be replaced everywhere with the binary relation $P^{*}(x,y)\equiv _{def}(\exists a_{2}\ldots a_{n}.y=(a_{2},\ldots ,a_{n})\wedge P(x,a_{2},\ldots a_{n}))$. If the foundations of mathematics are implemented in set theory, we of course have an ordered pair, and we have no primitive relations of arity higher than 2, nor (on the basis of this result) any reason ever to define a logical relation of arity higher than 2. In a type theory, this insight can only be applied if the type system is closed under cartesian product. The same argument also eliminates the need to consider logical functions with arity greater than 2. Randall Holmes 16:59, 27 January 2006 (UTC)

• There is a relationship between the two reductions: depending on exactly how n-tuples are defined in terms of pairs, the binary relation identified with an n-ary relation in the first paragraph may be the binary relation which replaces that n-ary relation in the second paragraph.

• I rather like this reduction: relations (and operations generally) of arity greater than 2 are syntactically inconvenient, though there are some ternary operators which are occasionally handy. I've probably just irrevocably propelled myself into the outer darkness from the JA standpoint :-) Randall Holmes 16:59, 27 January 2006 (UTC)

• JA: I will have to get back to this later, but just so nobody gets me wrong, let me just say for the (broken) record that I consider both of these putative "reductions" to be sophisms, though for different reasons in each case. Jon Awbrey 22:10, 27 January 2006 (UTC)
• RH: I indicated reasons why the first one should be taken with a grain of salt, but both are formally demonstrable results, one of set theory, and one of mathematical logic. But I didn't think you would like either of them :-) Randall Holmes 22:16, 27 January 2006 (UTC)

Another attempt at explanation

I'm trying to explain this again, because I feel like you guys aren't getting my real points. RH -- my merge proposal has absolutely nothing to do with the idea that n-ary relations can be thought of as binary relations. That's interesting to someone who theorizes about these things, but not to a lay reader, which is what wikipedia is for. I'm proposing the merge because very often people refer to "binary relations" simply as "relations," and that is an important aspect of the concept of relations in mathematics that is effectively receiving no coverage. Even the term "binary relations" is not explained here, it's just used. I really have nothing against the binary relations article: perhaps it is worth having two articles, but binary relations MUST be discussed in this one. Currently this article is about NON-binary relations. I would like it to be about relations in general. Mangojuice 19:12, 27 January 2006 (UTC)

• the case n=2 is included here, so we aren't talking about non-binary relations per se. But your point is reasonable, and I have no objection to the header you added. Randall Holmes 19:41, 27 January 2006 (UTC)

I consider the header the absolute minimum one can do to help this issue, sort of a stop gap, until we find a better solution. Mangojuice 20:55, 27 January 2006 (UTC)

• the reduction of "relation" to "binary relation" had come up in other contexts; this discussion was not really entirely about your proposal. After all, on the whole the substance of the previous section probably works in favor of your proposal rather than against it...Randall Holmes 19:44, 27 January 2006 (UTC)

Specific to the issue about the example, it really isn't explanatory to have these toy examples like the "X suspects Y likes Z" kind of thing. The problem with those is that they really do nothing to explain the *concept* of a relation, they simply help get a reader familiar with the formal definition and notation of relations. This isn't what the reader would want. It's not even helpful for students of the subject: if we don't use the same definition and notation their class uses, it's not helpful. Mangojuice 19:12, 27 January 2006 (UTC)

• I beg to differ; I think the example is quite useful -- but it isn't a panacea, just an example. What's wrong with getting used to the formal notation? Often the ability to manipulate the formal notation correctly precedes (and leads to) understanding of the concept. Randall Holmes 19:41, 27 January 2006 (UTC)

• It is probably impossible to teach the concept (for understanding, for one not well prepared to receive it) in an encyclopedia article. A formal definition with examples is the best one can do; when one starts trying to teach the concept (with an entirely unprepared audience in mind) one is no longer writing an encyclopedia article. This is not to say that one cannot learn a field by reading the encyclopedia; but this requires a great deal of preparation on the part of the reader. Randall Holmes 19:51, 27 January 2006 (UTC)

I hear you on that! I guess what I'm trying to say is that saying something like "Familiar concepts like equality, less than, greater than, and divides (evenly) are all basic examples of binary relations" helps by getting across what this whole relation thing is about. A toy example might be useful in addition; after all, we are introducing some notation and we might as well give an example of how to use it... but afterwards. Mangojuice 20:53, 27 January 2006 (UTC)

This reminds me very much of the discussion (some time ago) surrounding derivative. What ended up happening, which I think was a Good Thing, is that derivative is now a discussion of the high-school case (a real valued function of a real valued variable), and the cornucopia of other possible meanings of derivative are now summarised and categorised in derivative (generalizations), with appropriate links. The introductory paragraph for derivative does a good job of (1) not scaring off the high-school/undergrad students and (2) pointing more advanced readers to their intended destination. Mangojuice's observation is that the word "relation" behaves in a similar way to "derivative", and I think it's a good point. I'm somewhat in favour of Mangojuice's proposal, although not necessarily agreeing with her/his current draft text. (And I'm not intending to suggest that we should have two separate articles as in the derivative case.) Dmharvey 20:36, 27 January 2006 (UTC)

Exactly. But the way things stand, it's done the opposite way here: the relation (mathematics) article, which is the one people will probably link to, is the more difficult general one, while the link is to the basic one. I originally proposed (and still favor) the idea that this article be moved to something like 'n-ary relation' or 'relation (generalized)' and moving the binary relations article here: then the titles would be very much analogous to the way the same issue is handled under derivative. Mangojuice 21:02, 27 January 2006 (UTC)

Bibliography

On a different note, could we shorten the bibliography a bit? There are more references than are really necessary, and a lot of them are redlinks. Mangojuice 21:03, 27 January 2006 (UTC)

Is set theory a one or a many?

• JA: And while we're pondering insolubilia, we might as well take up the question as to whether set theory is a one or a many. When I was a child, much like ice cream, there were only three flavors of set theory: (1) naive, (2) the one where a set is an element, (3) the one where a set is a subset. Anyway that was my child's eye view of things, and of course, calling naive a "theory" is just as sloppy as any child with an ice cream cone, but face it, everybody still says that. But now you can get jalapeño set theory with blenderized M&M's™ if you like that sort of thing. So what's the deal here? Can it be that the store-bought axiomsets have yet to capture our intuitive conset? Jon Awbrey 22:30, 27 January 2006 (UTC)
• well, there were more flavors even then. How about New Foundations? There was also already the amusing theory of Ackermann. Nowadays I would say that there are 3 mathematically serviceable general approaches to set theory, embodied in ZFC and the associated theories with classes (and extensions with large cardinals, etc.), extensions of Jensen's variation NFU of New Foundations (and extensions), and (most recently) the powerful system of positive set theory due to Olivier Esser. Only one of these is actually much in service (and this is sociologically a good thing). There are other theories that cater to people with philosophical prejudices such as predicativism or constructivism. There is the variation of ZFC designed to ease the path to nonstandard analysis. I just wrote the article on alternative axiomatic set theories for the Stanford Encyclopedia of Philosophy, so I know more about this than I usually do (the article isn't up yet). Randall Holmes 23:44, 27 January 2006 (UTC)

but I would append the further remark that most systems (certainly the three I mentioned) provide essentially the same picture of the mathematical universe. It's all a matter of differing implementations of the same underlying abstraction. When I say that they provide the same picture, I am saying that there are ways to interpret the world of each of them in terms of the others; they certainly do not make the same surface assertions about sets! (the other two contenders both have a universal set!) Randall Holmes 23:48, 27 January 2006 (UTC)

by the way, this is probably not the right venue? Randall Holmes 23:50, 27 January 2006 (UTC)

Domain, codomain, domain of definition, range, source, target, etc.

• JA: I'm still in the process of going through as many of the pre-dusty and post-dusty books that I can find on my ultra-dusty shelves and reviewing the variorum of usages in this regard, but I am coming to the conclusion that there is no longer any choice but to accustom ourselves and our readers to the facts of life, that the usages they are a'changing, in large part it appears due to the increasing influence of category theory and computability considerations. I am desperately seeking to avoid the extremity of a word like "corange" ("corrange"?), despite the fact that it would make life so much easier for poets to finally have a word to rhyme with "orange", so here's an alternative suggestion. It would be copacetic with current practice to use "source" and "target" for the designated domains, with "domain" and "codomain" as synonyms in the 2-ary case, using "j^th image" or maybe "j^th project" for the natural projection on the j^th domain, with the synonym "range" in the appropriate context. Jon Awbrey 14:08, 28 January 2006 (UTC)

dude that is actually pretty funny. It never occurred to me that corange pseudo-rhymed with orange. I'm sure I once even heard a song called "nothing rhymes with oranges". Now I want to hear a whole poem, or a limerick or something! :-) Dmharvey 19:49, 28 January 2006 (UTC)

• JA: Quackwork Orangements Jon Awbrey 04:46, 29 January 2006 (UTC)

Not all relations are finitary, nor even have arities defined

• JA: One of the more glaring inaccuracies in the article as it currently stands is that not all relations in mathematics, as they are currently treated by those in the field, have finite arity, or even have a parameter analogous to arity defined on them. Now, you may not want dwell on this factoid at the outset of discussion, but you do not want to preclude all later discussion of it either. So a bit of careful phrasing is called for, which I had once upon a time put in place, of course. Jon Awbrey 14:18, 28 January 2006 (UTC)

• No, the scope is correct now. It is controversial whether those other things are relations at all. If they are mentioned, it should be only late in the body of the article. Randall Holmes 17:35, 28 January 2006 (UTC)

• JA: I doubt if it's necessary to mention those sorts of options in this article at all — I still don't know yet what level it will settle at — but it's not my place to close off the options either, as these things really are being taken more and more seriously of late. Jon Awbrey 17:54, 28 January 2006 (UTC)

Your note on language

Your note on language is wrong. If a mathematical definition says that something is an n-tuple, it is just that -- an n-tuple. It is the informal concept being implemented, not the formal mathematical concept, that is parcelled out into n pieces. Randall Holmes 17:35, 28 January 2006 (UTC)

• JA: Yes, I get all that. It's an informal expedient, designed to prevent some readers from closing their eyes and walking away, as I know quite well from experience that they will, and it's the easiest way possible to do this short of some de-monstrous digression into various POV's on the ontology of mathematical objects. Jon Awbrey 17:50, 28 January 2006 (UTC)

• JA: And I agree about the pleonasm of "set-theoretic product" -- I just thought I remember some people abjecting to the use of "cartesian product" earlier on? Jon Awbrey 18:00, 28 January 2006 (UTC)

• one still should not make statements that are actually false. see how you like my note on the use of n-tuples; one could add an analogy to the notion of "record" in CS datatypes, but I thought that would be more clutter.

• My personal comfort zone (when I call in mediation) has to do with statements being made which are false to mathematical fact or usage; this isn't (mostly) happening yet. But the pedegogical approach of the article is beginning to veer away from what I take others' understanding of "encyclopedia article" to be. Just a friendly reminder... Randall Holmes 20:58, 28 January 2006 (UTC)

• JA: It's not false. What you say is one POV. I have seen several others argued, and it's not worth the distraction to the reader at this point, so I leave it up in the air. My rule here is to help the reader get past a tricky wicket, not hit him/her over the head with every mallet on the field. Jon Awbrey 21:04, 28 January 2006 (UTC)

• You misunderstood me. I wasn't saying that anything in the article as it stands is false (the note on language was unequivocally false; a mathematical definition says what it says; there is some truth in what you said but it reflected a confusion of conceptual levels -- but that is not what I was talking about). I was saying that as long as content remains true, I'm not unhappy (or not too unhappy) but the way things are going may invite intervention from others. Randall Holmes 01:24, 29 January 2006 (UTC)

Embedded, included, situated relations

• JA: My sole purpose in adapting cartesian/relativistic idea of "frames of reference' to the present setting was to reduce the cognitive load on the reader from a (k+1)-tuple to a pair. Seeing as how that particular facility of language has now been expurgated from the account, there is no residual use for it. Thus, I resorted to the analogous examples in topology ("embedded"), categories and sets ("inclusion" or "included"), and several usages ranging across the recent literatures in logic, model theory, pragmatics, and cognitive psychology ("situated"). And I can't really imagine any casual readers who would be foolhardy enough to rush in where angelic dictators lay down their treads. Jon Awbrey 01:42, 29 January 2006 (UTC)

• I don't actually know what the term for this kind of definition is, but people on the talk list seemed to take naturally to "framed". What I would suggest is giving just one term for this purpose; one might ask (anyone listening?) what terms are commonly used for the contrasting forms of definition we are discussing? Giving three different terms (none of which are standard in mathematics) is confusing. Randall Holmes 02:00, 29 January 2006 (UTC)

• I'm not going to engage in an edit war about this, but I continue to think that "framed" (and just "framed") would be better terminology. It's a good metaphor. Randall Holmes 02:04, 29 January 2006 (UTC)

• JA: It was a good metaphor, but the A-frame that it was meta for got burned down in the last purge. As it is now, I think that it's helpful if the article alerts the reader to a sample of the language that he/she might actually encounter elsewhere. If it were necessary to pick one term, I guess that the most generic would be the one that reminds us of the inclusion relation $\subseteq$ and prepares us for the use of inclusion maps $i:G\hookrightarrow X$. Jon Awbrey

the nb

The point is that it is not a figure of speech that the framed relations are (k+1)-tuples; as defined, they really are (k+1)-tuples, and it is harmful to equivocate on that fact. What is true (and what may bother the reader) is that the tuples appear artificial; as indeed they are (it is quite clear that we don't naturally think that a relation (even a typed relation) is a tuple). This is one of the main reasons I consider this definition (and all its cousins) to be bad definitions (and especially bad in intro pedagogy)!!! What can be said (the absolutely true thing that you are trying to point out) is that this artificial device does capture a real feature of the preformal concept of "framed relation" that is being implemented: the fact that it comes in k+1 chunks. Randall Holmes 02:00, 29 January 2006 (UTC)

There's and then there's

It depends upon what the meaning of the word "is" is.

William Jefferson Clinton, 17 August 1998

JA: Randall, the reader advisory is doing its job as well as can be expected at that point in the text, so I count that one as "satisficed" for now. Still, a mathematical definition that says so and so is an n-tuple is not exactly the sort of thing that we would want to pin a cast in stone ontology on. Before we go about using "is" in anything that we might want to dignify as a properly "ontological" sense, as distinguished from merely a conventional or informational sense, we normally expect to see some argument for properties of invariance and so on. For example, the fact that the same information can be given as the (k+1)-tuples (X1, ..., Xk, G) or (G, X1, ..., Xk), or the pairs ((X1, ..., Xk), G) or (G, (X1, ..., Xk)), and so on, militates against reifying any one of those styles as the substance of the matter. Jon Awbrey 02:28, 29 January 2006 (UTC)

• RH: that's exactly why such definitions are bad. I never define a mathematical concept as a tuple, ever. (This sometimes leads me to frame (no pun intended) definitions in somewhat unusual ways; because I work in alternative set theory I can actually make the official definitions :-). If you define a relation in this way, you have to adopt a convention (and there is no convincing reason to pick one over the other). Once you pick a convention, you have to stick with it: that shape of tuple is a relation, forever after. That's how math works, formally. There is no kindness in giving a definition and then saying "kind of...sort of..." about it. There may be some merit in giving the definition and pointing out that we could have done it in other ways (so that the student understands that the definition really is artificial and doesn't have some inherent authority which she just doesn't get). Can you tell yet that I really think about these things? I teach philosophy of math, too :-) Randall Holmes 02:43, 29 January 2006 (UTC)
• Note that here we are actually talking about the same thing! Randall Holmes 02:48, 29 January 2006 (UTC)

• JA: Our druthers do not rule the roost here — non-reformer non-reform thyself. The persistent reader will run into these ways of talking — and if we provide them with a bit of propadeutic hermeneutic, that will be of service to them. Jon Awbrey 02:56, 29 January 2006 (UTC)

• I'm not suggesting reforming anything in the article! Randall Holmes 22:07, 29 January 2006 (UTC)

problem sentence

Gotta say that I think the intro is looking better, especially with that disclaimer (see binary relation for a more basic presentation) at the top. However, the next sentence A mathematical relation is an abstract object that captures formal aspects of a given type of concrete situation among a number of roles that things might play carries almost no information.... it's a very painful sentence. I'd rewrite it but I'm not even sure what it's trying to say. Dmharvey 11:46, 29 January 2006 (UTC)

Also, is it really necessary to say "The level of generality reflected in such a description is best approached in several stages, for example, as follows."? If that's the best way to do it, then why not just do it that way, instead of first explaining that this is what we're about to do? Dmharvey 11:48, 29 January 2006 (UTC)

Polymorphism, and plain ole perversity

• JA: I'm going to delete that remark about polymorphism for now, unless/until I can think of a non-bewildering way to explain it. Hard experience teaches that it's best to use different names, or at least different formats, for predicates (the functional kind) and sets, so I will copy the paragraph here and think on it some more. Jon Awbrey 02:36, 30 January 2006 (UTC)

Because a relation as above defines uniquely an n-ary predicate that holds for x₁, ..., x_n if (x₁, ..., x_n) is in G(R), and vice versa, the relation and the predicate are often denoted with the same symbol. So, for example, the following two statements are considered to be equivalent:

$(x_{1},x_{2},\dotsb )\in G(R)$

$R(x_{1},x_{2},\dotsb )$

• You should not do really this, because the described usage is common and should be presented. It will be more confusing if actual usages are not given... Randall Holmes 17:11, 3 February 2006 (UTC)

• JA: Yep, will probably put it back in a couple of days, byteing the bullet of a hopefuuly systematic ambiguity -- there's a story here to tell, or somewhere else to tell, about what happens when you try to get an partially automated reasoner to rechnen with human polysemeiosity, but never mind that now -- anyway, the question is just how to insulate it properly. And whether even to mention ploymorphism, as I know we deployed this forked tongue long before we ever forged that word as a hall pass for it. 22:10, 3 February 2006 (UTC)

Coming attractors, strange and otherwise

• JA: I'll set the bottle out to breathe a while before taking another draft, but here's a few notes to self and others on future party plans and residual dregs. Jon Awbrey 11:24, 30 January 2006 (UTC)

Bibliography

• JA: I don't know, but if the consensus is that this article should be "just the basics", then I can start moving some of the refs & bib to more specialized and theoretical articles. Jon Awbrey 11:24, 30 January 2006 (UTC)

Domain issues

(Text in progress, 30 January 2006) Jon Awbrey 11:24, 30 January 2006 (UTC)

Examples

• JA: It might be useful to develop the concrete examples a little more. The divisibility relation really belongs with binary relations, but it does seem to serve a useful purpose here. I have some 3-place examples that I can add later on. Jon Awbrey 11:24, 30 January 2006 (UTC)

History

• JA: Don't know how much people think should be here, but I can fold in a few notes and see how it goes. Jon Awbrey 11:24, 30 January 2006 (UTC)

To infinity and beyond

• JA: Right now the title is a misnomer, since the article as it is only covers finitary relations, and not even polyadic in the proper sense. But we can maybe wait and think on that. Jon Awbrey 11:24, 30 January 2006 (UTC)

Nonemptiness

Do sources stipulate that domains are nonempty? Not in my experience; after all, nothing goes wrong when they are empty, with either of the given definitions. Randall Holmes 19:38, 31 January 2006 (UTC)

• JA: I'm pretty sure that most pure and applied work that I can think of excludes empty domains, or puts them to one side very early in the game. And it's hardly more surprising than excluding a "factorization" like:

$1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 2$

from a doomain where you were sorta hoping for a unique factorization theorem before doomsday. It probably depends on what you mean by "nothing goes wrong". I'm $\varnothing$ if not a pragmatist about that. Jon Awbrey 20:10, 31 January 2006 (UTC)

• JA: Sorry, Lethe, but one can hardly anticpate the Fx on every browser. For instance, neither of my browsers can read some of the symbols that some folks like so much, but you don't hear me complaining about it, as if they'd do it on purpose especially just to irritate me in particular, though I am sure that's why they do it, do you? Jon Awbrey 14:20, 3 February 2006 (UTC)

Notes & Queries

• Move query to end and reply. Jon Awbrey 14:42, 3 February 2006 (UTC)

• I am confused by the second definition of relation (mathematics) and the consequent second definition of function (mathematics). I understand that there really is a very good reason for this second definition, but I am clueless as to what that very good reason might be, so please explain, and please let the § on formal definitions end where the formal definitions end. Bo Jacoby 12:39, 3 February 2006 (UTC)

• JA: Bo, it's best to append new talk at the bottom, as I only ran across your question by accident. But I desparately need more coffee right now, so'll get bak 2 u in a sec. Jon Awbrey 14:42, 3 February 2006 (UTC)

	Ye knowe eek, that in forme of speche is chaunge
	With-inne a thousand yeer, and wordes tho
	That hadden prys, now wonder nyce and straunge
	Us thinketh hem; and yet they spake hem so,
	And spedde as wel in love as men now do;
	Eek for to winne love in sondry ages,
	In sondry londes, sondry been usages.
	Geoffrey Chaucer, Troilus and Criseyde (1385)

• JA: Thanks for reminding me of this questying beast, as I've been meaning to get back to it under one of the headings above. I've actually begun to take a historical linguistic interest in Where and When, and now that we thinketh hem Why exactly did this chaunge in usage first begin to take place. By "Where" I joust mean in What parts of mathematicke, and so we come to the question "When". When did "We", Wel, some of "We", first start employing this "newefangel" forme of speche, anyway? But it's Freya's Day, TGIF, and many distraughts draw me off for the nonce. Jon Awbrey 18:48, 3 February 2006 (UTC)

• I don't think there's any very good reason for the second definition, and I'm a professional mathematical logician and set theorist... The first place (I think probably the only place in elementary mathematics) where the difference between the two definitions is important is in the definition of bijection. There is this cute idea that a bijection from A to B is a function which is "one-to-one" and "onto" (covers its target set). The problem is that from the graph of a function (the set of ordered pairs) one cannot tell what its intended target set is. Any function at all is "onto" its actual range. The only way to be able to identity a function as "onto" (a surjection) is to incorporate the intended target set as a component of the function. I believe that the correct approach is to define "surjection from A to B" as a function with range B. Then a function which is an injection from A to B and a (surjection from A to B) is a (bijection from A to B), and the definition of function (and so of relation) remains simple [note that it does not make sense to say that a function is a surjection or bijection without indicating the intended codomain under this usage). There are other reasons in more technical mathematics why one might want to consider types of functions ("functions from A to B") rather than all functions, but any interesting properties of "functions from A to B" can be expressed as properties with A and B as parameters; there is no reason to incorporate A and B into the function (or to incorporate domains and codomains into relations in general). However, all private opinions aside, the second definition is used and so should appear. Randall Holmes 17:09, 3 February 2006 (UTC)

Summary: A weak reason for the second definition to appear is that it is used somewhere in the literature. A strong reason for it to disappear is that it is confusing. The fair compromise is that it is moved to the bottom of the article tegether with a warning. Bo Jacoby 13:09, 8 February 2006 (UTC)

• JA: The second definition is used widely, both in the "purer" removes of mathematics and in the "impurer" realms of applications, for example, computer science, probability and statistics, systems engineering. People who continually self-report their lack of acquaintance with this and many other such facts speak only to their qualifications for determining the content of articles of general information. My teacherly advice to such people has always been that they open their minds, take some time to acquaint themselves with a novel subject matter, rather than rushing so rashly to reduce the subject matter to what is currently familiar to them. Jon Awbrey 14:06, 8 February 2006 (UTC)

• JA: Let me try to explain what I think is the motivation of the embedded, framed, or grounded version of the definition. This is not something that anybody ever explained to me, so I'm having to guess at what the underlying rationales might be. Unfortunately, the teachers that I had in mathematics almost uniformly (at random?) seemed to shy away from saying the reason why, so I'll have to leave it at my best guess.

• JA: Reason 1. I think that there's something analogous to the use of the function notation f : X -> Y that's going on here. A historical gloss from Cat.Work.Math comes to mind, so I will go dig that up and get back to it later today. Jon Awbrey 18:50, 8 February 2006 (UTC)

• I'm afraid, in spite of my actual preferences, that I have to back Awbrey on this. This definition is not merely advocated by a few eccentrics; it is widely attested, and actually even occurs in undergraduate discrete math books (where it does causes confusion!). So it must appear as an official definition. Alas. Randall Holmes 01:17, 11 February 2006 (UTC)

Typography

• JA: Maybe it's just the time of night, but that "damacles arrow over the vector notation" is making my eyes twitch, and they're not really vectors, anyway, but coordinate tuples, so I'm going to try replacing it with bold or roman bold and see how it looks. Jon Awbrey 06:28, 4 February 2006 (UTC)

Triadic vs. Ternary

Minor quibble: "Ternary relation" would be more in line with the terms unary and binary, which are both used extensively on Wikipedia. Also, a naive Google Test shows that "ternary relation" is used more often in the outside Web. Aragorn2 19:23, 19 April 2006 (UTC)

JA: Both are used quite a bit. "Monadic", "dyadic", "triadic" actually have a longer history, and they have a tradition of usage in some parts of logic and philosophy where they talk about 3-adic relations a lot. Using "binary" also creates havoc in computer science contexts, so it's often useful to call the relations "dyadic" there. There are whole literatures that will not change their ways, so it's best to get used to a mixed bag here. Jon Awbrey 19:56, 19 April 2006 (UTC)

Articles should be self consistent and indicate the existence of alternative terminology. --MarSch 11:52, 20 April 2006 (UTC)

Plenty of new characters

Unicode table Mathematical Operators ([1]) is full of relation symbols not discussed yet in the relation articles. Examples are: ≦, ≨, ≪, ≲, ≷, ≼ etc. Is someone able to discuss these symbols in the article? --Abdull 22:05, 28 May 2006 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Finitary relation/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

Lead is too complicated and should summarize the article. It might help to focus on binary relations. Geometry guy 00:01, 23 June 2007 (UTC)

Last edited at 03:44, 22 April 2009 (UTC). Substituted at 21:15, 4 May 2016 (UTC)