# Talk:Binary relation

Page contents not supported in other languages.
WikiProject Mathematics (Rated B-class, Mid-priority)

## Special types of binary relations

This section seems full of non-standard definitions, you might want to actually provide a solid reference for there first use, or who proposed them. — Preceding unsigned comment added by Differentiablef (talkcontribs) 03:59, 30 July 2011 (UTC)

### Not encyclopedia material

I concur. Some authors are trying to use Wikipedia, not as reference, but as a marketing tool for their preferred terminology. In particular, neither "serial relation" nor "connex relation" is common in the literature, outside, perhaps of a limited subgroup within computer science. 24.4.62.241 (talk) 22:59, 12 March 2019 (UTC) (besides, the word "serial" is a horrible word choice for what it is describing.) — Preceding unsigned comment added by 24.4.62.241 (talk) 23:02, 12 March 2019 (UTC)

## 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}.

In the current definition it says:

"The statement (x,y) ∈ R is read "x is R-related to y"".

Shouldn't it be like that:

"The statement (x,y) ∈ G is read "x is R-related to y""?

I mean (x,y) is an element of the Cartesian product X × Y, R refers to the triple (X,Y,G) so "(x,y) ∈ R" doesn't make sense. On the other hand "(x,y) ∈ G" does, as that's what G defines: all the ordered pairs (x,y) of X × Y such that x is R-related to y, no? —Preceding unsigned comment added by PhaseQ (talkcontribs) 14:44, 16 January 2010 (UTC)

--PhaseQ 14:45, 16 January 2010 (UTC)

## 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 yY, such that (x, y) ∈ R and (y, z) ∈ S },

to

R o S = { (x, z) | there exists yY, 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 : XY is identified with {(f(x),x); xX }). 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)

I think, I believe, that there is an error in the example given of composition where it is defined. I hesitate to fix it because I'm sure so many eyes have already passed over it that I find it hard to believe that they're all wrong and I'm right, but I will go ahead. As I read these comments it seems that the concensus is that f o g is "f after g" as is usual in most branches of math. Akurn (talk) 03:35, 11 June 2015 (UTC)

S o R is indeed read as S after R. Though, the given examples do seem counter-intuitive to that respect: "is mother of" o "is parent of" yields "is maternal grandparent of". When one is familiar with function composition, this (intuitively but incorrectly) reads as: x = mother(parent(z)). That means x is the grandmother of z, which differs from the definition of binary relations. To avoid confusion, I clarified the presence and meaning of an existing y: if x is the parent of y and y is the mother of z, then x is the maternal grandparent of z. sourcedennis 14:30, 27 May 2021 (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.

--User:Vanished user 8ij3r8jwefi 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)

Furthermore, this article is inconsistent: the very first sentence begins "In mathematics, a binary relation on a set A is ...". But the 3rd section says "If X = Y then we simply say that the binary relation is over X. " I haven't read "over" anywhere, my books always use "on". 145.97.197.129 (talk) 19:25, 6 August 2010 (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)

