Are We Related?Relations and FunctionsImages and Inverse ImagesSurjective and like thatEquivalence RelationsEquivalence by FunctionPartitionsProperties of Equivalence RelationsEquivalence by AxiomsPartial OrdersPartial Order by FunctionTotal OrdersProperties of Partial OrdersPartial Orders by AxiomsProducts and Restrictions of RelationsProductsRestrictionsDigraphsPaths in DigraphsDirected Acyclic GraphsTopological SortingParallel Task SchedulingDilworth's LemmaUndirected GraphsSome Common GraphsIsomorphismMassachusetts Institute of Technology Course Notes, Week 46.042J/18.062J, Fall ’05: Mathematics for Computer Science September 26Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld revised October 17, 2005, 463 minutesBinary Relations1 Are We Related?Questions about how two things are related are bound to come up whatever you’re doing. Fortwo people, you might ask if they’re related (as family), if they know each other, if one is olderthan the other, if they’re the same sex, race, age,. . . . For two countries, you might ask if they tradewith each other, if the first has a higher per capita income, if a visa is required to visit one from theother,. . . . In Mathematics or Computer Science, if two variables are assigned values, we’re used toasking if the values are the same, if the first value is bigger than the second (assuming both valuesare real numbers), if the values have a common divisor (assuming both values are integers), ifthe first value is a member of the second (assuming the second value is a set), if the first value isthe domain of the second (assuming the first is a set and the second is a function). These are allexamples of binary relations.The concept of binary relation is as fundamental mathematically as the concept of function or set.In these Notes we’ll define some basic terminology for binary relations, and then we’ll focus ontwo especially important kinds of binary relations: equivalence relations and partial orders.1.1 Relations and FunctionsHere’s the official definition:Definition 1.1. A binary relation, R, consists of a set, A, called the domain of R, a set, B, called thecodomain of R, and a subset of A × B called the graph of R.For example, we can define an “is teaching relation” for Fall ’05 at MIT to have domain equalto the names of all the teaching staff (faculty, T.A.’s, etc.) and codomain equal to all the subjectnumbers in the current catalogue. Its graph would look like{(Albert R. Meyer, 6.042), (David Shin, 18.062), (Sayan Mitra, 6.04),(Albert R. Meyer, 18.062), (Charles E. Leiserson, 6.046),(Donald Sadoway, 3.091), . . . }Notice that Definition 1.1 is exactly the same as the definition of a function, except that it doesn’trequire the functional condition that, for each domain element, a, there is at most one pair in thegraph whose first coordinate is a. So a function is a special case of a binary relation.A relation whose domain is A and codomain is B is said to be “between A and B”, or “from A toB.” When the domain and codomain are the same set, A, we simply say the relation is “on A.” It’scommon to use infix notation “a R b” to mean that the pair (a, b) is in the graph of R.Copyright © 2005, Prof. Albert R. Meyer. All rights reserved.2 Course Notes, Week 4: Binary Relations1.2 Images and Inverse ImagesBefore we go any further, it’s worth introducing some notation that we’ll get a lot of mileage outof. If R is a binary relation from A to B, and C is any set, defineCR ::= {b ∈ B | cRb for some c ∈ C},RC ::= {a ∈ A | aRc for some c ∈ C}.The set CR is called the image of C under R. Notice that if R happened to be a function, thenotation R(C) from Week 3 Notes would also describe the image of C under R.The set RC is called the inverse image of C under R . Notice the clash in notation when R happensto be a function: R(C) = CR, not R C. Sorry about that.1.3 Surjective and like thatA relation with the property that every codomain element is related to some domain element iscalled a surjective (or onto) relation —again, the same definition as for functions. More concisely,a relation, R, between A and B is surjective iff AR = B. Likewise, a relation with the propertythat every domain element is related to some codomain element is called a total relation; moreconcisely, R is total iff A = RB.The Fall ’05 “is teaching relation” relation above is not surjective since none of the Spring term-only subjects are being taught. It’s not total either, since not all the eligible teaching staff areactually teaching this term.2 Equivalence RelationsAn equivalence relation on a set of objects comes about when all we care about is some property—say the size, shape, or color—of the objects rather than the objects themselves. We say two objectswith the same property value are “equivalent.” Of course this happens all the time, which is whyequivalence relations appear everywhere.For example, two triangles in the plane are congruent iff they have the same three lengths of sides.They are similar iff they have the same three sizes of angles.Representation-equivalence comes up in Computer Science as the relation between representations ofthe same abstract data type. For example, the simplest way of representing a finite set of numbersis as an unsorted list. The two lists (3 4 -2 177 5) and (177 -2 3 5 4) are “representation-equivalent” because they represent the same set.2.1 Equivalence by FunctionAbstractly, we assume there is some function that extracts the angles, size, color, or whateverother property of elements we’re interested in. Two elements would be considered equivalent iffthe function extracts the same value for each.Course Notes, Week 4: Binary Relations 3For example, if fcis the function mapping a triangle to the lengths its sides, then fcdeterminesthe congruence relation. If fsis the function mapping a triangle to the sizes of its angles, then fsdetermines the similarity relation.Definition 2.1. Given any total function, f, with domain A, define the binary relation ≡fon A bythe rule:a ≡fb iff f(a) = f(b) (1)for all a, b ∈ A.A binary relation is an equivalence relation iff it equals ≡ffor some f.So congruence of triangles is an equivalence relation because it is ≡fc, as is triangle similaritybecause it is ≡fs. Likewise representation-equivalence on number lists is an equivalence relationbecause it is ≡fr, where frmaps a representation to the set it represents.Quick
View Full Document
Unlocking...