Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If the definition of a relation is that it is a set of ordered pairs, how come two relations are not equal if they contain the same elements but aren't on the same sets?

For example, Let $R_1$ be a relation from $A$ to $B$ and $R_2$ be a relation from $C$ to $D$ such that $B \ne D$ but $R_1$ and $R_2$ contain the same elements. If $R_1$ and $R_2$ are just sets shouldn't $R_1=R_2$?

Wouldn't it be more appropriate to define relations as something like an ordered triple? For example $(R,A,B)$ where $R \subseteq A \times B$.

Thanks in advance

share|cite|improve this question
If $B$ and $D$ are disjoint, $R_1$ and $R_2$ can't possibly contain the same elements. You're saying that both relations "stay inside" the intersection of $B$ and $D$? – Jack M May 29 '14 at 13:51
up vote 3 down vote accepted

If $R_1$ and $R_2$ have the same ordered pairs then they are equal. Period. Because two sets with the same elements are equal. For example the empty relation is the empty set is the same relation whether or not it is a subset of $A\times B$ or $C\times D$.

But we often care about both internal and external properties of a relation. For example a relation is a function from $A$ to $B$ if it satisfies the property that $(x,y),(x,z)\in R$ then $y=z$; and that its domain is equal to $A$. So if $f\colon A\to B$ is a function, and then we take $A'$ to be a set strictly bigger than $A$, then $f\subseteq A'\times B$, but $f$ is not a function from $A'$, but rather a partial function.

Similarly, reflexive relations are reflexive on a set, whereas symmetric relations are just symmetric. This is because reflexive and being a function from $A$ to $B$ are external properties of a relation, whereas being symmetric or have a functional property are internal properties.

Sometimes, if so, we are interested in the domain and codomain of a relation, for example in category theory a function is an ordered triplet consisting of a domain, codomain and a graph. In set theory, we only care about the graph. The same can be done with relations, and either approach has merits and uses for different purposes.

share|cite|improve this answer
Actually, my real problem is with functions. If two functions have different codomains, they are considered different. But, a function $f: A \to B$ can have the same set of ordered pairs as a function $g: A \to C$ with $B \ne C$. Could you clarify, please? – Ahmed Ali May 29 '14 at 15:44
This depends on the context. Without giving more context, your problem can't be adequately answered. In set theory, the function is really just the set of ordered pairs; in category theory the functions are ordered triplets and different codomains would yield different functions (to wit, consider $\sin$ as a function into $\Bbb R$ and into $[-1,1]$ gives you two different functions). But each of these interpretation of the notion of function have a reason, and these interpretations are used for different things in different contexts. – Asaf Karagila May 29 '14 at 15:47
Then if I consider a function as a relation then in my previous example $f=g$ but if I consider it an ordered triplet then $f \ne g$? – Ahmed Ali May 29 '14 at 15:52
Yes, and if you're working in a context where functions are defined as ordered triplets, then changing the codomain changes the function; and if you work in a context where the function is a set of ordered pairs, then any function has many different codomains. – Asaf Karagila May 29 '14 at 15:54
Then this book defines a function, essentially, as an ordered triplet. And in the context of that book, this is the given definition. – Asaf Karagila May 29 '14 at 16:04

You seem to be quoting an ill-stated version of the definition of a relation. A better crafted version will have the domain and range given as part of the definition:

  • Given sets $A$ and $B$, a relation between $A$ and $B$ is a subset of $A \times B$.
