# Ch. 7: Relations 7.1 Relations and their Properties

Ch. 8: Relations 8.1 Relations and their Properties Functions Recall ch. 1: Functions Def. of Function: f:AB assigns a unique element of B to each element of A

Functions- Examples and Non-Examples Ex: students and grades Function 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 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. Examples of relations Flights Review of AxB Recall that AxB={(a,b)|a A and b B}

For A={1,2,3} and B={x,y}, find AxB Find AxA Functions and Relations Do a few examples of students and grades and determine if they are functions and/or relations

Notations for Relations Notations: Graphical Tabular Ordered pairs aRb later: matrices and digraphs

Properties for a relation A relation R on a set A is called: reflexive if (a,a) R for every a A symmetric if (b,a) R whenever (a,b) R for a,b A 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

Alternative notation A relation R on a set A is called:

reflexive if aRa for every a A symmetric if bRa whenever aRb for every a,b A antisymmetric : aRb and bRa only if a=b for a,b A transitive if whenever aRb and bRc, then aRc for every a, b, c A Question What does RST show?

RAT? Ex: Consider the following relations R on the set A of all people. Determine which properties (RSAT) hold:circle if so: 1. R={(a,b)| a is older than b } RSAT 2. R={(a,b)| a lives within 10 miles of b }

RSAT 3. R={(a,b)| a is a cousin of b } RSAT 4. R={(a,b)| a has the same last name as b } RSAT More examplesR on the set A of all people. 5. R={(a,b)| as last name starts with the same letter as bs }

RSAT 6. R={(a,b)| a is a (full) sister of b } RSAT Let A=set of subsets of a nonempty set 7. R={(a,b)| a is a subset of b } RSAT

Let A={1,2,3,4} 8. R={(a,b)| a divides b } R={(1,1),(1,2),(1,3),(1,4),(2,2),} RSAT 9. R={(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1),

(4,4)} RSAT 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) }

RSAT RSAT RSAT Number of relations-questions How many relations are there on a set with 4 elements?

AxA has ___ elements. So number of subsets is ___ How many relations are there on a set with n elements? ___ Number of reflexive relations on a set with n elements The other ___may or may not be in. So ___ reflexive relations. Number of relations- Answers

How many relations are there on a set with 4 elements? AxA has 4^2=16 elements. So number of subsets is 2 16 How many relations are there on a set with n 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)} RS RS RS SR

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: S R = {(a,c)| a A, c C, and there exists b B such that (a,b) R and (b,c) S}

Composite example Ex 1: R from {0,1,2,3,4} to {0,1,2,3,4}, S from {0,1,2,3,4} to {0,1,2,3,4} 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 S R Find R S

Ex 2 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 S R Find R S Def of powers

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 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

Thm. 1 Theorem 1: Let R be a transitive relation on a set A. Then Rn is a subset of R for n=1,2,3, Proof what method would work well? Proof

By Induction: N=1: trivially true Inductive Step: Assume Rn R where n Z+. Show: _______ Assume (a,b) R n+1. (Question: Show?____) Then, since R n+1 = R n R, ______________ Since ______, then ____ R. Since _____________ then ______ R.

## Recently Viewed Presentations

• The key to receiving refunds from DMACC A debit card, NOT a credit card It's connected to the "OneAccount," a free FDIC insured checking account How Do I Get My DMACC OneCard and What Do I Do When I Get...
• Playoffs. Los Playoffs de la NBA son tres rondas de competición entre dieciséis equipos repartidos en la Conferencia Oeste y la Conferencia Este. Los ganadores de la Primera Ronda (o cuartos de final de conferencia) avanzan a las Semifinales de...
• Certified Evaluation Folder. Self-Reflection, PGP, Ongoing Reflection, Observations (peer observations will NOT be uploaded), SGG, SV, other documentation ... How often is Donna summatively evaluated? e. Explain what happens if Donna wishes to appeal her . evaluation.
• Dopo la scoperta dell'America Dopo la scoperta dell' America, la colonizzazione europea di quel continente estese la fabbricazione della carta al Nuovo Mondo. Con la fondazione di una prima cartiera nel Messico (1575) ad opera degli spagnoli e di una...
• youtube Cell Rap. The Cell . Cells were discovered in 1663 by Robert Hooke (published in 1665 Micrographia) ... Like a mini-digestive system. Endoplasmic reticulum. Membrane passageways that carry proteins from the nucleolus to the Golgi Bodies. ribosomes. protein synthesis.
• Chapter 4 Understanding research philosophies and approaches Underlying issues of data collection and analysis The research 'onion' Saunders et al, (2008) Understanding your research philosophy (1) 'Research philosophy is an over-arching term relating to the development of knowledge and the...
• Learning Intention. Success Criteria. 2. Work out Tan Ratio. To identify the hypotenuse, opposite and adjacent sides in a right angled triangle. Angles & Triangles
• Skin Appendages Cutaneous Glands Sebaceous (oil) glands Usually empty into hair follicle (oily hair) Produce Sebum - keeps skin soft and has chemical that kills bacteria Become very active in adolescence causing oily skin When sebaceous glands become blocked they...