Packet #5: Binary Relations

CSC224/226 – Packet 5 – Binary Relations

Packet #5: Binary Relations

Applied Discrete Mathematics

Table of Contents

Binary Relations SummaryPage 1

Binary Relations ExamplesPage 2

Properties of RelationsPage 3

ExamplesPages 4-5

RepresentationsPage 6

CompositesPage 8

ClosuresPages 10-11

Equivalence RelationsPages 12-13

Posets & Hasse DiagramsPages 14-17

CSC224 – Packet 5 – Binary Relations1

CSC224/226 – Packet 5 – Binary Relations

Binary Relations Summary

I.Definition: A binary relation is a set of points, or ordered pairs. The ordered pairs are of the form (a,b) where a is a member of a set A (a  A) and b is a member of a set B (b  B). Any subset R  A x B is a binary relation.

(Remember that A x B is the set of ordered pairs {(a,b) | aA  b  B})

II.Properties: Consider the binary relation R  A x A.

A.Reflexive:R is reflexive if  a  A, (a,a)  R

B.Irreflexive: R is irreflexive if  a  A, (a,a)  R.

Is  (R is reflexive)  (R is irreflexive)?

C.Non-reflexive:  (R is reflexive)

D.Symmetric: R is symmetric if  a, b  A, [ ((a,b)  R)  ((b,a)  R) ]

E.Antisymmetric: R is antisymmetric if

 a, b  A, [(a,b)  R  (b,a)  R]  (b = a)

F.Asymmetric: R is asymmetric if

 a, b  A, [(a,b)  R]  [(b,a)  R]

Asymmetric = irreflexive AND antisymmetric

G.Transitive: R is transitive if

 a, b  A, [(a,b)  R  (b,c)  R]  (a,c)  R

Also: R2 R if and only if R is transitive.

III.Representations

A.Matrix: Form a matrix with the rows labeled with elements of A and the columns labeled with elements of B. Then place a 1 in position (a,b) if (a,b)  R and a 0 in position (a,b) if (a,b)  R.

B.Digraph: Make a column of dots, label one for each element of A. Make another column of dots for the elements of B. Now, for every element (a,b) in R, draw an arrow from point a to point b.

IV.Inverse Relation

V.Composite Relations

VI.Closure Properties (Reflexive, Symmetric, & Transitive closures)

VII.Special Types

A. Equivalence Relations are reflexive, symmetric and transitive (RST)

B. Partially Ordered Sets are reflexive, antisymmetric and transitive (RAT)

Binary Relations

Definition

1.A binary relation is a set of ordered pairs.

2.Each ordered pair consists of elements taken from two sets.

3.The relation xRy is an ordered pair, <x,y> R, with x taken from

the set S, and y taken from the set S.

4.S and S can be finite or infinite. They do not have to be equal.

Examples of Binary Relations

A binary relation R on the set SxT.

Example:

S = {a, b, c}

T = {1, 2, 3}

R = {(a, 1), (a, 3), (b, 2), (c, 3)}

A special binary relation R is a subset of SxS.

Example:

S = {a,b,c,d}

R = {<a,a>, <a,b>, <a,c>, <b,a>, <b,d>, <c,a>, <c,b>, <d,b>}

R is a factor relation on , where for x,y , xRy  x is a factor of y

True or False? 3R6, 5R6, 6R3, 8R24, 5R5, 12R16

Define R on  by xRy  x < y

True or False? 2R3, 2R2, 5R10, 3R2, -1R1, 0R-1

Let R be the "congruent mod 5" relation on  x for x,y ,

xRy  (x-y) is divisible by 5 x  y (mod 5)

True or False? 2R7, -2R2, 2R2, 23R3, 3R23, -1R4, 0R10, -1R5

Let R be the subset relation,

P({1,2,3}), where for A,B  P({1,2,3}), ARB  A  B

True or False? R{1,2}, {1}R{2}, {1}R{1,2,3}, {2,3}R{2,3}, {1,2}R

Properties of Binary Relations

Relation R on set S (Universe of Discourse = S)

Reflexive:if, for all x in S, xRx exists, then R is said to be reflexive.

x[xRx]

Example:

S = {1,2,3,4}

if <1,1>;<2,2>;<3,3>;<4,4>  R, then R is reflexive.

if S = , then R is also empty. Is R reflexive?

Irreflexive:if, for all x in S, there is no xRx, then R is said to be irreflexive. x[(xRx)]

Note:To be irreflexive is different from being non-reflexive.

