In reading 3, we described a correspondence between predicates on one variable and sets.  A predicate defines a set, namely the set of all elements of the domain that satisfy the predicate. Conversely, any set S defines a predicate P (x):  x  ∈ S.  Today we discuss an extension of this correspondence to predicates on two variables.

11.1    Relations

Consider a predicate P (x, y) where x ∈ D1  and y ∈ D2  (recall that D1  and D2  are called domains). This predicate defines a (binary) relation. We can think of it as a set of pairs of elements, one from D1  and one from D2, that satisfy the predicate.

11.1.1    Examples

Example  11.1:

• P (x, y): x is a parent of y

• C(x, y): x is a child of y

• M(x, y): x is the mother of y

• S(x, y): x is the spouse of y

Example  11.2:  Some more mathematically flavored predicates we have seen are

• x ∈ y: x is an element of y

• x ≤ y: x is a subset of y

• x < y: x is less than y

• x ≤ y: x is less than or equal to y

• x j y: x divides y

• x  ()  y: x is logically equivalent to y  (in other words, x and y have the same truth table)

• x 三3  y: x and y have the same remainder after division by 3 (in other words, x and y  are congruent modulo 3).

Observe that sometimes both variables of a predicate come from the same domain, and some- times they come from diferent domains. For example, both variables in ≤ are sets. On the other hand, in the relation ∈, the domain for x is some set S, and the domain for y is the set of all subsets of S.  We could make x and y  be from the same domain if we chose the set of all sets as the domain.

11.1.2    Formal Definition of a Relation

We saw examples of operations that make new sets out of old sets.  These operations included taking intersections, unions, or power sets.  In order to define relations formally, we introduce another operation on sets.

Definition 11.1.  The  Cartesian product of sets  A  and B,  denoted A × B,  is  the  set  of all pairs of elements a ∈ A  and b ∈ B ,  that  is,

A × B = {(a, b) | a ∈ A ∧ b ∈ B}.

The parentheses in the notation (a, b) indicate that order matters.  Thus, when we describe an element of A × B, we always list the element of A first and the element of B  second.  Two elements of A × B  are the same if and only if both of their components are the same.  Formally, (a1 , b1 ) = (a2 , b2 ) if and only if a1  = a2  and b1  = b2 .

We now define a relation as a subset of the Cartesian product.

Definition 11.2. A relation R between A and B  (sometimes  from A to B)  is  a  subset  of A × B . We  call A the domain of R,  and B the  codomain of R.  If A = B,  we  say R is  a  relation on A.

The notation (x, y) ∈ R means that x is related to y by R, and we often denote this by xRy instead of using the former notation. For example, we say x ≤ y and x < y, and don’t say (x, y) ∈≤ or (x, y) ∈<.

11.1.3    Specifying Relations

The examples in this section illustrate multiple ways of describing relations. We can define a relation by listing all pairs.

Example  11.3:  Let A = B = {1, 2, 3, 4, 5, 6, 7}. We define the divisibility relation |  between A and B by listing all its elements.  Observe that since |A|  = |B|  = 7, |A × B|  = 49, so the relation | consists of at most 49 pairs. Therefore, there is some hope that we can list all the elements.

For each possibility for the first component, we list all its multiples in the second component. This gives usa representation of the relation | as the set {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (5, 5), (6, 6), (7, 7)}.

We can also represent a relation using a bipartite graph (we will define what a bipartite graph is later in this course). We list all elements of A one one side and elements of B on the other side.

If aRb, we connect the nodes corresponding to elements a ∈ A and b ∈ B with an edge.

Example  11.4:  Figure 11.1a is a graphical representation of the divisibility relation from Example 11.3. For example, 1 divides every integer, so the node labeled 1 on the left side is connected to all nodes on the right side.  In general, a node labeled x  on the left side is connected to nodes representing multiples of x on the right side.   

If a relation, such as the one from Example 11.3, is defined on a set A, we can represent it using a graph that has just one vertex set. This introduces an ambiguity because if we connect vertices a and b with an edge, this edge does not tell us whether aRb or bRa.  Thus, to disambiguate, we use directed edges, where the arrow points at b if aRb, and there will be two edges, one going from a to b, and one going from b to a if both aRb and bRa. Such a graph is called a directed graph, or simply a digraph. A digraph representing the divisibility relation from Example 11.3 is in Figure 11.1b.

