Talk:Binary relation.html

Mathematics portal

This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.

Mathematics rating:

B Class

Mid Priority

Field: Foundations, logic, and set theory

Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments.
Please add to or update the comments to suggest improvements to the article.
References needed. Geometry guy 14:13, 21 May 2007 (UTC)

1 comment by Dbachmann
2 Should all these properties have their own pages?
3 Functional relations
4 Another definition
5 error confusing < and <=
6 Relation negations in LaTeX
7 Definition of total?
8 Definition of composition
9 Distinction between class and set
10 Which concept nests in which?
11 Renaming things
12 Missing word "binary" somewhere
13 Relations "over" a set vs. "on" a set
14 relation vs binary relation
15 Linear relations?
16 Yanked linguistics/CS comments
17 Prime Division example in introduction
18 Symbols for Binary Relations

comment by Dbachmann

reflexive is a very common word -- this should be reflexive (mathematics). In linguistics, reflexive is the technical term for an action directed back at the agent. dab 21:12, 3 Sep 2004 (UTC)

You are probably talking about the article reflexive which was (I just changed it) a redirect to this page. Reflexive now redirects to Reflexive relation. Are there any articles about other meanings of "reflexive"? If so then we can turn Reflexive into a disambiguation page linking to each of the different articles. If there aren't any other "reflexive" articles, then until there are we should leave it as a simple redirect. Paul August 21:37, Sep 3, 2004 (UTC)

of course. I was 'blindly' linking to reflexive from Arabic grammar, and somebody removed my "wrong link" instead disambiguating reflexive. I will fix it myself when I get to it, no problem. dab 20:53, 4 Sep 2004 (UTC)

Should all these properties have their own pages?

Should all these properties have their own pages? And if so should that be under 'Reflexive' or under 'Reflexive binary relation'? -- Jan Hidders

The following pages now exist: reflexive relation, transitive relation, symmetric relation and antisymmetric relation Paul August 21:26, Sep 3, 2004 (UTC)

Functional relations

It seems to me that "mere" relations as "x > y", x and y of the given pair (x,y), can be repeated: {(5 > 1), (5 > 2), (2 > 1), (3 > 2)}. "x=5" is repeated. But "generated" relations --being the graph of a given function f: x --> y, y=f(x)-- as "y = 2x + 1", x and y of the given pair (x,y), can not be repeated: {(5,11), [(5,11),] (2,5), (3,7)} because when "x=5" is repeated, "y=11" is repeated, too. Yielding, duplicated pair member in the set, and being discarded immediatly. The explanation is mine but the idea is coming from: Costas Bush, http://www.cs.rpi.edu/courses/fall00/modcomp3/class1.ppt and //www.doc.eng.cmu.ac.th/course/cpe333/LectureNotes/chapter1_Introduction.pdf [Enrique Villar; mailto:evillarm@capgemini.es

The article already covers functional relations. --Zundark 12:48 Mar 3, 2003 (UTC)

Another definition

I have seen another definition of binary relation as an ordered triple R=(X,Y,G), where G is a subset of X × Y and is called the graph of R. This definition is better then the definition here as it avoid the confusion while talking about the function and its graph. Any comment? --Wshun

I have seen another definition of a graph - G(N, T), where N and T are set of nodes and connections/relations/associations/links/etc binding em correcpondingly. So, the notation G(R) used here for graph definition is merely unclear. Javalenok

So, in my opinion, the steps of constructing the graph G=(V,E) for a relation must be given. The set of vertices is the union N = (X v Y) which are connected by directed edges when xRy; that is, E={(x,y)|xRy}.

error confusing < and <=

"A partial order which is trichotomous is called a total order or a linear order." This is wrong. A partial order is antisymmetric and hence cannot be trichotomous.

To fix, either we also admit to call a relation < a partial order when it is: asymmetric (which has to be defined yet as: not (a<b and b<a)) and transitive, and then referring to this definition for adding trichotomy. Or we simply change "trichotomous" to "total" in the above sentence.

bo198214

Yes, the definition of "total order" given in the article was wrong. A total order is a partial order (i.e. reflexive, antisymmetric and transitive) which is total (i.e. everthing is related). I've fixed it now. Thanks for pointing out the error. Paul August 17:47, Sep 28, 2004 (UTC)

Relation negations in LaTeX

Does anyone know how to negate a binary relation signified by a letter (eg., R) in LaTeX? I figured that "\not R" would work, but it doesn't line up correctly. --Spikey 04:12, Nov 14, 2004 (UTC)