No, the ordered pair (d, a) was precisely my point. I can see some sense to characterizing the relation R above as total because for every pair of distinct elements x and y in the ground set, at least one of xRy and yRx holds. But the article asserts that for arbitrary binary relations on a set, the terms total and linear are synonyms. And I constructed R precisely to highlight the squirreliness of applying the label linear to a relation that contains a cycle. The problem does not arise for partial orders (where total and linear are indeed synonyms) because they are by definition transitive, and hence acyclic.
Would anyone out there care to confirm the synonymy of total and linear for arbitrary relations? If I don't eventually hear some such confirmation from somebody, the sheer squirreliness will eventually move me to deleting "(or linear)."—PaulTanenbaum (talk) 00:31, 3 September 2009 (UTC)
I've removed it per WP:V. "Linear relation" usually means something else in the context of vector spaces. Pcap ping 09:22, 3 September 2009 (UTC)
This book give a linear relation definition that is the total relation definition.--Malore (talk) 00:48, 13 June 2018 (UTC)

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 ${\displaystyle a\preceq b}$ stands for -any- partial order, but ${\displaystyle a\leq b}$ stands for the particular 'less-than' relation for numbers. Also, ${\displaystyle \approx }$ does not stand for an equivalence relation (approximation does not satisfy transitivity), and ${\displaystyle \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 ${\displaystyle \leq }$ 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 ${\displaystyle \leq _{1}}$, ${\displaystyle \leq _{2}}$ rather than odd symbols like ${\displaystyle \precsim }$. In fact, I can't remember ever seeing ${\displaystyle \precsim }$ used for such purpose, unlike ${\displaystyle \preceq }$ or ${\displaystyle \sqsubseteq }$. The reality is exactly opposite to what you claim, generic orders are usually denoted by ${\displaystyle \leq }$, whereas ${\displaystyle \preceq }$ is typically used for specific (pre)orders (e.g., elementary submodels in model theory). And yes, both ${\displaystyle \approx }$ and ${\displaystyle \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 ${\displaystyle \leq }$ 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 ${\displaystyle \leq }$, only occasionally ${\displaystyle \sqsubseteq }$, and rarely ${\displaystyle \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)

## Extended? (Or extendable?)

The term "extended" is not explained in the section about "Relations over a set" (bottom of the section) FredrikMeyer (talk) 10:39, 1 September 2009 (UTC)

It was overlooked when Hans Adler corrected the terminology in that section a few months ago. Thanks. —Dominus (talk) 13:28, 1 September 2009 (UTC)
What did it even mean? It was also mentioned in inverse relation with a link to here (where it isn't defined [now]), but I couldn't find it in the literature, so I've deleted the sentence about that over there. 86.127.138.67 (talk) 07:47, 19 April 2015 (UTC)
I see it meant serial. 86.127.138.67 (talk) 07:50, 19 April 2015 (UTC)

## Functions between relations?

I had expected to see something about "functions between relations on a set" in this article. Namely, given two relations (R on X) and (S on Y), we can consider functions f:X->Y which are relation-preserving in the sense that xRx' implies f(x)Sf(x'). This yields a category whose objects are pairs (X,R) with X a set and R a relation on X; an arrow (X,R) -> (Y,S) is a relation-preserving function X->Y.

A special case of relation-preserving functions is when the relations are posets: then relation-preserving functions are the monotonic ones. 145.97.197.129 (talk) 16:12, 7 August 2010 (UTC)

## Error in codomain/domain terminology?

In the section http://wiki.alquds.edu/?query=Binary_relation#Is_a_relation_more_than_its_graph.3F there is a sentence that goes "Most authors insist on distinguishing between a function's codomain and its range." I think this should be "a function's domain and its range or co-domain." Or am I mistaking what is being said here? Neil (talk) 13:47, 12 July 2011 (UTC)

You're mistaken. Some authors do not distinguish between the codomain and the range (e.g., Jean E. Rubin, Set Theory for the Mathematician). Most do. — Arthur Rubin (talk) 16:45, 12 July 2011 (UTC)

## Restriction definition

The section https://secure.wikimedia.org/wikipedia/en/wiki/Binary_relation#Restriction defines restriction only for a relation on a set S, i.e. over S×S. But a restriction may be defined for a relation over S×T, and in such case the current definition is wrong. See https://secure.wikimedia.org/wikipedia/en/w/index.php?title=Restriction_%28mathematics%29&oldid=451456911 and http://www.proofwiki.org/w/index.php?title=Definition:Restriction/Relation&oldid=66420. — Preceding unsigned comment added by Rosivaldo (talkcontribs) 16:37, 24 October 2011 (UTC)

## Homomorphisms?

Isn't there a notion of homomorphism of relations similar to that of orders? i.e. for relations R from ${\displaystyle M_{1}}$ to ${\displaystyle M_{2}}$ and S from ${\displaystyle N_{1}}$ to ${\displaystyle N_{2}}$, a pair of functions ${\displaystyle h=(h_{1}:M_{1}\to N_{1},h_{2}:M_{2}\to N_{2})}$ with ${\displaystyle \forall m_{1}\in M_{1}:\forall m_{2}\in M_{2}:R(m_{1},m_{2})\Rightarrow S(h_{1}(m_{1}),h_{2}(m_{2}))}$? Shouldn't something like this be mentioned in the article? -- 132.231.198.153 (talk) 10:08, 7 December 2011 (UTC)

## Correspondence definition

Page 1331 of Encyclopedic dictionary of Mathematics seems to define correspondence just like relation without the left and right total bit, in fact no real difference from abinary relation. Dmcq (talk) 13:27, 14 February 2012 (UTC)

## Intro

change 'The concept of function is defined as a special kind of binary relation' to 'A function with one domain variable is a special kind of binary relation' ? — Preceding unsigned comment added by 72.160.223.249 (talk) 12:01, 23 June 2012 (UTC)

## Left- vs right- uniqueness

I cannot believe that "left-unique" means injective instead of functional, and that "right-unique" means functional instead of injective.

I can't verify the claim, because I don't have the referenced book, and it costs a shitton of cash. Can someone verify that the terms "left-unique" and "right-unique" are not mixed up on Wikipedia? — Preceding unsigned comment added by 31.46.91.77 (talk) 13:49, 15 January 2013 (UTC)

I can see the referenced page through Google books, and it agrees with our article. In any case, I find the terminology perfectly natural: right unique means that elements on the right-hand side corresponding to a given element are unique (i.e., the relation is a partial function), and symmetrically for left-unique.—Emil J. 14:11, 15 January 2013 (UTC)
And I find an opposite terminology perfectly natural: right-unique means that elements on the right-hand side are unique (i.e., an element appears on the right-hand side at most "once", i.e., the relation is injective). — Preceding unsigned comment added by 81.182.174.55 (talk) 17:38, 15 January 2013 (UTC)
Are these terms standard terminology? They seem natural to me, but I had never heard them before reading wikipedia, and I wonder if the article should really mention them at all. Are there any books other than M. Kilp, U. Knauer, A.V. Mikhalev, "Monoids, Acts and Categories" (ISBN 3-11-015248-7) that use these terms? – Tobias Bergemann (talk) 14:26, 15 January 2013 (UTC)
For what it's worth, there's a discussion at MathOverflow at http://mathoverflow.net/questions/17854, where people wonder about these terms. Specifically the comment by Harald Hanche-Olsen (associate professor at the Department of Mathematical Sciences at the Norwegian University of Science and Technology): "I certainly did not know the terms left-unique and right-unique, and moreover when I tried to guess what they meant, I ended up with the opposite meanings. Left-unique, I reasoned, must mean that a pair in the relation is uniquely determined by its left member, i.e., functional. But that is the definition of right-unique. Go figure." –Tobias Bergemann (talk) 14:35, 15 January 2013 (UTC)
A web search suggests that various authors use these terms, it’s certainly not just one book. I think it does not do any harm to mention them, even though it is a minority usage.—Emil J. 14:49, 15 January 2013 (UTC)
I also never saw those usages in mathematics, but there are lots of hits on Google Books for "left unique" relation. The same issue with "left" and "right" not having clear meanings also happens in other places, e.g. group actions. — Carl (CBM · talk) 15:03, 15 January 2013 (UTC)

After doing the search you suggested, it seems these four {left-,/right-}{unique/total} terms appear more common in a computer science context. For example, they also appear (with no change in left-right meaning) in:

• Mathematical Foundations of Computational Engineering: A Handbook by Peter J. Pahl and Rudolf Damrath, p. 506
• Semantics of Sequential and Parallel Programs by Eike Best, p. 19
• Modelling of Concurrent Systems by Robert-Christoph Riemann, p. 21

Since the book by Kilp et al., although written by mathematicians, also deals with automata (as acts), I suspect they were more aware of this terminology than other mathematicians. Why they preferred it is another matter, which I can't speak of. I have yet to find these terms in any book that was published before 1990, so I suspect they are of somewhat recent coinage, although I can't yet say who came with them. An earlier mention I found is in a 1991 IJCAI paper (and the associated 1990 technical report) "How to Prove Higher Order Theorems in First Order Logic" by Manfred Kerber. An even earlier mention appears in a 1985 paper/chapter doi:10.1007/978-3-642-69962-7_4; this text does not even bother to define the terms, so I guess it assumed they were well-known to its intended audience (people dealing in algebraic specifications). Some1Redirects4You (talk) 03:57, 20 April 2015 (UTC)

According to [1] it seems the terms were introduced by Bourbaki, but I have yet to confirm them. It seems plausible though given the group's propensity for definitional symmetries and lack of fear in coining new terms like magma (algebra). Some1Redirects4You (talk) 04:51, 20 April 2015 (UTC)

Well, I can't find it the terminology as such in Bourbaki, so the authors of the pdf above might just mean that the notions are defined there (but not necessarily in that terminology). But I found at least "left total" defined in a pretty ancient 1967 book [2] Lattice Theory by Helmuth Gericke. I can only see snippets in Google though, and he doesn't seem to define the left/right unique but he does use the term "bi-unique" for bijective. Some1Redirects4You (talk) 05:19, 20 April 2015 (UTC)

## Error in the transitivity in relations

It's written that "The transitive relation is irreflexive if and only if it's asymmetric" how is that? if I defined a relation xRy that holds if both X and Y are even numbers, so it is clear that it is transitive - if xRy is valid and yRz is valid then xRz is valid - and symmetric, if xRy is valid then yRx is valid too, however it is irreflexive in the same time, for example 3R3 is false! so it is Symmetric, Transitive and Irreflexive in the same time. Mo-Cubed (talk) 22:53, 22 October 2014 (UTC)MCubed

Your example is not irreflexive since that property must hold for all x and you have that 2R2 is true. Bill Cherowitzo (talk) 03:45, 23 October 2014 (UTC)
You are right in that your relation isn't reflexive, since not 3R3. But it isn't irreflexive, since 2R2. I added a note to the article about this issue. - Jochen Burghardt (talk) 04:18, 23 October 2014 (UTC)

## Section titled "Examples of common binary relations"

It should probably be merged with (or at least turned into a subsection of) the section on [types of] endorelations. Arguably functions are very common examples of relations too... Some1Redirects4You (talk) 03:49, 20 April 2015 (UTC)

## Relations as "usually defined"

In a random sample of about 40 textbooks from diverse areas of mathematics (algebra, analysis/calculus, discrete math, logic, set theory), all sources define relation simply as a set of ordered pairs, nothing less, nothing more. A wise decision: this allows defining the composition of arbitrary relations.

Only a directed search (internet, own book collection, book exhibitions at various math conferences) yielded a definition for a related concept based on triples (A, B, G) in two sources: Bourbaki, Théorie des Ensembles page 72, and Encyclopedic dictionary of Mathematics, page 1331. Invariably, the triples-based concept is called 'correspondence'. One of its many disadvantages is that composition of the correspondences (A, B, G) and (C, D, H) is defined only for the restricted special case B = C.

The evident conclusion is that the current Wikipedia article represents things backwards, claiming that relations are "usually" defined as triples, "sometimes" called correspondences, whereas in reality relations are usually defined as sets of ordered pairs, and the triples variant (a different concept) is usually called a correspondence.

The absence of any evidence or reference for the false claim that a relation is "usually" defined as a triple should be a warning to all readers that something is askew in the Wikipedia article (Aside: Bourbaki is regularly misquoted by Wikipedia editors who did not get themselves a copy of the relevant book). Interested Wikipedians can obtain an annotated bibliography by sending me an email, Boute (talk) 11:20, 24 August 2015 (UTC)

I tend to agree with you. On the other hand, some characteristics of binary relations make sense only when dealing with them as triples; for example, totality. — Arthur Rubin (talk) 18:38, 24 August 2015 (UTC)
Careful use of existing terminology offers a simple way out: totality is the dual of onto-ness (for functions). Just as many authors (extensive bibliography on request) say that a function is onto Y (not just "onto"!) iff its range is Y, a function or relation is total on X iff its domain is X (domain/range being defined as the set of first/second elements of the pairs). So the triples are not needed. Moreover, it seems unwise to make a simple concept (set of pairs) more complicated (triple) just to accommodate a (lazy?) shorthand, at the cost of ruining generality, e.g., for composition and inverses. Anyway, I'd be interested in references defining relations (rather than correspondences) as triples.
BTW, in my previous post, I forgot to mention that [3] translates Bourbaki into his own terminology. Bourbaki simply defines a function as a functional graph (page 77 in Théorie des Ensembles), where a graph is set of ordered pairs (nowadays called relation by most authors, whereas Bourbaki uses the term relation for an assertion with two variables - p. 16). Bourbaki briefly experimented with the triple concept for functions (p. 76) but abandons it on the next page in favor of the more common functional graph definition of function. In his May 1957 article "Nicolas Bourbaki", Halmos pokes a little fun at the group for its temporary deviations from common terminology! Boute (talk) 03:12, 25 August 2015 (UTC)

## Confusing Sentence Order in definition of Transitive Relation

The definition of transitive offers a statement about transitive relations (connecting their irreflexiveness and asymmetry) and then gives an example of two relations, both of which are irreflexive and asymmetric, but one of which is transitive and the other of which is not. These two sentences should be reversed.

Not sure if this is worthy of the talk page or if I should just make the change, but I've only ever done small edits. clahey (talk) 00:05, 6 October 2015 (UTC)

Done Be bold, you should have done this yourself. If you make a mistake, someone is very likely to spot it and correct it, so don't let that hold you back. The trick is to not involve your ego with your edits − you do the best you can, knowing that you can't always be perfect. Bill Cherowitzo (talk) 01:53, 6 October 2015 (UTC)

## Tag on section "Is a relation more than its graph?"

There is a tag on the section "Is a relation more than its graph?" saying it is confusing and requires clarification. I just reverted a change where someone was saying a relation was always a correspondence as in the formal definition section before rather than the looser definition often use din logic. So it looks like the tag is needed an a bit more clarification is in order but I can't see how to phrase it better. Dmcq (talk) 21:18, 4 January 2016 (UTC)

That section is not simply misleading, but plain wrong: A Graph consists of both a set of vertices and a set of edges. In particular, a graph can have vertices without edges. The section here claims a graph would consist of its edges. --84.153.18.145 (talk) 08:19, 8 October 2016 (UTC)
It's graph of a relation, not graph (discrete mathematics). I repeated the wikilink in the article's section. - Jochen Burghardt (talk) 13:58, 8 October 2016 (UTC)
This question isn't well posed, because it presumes that a relation is conceptually distinct from it's graphical representation, and they are not. An algebraic OR a graphical description of a given mapping may be unclear; but this is usually due to the fact that the writer implied information that the reader failed to infer.

A graph of a relation only exists at the points over the domain and range where the relation is defined. At the co-ordinates within the cross product of the domain and range, a graph depicts the point at that co-ordinate with one color if it belongs to the relation; otherwise, it marks that point in another color.

Outside of the area where the relation is defined, there is no point to mark one way or another; it's not part of the graph being drawn.

For maximum clarity, the parts of the page where points on the graph do not exist should be visually distinct from the points where the graph exists (for example, drawn in a different color); but mathematicians traditionally saved time and ink by only marking the points on the page where the relation is defined. In cases where it matters, the domain and range are typically stated; where they are not, a specific domain and range is typically implied by context within a given branch of mathematics: anything left unstated within a mathematical formula is implied by context to be "usual one" for the branch of math being studied (eg. the domain and range of a function are real numbers when doing Real analysis, Complex numbers with Complex Analysis, etc.) — Preceding unsigned comment added by 206.108.127.16 (talk) 19:36, 20 December 2018 (UTC)

## Definition of "reflexive"

If X is the set {1,2,3} then is the relation {(1,1),(2,2)} a reflexive binary relation "on" the set X?

The definition of "reflexive" in the current article is: "for all x in X it holds that xRx." By that definition, a reflexive relation "on" {1,2,3} is required to contain the ordered pair (3,3).

Is the intent of the definition of "R is a reflexive relation on X" to require that each element of X must appear as the first member of an ordered pair of R ?

Tashiro~enwiki (talk) 23:05, 4 November 2016 (UTC)

Yes, that is the intent. This is the standard definition and without that condition "reflexive" would be a rather useless property. Bill Cherowitzo (talk) 02:53, 5 November 2016 (UTC)

## Serial/Total

There are two names given for the same type of relation given in the current version of this article. Both left-total relation and serial relation are described in different sections. In fact, both names have references supporting them, now mentioned on Serial relation. Consolidation of the descriptions is recommended for reading consistency. — Rgdboer (talk) 03:31, 13 April 2018 (UTC)

Clarification comes with a new article: Connex relation. Since this property of a relation is key to a total order, there have been some references to a connex relation as a total relation. Such reference can be avoided due to a 2011 source for connex. Intensified scrutiny of relations due to modern data massage is clearing up some obsolescent terminology reflecting the long but low-profile study of this topic. — Rgdboer (talk) 21:58, 23 May 2018 (UTC)

I agree with these clarifications. However, I suggest to keep warning footnotes about the old terminology, both at total order (there explaining the name "total" by historical reasons), at connex relation (there hinting at a former name that is still in use); possibly also at the "connex" item in binary relation#Relations over a set. - Jochen Burghardt (talk) 07:33, 24 May 2018 (UTC)

## Graph theory

According to Roland Fraisse in Theory of Relations (1986) page v:

Relation theory intersects only weakly with graph theory, with which it is sometimes still confused. Firstly, techniques in relation theory only rarely distinguish between graphs, i.e. symmetric binary relations, and relations of arbitrary arity. Additionally, as opposed to graph theory, in relation theory one considers equally two truth values (+) and (–) taken on by a relation with base E for each element of E2 (or of En for the arity n).

A binary relation R between arbitrary sets (or classes) X (the set of departure) and Y (the set of destination or codomain) is specified by its graph G, which is a subset of the Cartesian product X × Y. The binary relation R itself is usually identified with its graph G, but some authors define it as an ordered triple (X, Y, G), which is otherwise referred to as a correspondence.[1]

Apparently the author of this "formal definition" wanted to include infinite binary relations so the link for "graph" is 2-dimensional graph, not graph (discrete mathematics). Further, this definition with XY, is for a heterogeneous relation. In graph theory one uses a single set of vertices.

Editing an article with 200 watchers requires discussion to reach consensus, thus this Talk. — Rgdboer (talk) 23:20, 21 May 2018 (UTC)

I'm afraid I didn't get your point. You arguments appear to be in favor of changing the "graph" link from graph (discrete mathematics) to 2-dimensional graph, but the latter link is already in use in the article. Do you suggest to change it to n-dimensional graph, to cover also n-ary relations? Or what else is your intention? - Jochen Burghardt (talk) 11:12, 22 May 2018 (UTC)

No, my point is that the notion of a graph (whichever type) is unnecessary in a definition. In fact, for heterogeneous relations it would be necessary to refer to bipartite graphs. A section lower in the article explaining that a finite or denumerable homogeneous binary relation can be illustrated by a graph (discrete mathematics) would be appropriate. The current link to 2-dimensional graph only confuses the subject. Even the well-regarded book Relations and Graphs by Schmidt does not try to blend the subjects as this definition does. Further, a relation and its complement are taken on par, but not so with a graph, according to Fraisse. — Rgdboer (talk) 23:16, 22 May 2018 (UTC)

I agree with Rgdboer. The definition of the lead is perfectly correct and does not need introducing a more complex structure (that of graph) for being formalized. IMO the section "Formal definition" must be renamed "Interpretation in terms of graphs" (or something like that) and completely rewritten. Among many issues, this section begins with the blatant error of talking of Cartesian product of classes, which is certainly defined in some extensions of ZFC, but certainly not in standard mathematics. Also, a section on basic properties and operations on relations is lacking (identity relation, reciprocal, composition of relations, ...) D.Lazard (talk) 10:37, 23 May 2018 (UTC)
@Rgdboer: You should be aware that 2-dimensional graph and graph (discrete mathematics) are completeley unrelated notions. Your link bipartite graph belongs to the latter area and has nothing to do with the current link in the article. — Trying to paraphrase the section "Is a relation more than its graph?", I think its intention is as follows: in order to be able to define "left-total" and "right-total", the "set of departure" and "set of destination" of a relation must be available. Hence, a relation is defined (by some authors) as a triple (X,Y,G), with X and Y arbitrary sets, and G a subset of the cartesian product X×Y. In order to have names for the three components, they are called "set of departure", "set of destination", and "graph" of the relation, respectively. (Then a relation is e.g. left-total iff its set of departure agrees with its domain, the latter obtained by projection from its graph.) G is far from being a graph (discrete mathematics), but is it in fact a 2-dimensional graph (naively assuming that both X and Y can be depicted along some line). In the table "1st example relation" in the article, X is {ball,car,doll,gun}, Y is {John,Mary,Ian,Venus}, and the graph is the set of points in the 4×3 space that are marked "+". The latter is a graph in the same sense as the "graph of the function ${\displaystyle f(x)={{x^{3}}-9x}}$" shown at 2-dimensional graph is, but not in the sense as "labeled graph on 6 vertices and 7 edges" shown at graph (discrete mathematics) is.
I looked at the 1976 German translation of Halmos' Naive Set Theory, Ch.7 "Relations". Initially, Halmos omits X and Y and defines a relation just to be a set of ordered pairs (p.39/40). Later (p.41), he introduces the notion of "R being a relation from X to Y". When he comes to functions (Ch.8), he defines "a function f from X to Y" to be a relation from X to Y such that for each X in X there is exactly one y in Y such that (x,y) is in f. This appears to be the first place where X and Y are actually used. — This way, Halmos avoids defining a relation as a triple, and the notion of a "graph of a relation". The triple-approach used in the wikipedia article appears inspired by the usual style automata theory definitions (see e.g. Pushdown_automaton#Formal definition).
If we can agree on the Halmos approach, the section "Is a relation more than its graph?" could be rewritten accordingly, by saying e.g. "The same set R of pairs can have different properties when used in a relation R from X1 to Y1 and a relation R from X2 to Y2. For example (...ball,car,doll example...)".
@D.Lazard: I guess rephrasing along the Halmos approach would be in you sense, too. As for classes, I agree to omit that notion in the introductory section(s); but I'd like to have at least a footnote somewhere about them. When it comes to "∈" itself, one often wishes to treat it like a relation, saying that it should be irreflexive, well-founded, etc. Allowing classes (in whatever axiomatization) makes it possible to do this. — There is a section "Operations on binary relations", but I agree it should be extended. I'm missing "empty relation" and "universal relation", too. - Jochen Burghardt (talk) 08:38, 24 May 2018 (UTC)

Halmos chapter 7 only goes up to equivalence relation. Thank you for citing one source at least, though not on the relation-graph connection. Reviewing Relations and Graphs produces a definition of a 1-graph on page 6, with an "associated relation", and a simple graph on page 11, with an irreflexive, symmetric adjacency relation. If B is the relation of a 1-graph, then ${\displaystyle {\bar {I}}\cap (B\cup B^{T})}$ is the adjacency of the associated simple graph. Heterogeneous relations are introduced in chapter 4, starting with bipartite graphs. Chapters 5, 6, and 7 also address graphs. A 1989 version is Relationen und Graphen ISBN 3-540-50304-8. Who are these authors that use the triple (X,Y,G)? Your assertion that this approach is also found in automata theory has a link, but there is no reference in the linked paragraph. It mentions a transition relation with arity 7, but this example does not justify unnecessary complication to this article on binary relations. It does prove that relations are important in computer science. — Rgdboer (talk) 22:07, 24 May 2018 (UTC)

Just a reply concerning automata theory sources: I usually prefer John E. Hopcroft and Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Reading/MA: Addison-Wesley. ISBN 0-201-02988-X.. They define every kind of automaton as some tuple. The follow-up edition is currently available online: John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman (2003). Introduction to Automata Theory, Languages, and Computation (PDF). Upper Saddle River/NJ: Addison Wesley. ISBN 0-201-44124-1. See e.g. Sect.2.2.1, p. 62-->46 for a 5-tuple definition of deterministic finite automata. — Please note that I don't suggest in any way to adopt the tuple notation for binary relation. On the contrary, I agree with you that it is an unnecessary complication (compared e.g. to Halmos). I haven't available any of the references [1][2][3][4] cited in binary relation#Formal definition, so I can't check which of them uses the triple definition.- Jochen Burghardt (talk) 21:55, 25 May 2018 (UTC)

References

## Rectangular

Currently the article contains this paragraph:

In automata theory, the term rectangular relation has also been used to denote a difunctional relation. This terminology is justified by the fact that when represented as a logical matrix, the columns and rows of a difunctional relation can be arranged as a block diagonal matrix with rectangular blocks of true on the (asymmetric) main diagonal. [1] Other authors however use the term "rectangular" to denote any heterogeneous relation whatsoever (Winter 2007).

These sources have been confirmed to use the term rectangular relation as described. However, Jacques Riguet has used the term in another sense (as described in his article). His usage has been taken up by Gunther Schmidt in his books on relations. Suggestions are requested for properly digesting these various uses of the same term in the study of relations. — Rgdboer (talk) 21:42, 9 June 2018 (UTC)

In the spirit of WP:BOLD a new article heterogeneous relation has been started. The various uses of "rectangle" with respect to relations is described, with references. At 41 kB this article is getting large. Most of the content here concerns homogeneous relations ("binary relation on a set"). The new article can absorb heterogeneous material, such as difunctional. Please, don't be shy if there is something you don't like. — Rgdboer (talk) 22:58, 17 June 2018 (UTC)

References

1. ^ Julius Richard Büchi (1989). Finite Automata, Their Algebras and Grammars: Towards a Theory of Formal Expressions. Springer Science & Business Media. pp. 35–37. ISBN 978-1-4613-8853-1.

## Relation (mathematics) redirect page

This redirect page is potentially confusing, since relation can refer to other finitary relations instead of binary relations. I've seen several Wikipedia articles that link to this page in error, when they should link to finitary relation instead. Should we re-target it to Relation#Mathematics to avoid this misunderstanding? Jarble (talk) 06:35, 19 June 2018 (UTC)

In mathematics, binary relation is clearly a primary topic for relation (unless otherwise specified, relation means generally binary relation). So, if "relation" would not have meanings outside mathematics, Binary relation would be simply named "Relation", with a disambiguating hatnote. Here the ambiguity is solved exactly as usual, with a disambiguating hatnote. If you know articles containing wrong links, the simplest way is to fix them directly. D.Lazard (talk) 08:19, 19 June 2018 (UTC)

## Algebras

=== Algebras, categories, and rewriting systems ===

Various operations on binary endorelations can be treated as giving rise to an algebraic structure, known as relation algebra. It should not be confused with relational algebra which deals in finitary relations (and in practice also finite and many-sorted).
For heterogenous binary relations, a category of relations arises. [1]
Despite their simplicity, binary relations are at the core of an abstract computation model known as an abstract rewriting system.

References

1. ^ Winter 2007

This long-neglected subsection has been superseded by heterogeneous relation and improvements to algebraic logic. — Rgdboer (talk) 23:53, 25 July 2018 (UTC)

## Merge discussion

See Talk:Binary operation#Merge with Binary relation?. --Ipatrol (talk) 17:48, 26 November 2018 (UTC)

## Merge with category of relations

I don't think we need a separate article for the category of relations; so merging it into this article should be in order. Also, maintaining such a separate article makes the quality control more difficult; in particular, as far as I can tell, the definition in the cat article is inconsistent with the one given here. (Actually I'm not completely sure about the definition here or if this article wants to talk whether this article wants to discuss a binary relation or correspondence). -- Taku (talk) 23:02, 3 February 2019 (UTC)