Figure 11.1: Representing the divisibility relation of Example 11.3.

Example 11.5:  Congruence modulo 3 (三3) is arelation on A = {1; 2; 3; 4; 5; 6; 7}. The set represent- ing this relation is {(1; 1); (1; 4); (1; 7); (2; 2); (2; 5); (3; 3); (3; 6); (4; 1); (4; 4); (4; 7); (5; 2); (5; 5); (6; 3); (6; 6); (7; 1); (7; 4); (7; 7)}.

Note that since pairs are ordered, we need to list both (1; 7) and (7; 1) in the enumeration of all elements of 三3 .  We also remark here that congruence modulo 3 is an equivalence  relation.  We’ll say more about equivalence relations in the next lecture.

Figure 11.2 shows a directed graph representing the relation 三3 .

Figure 11.2: A directed graph representing the relation 三3 .

11.2    Types of Relations

There are many special types of relations that deserve closer attention. These include

• Functions

• Equivalence relations

• Order relations

We will discuss them in more detail today and in the next lecture.

11.2.1    Functions

You are probably familiar with the concept of a function. Functions turn out to be special cases of relations.

Definition 11.3.  A function f from A to B  is  a  relation  R from A to  B  where for every a ∈ A there  is  at  most  one  b ∈ B  such  that  aRb.   We  say  a function is  total if for  every  a ∈ A  there  is one b ∈ B such that aRb.

We use the notation f : A → B to denote that f is a function from A to B, and write f (a) to denote the the unique b ∈ B  (if any) such that aRb. We also say b is the image of a  under f.

We also mention the notion of an inverse of a relation. Among other things, it is used to describe some properties of relations.  You may be familiar with the notion of an inverse function.  Unlike inverse functions, inverse relations always exist.

Definition 11.4.  The  inverse relation of R from A to B,  denoted R-1,  is  a  relation from B to A such that for all a ∈ A and b ∈ B , aRb  ⇐⇒ bR-1a.

Example  11.6:  Let’s consider the relations from Example 11.1 and see if they are functions.

P (x, y) is not a function.  For a fixed x, there is not necessarily a unique y such that P (x, y)

holds. Person x can be a parent of multiple children.

C(x, y) is also not a function. A child has two parents.

M (x, y) is not a function because a person can be the mother of multiple children; however, the inverse relation is a function. The predicate M-1(y, x) says “y has x as a mother”, and every person has exactly one mother. Thus, M-1  is a total function.

S(x, y) is a function because a person has only one spouse.  The function isn’t total because some people are not married.   

Below we describe some important kinds of functions:

Definition 11.5. A function f is one-to-one if its  inverse relation f-1  is  a function.   We  also say f is injective.

Observe that f is injective if and only if (∀a1 , a2  ∈ A)  (f (a1 ) = f (a2 )) ⇒ (a1  = a2 ).

Definition 11.6. A function f is onto if for every b ∈ B, there is some a ∈ A such that f (a) = b. We also say f is surjective.

Definition 11.7. A function that is injective and surjective is called bijective.

Suppose f is an injective total function. Then every element of A maps to a diferent element of B, and for this to be possible, there must be at least one diferent element of B for each element of A. Hence, |A| ≤ |B| .  We don’t get equality because there could be some elements b  ∈ B  that are not related to any a ∈ A. Also note that we can have |A| > |B| if f is injective but not total.

If f is a surjective function, we have |A| ≥ |B| . This does not require f to be total. If f is a bijective total function, then |A| = |B| .

We can use the observations about injective, surjective, and bijective functions to compare cardinalities of sets. For example, if we can find a total function from A to B and prove that it is injective, we also get a proof that |A| ≤ |B| .

11.2.2    Relations on a Set A

We have seen many examples of relations where the domain and the codomain are equal. We now introduce some properties such relations can have. We use some of the relations from Example 11.2 to give examples of relations with those properties. A summary of relations and their properties is in Table 11.1 at the end of this section.

Definition  11.8.  A   relation  R  on  set  A  is   reflexive  if  (∀a  ∈ A)   aRa.   It  is   antireflexive  if

(∀a ∈ A) ¬aRa.