Binary Relations

Definition. A binary relation from a set X to a set Y is a subset of the product $X \times Y$ .

X is called the domain of the relation and Y is called the codomain.

A binary relation on a set S is a subset of the Cartesian product $S \times S$ .

This definition is so abstract that you may find it difficult to see how this is connected to the ordinary idea of things being "related". Here's the idea.

A relationship between two objects is something like

"x is the father of y"

"x is greater than y"

"x and y have the same color"

"$x^2 + y^2 = 4$

Look at "x is the father of y". Your experience in the real world tells you what this means --- how you would verify that a given person is the father of another person. But another way to define the "father" relationship would be to make a list of all father-child pairs. For example, if Bonzo has a son named Wickersham and a daughter named Gordinier, then the following pairs would be on the "father" list:

$$(\hbox{Bonzo}, \hbox{Wickersham}) \quad\hbox{and}\quad (\hbox{Bonzo}, \hbox{Gordinier})$$

You can see that these are ordered pairs --- elements of the Cartesian product

$$\hbox{people} \times \hbox{people}.$$

And a little thought shows that any binary (two-element) relationship can be defined in this way. That's why the formal definition I gave above makes sense.

Example. Suppose $S = \{1, 2, 3, 4\}$ . List the elements of the relation $x < y$ on S, then draw a picture of the relation.

$$S = \{(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)\}.$$

For example, $(1, 4)$ is in the set, because $1 < 4$ .

The picture of the points in a relation is called its graph. Here's the graph of $x < y$ on S:

$$\hbox{\epsfysize=1.5in \epsffile{relations-1.eps}}$$

As usual, I'm using the horizontal axis for the first component and the vertical axis for the second component.

Example. A relation R is defined on $\real$ by

$$(x, y) \in R \quad\hbox{means}\quad x y^3 - x^3 y = 6.$$

Show that $(1, 2)\in R$ . Sketch the graph of R. (You might need a computer to do this.)

$(1, 2)$ is in the relation, because

$$1 \cdot 2^3 - 1^3 \cdot 2 = 6.$$

The graph of the relation looks something like this

$$\hbox{\epsfysize=1.5in \epsffile{relations-2.eps}}$$

Notice that this is not the graph of a function.

Example. List the elements of the relation on the set $S = \{a, b, c, d\}$ whose graph is shown below:

$$\hbox{\epsfysize=1.5in \epsffile{relations-3.eps}}$$

The relation is the set of pairs

$$\{(b, a), (b, c), (c, b), (c, c), (c, d), (d, b), (d, d)\}.\quad\halmos$$

It's common in math to use infix notation for relations. This means that instead of writing an ordered pair $(x, y)$ , you put a relation symbol between x and y --- for example,

$$xRy, \quad\hbox{or}\quad x \oplus y, \quad\hbox{or}\quad x \bowtie y, \quad\hbox{or}\quad x \sim y.$$

It's best to avoid symbols like "$=$ " or "$>$ " which have special meanings --- unless that special meaning is what you want.

For example, consider the relation in the previous example:

$$\{(b, a), (b, c), (c, b), (c, c), (c, d), (d, b), (d, d)\}.$$

Using $\sim$ as the infix relation symbol, you'd write

$$b \sim a, \quad b \sim c, \quad c \sim b, \quad c \sim c, \quad c \sim d, \quad d \sim b, \quad d \sim d.$$

Example. Consider the relation $\sim$ on $\real$ defined by

$$x \sim y \quad\hbox{means}\quad x^2 + x \ge y^2 + y.$$

(a) Prove that $3 \sim 2$ .

(b) Prove that $-1 \not\sim -2$ .

(a) $3^2 + 3 = 12$ and $2^2 + 2 = 6$ . Since $12 \ge 6$ , I have $3 \sim 2$ .

(b) $(-1)^2 + (-1) = 0$ and $(-2)^2 + (-2) = 2$ . Since $0 \not\ge 2$ , I have $-1 \not\sim -2$ .

Example. Consider the relation $\sim$ on $\real^2$ defined by

$$(a, b) \sim (c, d) \quad\hbox{means}\quad a + b > c + d.$$

(a) Prove that $(5, -3) \sim (7, -6)$ .

(b) Prove that $(4, 0) \not\sim (2, 3)$ .

(a) $5 + (-3) = 2$ and $7 + (-6) = 1$ . Since $2 > 1$ , I have $(5, -3) \sim (7, -6)$ .

(b) $4 + 0 = 4$ and $2 + 3 = 5$ . Since $4 \not> 5$ , I have $(4, 0) \not\sim (2, 3)$ .

Very often additional axioms or assumptions are added to the definition of binary relation in order to obtain useful structures. Here are some that we'll consider in detail.

Definition. A relation $\sim$ on a set S is an equivalence relation if:

1. (Reflexivity) $s \sim s$ for all $s \in S$ .

2. (Symmetry) For all $s, t \in S$ , if $s \sim t$ , then $t \sim s$ .

3. (Transitivity) For all $s, t, u \in S$ , if $s \sim t$ and $t \sim u$ , then $s \sim u$ .

An equivalence relation is meant to capture the idea of things "being the same" for the purposes of a given discussion. Here's a real-world example. Suppose you plan to drive to the movies. With that intention alone in mind, there are many things about the car you drive that aren't important --- what color it is, how many miles it's been driven, whether the windshield is tinted, and so on. You care only about the car being suitable for transporting you to the movies. So any two cars --- whatever their color, mileage, or windshield tint, for instance --- are the same for your purposes if either will get you to the movies. The equivalence relation on the set of cars is that two cars are equivalent if both will get you to the movies or both will not get you to the movies.

"Equality" is an obvious example of "being the same". Thus, equality of integers, rational numbers, real numbers, or complex numbers is an equivalence relation.

Definition. Let n be a positive integer. Integers x and y are congruent mod n if $x - y$ is divisible by n. Notation: $x = y \mod{n}$ .

Congruence mod n is an equivalence relation on $\integer$ . Another way to express congruence mod n is: x and y are congruent mod n if x and y leave the same remainder on division by n. But the first definition is easier to use.

For example, $37 = 13 \mod{8}$ , because $37 - 13 = 24$ , and $8 \mid 24$ . And $-50 = 14 \mod{16}$ , because $-50 - 14 = -64$ and $16 \mod -64$ .

Most of the earlier examples been examples of relations on a single set; that is, subsets of a $X \times X$ for some set X. Here's an important example of a relation from a set X to a set Y where X and Y might be different.

Definition. A function is a relation f from a set X to a set Y which satisfies the following property: If $(x, y_1)$ and $(x, y_2)$ are elements of f, then $y_1 = y_2$ .

You may have a little trouble telling how this is the definition of a function you're accustomed to. First, this is a case where we usually use prefix notation for the relation. So instead of writing "$(x, y) \in f$ " or even "$x \sim y$ ", we write "$f(x) = y$ ".

Using prefix notation, the defining condition can be translated to this: If $f(x) = y_1$ and $f(x) = y_2$ , then $y_1 = y_2$ . This is the familiar idea that a function produces a single output for each input. Graphically, this is the "vertical line test".

It's interesting to note that, since a function is a relation, and a relation is a set of ordered pairs (i.e. "points" in the product $X \times Y$ ), a function has actually been defined as its graph.

Contact information

Bruce Ikenaga's Home Page

Copyright 2019 by Bruce Ikenaga