Oppose: The references at Category of relations are all from works on category theory. Furthermore, that article shows more than one type of object (category theory) in Rel. — Rgdboer (talk) 02:25, 5 February 2019 (UTC)
Category theory is useful to clarify things; for example, composition of relations is much clearer in the category-theory language but I get your point: every reader may not be familiar with category theory.
Also, what do you mean by "more than one type"? Do you mean the section named "Relations as objects". In fact, that section probably belongs to homogeneous relation. -- Taku (talk) 04:42, 5 February 2019 (UTC)

## Spltting off to Homogeneous relation

Your movement of stuff from here to Homogeneous relation may make sense; however, it should be discussed before. I couldn't find such a discussion anywhere - did I miss something?

If the split-off is to be kept, then the text on closure operations, on complement properties for homogeneous relations, as well as most of the Restrictions section, and the complete Examples section would need to be moved also. The lead should be modified in order not to start with the narrow definition "subset of A \times A" which isn't handled here any longer; instead it should mention that the most common binary relations are homogeneous ones (with the wikilink to Homogeneous relation, the "subset of A \times A" definition, and one or two examples). -

As a side remark: if we consider "binary relation" to be different from "correspondence", we should modify the lead sentence that claims the opposite. - Jochen Burghardt (talk) 12:54, 4 February 2019 (UTC)