x[ (xRx)] irreflexive

¬x(xRx) = x[(xRx)] non-reflexive

Symmetric:If xy[xRy  yRx] then R is said to be symmetric.

Antisymmetric:If xy[(xRy  yRx)  (x = y)] then R is said to be antisymmetric.

Note:To be antisymmetric is different from being asymmetric.

xy[xRy (yRx)] asymmetric

Transitive:If xy[(xRy yRz)  xRz] then R is said to be transitive.

Also: R2 R if and only if R is transitive.

Examples of Binary Relations

Example 1: The real plane (R x R) is a binary relation, where points are of the form (x,y) where x R is on the real x-axis and y R is on the real y-axis.

Example 2: The set of points on the graph y = x2 forms a subset of R x R, so it is a binary relation. It can be written as a set as well as by a graph. The set notation is: {(x,f(x)) | x R and f(x) = x2 }. Some points in this binary relation are: (0,0), (-1,1), (1,1), (2,4), (3,9). What are some points that are not in this binary relation?

Example 3: Define a relation R  A x B where A is the set of all dogs on the planet, and B is the set of all humans, and (a,b)  R if dog a belongs to person b. If Tony is a boy and Sparky is a dog, can (Tony, Sparky) be in R? Notice that not all dogs have owners and not all people have dogs, so R  A x B.

Example 4: Let A = {1,3,4,6,7}. Here are some binary relations on A x A. For each of them, determine which properties the relations have.

R1 = {(1,3),(7,4)} is a binary relation.

R2 is defined by: a  A) b  A) a  b  (a,b)  R

R2 ={(1,1),(1,3),(1,4),(1,6),(1,7),

(3,3),(3,4),(3,6),(3,7),(4,4),(4,6),(4,7),(6,6),(6,7),(7,7)}

R3 is defined by: a  A) b  A) a > b  (a,b)  R

R3 = ?

R4 is defined by: a  A) b  A) a  b (mod 3)  (a,b)  R

(Remember that a  b (mod 3) means that a and b have the same remainder if you divide both of them by 3.)

R4 = { (1,1),(1,4),(1,7),(3,3),(3,6),(4,1),(4,4),(4,7),(6,3),(6,6),

(7,1),(7,4),(7,7)}

Examples (Illustrated Under Examples of Binary Relations)

Representations of Binary Relations

A matrix can be used to represent the binary relation by using a 1 to indicate the pairs in the relationship and 0 elsewhere. If S = S, a digraph (also called a directed graph) can be also used to represent the relation, xRy. A digraph consists of vertices (elements of the set S) and directional branches indicating the connection in the ordered pair.

example:S = S = S = {1,2,3,4}

xRy = {<1,2>,<1,4>,<2,3>,<4,4>}

Matrix Representation:

Digraph Representation

It is easy to see if a relation is reflexive from the matrix representing the relation. If the relation is reflexive, M will have all 1's in its major diagonal. If the relation is irreflexive, M will have all 0's in its major diagonal. If the relation is non-reflexive, M will have a mixture of 0's and 1's in its major diagonal.

This matrix is reflexive.

If the relation is symmetric, M is symmetric about the major diagonal. If the relation is antisymmetric, M will not have any symmetry about the major diagonal. If the relation is non-symmetric, M will have at least one set of elements that are symmetric about the major diagonal. (The matrix given below is symmetric.)

Transitivity is a little more difficult to check. One can check element by element xRy, yRz, and xRz for all x, y, and z. You must check EVERY pair xRy and yRz and make sure that xRz is in the relation. Alternatively, you can compute R2 and check: if R2 R then R is transitive.

Definition of R

R is obtained by interchanging the x,y pair for each element in R. So if

R  A x B, then R B x A.

Example 1:R = {<1,2>, <3,4>, <2,3>, <4,1>}

R = {<2,1>, <4,3>, <3,2>, <1,4>}

Using the Matrix to check for properties:

If M is the matrix for R, then R is represented by the transpose of M, where we interchange the rows and columns of M to get M.

if R  M then R M.

If R is symmetric: M = M.

If R is antisymmetric: (M M) is a subset of the identity matrix: i.e. the only 1s are on the major diagonal.

If R is transitive: then R2 R. Compute this using M M, the matrix composition.
Example 2:

R for this case is antisymmetric since: xy[(xRy  yRx)  (x = y)]

(only elements along major diagonal)

Composite Relations

