Section 13.1 Introduction to relations
A relation is a way to mathematically encode the idea of a relationship between objects. What does that mean? When we “encode” an idea mathematically, we are defining a mathematical object that captures the important data of that idea. Because the thing is now a mathematical object, we can do mathematics to it. If the thing has become an expression involving real numbers, it is now subject to algebra. If the thing has become a set, it is now subject to set operations, logic, proof, combinatorics, so on. One may imagine importing a package into a programming language so they have new objects to “play with” in that language.
In this chapter we will define relations, discuss various ways to represent them, and discuss some properties of interesting relations.
Remember that the product \(X \times Y\) of two sets is the collection of all pairs \((x,y)\) whose first component is from \(X\) and whose second component is from \(Y\text{.}\) Therefore, this is a good place to start thinking about connecting two sets.
Definition 13.1.1.
Let \(X\) and \(Y\) be sets. A relation \(R\) from \(X\) to \(Y\) is any subset \(R \subseteq X \times Y\text{.}\) We say that \(X\) is the domain and \(Y\) is the codomain of \(R\text{.}\) When \((x,y) \in R\text{,}\) we say “\(x\) is related to \(y\)” and may write \(xRy\text{.}\)
If \(X=Y\text{,}\) we say \(R\) is a relation on \(X\text{.}\)
Example 13.1.2.
Let \(X = \{x,y,z\}\) and \(Y=\{1,2\}\text{.}\) One of the many relations from \(X\) to \(Y\) is the set
We would say (for instance) that \(x\) is related to \(1\text{,}\) or that \(z\) is related to nothing.
Example 13.1.3.
Let \(A\) be the set of seven-digit numbers and let \(B\) be the set of students at Coastal Carolina University. Consider the relation \(S\) consisting of pairs \((a,b)\) where \(b\) is a student and \(a\) is that student's ID number.
Some relations have their own symbols. We will be a little sloppy and sometimes identify the statement \(xRy\) with the relation itself. For example, we might write the statement \(x \le y\) to refer to the set
Definition 13.1.4.
The relation \(\Delta=\{(x,x) \;|\; x \in X\}\) is the relation of all pairs \((x,y) \in X \times X\) where \(x=y\text{.}\) (When the domain and codomain of a relation are the same we say it is a relation on \(X\text{.}\)) This relation is called the diagonal relation on the set \(X\text{.}\)
As an exercise, figure out before the next section why this relation is called the diagonal relation. It may be denoted with the symbol \(\Delta\) (capital “delta”), or it may be denoted with the statement characterizing its elements. In other words, we might say “Consider the relation \(x=y\) on a set \(X\text{.}\)”