Definition of total?

What does it mean for a relation to be total? There are two different definitions in the article, one under special relations (for all x in X there exists a y in Y such that xRy) and one under relations over a set (for all x and y in X it holds that xRy or yRx); the latter one I have seen before. If the former one is also used in the literature, then it should be clarified that there are different definitions. -- Jitse Niesen 14:57, 16 Jun 2005 (UTC)

For the first meaning the term entire may be preferable. I used this term in the Axiom of dependent choice article, but I don't remember where I got it from. --Zundark 15:42, 16 Jun 2005 (UTC)

I now recall that total function is used in computer science for a function which is defined on all elements of its domain to distinguish it from a partial function (of course, it would be confusing to talk about entire functions in this context). But it does not matter which term is preferable, we should find out which term(s) is/are used in practice. -- Jitse Niesen 17:40, 16 Jun 2005 (UTC)

Definition of composition

What is the "correct" definition of composition. Some hours ago, an anonymous changed it from

S o R = { (x, z) | there exists y ∈ Y, such that (x, y) ∈ R and (y, z) ∈ S },

R o S = { (x, z) | there exists y ∈ Y, such that (x, y) ∈ R and (y, z) ∈ S }.

Now, Paul August has changed it back. I seem to remember that it has also changed some time ago,

The first definition has the advantage that it agrees with function composition (as Paul notes). However, I looked at some web pages found via Google (which is of course heavily slanted towards computer science), and it does seem that the second definition appears regularly. What should we do? Should we mention both? -- Jitse Niesen (talk) 21:35, 11 October 2005 (UTC)

I'm afraid there's no "correct" definition. Conventions differ, though in my experience the second definition is more common. The fact that it conflicts with function composition is not necessarily a problem; also, it is sometimes resolved in other ways, either by changing the order of arguments in function composition, or by swapping domain and range in the representation of functions by relations (i.e., f : X → Y is identified with {(f(x),x); x ∈ X }). I guess any definition would work here, provided we use it consistently, and mention the other possibility as well. -- EJ 19:13, 12 October 2005 (UTC)

