Relations and Their PropertiesWhat is a relationMore relation examplesRepresenting relationsRelations vs. functionsWhen to use which?Relations on a setSlide 8More examplesRelation propertiesReflexivityIrreflexivityReflexivity vs. IrreflexivityGoogle MapsSymmetryAsymmetryAntisymmetryNotes on *symmetric relationsTransitivityTransitivity examplesRelations of relations summaryCombining relationsCombining relations via Boolean operatorsCombining relations via relational compositionSlide 25Slide 26Quick surveySlide 28Slide 29Today’s demotivators11Relations and Their Relations and Their PropertiesPropertiesRosen, section 7.1Rosen, section 7.1CS/APMA 202CS/APMA 202Aaron BloomfieldAaron Bloomfield22 What is a relationWhat is a relationLet Let AA and and BB be sets. A binary relation be sets. A binary relation RR is a is a subset of subset of AA  BBExampleExampleLet Let AA be the students in a the CS major be the students in a the CS majorAA = {Alice, Bob, Claire, Dan} = {Alice, Bob, Claire, Dan}Let Let BB be the courses the department offers be the courses the department offersBB = {CS101, CS201, CS202} = {CS101, CS201, CS202}We specify relation We specify relation RR = = AA  BB as the set that lists all as the set that lists all students students aa  AA enrolled in class enrolled in class bb  BBR = { (Alice, CS101), (Bob, CS201), (Bob, CS202),R = { (Alice, CS101), (Bob, CS201), (Bob, CS202), (Dan, CS201), (Dan, CS202) } (Dan, CS201), (Dan, CS202) }33 More relation examplesMore relation examplesAnother relation example:Another relation example:Let Let AA be the cities in the US be the cities in the USLet Let BB be the states in the US be the states in the USWe define We define RR to mean to mean aa is a city in state is a city in state bbThus, the following are in our relation:Thus, the following are in our relation:(C’ville, VA)(C’ville, VA)(Philadelphia, PA)(Philadelphia, PA)(Portland, MA)(Portland, MA)(Portland, OR)(Portland, OR)etc…etc…Most relations we will see deal with ordered Most relations we will see deal with ordered pairs of integerspairs of integers44 Representing relationsRepresenting relationsCS101CS201CS202AliceBobClaireDanCS101CS101CS201CS201CS202CS202AliceAliceXXBobBobXXXXClaireClaireDanDanXXXXWe can represent relations graphically:We can represent relations in a table:Not valid functions!55 Relations vs. functionsRelations vs. functionsNot all relations are functionsNot all relations are functionsBut consider the following function:But consider the following function:All functions are relations!All functions are relations!1234abcd66 When to use which?When to use which?A function is used when you need to A function is used when you need to obtain a SINGLE result for any element in obtain a SINGLE result for any element in the domainthe domainExample: sin, cos, tanExample: sin, cos, tanA relation is when there are multiple A relation is when there are multiple mappings between the domain and the co-mappings between the domain and the co-domaindomainExample: students enrolled in multiple Example: students enrolled in multiple coursescourses77 Relations on a setRelations on a setA relation on the set A relation on the set AA is a relation from is a relation from AA to to AAIn other words, the domain and co-domain are In other words, the domain and co-domain are the same setthe same setWe will generally be studying relations of this We will generally be studying relations of this typetype88 Relations on a setRelations on a setLet Let AA be the set { 1, 2, 3, 4 } be the set { 1, 2, 3, 4 }Which ordered pairs are in the relation Which ordered pairs are in the relation RR = { ( = { (a,ba,b) | ) | aa divides divides bb } }R = { (1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4) }R = { (1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4) }12341234RR1122334411XXXXXXXX22XXXX33XX44XX99 Consider some relations on the set Consider some relations on the set ZZAre the following ordered pairs in the relation?Are the following ordered pairs in the relation?(1,1) (1,2) (2,1) (1,-1) (2,2)(1,1) (1,2) (2,1) (1,-1) (2,2)RR11 = { ( = { (aa,,bb) | ) | aa≤≤bb } }RR22 = { ( = { (aa,,bb) | ) | aa>>bb } }RR33 = { ( = { (aa,,bb) | ) | aa=|=|b|b| } }RR44 = { ( = { (aa,,bb) | ) | aa==bb } }RR55 = { ( = { (aa,,bb) | ) | aa==bb+1 }+1 }RR66 = { ( = { (aa,,bb) | ) | aa++bb≤3 }≤3 }More examplesMore examplesXXXXXXXXXXXXXXX1010 Relation propertiesRelation propertiesSix properties of relations we will study:Six properties of relations we will study:ReflexiveReflexiveIrreflexiveIrreflexiveSymmetricSymmetricAsymmetricAsymmetricAntisymmetricAntisymmetricTransitiveTransitive1111 ReflexivityReflexivityA relation is reflexive if every element is related A relation is reflexive if every element is related to itselfto itselfOr, (Or, (aa,,aa))RRExamples of reflexive relations:Examples of reflexive relations:=, ≤, ≥=, ≤, ≥Examples of relations that are not reflexive:Examples of relations that are not reflexive:<, ><, >1212 IrreflexivityIrreflexivityA relation is irreflexive if every element is A relation is irreflexive if every element is notnot related to itselfrelated to itselfOr, (Or, (aa,,aa))RRIrreflexivity is the opposite of reflexivityIrreflexivity is the opposite of reflexivityExamples of irreflexive relations:Examples of irreflexive relations:<, ><, >Examples of relations that are not irreflexive:Examples of relations that are not irreflexive:=, ≤, ≥=, ≤, ≥1313 Reflexivity vs. IrreflexivityReflexivity vs. IrreflexivityA relation can be neither reflexive nor A relation can be neither reflexive nor irreflexiveirreflexiveSome elements are related to themselves, Some elements are related to themselves, others are notothers are notWe will see an example of this later onWe will see an example of this later on1414Google MapsGoogle Maps1515 SymmetrySymmetryA relation is symmetric if, for every (A relation is symmetric if, for every (aa,,bb))RR, then , then ((bb,,aa))RRExamples of symmetric relations:Examples of symmetric relations:=, isTwinOf()=, isTwinOf()Examples of relations that are not symmetric:Examples of relations that are not symmetric:<, >, ≤,