# 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

• Women and Epilepsy. FACES. 2014 Annual Epilepsy Conference. April 27, 2014. Patricia Dugan, MD. Assistant Professor of Neurology. NYU Langone Medical Center
• All of the samples will be tested, each to a different cyclic load. Review the video to identify the failure cycle and to identify any pre-failure deformation. Statistical analysis of the populations of two stitch types. The stress-strain curve for...
• Naturalism Vs Non-Naturalism. In the last 150 years, moral realism has focused on trying to decipher the exactly relation between moral properties and natural properties i.e. properties that we can identify through sense experience and science.. This has led to...
• El Retablo Mayor es renacentista con restos de otro anterior. Destacan la tablas pintadas por Pedro Berruguete, cuatro esculturas y un Calvario. Retablo de Nuestra Señora de la Asunción, Iglesia de Santa Eulalia Retablo de la Iglesia de Santa Eulalia...
• QOF - Quality Outcomes Framework. HES - Hospital Episode Statistics. ePACT- electronic Prescribing Analysis and CosTtool. MO KTT- Medicines Optimisation Key Therapeutic Topics . GBIE.DIA.12.09.13(4) Date of Prep - October 2015. Analysis of Diabetes activity, spend and indicators in local...
• Concupiscence:synderesis, conscience, & free will. Damaged or destroyed—Catholic vs. Christian. Death, pain, toil, suffering—punishment or 2nd chance. Spiritual battle since original sin. Sides of the battle. What is really being fought over—war or battles
• Reusable Casting Apparatus for Custom Orthotics Group Members: Ryan Cook, Keegan Compton, Michelle Sauer ... hot plate, heating pad Cold Cold pack, freezer, ice bucket Applied Force & Time of Applied Force Shape of Material Addition of Liquid Foam Density...
• Involvera pat/brukare i den direkta inspektionen tex via intervjuer, enkäter, fokusgrupper. Kan ske redan inledningsvis vid designen av tillsynen, i samband med inspektionen och återföringen av resultatet. GoodMorning and Welcome! ... Chris Day, Director of CommunicationQuality Care Commission.