We should mention both. But, since we define a function as a particular kind of a relation, I think we need to keep the present definition, which agrees with function composition, as the "primary" definition. Unfortunately this whole business is inherently confusing. Since both orders are used for functions and relations. However, in the case of functions at least, the order now used is fairly standard (see the discussion at function composition. The current standard defines f o g, so as to preserve the "natural" order of f(x), that is so that (f o g)(x) = f(g(x)). Being a category theorist, I would actually prefer the opposite "arrows order", whereby f followed by g, would "naturally" equal f o g. But alas it wasn't meant to be. Paul August ☎ 20:15, 12 October 2005 (UTC)

Distinction between class and set

JA: I humbly (but most sensibly) suggest that the class/set distinction, however important it may be in the long run, is definitely not 'line 1' material, since it can't be defined or discussed without getting into a controverted variety of different axiomatizations for set theory, and that the (non-pejoratively speaking) 'naive' reader should probably be given a (however illusorily) 'solid' foundation in naive set theory before being led down that particular garden of forking paths. Jon Awbrey 17:16, 18 January 2006 (UTC)

I disagree: the remark about membership and inclusion as examples of relations (not to mention general equality) requires some qualification if classes are excluded. Randall Holmes 17:40, 18 January 2006 (UTC)

A concrete example: if proper classes are not considered, the statements in the article on equality are wrong unless everything is restricted to a specific set. Randall Holmes 17:43, 18 January 2006 (UTC)

JA: I am not responsible for any of the content currently in this article, and only linked to it in connection with other topics. No doubt it can be improved. But the issues that you are raising at the "out-set", so to speak, do not need to be raised at that point, and will only serve to put a big cliff in the learning curve that will obstruct the general reader's ability to learn anything at all about the subject. I am very much for rigor with vigor, all in good time, but I am not for that, just for starters, so I can only recommend some thoughtful reflection and discussion here. Jon Awbrey 18:24, 18 January 2006 (UTC)

I moved the discussion of class/set to a subsection in binary relations (as requested by Stolfi) and omitted all reference to it in function (mathematics); I think a mention is needed in binary relations, but it doesn't need to be at the outset, and not even a mention is needed in the function article. When you're right, you're right. Randall Holmes 18:28, 18 January 2006 (UTC)

Which concept nests in which?

If relations have frames (as described in the relation (mathematics) article), 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: I think that you may be confusing relations with tuples. That lingo that goes "so and so is a k-tuple ..." is just an idiom that means "the information that is required to specify a so and so comes in k pieces". It may be confusing if one takes the "is" in too literal an ontological sense, rather than what is more properly understood as an informational sense. Be that as it may, the specification still invokes only a tuple, and not a relation, and so there is no unfounded loopiness here. And even if one forces a recursive definition on the matter, a singleton relation consisting of a single tuple is still a simpler sort of relation, and so the recursion goes to ground as it ought. I don't get the thing about labels — the "frame" is just the requisite context made explicit. And that's a good thing. Jon Awbrey 05:36, 21 January 2006 (UTC)

No, I'm not confusing anything. I am standing up for the old-fashioned view that a binary relation from A to B is best identified with its graph (a subset of the cartesian product of A and B) and not complicated with indications of its domain and codomain. If binary relations are defined in this way, then ternary relations (for example) are a kind of binary relation (I don't tout this as a virtue of the old approach -- it's merely an observation that things are different there). If relations are encumbered with explicit indications of domain, then this ceases to be true (binary relation is then a special case of k-ary relation). The domain and codomain labels are indications of type (indications of how the graph is intended to be used); my view (in general) is that the context in which an object is used rather than intrinsic features of the object should give type information (the context should not be part of the object, but just that -- its context). Please note though that this is a philosophical grumble (because in my writing I keep having to nod to the (IMHO misguided) general practice), not a proposal that articles should be written differently. Randall Holmes 00:36, 23 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)

Please don't. How would that help, at all? Binary relations are an important special case, but are certainly special. Charles Matthews 19:51, 25 January 2006 (UTC)

Missing word "binary" somewhere

I think there word "binary" in front of word "relation(s)" is missing somewhere. In other case if someone read those paragrafs out of text context it can be confusing and maybe false.

--Čikić Dragan 14:09, 10 February 2006 (UTC)

Relations "over" a set vs. "on" a set

The text i'm using uses the terminology "on" a set instead of "over" a set.. would it be appropriate to add a note mentioning the alternative usage?--Keith 00:42, 12 April 2006 (UTC)

relation vs binary relation

According to my experience, a "binary relation" is usually a relation from one set to itself; a "relation" is usually a (dyadic) relation from one set to another, and never an n-ary relation unless this is explicitely stated.

Thus, all (...) could be dropped in the following:

a function from E to F is a (functional) relation from E to F (m-maybe "on" E x F)
a relation (on E x F) is a (dyadic) relation from some set E to some set F
a (partial) order on E is a binary relation on E, i.e. a dyadic relation on E x E or from E to E
a n-ary relation on E_1 x E_2 x ... x E_n is an n+1 tuple R = (E_1,...,E_n, G) where G is a subset of E_1 x E_2 x ... x E_n, called the graph of R.

Do you really know (one? / several? / many?) places where an author speaking of a "relation" tacitely understands relations which are not dyadic relations (i.e. more than 2 arguments), without saying so explicitely?

If not, I would strongly argue for making some minor changes explaining more clearly this (IMHO) universial use of terminology. — MFH:Talk 16:14, 13 October 2006 (UTC)

Linear relations?

I am unfamiliar with the use of total and linear when referring to relations. Certainly they are synonymous in the context of (partial) orders. But consider the relation R on {a, b, c, d} defined by R = {(a,b), (b,c), (c,d), (a,c), (b,d), (d,a)}. While it makes sense to call R total, it seems to me squirrely to describe a structure that contains a directed cycle as linear.—PaulTanenbaum 05:16, 8 November 2007 (UTC)

There are two difficulties here, one about naming conventions and another technical.

First, the name of a mathematical entity does not necessarily imply all its properties, and a modifier doesn't necessarily create a subentity. A 'total order' is not an order that is total, it is a 'partial order' that is total (actual 'order' by itself is a bit fuzzy as a technical term (I don't think there is a community accepted definition though it seems closest to just 'is transitive')). Also, whatever technical meaning 'linear' has, it is only metaphorical in 'linear order', meaning it lays out in a line (more formally, there is exactly one way to lay it out on a line).

Second, technically, the realtion you gave is not a 'linear order' because of the last edge: (d, a). That forms a cycle, true, and you cannot have a cycle in 'total-' or 'linear order', so you probably meant to have that edge be (a, d). With that, the 'squirreliness' goes away.

Hahahaha4 (talk) 20:58, 10 September 2008 (UTC)

