Talk:Binary relation

From Wikipedia, the free encyclopedia

WikiProject Mathematics
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

Contents

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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}.

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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 },

to

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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)