Recall: A binary relation R from A to B is a subset of the Cartesian product  If , we write xRy and say that x is related to y with respect to R.
              A relation on the set A is a relation from A to A.

Examples: Given the following relations on Z,

  a.   For which relations is it the case that "2 is related to -2"?
b.   For which relation is it the case that (0,1) belongs to the relation?
 

Exercise: How many relations are there on a set with n-elements?
Ans: By definition a relation is a subset of the Cartesian product A X A. So the question translates into how many subsets are there of the Cartesian product A X A? By known result the answer is.
 

Properties of Relations:

Definition: A relation R on a set A is called reflexive if aRa for every element a in A.

A relation R on a set A is called symmetric if aRb whenever bRa.

A relation R on a set A is called transitive if whenever aRb and bRc, then aRc, for a, b and c in A.
 
 

Exercises: Which of the following relations are reflexive, symmetric and /or transitive.

R₅ = {(x,y) : x and y have the same father}

R₆ = {(x,y) : x is the mother of y}

Combining relations:

Example: Let A = {1,2, 3} and B = {1, 2,3, 4}. Given the relations R₁={ (1,1), (2,2), (3,3)} and R₂={(1,1),(1,2), (1,3), (1,4)}, find

= { (1,1), (2,2,), (3,3), (1,2), (1,3), (1,4) }
= { (1,1)}
= { (2,2,), (3,3) }
= { (1,2), (1,3), (1,4) }
 
 

Definition: Let R be a relation from a set A to a set B and S a relation from B to a set C. The composite of R and S is the relation consisting of ordered pairs (a,c), where a is from A and c is in C, and for which there exists an element b in B such that aRb and bSc. We denote the composite of R and S by
 
 

Example: Suppose R is a relation from A to B and S is a relation from B to C , where A= {1, 2,3}, B = { 1, 2,3, 4}, and C = {0, 1,2} with R = { (1, 1), (1,4), (2, 3), (3, 1), (3, 4)} and S = { (1,0), (2,0), (3,1), (3,2), (4,1)}. What is the composite relation of R and S?
 
 

Homework:

1.  Let R be a relation from a set A to a set B. The inverse relation from B to A, denoted R^-1, is the set of ordered pairs {(b,a) : (a,b) is in R}. The complementary relation  is the set of ordered pairs {(a,b): (a,b) is not in R}. Let be the relation R = { (a,b) : a < b} on the set of integers. FindR^-1 and b. .
2.  Show that the relation R is reflexive if and only if the inverse relation R^-1 is reflexive.

1. Determine whether the relation R on the set of all people is reflexive, symmetric and /or transitive, where aRb if and only if
• a is taller than b
• a and b were born on the same day.
• a has the same first name as b.
• a and b have a common grandparent

1.  Give an example of a relation on a set that is

1. reflexive but not symmetric.
2. Symmetric but not transitive.

3. How many relations are there on a set with n elements that are reflexive?

Convenient Representation for binary relations on a set:
 
 

Let A be an n-element set, B be an m-element set, and . A convenient representation for R is as an matrix [r_ij] in which
 
 

Note that this is a characteristic function on  for the relation R.
 
 
 
 

Queries:

1. What can be said about the matrix for a relation on a set A?

The matrix for a relation on a set A is a square matrix.
 
 
2. What can be said about the matrix for a reflexive relation R on a set A?

The main diagonal consists of all ones.
 
3. What can be said about the matrix for a symmetric relation R on a set A?

It is symmetric with respect to the main diagonal.
 
4. Suppose that  and , what can you say about ?
5. See the Theorem below.

Theorem(composite relations) Let  and  be relations. Then the matrix of the relation is equal to the product of the matrices for relations R and S.
 

Equivalence Relations
 
 

Definition: A relation on a set A is called an equivalence relation if it is reflexive , symmetric and transitive.
 

Example: Let R be the relation on the set of real numbers such that a R b if and only if a - b is an integer. Is R an equivalence relation?
 
 
 
 
 
 
 
 

Example: Let m be a positive integer greater than 1. Show that the relation R = { (a,b) :  is an equivalence relation.
 
 

Equivalence Classes:

Let R be an equivalence relation on a set A. The set of all elements that are related to an element a of A is called the equivalence class of a. The notation is [a]_R.

Example: Given the equivalence relation R = { (a,b) : , list the elements of
[0] =
[1] =
[2] =
[4] =
 
 

Theorem. Let R be an equivalence relation on a set A. The following statements are equivalent:

    i.   a R b

    ii.  [a] = [b]

    iii. [a] [b] = 

Example: Given the set A = {1, 2, 3, 4, 5, 6}. Describe an equivalence relation that produces the following equivalence classes {1,3} , { 2, 4}, and {5, 6}.
 
 
 
 

Definition: A partition of a set A is a collection of disjoint nonempty subsets of A such that their union is the set A.
 
 

Theorem: Let R be an equivalence relation on a set A. Then the equivalence classes of R form a partition of S. Conversely, given a partition {A_i : i is in I} of the set A, there is an equivalence relation R that has the sets A_i, i in I as its equivalence classes.
 
 
 
 
 
 

More Homework:

1. Determine whether the relations represented by the following zero-one matrices are equivalence relations.

 

 
 
 
 
 

(a)  (b)  (c) 
 
 
 
 

2. Let R be the relation on the set of ordered pairs of positive integers such that ((a,b),(c,d)) R if and only if ad = bc. Show that R is an equivalence relation.

1. Which of the following collections of subsets are partitions of the set of integers?

1. the set of even integers and the set of odd integers.
2. The set of positive integers and the set of negative integers.
3. The set of integers divisible by 3, the set of integers leaving remainder 1 when divided by 3, and the set of integers leaving remainder of 2 when divided by 3.
4. The set of integers less than -100, the set of integers with absolute value not exceeding 100, and the set of integers greater than 100.