Binary Relations

We recall that the cartesian product of two sets $A \times B$ is the set of all ordered pairs (a,b) with $a \in A$ and $b \in B$. A subset of the cartesian product is called a relation or binary relation on the two sets.

It follows that if $\Re$ is a relation defined over the sets Aand B, then for any given ordered pair $(a,b) \in A \times B$, that ordered pair will or will not belong to $\Re$. If (a,b) does belong to $\Re$, that is $(a,b) \in \Re$, then we write a $\Re$ b. This notation is used to stress the fact that when $(a,b) \in \Re$, a relationship exists between a and b. If the sets A and B are the same, then a relation $\Re$ is a subset of $A \times A$ and we say that $\Re$is a relation on A.

As an example of a relation, suppose that John knows PASCAL, Lee knows FORTRAN, Barbara knows C and Pauline knows COBOL. If we let Pdenote the set of people, so that

$P = \{John, Lee, Pauline, Barbara\}$

and D denote the set of computer languages

D = {C, COBOL, FORTRAN, PASCAL}

we can then express who knows which language in terms of a relation K where

K = { (John, PASCAL), (Lee, FORTRAN), (Barbara, C), (Pauline, COBOL)}

In this example, p K d represents the relation ``person p knows computer language d''. We can also express this relation formally using set notation

K = { (p, d) $\vert$ person p knows computer language d }

Note that the cartesian product $P \times D$ contains 16ordered pairs and that K is a subset containing four of those pairs.

The following are all examples of relations on the set of integers $\Int$.

1.

     $\{ (x,y) \enskip \vert \enskip x > y \}$

2.

     $\{ (x,y) \enskip \vert \enskip y = x^2 \}$

3.

     $\{ (x,y) \enskip \vert \enskip 2x + 3y = 1 \}$