Yes, it was a bold move in the spirit of WP:BRD. I noticed many incoming links are about homogeneous binary relations instead of binary relation in a more general sense (heterogeneous one) and thus it makes sense to have a separate article on the homogeneous case.
And, yes, to complete the split-off, some more edits are needed; I’m implementing things slowly so to make it easier to revert the action (though I didn’t think there would be a strong objection to splitting).
I think the article needs to have more stuff on correspondence, as it appears the article wants to discuss correspondence as well as a binary relation. In fact, this split was a response to the general problem that it’s not clear what the article really wants to discuss: correspondence? homogeneous relation? or whether it wants to distinguish between binary relation and correspondence. Please note we have correspondence (mathematics) as a separate article. —- Taku (talk) 19:47, 4 February 2019 (UTC)
Takuya Murata does not know the literature so should not be editing. He attempts to redefine Heterogeneous relation. The poison of the firearm reference in this article has resulted in disregard and now a separate article on Homogeneous relation, which redirected to Binary relation until 3 February 2019. — Rgdboer (talk) 02:34, 5 February 2019 (UTC)
Ok. I admit my use of "heterogeneous" might have slightly conflicted with the literature: "non-commutative" means not necessarily commutative as opposed to strictly non-commutative; I meant to say "not-necessarily-homogeneous" (but apparently that's not how the literature works). (I was right; see below) There is no attempt for the redefinition. -- Taku (talk) 04:05, 5 February 2019 (UTC)
What does "The poison of the firearm reference in this article has resulted in disregard" mean? -- Taku (talk) 04:07, 5 February 2019 (UTC)
In fact, [4] says "possibly distinct" not "necessarily distinct"; so isn't just a some usage variation? -- Taku (talk) 04:13, 5 February 2019 (UTC)
I'm unconvinced my use was incorrect: see [5][6][7] It seems to me "heterogeneous relation" is often a synonym for a "binary relation"; i.e., not-necessarily-homogeneous relation, as I have thought. (Again see below; mathematicians abuse English language; that's ... not my crime.) -- Taku (talk) 04:51, 5 February 2019 (UTC)
I did some Google search and couldn't find a claim that "heterogeneous" means not "not-necessarily-homogeneous" but two set must be *distinct*. (Incidentally, some references define a function as a particular kind of a heterogeneous relation and this means that the two sets must be allowed to coincide.) In fact, this is the basic problem: for example, I also couldn't find a reference saying you have to use a graph to define a binary relation instead of set of ordered pairs. -- Taku (talk) 07:59, 5 February 2019 (UTC)
In fact, I have just rewritten the definition section. I have removed stuff I couldn't find in the refs; for example, a definition in terms of a graph instead of just as a set of ordered pairs. I have also limited the def to sets; maybe a class can be used instead of a set but that needs to be justified by a reference. -- Taku (talk) 09:47, 5 February 2019 (UTC)
Also on binary relation vs correspondence. Again, I couldn't find a reference "explicitly saying" one must distinguish between a binary relation and a correspondence. In fact, Jacobson, Basic Algebra simply defines a correspondence as a binary relation; i.e., as a subset of a Cartesian product. I know there is a "ordered triple" definition of a correspondence and thus I have added a note on this matter, and this should hopefully dispel a confusion the article had. -- Taku (talk) 11:24, 5 February 2019 (UTC)