Two relations (R and R) might be composed with each other. However, the inner set between R and R must be the same set.

R R is read as R composed with R. Order is important. One starts with R and looks for the connection to R.

If R is a relation from SS then R must be a relation from Sx Swhere S can be any set. The resulting relation comes from Sx S.

Example 1:

R = {<1,a>, <3,b>, <3,c>, <4,c>}S = {1,2,3,4}

R = {<a,1>, <a,2>, <b,3>, <c,2>}S = {a,b,c}

S = {1,2,3}

R composed with R:

R R = {<1,1>, <1,2>, <3,3>, <3,2>, <4,2>}

RRR R

<1,a<a,1>, <a,2<1,1>, <1,2>

<3,b<b,3<3,3>

<3,c>, <4,c<c,2<3,2>, <4,2>

This function R R can be obtained from the matrices of R and R, i.e. M and M. M of R R = M M. M and M are matrices of 1's and 0's only. M M is simply to multiply M M except multiply is , and add is . NOTE: R R = M M!!!!

Example: (R R)

M M is the same as the matrix of R R.

Note that R R gives all of the linkages between S and S through S of exactly length 2. If S = S = S (special relations), then R R gives all the linkages of exactly length 2 in S. Notice the comparison of that to the statement xRy  yRz (link y of length 2 between x and z).

Therefore, if R is transitive, xy[(xRy yRz)  xRz]

then x  (R R) x  R. Therefore the matrix of R R must be a subset of R.

If R is reflexive, symmetric, and transitive, then R is an equivalence relation. (Discussed later.)

If R is reflexive, antisymmetric, and transitive, then R is a partially ordered set (or poset for short). (Discussed later.)

(R R)  R = R (RR) Associative Law holds

(R R) = RRInverse

Class Lemma: If R and R are relations in ST and R and R are relations in TV, the following holds:

if R R and R R then RR R R

Proof:

<x,y> in RR =

<x,y> in R R =

Since R R and R R

all <x,j> in R <x,j> in R

and <j,y> in R <j,y> in R

Therefore, <x,y> in RR <x,y> in R R

Therefore, RR R R

Closure Properties

The closure of a binary relation, R, with respect to a property, is the minimal relation that contains the relation R and exhibits the given property.

Reflexive closure:

R = R  E where E = {<x,x>  x  S}

Symmetric closure:

R = R  R

Transitive closure:

R =

Reflexive and symmetric closures are easy to see. We shall now prove the transitive closure.

Transitive closure of R is R = . Proof:

1.R must contain R and be transitive.

2.R must be the minimal relation of that type.

Since R is as follows:

R =

it contains R = R.

To see if R is transitive:

xy[(xRy yRz)  xRz]

if there is an xRy, then <x,y> is an element in some R since R is

R =

and if there is an yRz, <y,z> is an element in some R.

RR = R will have the element <x,z> from the definition of the composite of two relations, but the elements of R are also elements of R.

Therefore, R = is transitive.

To show that R is the minimal relation containing R that is transitive, assume that there is another relation R that is (1) transitive, and (2) contains R.

We will show by induction that R R. We will do this by showing that R R for all i, since

R =

For i = 1, R  R, true since R contains R.

Assume true for R, ie R R

Prove true for R, must show that R R.

R = RR

R R by assumption and R  R by basis

RR  RR by class lemma proven earlier

but RR  R since R is transitive.

Therefore, RR  RR R

Therefore, RR  R is true for all i.

Equivalence Relations

A relation is an equivalence relation if it is (reflexive, symmetric, transitive)

Examples:

1.Define R on N by xRy  x = y.

2.Let S be the set of all triangles.

Define R on S by TRT triangles T and T are similar.

3.Let S be the set of all finite state machines with input alphabet {0,1}.

Define R on S by MRM triangles M and M accept the same language.

4.Let f be a function f: S  T.

Define R on S by xRy  f(x) = f(y).

Show R is an equivalence relation:

1.Reflexive: (x[xRx]?)

Since f(x) = f(x) for all x  S, xRx for all x  S.

2.Symmetric: (xy[xRy  yRx]?)

For any x,y in S, if xRy then f(x) = f(y). Thus f(y) = f(x), so yRx.

3.Transitive: (xy[(xRy  yRz)  xRz]?)

For any x,y,z  S, if xRy and yRz then f(x) = f(y) and f(y) = f(z).

Thus f(x) = f(z), so xRz.

5.Let p . (Congruence mod p)

Define R on Z by x Ry  (x-y) is divisible by p

