Relations
[Video Tutorials] (coming soon)
In this tutorial, we go over the basics of relations, which are just sets of pairs of elements that satisfy some property.
Introduction
A binary relation is defined as a subset of the Cartesian product of two sets, indicating pairs of items that are related in some way, with terminology specific to it being a mathematical relation. We illustrate the concept using a simple, non-numeric example. Let A be a set of students, with
A=\{ Mary Smith, James Williams, William Jones, Linda Johnson \}.
Note: Names do not uniquely identify a person, since there are many “Mary Smith”s in the world, so we would normally use unique student IDs for this – we want this initial example to be more readable though.
We define a set B of classes at a university:
B=\{ CS 101, CS 103, CS 105, MAT 151 \}.
The Cartesian product A\times B then is the set of all student/class pairs. We can define a binary relation called “is taking” that relates students and classes when the student is taking the class. This is a subset of the Cartesian product, and we might list it out in a table as follows.
| Student | Class |
|---|---|
| Mary Smith | CS 103 |
| James Williams | CS 101 |
| James Williams | MAT 151 |
| William Jones | CS 101 |
| Linda Johnson | CS 101 |
| Linda Johnson | MAT 151 |
This relation (and table) indicates that Linda Johnson is taking CS 101 and MAT 151, while William Jones is taking only CS 101. Looking at all pairs that have CS 101 as the second element, we see that the class roster for CS 101 is James Williams, William Jones, and Linda Johnson. While you might not naturally think of it this way, this is just a subset of A\times B, so is a relation. There are no restrictions on the subset – a student can take any number of classes, and a class can have any number of students. For example, three students are taking CS 101, while only one is taking CS 103, and no student is taking CS 105. This use of relations and the view as a table is one of the core ideas behind a relational database, a key technology in computing, although relations in a relational database are often between more than two sets, represented with many columns in the table.
In discrete mathematics (and hence in these tutorials) we are primarily interested in binary relations, and usually binary relations on numbers. We’ll see examples below, but now that we have the idea of a binary relation, let’s give a formal definition.
Definition 1
When a binary relation is from A to A, so is a subset of A\times A, we will refer to this as a “relation on A.”
While we sometimes say that R is a relation between A and B, it is important to remember that pairs in A\times B are ordered, and the statement “from A to B” make the differing roles of A and B more clear.
If you haven’t seen this general definition of relation before, the notation with the letter R between two elements may seem strange. A couple of examples should help clarify this. With our non-numeric example above, think about the “R” in the relation notation as “is taking,” so when we say ( James Williams, CS 101 )\in R, we can read this out as “James Williams is taking CS 101”. The following example is more typical of discrete mathematics.
Example 2
\{ (x,y)\in\mathbb{Z}^2 \ |\ x \text{ is less than } y \} \ .
The symbol “<” is special notation used for this relation R, so “xRy” is the familiar notation “x<y.”
Other similar relations on the integers (or on \mathbb{Q} or \mathbb{R}) are relations \leq, >, \geq, =, and \neq. While you may have seen these and thought of them as “comparisons,” they are really relations as in Definition 1.
While n-ary relations can also be defined as subsets of n-way Cartesian products, or subsets of n-tuples, (e.g., a 3-ary relation could be a subset of 3-tuples from A\times B\times C), binary relations are by far the most commonly used in discrete mathematics. Therefore, in these tutorials when we simply say relation, we are referring to a binary relation as long as there is no ambiguity or confusion.
We can denote that two elements are not related by putting a line through the R in the general notation, like a \not\mathrel{R} b. This is the same idea as writing x\neq y and a\not\in S.
Relations are often used to define a property of a pair of values, and for a pair (x,y) you can ask “Is the property true for x and y?” For example, with the less-than relation you can ask “Is x less than y?” The pair (x,y) is in the relation if and only if the answer to this question is “yes.”
Given this perspective, you can see that many standard mathematical notations are just relations. For example, if S is a set from universe U, then notation “x\in S” is a relation from U to the power set {\mathcal P}(U), which we call the “element-of” relation, and is a subset of U\times{\mathcal P}(U). Stop for a moment and think that through if you don’t understand it, and in particular why the second set in the relation is {\mathcal P}(U).
If you’re given a statement that’s a property, like x\in S, ask yourself this: What is x? and What is S? Now that you know what they are (like a “type” in programming) ask yourself what the set of all possible values of that type are.
For the statement “x\in S,” what is x? We can ask the “element-of” question for any element of the universe U, so the set of all possible x values is just the set U.
What is S? It is a set of values from U, or a subset of U. What is the set of all possible S values? Since S is a subset of U, that’s just the set of all subsets of U. This is the definition of the power set of U, or {\mathcal P}(U).
Combining these observations, the “element-of” relation is from U to {\mathcal P}(U), and is a subset of U\times {\mathcal P}(U).
A lot of interesting properties of integers deal with divisibility, from which we can define concepts like prime numbers, greatest common divisors, least common multiples (and lowest common denominator), and more. Divisibility is just a relation on integers, so we define a “divides” relation, and associated notation, so we can talk about this precisely and rigorously.
Definition 3
The importance of formal definitions: Since divisibility is a common topic throughout early math classes, most students should have dealt with this concept regularly and have a good intuitive idea of what “x divides evenly into y” means. However, when working with this concept mathematically you should not use intuitive notions, which often devolve into hand-waving statements like “well, you know….” Always go back to the definition! If you need to prove some property about divisibility, go back to this definition – you should be specifically looking for that k value that satisfies the definition! Furthermore, if you get stuck on a problem that relates to divisibility, you should always write out the definition. That’s what it really means, so write out the formula and see what ideas it can inspire.
Example 4
It’s also important to note that zero can be used, and in fact x|0 for all x\in\mathbb{Z}, since with k=0 we have 0=k\cdot x (or 0=0\cdot x) for any x. It’s also the case that the only value of x for which 0|x is x=0.
Note that some students are tempted to turn their intuition of “divides” into a definition by saying something like a|b if b divided by a has a zero remainder. With this “definition” we could not talk about a=0, so the last sentence in the previous paragraph (talking about 0|x) would not make sense.
When we get to proofs, we’ll use the divides relation to define even numbers, so x\in\mathbb{Z} is even if and only if 2|x. This means negative numbers can be even: for example, -4 is even since we had 2|-4 in the example above. Furthermore, zero is even since 2|0.
Here’s another example of a relation, which has an important property that we’ll explore later.
Example 5
R = \{(x,y)\in\mathbb{R}^2\ |\ y=2x+3 \} \ .
In other words, the pair (x,y) is in the relation if and only if it satisfies the equation y=2x+3. An important property of this relation is that every x\in\mathbb{R} is related to one and only one value y. For example, 2R7 but there is no other y value for which 2Ry. This is precisely the property we need for a relation to be a function which we will define and discuss a little later.
Relation Properties
There are no real restrictions on a binary relation from A to B, since it can be an arbitrary subset of A\times B. It’s useful to consider some restrictions, or properties that a relation might satisfy. For general binary relations, you can classify them as “one-to-one” or “many-to-one” and more. However, for our purposes, we are generally interested in relations on a set A (so subsets of A^2), and the following definition gives some important properties for this case.
Definition 6
A relation R on set A (i.e., a subset of A^2) is
- reflexive if aRa for all a\in A
- symmetric if aRb implies that bRa for all a,b\in A
- transitive if aRb and bRc implies that aRc for all a,b,c\in A
While those are the most fundamental properties, we can define a few related properties. In particular, R is
- antisymmetric if aRb and bRa is only true when a=b
- asymmetric if (a,b)\in R implies (b,a)\not\in R for all a,b\in A
- irreflexive if (a,a)\not\in R for all a\in A
We illustrate these properties with a few examples.
Example 7
What about symmetry? The relation is not symmetric, because 1\leq 2 but 2\not\leq 1. Are there cases in which a\leq b and b\leq a? Yes! When a and b are equal, this holds (for example, a=b=2). However, equality is the only time we have this symmetry, so \leq is in fact antisymmetric.
Example 8
What about symmetry? It’s not symmetric, but is it antisymmetric like \leq? There are no values a and b such that a<b and b<a, so there are no counterexamples to disprove anti-symmetry – in such a situation we say the definition is vacuously true and so < is indeed antisymmetric. However, in this situation, the more useful observation is that < is asymmetric, since there are no values a,b\in\mathbb{R} with a<b and b<a.
Example 9
R=\{(1,3),(2,3),(2,4),(3,2),(3,3),(3,4)\}.
This relation is not reflexive, since (1,1)\not\in R.
This relation is not symmetric, since (1,3)\in R, but (3,1)\not\in R.
While it’s a little harder to spot, this relation is also not transitive since (1,3)\in R and (3,4)\in R, but (1,4)\not\in R.
The relation is also not antisymmetric, since (2,3)\in R and (3,2)\in R but 2\neq 3. This example also shows that R is not asymmetric.
Finally, R is not irreflexive, since (3,3)\in R.
The bottom line here is that we have six different properties that a relation can satisfy, and this relation R satisfies none of them!
An important type of relation is an equivalence relation, and certain very important properties follow from a relation being an equivalence relation. Many of these go beyond basic discrete math material, so we won’t discuss them further here, but the notion of equivalence classes is extremely powerful in some areas and applications of mathematics. For here, we just define the term so that you can recognize it in the future.
Definition 10
Let’s see a couple of examples.
Example 11
The “=” relation is reflexive since a=a for all a\in\mathbb{R}.
The “=” relation is symmetric since whenever a=b we also have b=a.
The “=” relation is transitive since whenever a=b and b=c it must be the case that a, b, and c are the same number, so a=c.
Therefore, “=” is an equivalence relation.
Example 12
Given a,b,m\in\mathbb{Z}, we say that a and b are “equivalent modulo m” or “congruent modulo m,” written “a\equiv b\pmod{m}”, if and only if m|(a-b). We sometimes shorten the wording by using “mod” instead of “modulo,” and a more compact notation is a\equiv_{m} b.
Note: while we don’t restrict m in the definition, this concept is really only interesting and useful when m\geq 2.
The “\equiv_m” relation is reflexive: For any a,m\in\mathbb{Z}, a-a=0 and m|0, so a\equiv_m a.
The “\equiv_m” relation is symmetric: Given a,b,m\in\mathbb{Z} with a\equiv_m b, we have m|(a-b) and so there is a k\in\mathbb{Z} such that (a-b)=km. Then we have (b-a)=-km, and since -k\in\mathbb{Z} this implies m|(b-a) and so b\equiv_m a.
The “\equiv_m” relation is transitive: Given a,b,c,m\in\mathbb{Z} with a\equiv_m b and b\equiv_m c, we have m|(a-b), meaning there is a k_1\in\mathbb{Z} such that a-b=k_1 m. Furthermore, we have m|(b-c), meaning there is a k_2\in\mathbb{Z} such that b-c=k_2 m. Combining these, we have a-c=(a-b)+(b-c)=k_1 m + k_2 m = (k_1+k_2)m, and since (k_1+k_2)\in\mathbb{Z} it follows that m|(a-c) and so a\equiv_m c.
Therefore, “\equiv_m” is an equivalence relation.
Note how in the argument about transitivity in Example 12 we started our argument by going back to the definitions of “what we know.” We explicitly applied the definition to specify values k_1,k_2\in\mathbb{Z}, and manipulated equations from there. This repeats what we said above about the importance of formal definitions: always go back to the definitions!
Practice Problems
The following problems can be used to test your understanding of the material above. Each problem has a solution that you can open, but you should try to solve it yourself first. In particular, you are strongly encouraged to actually write down a solution to commit yourself to it, and then open the answer to see if you were correct.
Let D=\{1,2,3,4,5,6\} and define relation R on D by R=\{(x,y)\in D^2\ |\ x+y=4\}.
- List out the pairs in R.
- How many pairs are in D^2?
- What fraction of pairs in D^2 are also in R?
Let A=\{1,2,3,4\}. For each relation on A described below, list out the pairs in the relation.
- R_1=\{(x,y)\in A^2\ |\ x<y\}
- R_2=\{(x,y)\in A^2\ |\ x+y\leq 4\}
- R_3=\{(x,y)\in A^2\ |\ |x-y|>1\}
For each of the three relations in the previous question, determine if they are reflexive, symmetric, or transitive.
Consider the following relations between people.
Consider the “full siblings” relation, where two people are related by “full siblings” if they have the same biological father and mother. Is this relation reflexive? Symmetric? Transitive?
Consider the “siblings” relation to include half-siblings, where two people are related by “siblings” if they have the same biological father or mother. Is this relation reflexive, symmetric, or transitive?
Consider a relation on students for “taking a class together”, where two students are in the (symmetric) relation if they are taking the same class. Students take more than one class though. Come up with a hypothetical set of students and relations that shows that this relation is not necessarily transitive, and give a brief justification of why your example is not transitive.
While “symmetric” and “antisymmetric” sound like opposites, a relation can be both symmetric and antisymmetric. name a standard mathematical relation on numbers that is both symmetric and antisymmetric.
For each of the following relations on A=\{1,2,3\}, one of the three properties required for it to be an equivalence relation is not satisfied. Identify which property is not satisfied, and explain your answer.
- R_1=\{(1,1),(1,2),(1,3),(2,2),(3,1),(3,2),(3,3)\}
- R_2=\{(1,1),(1,3),(3,1),(3,3)\}
- R_3=\{(1,1),(1,2),(2,1),(2,2),(2,3),(3,2),(3,3)\}
Is every asymmetric relation antisymmetric? Explain.
Is the “divides” relation (see Definition 3) reflexive? Is it symmetric? Is it transitive? Briefly justify any “yes” answer, and give a counterexample for each “no” answer.
YouTube
Facebook