When "Homogeneous binary relation" is split off, I suggest to consider merging the rest into "Finitary relation". I'm neither aware of well-known examples of non-homogeneous binary relations, nor of particular properties of them. The only exception are partial or total functions, but they can have arbitrary arity as well. - Jochen Burghardt (talk) 14:51, 5 February 2019 (UTC)

Of course, a binary relation is a special case of n-ary relation; but the reliable sources (e.g., textbooks in set theory) discuss a not-necessary-homogeneous binary relation as an independent topic and so it makes sense to have a standalone article. Since we still have stuff like composition here, so this article will not be too short. And because of split-off, we can have more focused if concise article. I see that as a feature not a bug. —- Taku (talk) 16:48, 5 February 2019 (UTC)
Also, what doesn’t make sense to me is that we have heterogeneous relation as a separate article. —- Taku (talk) 17:03, 5 February 2019 (UTC)
As homogeneous relations are typical binary relations, they should be treated in this article. As to why heterogeneous relations deserve separate treatment, it is because of their greater complexity. Consider the set membership xA. At first glance it seems simple, in or out. When viewed as a binary relation one requires a universe (set theory) and power set on that universe. Just try to describe the transpose of the set membership relation. The contact relations of Georg Aumann deal with the same domain and range, but the subject of contact relations is deeper. Another instance is the concept lattice interpretation of a relation, and the decomposition of a relation by mappings and partial order. A reader new to binary relations might learn through graphs and directed graphs first about homogeneous relations, and particularly about properties of an equivalence relation. The other article offers the generalization to AB. — Rgdboer (talk) 02:03, 6 February 2019 (UTC)
I think we can all agree we need more than one article on binary relation; there are a lot of stuff to cover. And I do agree that the beginning readers should learn about homogeneous relations first. That's precisely why we have homogeneous relation as a separate article so that this article can focus on a generalization. Many incoming links to this page is about the homogeneous case; they can now be retargeted to homogeneous relation (by the way, this is also why I decided to go ahead with splitting since otherwise such retargetting will be weird).
As I wrote above, heterogeneous means "not-necessarily-homogeneous" according to the literature (as I initially thought). Maybe you are right to have an article specialized to the "strictly or literary heterogeneous case"; i.e., AB. But that article should not be named "heterogeneous relation" (since the term is a synonym for a binary relation). -- Taku (talk) 03:59, 6 February 2019 (UTC)
An analogy to linear algebra may clarify the picture: square matrices like M(2,R) and M(2,C) are classical computational tools first described as coquaternions an biquaternions respectively. Closed under multiplication they generalized complex numbers and were called hypercomplex numbers. With the rise of linear algebra, rectangular matrices gained a foothold, but lacked the multiplicative closure. Nevertheless, using transpose, a rectangular m induced square m^T m and m m^T. Similarly, homogeneous and heterogeneous relations, considered as logical matrices, are square or rectangular respectively. Now Binary relation is the portal of choice for most readers. They should be treated to the basic material here, which is homogeneous relation. The offensive gun was changed to cup in the example. There is much to be done here, but please move the basic material back here (there is considerable push-back in Talk:Homogeneous relation). — Rgdboer (talk) 03:13, 7 February 2019 (UTC)
I don't understand your analogy; I mean I get "homogoous relation" is to a square matrix and "binary relation" to a rectangular one. But what is your point? Are you disagreeing that the term "heterogeneous relation" is a synonym for the term "binary relation" (so "homogeneous relation" is a special case of a heterogeneous relation)? I understand it's probably an abuse of English language but that's how it's done in literature (see the text and ref in the article).
As for undoing the split-off: I will do that as we need to go back to the status quo when the edit was controversial. I still maintain my position that the basic materials should be covered in a separate article not as an example in a general article. (The analogy would be "vector space" is discussed in module (mathematics) as a special case.) -- Taku (talk) 04:29, 7 February 2019 (UTC)
Done. The basic issue still remains: that "binary relation" sometimes means "homogeneous one"; I have therefore left the hat note intact. -- Taku (talk) 04:42, 7 February 2019 (UTC)
Very good. Your analogy is perfect: when ring and vector space have been familiarized, then module is in the zone of proximal development. At that point mentioning that modules include vector spaces when the ring happens to be a field, is superfluous. — Rgdboer (talk) 02:36, 8 February 2019 (UTC)