Can show R is an equivalence relation.

If R is an equivalence relation on a set S, then R partitions S into equivalence classes.

For any s  S, [s] denotes the equivalence class containing s.

[s] = {x  S  xRs}

Consider R:

[7] = {...-5,-3,-1,1,3,5,7,9,11,13,...}

[5] = {...-5,-3,-1,1,3,5,7,9,11,13,...}

[2] = {...-4,-2,0,2,4,6,8,...}

How many equivalence classes? 2 (evens and odds)

Consider R : What are the equivalence classes?

[0] = [3] = multiples of three

[1] = [4] = {...-8,-5,-2,1,4,7,10...}

[2] = [5] = {...-4,-1,2,5,8,11,...}

What about R?

[0] = [1] = [2] = ...

(one equivalence class)

6.Define R on by <x,y>R<u,v> x+ y= u+ v

Show R is an equivalence relation: (S = )

1.Reflexive: For any <x,y>  S, <x,y>R<x,y> since x+ y= x+ y.

2.Symmetric: For any <x,y>, <u,v>  S, if <x,y>R<u,v>, then

x+ y= u+ v. So, u+ v = x+ y. Thus, <u,v>R<x,y>.

3.Transitive: For any <x,y>, <u,v>, <w,z>  S, if <x,y>R<u,v> and <u,v>R<w,z>, then x+ y= u+ vand u+ v= w+ z.

So, x+ y= w+ z. Thus, <x,y>R<w,z>.

Equivalence classes of R?

[<0,0>] = ?{<0,0>}

[<0,1>] = ?

[<-2,3>] = ?{<x,y>  x+ y= 13}

How many equivalence classes? infinitely many

Partially Ordered Sets (Usually called a Poset)

A relation is called a poset if it is reflexive, antisymmetric, and transitive.

A subset of a poset P is a poset called a subposet of P.

Hasse Diagrams

Suppose R is a partial order on S. For elements s,t  S, say "t covers s" if sRt and there is no u S satisfying: sRuRt but u  s and u  t.

A Hasse Diagram follows the rules given below:

1.has a point for each element of S.

2.whenever t covers s, point t should be higher than point s, and t and s should be joined by a line segment.

Note: Do not connect an element to itself and do not connect transitive elements.

An element x is maximal if there is no y in the poset so that xRy. An element x is maximum if yRx for all y in poset. Note that maximum elements are also maximal. (Think about this). Maximal elements and maximums are covered by nothing. There is at most one maximum element in a poset. There can be many maximal elements in a poset.

An element x is minimal if there is no y in the poset so that yRx. An element x is minimum if xRy for all y in poset. Note that minimum elements are also minimal. (Think about this). Minimal elements and minimums cover nothing. There is at most one minimum in a poset. There can be many minimal elements in a poset.

Examples

Example 1: Define R as "is a factor of" with S = {1,2,3,4,...,16}.

What covers1? 2,3,5,7,11,133? 6,9,159? Nothing

What is covered by12? 4,6

Hasse Diagram: (Minimal elements are boxed and maximal elements are circled.)

Example 1: Hasse diagram for the relation R=({1,2,3,4, ... , 16}, |)

(|= divides, or "is a factor of")

Example 2: Hasse Diagram for the relation "" on P({1,2,3})

Upper Bounds and Lower Bounds

ub({a}) = {z| aRz }, the set of elements z so that a relates to z.

ub({a,b,c}) = the intersection of ub({a}), ub({b}), and ub({c}).

lb({a}) = {z| zRa}, the set of elements z so that z relates to a.

lb({a,b,c}) = the intersection of lb({a}), lb({b}), lb({c}).

lub(x,y) is the least upper bound = "lowest" element z with xRz and yRz.

glb(x,y) is the greatest lower bound = "highest" element w with wRx and wRy.

Examples

Example 1: Hasse Diagram:

lub(e,d) = a glb(f,g) = h

lub(h,c) = aglb(a,b,d) = d

lub(i,h) = hglb(e,d) = i

lub(e,h,g) = aglb(i,h) = i

lub(a,b) = does not exist

Example 2: If R is the "is a divisor of" relation on , then for x,y 

lub(x,y) = least common multiple of x and y

glb(x,y) = greatest common divisor of x and y.

Lattice: A poset is a lattice if for every pair of elements x,y in the poset, both lub(x,y) and glb(x,y) exist and are in the poset.

CSC224 – Packet 5 – Binary Relations1