RelationsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSections 7.1, 7.3–7.5 of [email protected] that a relation between elem ents of two sets is a subset oftheir Cartesian product (of ordered pairs).DefinitionA binary relation from a set A to a set B is a subsetR ⊆ A × B = {(a, b) | a ∈ A, b ∈ B}Note the difference between a relation and a function: in arelation, each a ∈ A can map to multiple elements in B. Thus,relations are generalizations of functions.If an ordered pair (a, b) ∈ R then we say that a is related to b. Wemay also use the notation aRb and a6Rb.NotesRelationsTo represent a relation, you can enumerate every element in R.ExampleLet A = {a1, a2, a3, a4, a5} and B = {b1, b2, b3} let R be arelation from A to B as follows:R = {(a1, b1), (a1, b2), (a1, b3), (a2, b1),(a3, b1), (a3, b2), (a3, b3), (a5, b1)}You can also represent this relation graphically.NotesRelationsGraphical ViewA Ba1a2a3a4a5b1b2b3Figure: Graphical Representation of a RelationNotesRelationsOn a SetDefinitionA relation on the set A is a relation from A to A. I.e. a subset ofA × A.ExampleThe following are binary relations on N:R1= {(a, b) | a ≤ b}R2= {(a, b) | a, b ∈ N,ab∈ Z}R3= {(a, b) | a, b ∈ N, a − b = 2}Exercise: Give some examples of ordered pairs (a, b) ∈ N2thatare not in each of these relations.NotesReflexivityDefinitionThere are several properties of relations that we will look at. If theordered pairs (a, a) app ear in a relation on a set A for every a ∈ Athen it is called reflexive.DefinitionA relation R on a set A is called reflexive if∀a ∈ A(a, a) ∈ RNotesReflexivityExampleExampleRecall the following relations; which is reflexive ?R1= {(a, b) | a ≤ b}R2= {(a, b) | a, b ∈ N,ab∈ Z}R3= {(a, b) | a, b ∈ N, a − b = 2}IR1is reflexive since for every a ∈ N, a ≤ a.IR2is also reflexive sinceaa= 1 is an integer.IR3is not reflexive since a − a = 0 for every a ∈ N.NotesSymmetry IDefinitionDefinitionA relation R on a set A is called symmetric if(b, a) ∈ R ⇐⇒ (a, b) ∈ Rfor all a, b ∈ A.A relation R on a set A is called antisymmetric if∀a, b,(a, b) ∈ R ∧ (b, a) ∈ R→ a = bfor all a, b ∈ A.NotesSymmetry IIDefinitionSome things to note:IA symmetric relationship is one in which if a is related to bthen b must be related to a.IAn antisymmetric relationship is similar, but such relationshold only when a = b.IAn antisymmetric relationship is not a reflexive relationship.IA relation can be both symmetric and antisymmetric orneither or have one property but not the other!IA relation that is not symmetric is not necessarily asymmetric.NotesSymmetric RelationsExampleExampleLet R = {(x, y) ∈ R2| x2+ y2= 1}. Is R reflexive? Symmetric?Antisymmetric?IIt is clearly not reflexive since for example (2, 2) 6∈ R.IIt is symmetric since x2+ y2= y2+ x2(i.e. addition iscommutative).IIt is not antisymmetric since (13,√83) ∈ R and (√83,13) ∈ Rbut136=√83NotesTransitivityDefinitionDefinitionA relation R on a set A is called transitive if whenever (a, b) ∈ Rand (b, c) ∈ R then (a, c) ∈ R for all a, b, c ∈ R. Equivalently,∀a, b, c ∈ A(aRb ∧ bRc) → aRcNotesTransitivityExamplesExampleIs the relation R = {(x, y) ∈ R2| x ≤ y} transitive?Yes it is transitive since (x ≤ y) ∧ (y ≤ z) ⇒ x ≤ z.ExampleIs the relation R = {(a, b), (b, a), (a, a)} transitive?No since bRa and aRb but b6Rb.NotesTransitivityExamplesExampleIs the relation{(a, b) | a is an ancestor of b}transitive?Yes, if a is an ancestor of b and b is an ancestor of c then a is alsoan ancestor of b (who is the youngest here?).ExampleIs the relation {(x, y) | x2≥ y} transitive?No. For example, (2, 4) ∈ R and (4, 10) ∈ R (i.e. 22≥ 4 and42= 16 ≥ 10) but 22< 10 thus (2, 10) 6∈ R.NotesOther PropertiesDefinitionIA relation is irreflexive if∀a(a, a) 6∈ R IA relation is asymmetric if∀a, b(a, b) ∈ R → (b, a) 6∈ R LemmaA relation R on a set A is asymmetric if and only ifIR is irreflexive andIR is antisymmetric.NotesCombining RelationsRelations are simply sets, t hat is subsets of ordered pairs of theCartesian product of a set.It therefore makes sense to use the usual set operations,intersection ∩, union ∪ and set difference A \ B to combinerelations to create new relations.Sometimes combining relations endows them with the propertiespreviously discussed. For example, two relations may not betransitive alone, but their union may be.NotesCombining RelationsExampleLetA = {1, 2, 3, 4}B = {1, 2, 3}R1= {(1, 2), (1, 3), (1, 4), (2, 2), (3, 4), (4, 1), (4, 2)}R2= {(1, 1), (1, 2), (1, 3), (2, 3)}ThenIR1∪ R2={(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (3, 4), (4, 1), (4, 2)}IR1∩ R2= {(1, 2), (1, 3)}IR1\ R2= {(1, 4), (2, 2), (3, 4), (4, 1), (4, 2)}IR2\ R1= {(1, 1), (2, 3}NotesDefinitionLet R1be a relation from the set A to B and R2be a relationfrom B to C. I.e. R1⊆ A × B, R2⊆ B × C. The composite ofR1and R2is the relation consisting of ordered pairs (a, c) wherea ∈ A, c ∈ C and for which there exists and element b ∈ B suchthat (a, b) ∈ R1and (b, c) ∈ R2. We denote the compos ite of R1and R2byR1◦ R2NotesPowers of Rel ationsUsing this composite way of combining relations (similar tofunction composition) allows us to recursively define powers of arelation R.DefinitionLet R be a relation on A. The powers, Rn, n = 1, 2, 3, . . ., aredefined recursively byR1= RRn+1= Rn◦ RNotesPowers of Rel ationsExampleConsider R = {(1), (2, 1), (3, 2), (4, 3)}R2=R3:R4:Notice that Rn= R3for n=4, 5, 6, . . .NotesPowers of Rel ationsThe powers of relations give us a nice characterization oftransitivity.TheoremA relation R is transitive if and only if Rn⊆ R for n = 1, 2, 3, . . ..NotesRepresenting RelationsWe have see n ways of graphically representing a function/relationbetween two (different) sets—specifically a graph with arrowsbetween nodes that are related.We will look at two alternative ways of representing relations; 0-1matrices and directed graphs.Notes0-1 Matrices IA 0-1 matrix is a matrix whose entries are either 0 or 1.Let R be a relation from A = {a1, a2, . . . , an} toB = {b1, b2, . . . , bm}.Note that we have induced an ordering on the elements in eachset. Though this ordering is arbitrary, it is important to beconsistent; that is, once we fix an ordering, we stick with it.In the case
View Full Document
Unlocking...