We can be thankful that Gunther Schmidt has advanced the understanding of binary relations with his textbooks, including Relations and Graphs (1996, 2012). In the introduction to chapter 2, Homogeneous Relations, Schmidt and Strolhein write:

Relations between elements of the same set are called homogeneous; they are the easier to investigate. We defer the study of heterogeneous relations, i.e. those between elements of different sets to chapter 4. The homogeneous case already presents many of the essential features and is notationally simpler. (page 5)

In a later book, Relational Mathematics (2011), sets up his work for chapter 8: Relational Algebra:

We should stress that we work with heterogeneous relations. This contrasts greatly with the traditional work of the relation algebra community which is almost completely restricted to the homogeneous environment ... Some of the constructs that follow simply do not exist in the homogeneous context, for example the direct power and the membership relation. At first glance it seems simpler to study homogeneous as apposed to heterogeneous relations ...(page 157)

For the sake of the reader, the subject is unfolded in stages. — Rgdboer (talk) 03:07, 10 February 2019 (UTC)

You're still failing to interact with me: this article treats "homogeneous relation" as a special case. Isn't it a good idea to treat such a special case in a separate article? You're sounding like you agree with this. -- Taku (talk) 06:07, 11 February 2019 (UTC)
I think the confusion has to do with your insistence of using "heterogeneous relation" to mean not a synonym for "binary relation" but a binary relation between the two "distinct" sets. But that's not what's in the ref: see for example the ref cited in the article: Schmidt, Gunther; Ströhlein, Thomas (2012). Relations and Graphs: Discrete Mathematics for Computer Scientists. Definition 4.1.1.: Springer Science & Business Media. ISBN 978-3-642-77968-8. -- Taku (talk)

Just last year Schmidt and Winter wrote in Relational Topology (2018):

The modern algebraic treatment of relations has its origins in the work of Alfred Tarski. His relation algebras are concerned with relations on a single universe, i.e., they are homogeneous. A heterogeneous approach using category theory, the approach taken in this book, was proposed by multiple researchers including the authors of this book starting in the 70s of the previous century. It can be shown that only this version of the calculus of relations is capable of handling the "is element" relation ε in an algebraic fashion and, hence, makes it possible to investigate topology via relations.

A higher order of relation theory is aspired and achieved in the book. Taku cites the book listed above, and a phrase from chapter 4 which he believes justifies gathering in a more advanced article. Readers need to be gradually brought through a topic and this article serves to introduce binary relations, especially the ones "on a single universe". As mentioned above, there is no depth in sources to Taku's view; rather three works of his author are cited at length here to indicate there is a break when it comes to the general case. — Rgdboer (talk) 01:18, 12 February 2019 (UTC)

@Rgdboer and TakuyaMurata: Would it be possible to summarize your dissent in a few lines? - Do you disagree about which relations should be called "homogeneous" and which ones should be called "heterogeneous"? If so, could you given an example relation on which you disagree? - Do you disagree on how the stuff should be separated into articles? If so, could both of you make a brief suggestion e.g. of the form "(Title1, Topics1), ..., (TitleN, TopicsN)"? - Jochen Burghardt (talk) 08:42, 12 February 2019 (UTC)

My problem is quite simple: I cannot find a reference saying a heterogeneous relation require two sets be distinct, as opposed to possibly distinct. To quote, Defintion 4.1.1. of Schmidt, Gunther; Ströhlein, Thomas (2012). Relations and Graphs: Discrete Mathematics for Computer Scientists has this:[8]
Given possibly different sets X and Y, a subset R of ${\displaystyle X\times Y}$ is called a (heterogeneous) relation between X and Y.
This definition looks most standard (I have also mentioned above some other refs giving the same definition). The edits of Rgdboer seem to insist Wikipedia must differ from the standard def and I'm simply saying we can't do.
Another disagreement is whether "homogeneous relation", the case when ${\displaystyle X=Y}$, should be discussed in a separate article or not. I think it should be: many incoming links to this page are actually on "homogeneous" binary relation, as opposed to a general (i.e., heterogeneous) relation, the topic of this article.
If I understand Rgdboer correctly, doing so would make it hard to see there is a difference between "homogeneous relation" and a general (heterogeneous) relation. In other words, it will make this article looks less introductory by not discussing the familiar case. But I think it's easier for the general readers if the basic case is discussed in a separate article not as a part of the general article; like discussing "vector space" in the vector space article rather than as a section in the "module" article.

I agree with Taku's summary except where it says that I "insist that Wikipedia differ from the standard def[inition]." The principle for writing here is WP:Make technical articles understandable. For example, WP:UPFRONT: least obscure topic first. Another suggestion is made there in WP:TECH-CONTENT: "It may be helpful to compare to a standard reference work in the particular technical field to which the subject of the article belongs." In this case, Schmidt's books, which show respect for the profundity of the heterogeneous case. Taku is so taken with his notion that he wants to override the Greek meaning of heterogeneous as seen in his edits at homogeneity and heterogeneity. He also abuses a WP:Hatnote by linking to a section of this article, whereas Hatnotes are meant for linking out to other articles. The section Homogeneous relation is visible in the WP:Table of contents, and the topic is described in the lede. Extensive quotations from Schmidt's books have been made above to show that a separate article for the more obscure topic is justified, even if it falls under the umbrella of the general binary relation. — Rgdboer (talk) 02:11, 13 February 2019 (UTC)

