7.1 Relations and Their Properties

Ch. 7: Relations

7.1 Relations and their Properties

Recall ch. 1: Functions

Def. of Function: f:A→B assigns a unique element of B to each element of A

Show Ex and Non-Ex

Ex: A={1,2,3,4,5,6}, B={a,b,c,d,e,f}

{(1,a),(2,c),(3,b),(4,f),(5,b),(6,c)} is a subset of AxB

Also show graphical format.

Relations are also subsets of AxB, without the above uniqueness requirement of functions.

Def. of Relations: Let A and B be sets. A binary relation from A to B is a subset of AxB.

Special Case: A relation on the set A is a relation from A to A.

Notations:

·  Graphical

·  Tabular

·  Ordered pairs

·  aRb

·  later: matrices and digraphs

Properties:

A relation R on a set A is called:

·  reflexive if (a,a) R for every a A (or: aRa for every a A)

·  symmetric if (b,a) R whenever (a,b) R for a,b R

·  antisymmetric : (a,b) R and (b,a) R only if a=b for a,b A

·  transitive if whenever (a,b) R and (b,c) R, then (a,c)R for a,b,c A

Q: What does RST show?

RAT?

Ex: Consider the following relations R on the set A of all people. Determine which properties (RSAT) hold:

1. R={(a,b)| is older than b }

2. R={(a,b)| a lives within 10 miles of b }

3. R={(a,b)| a is a cousin of b }

4. R={(a,b)| a has the same last name as b }

5. R={(a,b)| a’s last name starts with the same letter as b’s }

6. R={(a,b)| a is a (full) sister of b }

Let A=set of subsets of a nonempty set

7. R={(a,b)| a is a subset of b }

Let A={1,2,3,4}

8. R={(a,b)| a divides b }

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

9. R={(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4)}

Let A=Z (integers)

10, R={(a,b)| a≤ b }

11. R={(a,b)| a=b+1 }

12. R={(1,1), (2,2), (3,3) }

Number of relations:

How many relations are there on a set with 4 elements? AxA has 4^2=16 elements. So number of subsets is 216

How many relations are there on a set with 4 elements? 2n^2

Number of reflexive relations on a set with n elements

The other n(n-1) may or may not be in.

So 2n(n-1) reflexive relations.

Combining Relations

Ex: sets A={1,2,3}, B={1,2,3,4};

Relations: R={(1,1),(2,2), (3,3)}, S={(1,1), (1,2), (1,3), (1,4)}

R∩S

RŲS

R – S

S – R

Def. of Composite:

Let R be a relations from A to B and S a relations from B to C.

The composite of R and S:

SR = {(a,c)| a A, c C, and there exists b B such that (a,b) R and (b,c) S}

Ex 1: R from {0,1,2,3} to {1,2,3,4}, S from {1,2,3,4} to {0,1,2,3}

R={(1,0), (1,1), (2,1), (2,2), (3,0), (3,1)}

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

Find SR and RS

Ex. 2: R and S on the set of all people:

Let R={(a,b)| a is the mother of b}

S={(a,b)|a is the spouse of b}

Find SR and RS

Def: Let R be a relation on the set A.

The powers Rn, n=1,2,3,… are defined inductively by R1=R and Rn+1=Rn R

Ex:

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

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

R3=…

Show R4=R3

So Rn=R3 for n=4, ..

Ex.

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

R2 = {(1,1), (1,2), (3,5)}

R3={(1,1), (1,2)}

R4=R3 so Rn=R3

Theorem 1: Let T be a transitive relation on a set A. Then Rn is a subset of R for n=1,2,3,…

Proof—……