Discrete Math 3: Relations

Last time I talked about sets and some stuff that can be done with sets. First we can look at the union of sets which is the set containing as elements, all of the elements from the sets being unioned. Then we can also look at the intersection of sets, which is the set of all overlapping elements of whatever sets we are looking at.

These are operations between sets, just like addition and multiplication are operations between numbers.

Now I add one more basic, but very essential operation, called the product between sets. For now we only worry about the product of two sets.

Say that we have two sets A and B, then we can form the set of all ordered pairs (a,b) where a is an element of A and b is an element of B. We are taking all possible pairs of things in each set. The notation is

$A \times B = \{(a,b) \mid a \in A, b \in B\}$

Examples will help solidify the concept, one is something that most everybody knows. The X-Y plane that most students are accustomed to use for graphing is just the real numbers “crossed” with the real numbers.

$\mathbb{R} \times \mathbb{R} = \{(x,y) \mid x \in \mathbb{R}, y \in \mathbb{R}\}$

Notice that A and B are just general sets, so they are replaced by the example sets and a,b were just placeholders so this time I chose to use x,y instead. The letters don’t matter much, but some are used for historical reasons.

For example, the point $(0,0)$ is inside of the set $\mathbb{R} \times \mathbb{R}$ because I am taking 0 from the first set and then 0 from the second set.
$(3+i,4)$ is not in $\mathbb{R} \times \mathbb{R}$ because 3+i is not a real number.

I can do a more discrete example by just making up some sets. Say that

$A = \{chair,apple,table\}$
$B = \{1,2,3\}$

Then we can find $A \times B$ by writing out all possible elements.

$A \times B = \{(chair,1),(chair,2)(chair,3),(apple,1),(apple,2)(apple,3),(table,1),(table,2),(table,3)\}$

Notice how the set consists of ordered pairs, and not just single things written out. You can see that as A and B get bigger, $A \times B$ will also grow. In fact for finite sets we have

$n(A \times B) = n(A) n(B)$

Another thing to note is that the order matters. $A \times B$ is generally different from $B \times A$. If we use the same example then

$B \times A = \{(1,chair),(1,apple),(1,table),(2,chair),(2,apple),(2,table),(3,chair),(3,apple),(3,table)\}$

This is different from $A \times B$ because each element is different.
$(1,chair) \ne (chair,1)$

In fact, two ordered pairs are only considered equal when each coordinate is equal.
$(a,b) = (c,d) \text{ when } a=c \text{ and } b = d$

Understanding products of sets will allow us to understand relations. We define a relation in way that will seem weird at first.

Let A and B be two sets, a relation from A to B is a subset of $A \times B$.
Remember $A \times B$ is the set of all possible ordered pairs, so a relation is just some of the possible ordered pairs since it is a subset of $A \times B$.

We generally use the letter R to denote a relation. So for example we would say that a subset

$R \subset A \times B$

is a relation. R is made up of ordered pairs $(a,b)$. Whenever we have that

$(a,b) \in R$ we say that a is related to b. So for something to be related to something else means that the ordered pair consisting of those two things IN THE CORRECT ORDER must be in R.

What I mean is that just because $(a,b) \in R$ doesn’t mean that $(b,a) \in R$ because $(a,b) \ne (b,a) R$ in general.

If we have that R is a relation from A to A then we say that R is a relation on A.
Once we have what R is, the domain of R is all the first coordinates that show up, while the range is all of the possible second coordinates, i.e., not all of A is the domain and not all of B is the range, only some subsets that are actually used in R.

An example is overdue. Let
$A = \{1,2,3\}$
$B = \{a,b\}$
and let
$R = \{(1,a),(3,a),(3,b)\}$

Then R is a relation from A to B since R is a subset of

$A \times B = \{(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)\}$

and we can say that 1 is related to a, 3 is related to a, and 3 is related to b, or with better notation; 1Ra, 3Ra, 3Rb.

The domain of R is the set {1,3} because 2 is not related to anything.
The range of R is the set {a,b} because things are related to both a and b.

In practice we don’t write relations from A to B explicitly in terms of sets, but rather we notice that certain operations ARE relations. Consider the set of integers $\mathbb{Z}$ and cross it with itself.

$\mathbb{Z} \times \mathbb{Z} = \{(a,b) \mid a \in \mathbb{Z}, b \in \mathbb{Z}\}$

Then a relation ON $\mathbb{Z}$ is $<$

The operation of "less than" gives us a subset R of $\mathbb{Z} \times \mathbb{Z}$.
R is the set of all ordered pairs (a,b) with the relation that $a So for example
$(1,3) \in R$ because $1 < 3$, but (4,2) is not in R because 4 is not less than 2.

We can write R as : $R = \{(a,b) \mid a < b\}$

Another relation is equality on a set. Just to be different, we can use the set of positive integers $\mathbb{N}$.
Then $\mathbb{N} \times \mathbb{N} = \{(a,b) \mid a \in \mathbb{N}, b \in \mathbb{N}\}$

Remember for the operation of less than, we were looking at (a,b) where a is less than b. Now we are looking at (a,b) where a = b. Well we know that a = b only when a and b are the same thing, that is we can just say a = a.

Put simply, we want elements of the form (a,a).

$R = \{(a,a) \mid a \in \mathbb{N}\}$

Having a relation leads us to having an inverse relation. Let R be any relation from A to B, then the inverse of R, denoted $R^{-1}$, is the relation from B to A, consisting of elements which when reversed are in R. More precisely,

$R^{-1} = \{(b,a) \mid (a,b) \in R\}$

An easier way to understand this is just to reverse all of the elements. For example if
$R = \{(a,1),(b,3),(c,2)\}$ then
$R^{-1} = \{(1,a),(3,b),(2,c)\}$