@Rgdboer and TakuyaMurata: Thanks for your summaries! To ensure that I got you right, let me rephrase you along the example from the article: A = {ball, car, doll, cup} and B = {John, Mary, Ian, Venus}. All of us would agree to call a relation on A×B a heterogeneous one, and a relation on A×A a homogeneous one. None of us would call a relation on A×B a homogeneous one, since AB. TakuyaMurata (and Schmidt+Ströhlein) would call a relation on A×A also a heterogeneous one, while Rgdboer would refuse that. - Provided I got you right, I think we should in the lead of Binary relation (I guess this article would exist in any proposed structure) describe the situation found in the literature, like (wording subject to improvement):

"Most authors call a relation on A×B 'heterogeneous' only if AB,[many references] while some do not require this restriction, using 'heterogeneous' synonymously to 'possibly heterogeneous'.[few references]

or vice versa, depending on the number of (preferrably textbooks) references. - As I am not a native English speaker, I do not have an overview over the literature. From a mathematical point of view, I think there is not much to say about relations on necessarily distinct sets; they aren't even closed w.r.t. composition. So I'd expect TakuyaMurata's view to agree with the majority. From computer science, I remember a similar setting that was a source of confusion for a long time: it is well-established to consider each deterministic finite automaton also a nondeterministic finite automaton (the latter article's lead explains that). -
As for the article structure, we probably all agree that most readers who search for "Binary relation" are in fact looking for information on homogeneous binary relations. Independent of the structure, in some way or another, we have to make them aware that "Binary relation" is more general than what they look for. If we split-off "Homogeneous binary relation", readers who follow a wikilink, e.g. from total order and from Complement (set theory), can be directed to "Homogeneous binary relation" and to "Binary relation", respectively, where they find just what they need; I think this would be a great advantage. Also, splitting off would resolve the issue of a hatnote linking to a subsection. However, I didn't yet think about all possible structures and their pros and cons. (Anyway I withdraw my above suggestion of 5 Feb to merge the non-homogeneous stuff into "Finitary relation"; the most prominent notion to search for is "Binary relation", so this article should exist in any case.) - Jochen Burghardt (talk) 10:50, 13 February 2019 (UTC)
(It's very nice that the disagreements are now clear). First, the terminology: as I mentioned before, this is a problem of mathematicians abusing English language. I know the Greek (and everyday) meaning of heterogeneous; mathematicians (arrogantly?) chose to override/ignore it. It's not my choice. So, I don't believe the statement
Most authors call a relation on A×B 'heterogeneous' only if AB
is supported by references. All references I can find only require A, B "possibly distinct" as opposed to "distinct", in their definitions of heterogeneous relations. The wording in the current article is true to the references as far as I can tell. ("NFA" v.s. "DFA" is the similar case when English language is abused).
As for the organization matter, yes, I don't think some kind of a hatnote is avoidable since "binary relation" can mean "homogeneous one" frequently if not primarily. (I agree that a "separate article for the more obscure topics" is probably a good idea). But I'm less concerned with this than the terminology issue; when mathematicians or computer scientists use the terminology in a confusing way, that need to be clearly and explicitly mentioned. -- Taku (talk) 00:03, 14 February 2019 (UTC)

## ≘ listed at Redirects for discussion

An editor has asked for a discussion to address the redirect . Please participate in the redirect discussion if you wish to do so. D.Lazard (talk) 16:20, 18 June 2019 (UTC)

## Infix standard

For a binary relation RA x B, the standard representation in terms of elements of A and B is through infix notation aRb as is seen in textbooks by Schroder, Lewis, and Schmidt as well as in the works of Tarski. Policy is to mention exceptional cases without undue emphasis. Currently the article raises prefix and suffix notation to the level of infix notation, misleading readers.

The elephant in our museum is the prefix notation f(x)=y used to study function (mathematics)s. The prefix results in a retrograde notation for composition of functions, something finding some remedy at composition of relations. This notational racket has been a favorite of gatekeeping teachers to trip up students by obfuscation, and can be addressed in wikis and their Talks. Reverse gear is sometimes necessary for mobility; but beyond reporting standard usages, clarity is of the essence per WP:TECHNICAL. _ Rgdboer (talk) 17:46, 14 July 2020 (UTC)

I agree that infix notation is seen most often, I saw prefix notation occasionally (e.g. used by logicians who handle binary like n-ary relations), but never postfix notation. So I suggest to change the sentence to:

The statement (x, y) in R reads "x is R-related to y" and is denoted by xRy (infix notation) by most authors,[1][2] and sometimes by Rxy (prefix notation).[3]

References

1. ^ Schroder/Lewis/Schmidt
2. ^ Tarski
3. ^ Hans Hermes (1973). Introduction to Mathematical Logic. Hochschultext (Springer-Verlag). London: Springer. ISBN 3540058192. ISSN 1431-4657. Sect.II.§1.1.4
I wouldn't complain if the "(...fix notation)" parantheses were deleted. Could you provide a full citation for Schroder/Lewis/Schmidt and Tarski? The former is needed anyway. We needn't discuss function application notation, I believe. - Jochen Burghardt (talk) 14:29, 15 July 2020 (UTC)

Schröder/Lewis/Schmidt references now in place. Your sentence about infix/prefix is acceptable. — Rgdboer (talk) 19:05, 17 July 2020 (UTC)

Use of prefix in modal logic could not be confirmed. Gasquet was added to references at accessibility relation and notation changed to infix in that article. Prefix in n-ary relations for n>2 is a weak argument for use with n=2 when infix is standard in texts. — Rgdboer (talk) 21:48, 23 July 2020 (UTC)

Checking Hans Hermes (1973) the prefix is used for "Peano relation" at page 156 and 7 and a Google Books search did not turn up a single use of "binary relation" in the textbook. Hermes does not represent a reliable source for the notation issue at hand. Acceptance of suggested sentence is withdrawn. — Rgdboer (talk) 22:15, 23 July 2020 (UTC)

I agree that Hermes doesn't consider binary relations in particular, but deals only with n-ary relations in general, and uses prefix nation for this reason. However, I tend to disagree (but am not quite sure) that his notation shouldn't be mentioned here. For example, at the end of sect. VI.2 (p.146 in my German edition), he gives an exercise involving an axiom system about a reflexive, symmetric, and transitive 2-ary relation R on a 2-element domain; Wikipedia should allow a reader to recognize that Hermes' "Rxx" and Wikipedia's "xRx" means the same. So what about this wording:

The statement (x, y) in R reads "x is R-related to y" and is denoted by xRy.[1][2] Authors who deal with binary relations only as a special case of n-ary relations for arbitrary n usually write Rxy as a special case of Rx1...xn (prefix notation).[3]

References

1. ^ Schroder/Lewis/Schmidt
2. ^ Tarski
3. ^ Hermes
Some fine-tuning may be needed, as I'm not a native English speaker. The part "as a special case of Rx1...xn" could also be omitted. Also, the whole 2nd sentence could appear only as a footnote. - Jochen Burghardt (talk) 08:52, 24 July 2020 (UTC)
Done I implemented the above edit, putting the "prefix" sentence in a footnote. - Jochen Burghardt (talk) 18:12, 1 August 2020 (UTC)

## Merge with Heterogeneous relation

The following discussion is closed. Please do not modify it. Subsequent comments should be made in a new section. A summary of the conclusions reached follows.
The result of this discussion was: merge/restructure as suggested on 4 June 2021 (discussion bottom). Jochen Burghardt (talk) 12:56, 12 June 2021 (UTC)

Pinging the earlier participants: @Rgdboer, D.Lazard, and TakuyaMurata:

Despite the lengthy discussion at #Spltting off to Homogeneous relation and #Schmidt comments, the article structure is still not satisfying. In particular, everything said in Heterogeneous relation applies in general to (and thus belongs to) Binary relation, except for the requirement AB. Adding the latter does not add any new results to the theory. For these reasons, I suggest the merge.

Much of the earlier discussion was about the definition of a HomogeneousHeterogeneous relation: whether it should (1) require AB, or just (2) allow AB. The article currently uses definition (1). The current merger proposal, however, is independent of this issue, since there is not much to say about a HomogeneousHeterogeneous relation in the sense of (1), except that it is a binary relation on two different sets. Just to say the latter, an own article is hardly needed.

Beyond that, and risking a re-opening of the earlier discussion, I note that I'd favor to split off Homogeneous relation (handling A=B as a special case), and leaving the rest in Binary relation (handling the general case A=B or AB). - Jochen Burghardt (talk) 16:15, 16 May 2021 (UTC)

• Oppose: The introductory article Binary relation satisfies the needs of a reader fresh to the topic. In most cases homogeneous relations such as orders, graphs, or equivalence relations draw attention. The heterogeneous article involves more complexity and is of interest to investigators. While the general case includes these topics, they would encumber the introductory article. Rgdboer (talk) 05:05, 17 May 2021 (UTC)

I see your point. Having an introductory article and a more advanced article on relations is a good idea, similar to Set (mathematics) / Set theory and Group (mathematics) / Group theory. What about re-organizing the available stuff (at Binary relation, Heterogeneous relation, Draft:Correspondence (mathematics)) into an introductory article called (e.g.) Relation (mathematics), and two more advanced articles called (e.g.) Binary relation theory and Homogeneous binary relation theory? This would allow us to move the sections Heterogeneous_relation#Induced_concept_lattice, Heterogeneous_relation#Particular_relations, Heterogeneous_relation#Preorder_R\R, Heterogeneous_relation#Fringe_of_a_relation, Heterogeneous_relation#Mathematical_heaps to where they actually belong, viz. to Binary relation theory, since they actually apply to all binary relations (as far as I could see). - Jochen Burghardt (talk) 07:36, 18 May 2021 (UTC)

Support with the merger with heterogeneous relation and split-off of homogeneous relation: I am very confused with Jochen Burghardt's rendering of the current situation. My understanding is that the current article takes a view that a "binary relation" is synonymous with "heterogeneous relation"; both terms refer to "not-necessarily-homogeneous relation" (and this is the view that can be backed by the sources, if we like it or not). But the use of the term can emphasize the fact the domain and codomain might be different for the benefit of the audience who are more familiar with homogeneous relation. Since a homogeneous relation is a binary relation that is more frequently used by the general readers, it makes sense to have a separate article for it. -- Taku (talk) 03:22, 19 May 2021 (UTC)
Just to clarify myself: I share your view that "heterogeneous relation" should be synonymous with "binary relation" (what I called def. (2) above), but I understand the current version of Heterogeneous relation to use definition (1), as I read "distinct" as "≠". I would have no objection to change the 1st lead sentence e.g. to "where A and B are allowed to be different sets". - Jochen Burghardt (talk) 08:53, 19 May 2021 (UTC)
Ah, I see: in your original post, you meant to say "Heterogeneous relation" not "Homogeneous relation". This is why I couldn't follow your argument. I think we are in agreement (on possible organizational changes). -- Taku (talk) 21:17, 19 May 2021 (UTC)
Oops - yes, you are right. I changed my original post to fix that. Sorry for the confusion. - Jochen Burghardt (talk) 21:39, 19 May 2021 (UTC)
• Comments: The topic of “binary relation theory” is called Calculus of relations, found as the first section in algebraic logic. The composition of relations is what makes it a calculus. This introductory article on binary relations has little reference to compositions, focused mainly relations per se. Contrast that with composition as essential to understanding the Heterogeneous article. Do you advocate inclusion of the Composition of relations material? Rgdboer (talk) 04:13, 20 May 2021 (UTC)

You are right that "binary relation theory" is more commonly used for Calculus of relations than for an advanced treatment of binary relations in general. The new article names I suggested were inspired by analogy to Set and Group; they may not be the best choices for Relation. The essence of my above suggestion is just to have an introductory article, one advanced article about binary relations in general, and one advanced article about homogeneous binary relations; their names aren't too important to me (what about Relation (mathematics), Binary relation, and Homogeneous binary relation?). As for the algebraic stuff from Composition of relations etc., I think it needn't be mentioned in the introductory article (or maybe just in one sentence), and it could be mentioned briefly in the advanced homogeneous article, with a {{main}} link. - Jochen Burghardt (talk) 08:14, 22 May 2021 (UTC)

@Rgdboer, D.Lazard, and TakuyaMurata: If there are no objections, I'll go ahead and set up the following structure:

- Jochen Burghardt (talk) 19:01, 4 June 2021 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

## Semantics, or, the trouble with non-mathematical examples

I appreciate your work with this article, and with the earlier stand-alone versions of Heterogeneous relation. However, I think your example with continents and oceans suffer from being not in accordance with the dominating use of the word continent. Now, as I'm sure you agree, illustrations from "the real world" often suffer slightly from the fact that terms in ordinary use mostly are much less precise than well-defined mathematical terms. In this particular case, I fear that the usage of continent that you employ collide with the usages both in enwp and in OED. Note, that OED stresses that the continents be continuous land masses. (Actually, the etymologies for continent and continuous in OED both ultimately derive the words to the same Latin verb, continēre, and mentions an old an now obsolete adjectivistic use of continent as being continuous.)

There is some unclearity about what should be connected, though. Our article Australia (continent) includes New Guinea and Tasmania, since they belong to the same continental plate as does the Australian mainland proper. However, neither Micronesia nor Polynesia is situated on this plate, although they (bye and large) belong to Oceania (as defined by the UN and identified with the code OCE).

There may some alternative terms; the article Oceania defines it as a geographic region. I found no simple resolution, though. (In German, I'd have suggested the use of alternative terms without the implicit continuity requirement of Kontinente, such as Erdteile or Weltteile. I know no similar common term in Engliush, though.) JoergenB (talk) 22:02, 13 July 2021 (UTC)

One possibility that comes to my mind is to remove smaller non-continuous parts (islands) from the map, and add a footnote that we show a simplified map. - Jochen Burghardt (talk) 07:59, 14 July 2021 (UTC)
Mention of tectonic plates led to an example posted to Homogeneous relation. Thank you JoergenB for insightful comments on use of non-math examples. Math is extremely austere when not illustrated concretely. The ocean/continent example was meant to show heterogeneous meaning in relations. That example also ignores the Southern ocean notion which is gaining adherents. Nevertheless, concrete illustration encourages application of math ideas. Rgdboer (talk) 21:05, 14 July 2021 (UTC)
Done I tested a world map without islands, as suggested above. Revert me if you don't like it (I'm not sure about it myself).
As for continuity, JoergenB may be right about the etymology, but what we call continents are not the largest possible continuous land masses. Otherwise, North and South America together would be a single continent, and Africa, Asia, and Europe together would be another one. - Jochen Burghardt (talk) 14:49, 16 July 2021 (UTC)
I do not think that equating continents with large enough connected components of dry land with the resulting four continent system (Afro-Eurasia, America, Antarctica, Australia) is a modern usage widespread enough to bother the example in this article. (If you really are interested in this particular definition, and what kind of impact it may have or not have to-day, see e. g. the discussion in Continent#Separation, and perhaps the discussion and suggested sources in de:Diskussion:Amerika#Häufigkeit!) However, this was not the point. While not demanding maximality, still, I think that most usual definitions demand continents to be contiguous. This is a main reason why the region Oceania (abbreviated "OC") rarely is called a 'continent'.
I think that the revised map indeed resolves most of the issue. However, I'll replace the abbreviation "OC" with "AU" in the enumeration and the table (= the relation graph). JoergenB (talk) 12:44, 17 July 2021 (UTC)