Yanked linguistics/CS comments

I'm going to delete the mods made anonymously that mention usage of binary relation in linguistics and computer science. Here's why... if the usage(s?) is (are?) distinct from the mathematical usage, then it (they) should be in a separate article treated through Wiki-style disambiguation. If, on the other hand, it (they?) is (are?) a special class of (isomorphic to?) the usage already described in this article, then the references to its use in linguistics and computer science should make this identity explicit. Until then, the comments confuse and cruft up this article.—PaulTanenbaum (talk) 13:17, 28 January 2008 (UTC)

Prime Division example in introduction

I'm wondering if this example should be changed to one with plain old integer division. I think its confusing because it gets people thinking that the binary relation can only relate two objects. (The only divisors of a prime are 1 and the prime itself)

Talking about division, without the prime number, would make the point that while the comparison is only between two numbers, it can be true in multiple instances.

I'm gonna change it in a week or so.

Jafraldo Ramierez (talk) 15:44, 3 July 2008 (UTC)

Readers who get confused by this must be careless readers. The article states immediately that for this example the prime 2 is associated with, among others, the integers -4, 0, 6, 10, but not 1 or 9; and the prime 3 with, among others, 0, 6, and 9. It is almost impossible to get from this the misconception that an element of one set can relate to only two elements of the other set. Also conversely, each prime is related to 0 and many primes are divisors of, for example, 2305567963945518424753102147331756070.

A reason not to replace the example by general integer divisibility is that in the present example the two sets, P and Z, are different. If the two sets involved in a relation are the same in all examples in the lede, readers might be tempted to assume that each binary relation is an endorelation (homogeneous). --Lambiam 23:43, 6 July 2008 (UTC)

Symbols for Binary Relations

I reverted the changes from the curly to the straight LaTeX symbols because the former are for general binary relations (of the given kind), the straight ones for particular binary relations. For example $a \preceq b$ stands for -any- partial order, but $a \le b$ stands for the particular 'less-than' relation for numbers. Also, $\approx$ does not stand for an equivalence relation (approximation does not satisfy transitivity), and $\equiv$ is a specific equivalence relation on integers. Hahahaha4 (talk) 19:21, 25 September 2008 (UTC)

Sorry, but what you are saying is complete nonsense. In order theory and algebra (lattice theory), orders (and preorders) are always denoted $\le$ by default, other symbols being employed only to avoid confusion when several distinct orders are considered at the same time, and even then it is more common to use indices like $\le_1$ , $\le_2$ rather than odd symbols like $\precsim$ . In fact, I can't remember ever seeing $\precsim$ used for such purpose, unlike $\preceq$ or $\sqsubseteq$ . The reality is exactly opposite to what you claim, generic orders are usually denoted by $\le$ , whereas $\preceq$ is typically used for specific (pre)orders (e.g., elementary submodels in model theory). And yes, both $\approx$ and $\equiv$ are used to denote various equivalence relations, not just the two specific relations which you mention. — Emil J. 14:13, 26 September 2008 (UTC)

It was my impression that more recent usage favors the curly symbols for abstract relations and straight for specific relations. But I could have narrow experience that is also skewed by LaTeX/CS culture. Hahahaha4 (talk) 20:16, 26 September 2008 (UTC)

I agree with EmilJ, and I and I don't think it's a question of publication dates. More likely a matter of different conventions in different fields. I would imagine that many school teachers agree with your comments (as less confusing for the kind of children, in the same way that the same letter in school physics always has the "same" meaning), but the universal practice in the mathematical community is as described by EmilJ (as much more convenient). --20:24, 26 September 2008 (UTC)

Very context-dependent. In some contexts, "≤" is used for any of many different partial orderings. Michael Hardy (talk) 04:54, 27 September 2008 (UTC)

Some texts using $\le$ for general partial order: Rutherford, "Introduction to Lattice Theory" (1965); Welsh, "Combinatorial Mathematics and its Applications" (1971); Preparatah, Yeh "Introduction to discrete structures" (1972); Oxley, "Matroid Theory" (1992); Spiegel, Carmichael "Incidence algebras" (1997); Davey, Priestley, "Introduction to Lattices and Order" (2002).

Although I've seen mostly just $\le$ , only occasionally $\sqsubseteq$ , and rarely $\preceq$ , perhaps there should be a short section listing all of these symbols, stating that they are all sometimes used to denote ordering? linas (talk) 13:29, 27 September 2008 (UTC)