share|cite|improve this answer
Do note, by the way, that this is a crafty definition that doesn't fully prescribe to neither set theoretic notion of relation, nor category/type theory notion of a relation. From one end, $\varnothing$ is a relation between any two sets because $\varnothing\subseteq A\times B$. On the other hand, the definition is worded in such way that you might think that specifying what are $A$ and $B$ is essential, therefore a relation is again a triplet. Seeing how this looks a bit open for interpretation, I choose the first one, for obvious reasons. :-) – Asaf Karagila May 30 '14 at 0:01
A problem with this approach is that one can never even mention a relation without explicitly naming its domain/codomain. For the true danger, consider this accident when Bourbaki does matrices (possibly without entries): (1) A $n\times m$ matrix with entries in $R$ is map $[n]\times[m]\to R$; (2) so if $n=0$ or $m=0$ then the map is the empty set; it being unique there is a unique empty matrix; (3) for a matrix product $A*B$ to be defined, $A$ must be a $n\times k$ and $B$ a $k\times m$ matrix, and... But the product of two empty matrices can now be a $n\times m$ zero matrix for any $n,m$. – Marc van Leeuwen May 30 '14 at 3:44
... The link with the current question is that giving the dimension of a matrix is like giving domain/codomain of a relation. Point (2) is wrong since one only can conclude that there is a unique (empty) $n\times m$ matrix when $nm=0$; comparing them for different $(n,m)$ is just not possible with this definition; finally point (3) introduces matrices without fixing their dimension first, an error which becomes fatal. (Check out Bourbaki for the details, they shoot themselves in the foot beautifully by requiring a discipline (only defining matrices with specified size) and not adhering to it.) – Marc van Leeuwen May 30 '14 at 3:59
... The conclusion I would like to extract from this is that one should either choose to define what a notion (relation, matrix) is independently of having first specified its attributes (comain/codomain, dimensions), and live with the consequences, or define those attributes to be part or the object defined (so they are available whenever the object is discussed) which seems a somewhat more prudent approach (and the correct one for matrices). But giving a definition that is only meaningful if the context supplies the necessary attributes is asking for trouble: in practice it won't always. – Marc van Leeuwen May 30 '14 at 4:11

Your problem is that you're mixing up a relation with its graph.

A relation doesn't contain elements: the graph of the relation contains elements. And it is possible for relations on different sets (which therefore cannot be equal) to have equal graphs.

Actually, that is only true if you think of the graph of a relation as merely being a set. If you think of it as a subset of the domain of the relation, then the graphs would still be different: "$S \subseteq A \times B$" is different from "$S \subseteq C \times D$", and it is merely their underlying sets that are the same.

In some sense, relations on different domains are different types of objects, and it's not obvious that it should even be meaningful to ask if they are equal.

It's worth noting that your $R_1$ and $R_2$ can be extended to binary relations on $(\mathbf{Set}, \mathbf{Set})$, and they extend to the same relation $R$, as both definitions below give the same relation

$$ xRy \Leftrightarrow (x,y) \in A\times B \wedge xR_1y $$ $$ xRy \Leftrightarrow (x,y) \in C \times D \wedge xR_2y $$

so they really are the same relation if you're really thinking not in terms of of relations on sets but in terms of relations on the entire universe of sets.

Sometimes, it is useful to have a set-theoretic model of the notion of relation. Interpreting a relation as its graph is a reasonable model for a great many purposes.

But if your notion of relation is that it is meaningful to compare relations on different domains and you want a model that faithfully captures equality, then the graph of the relation does not make a good model. The triple consisting of the graph, domain, and codomain that you suggest is indeed a reasonable model.

share|cite|improve this answer
The "problem" is that students are being taught that relations are their graphs. But it's not really a problem. It simplifies some things in many cases. The real problem is that we teach students that there can only be one interpretation per notion of something in mathematics (or rather, we don't teach them that the same notion can have several incompatible interpretations which we can translate into one another). There's no mix up, if you define a relation to be a set of ordered pairs, then you are confusing between a relation and something else which extends the notion of a relation. – Asaf Karagila May 29 '14 at 14:34

The problem is that a relation IS NOT just a collection of ordered pairs. Just as a function is not defined only by the rule of assignment, a relation isn't either. You must also explicitly specify the "domain" and "range" ($A$ and $B$, in the case of $R_1$). So it really already IS an ordered triple.

share|cite|improve this answer
Your answer, being phrased as an absolute truth, contradicts the entire approach taken by many mathematicians. – Asaf Karagila May 29 '14 at 14:29
And many mathematicians (including myself, on occasion) use an intentionally vague idea of what a function is. At the bare-bones minimum, a function ALWAYS comprises domain, range, and rule of assignment. But most mathematicians have no problem speaking of "the function" $\sin x$, letting the domain and range be implicit (often $\mathbb R$ for both). In practice it is often unimportant what the domain and range are; however, if one asks technically detailed questions, these distinctions are crucial. – MPW May 29 '14 at 18:19
Yes. So instead of writing an answer which presents something which is "quietly controversial" (i.e. there are several well established standards) as a CAPITAL LETTERS TRUTH, perhaps you can not ignore all those people who disagree with you, and for them a relation is a set of ordered pairs. Maybe they'll appreciate being included in your universe of mathematics, as much as you'd be happy to be included in theirs. – Asaf Karagila May 29 '14 at 18:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.