Four Relations and Functions Set theory provides a formal foundation for studying objects that are interesting and useful in computer applications When objects of several sets are related we use more complex sets called relations and functions to model their relationships For example the student body and the academic departments in a college are related through the Majors relationship relating each student to the student s current major s In another example the set of students and the set of classes offered in a given semester are related based on the classes taken by each student In this chapter we will first study the formal definitions and properties of relations We will then study a restricted type of relations known as functions 4 1 Relations 4 1 1 Notations and Definitions Definition A relation R defined over sets A and B is a i e any subset of A B that is R A B Such a relation is a binary relation the degree of R is 2 For each element a b R of a binary relation R we also write it as aRb Example Let A Adam John Smith be a set of students and B Art History mathematics be a set of departments A relation Student major showing the students and their major s could be Student major Adam History Adam Mathematics John Art Smith History 4 1 Dr S Lang A binary relation R can be conveniently depicted by a directed graph in which each pair a b R corresponds to a directed edge from vertex a to vertex b Example The following digraph represents the Student major relation defined in the preceding example p 2 1 Art Adam John History Smith Mathematics More generally A relation can be defined over n sets n 2 Definition An n ary relation R over sets A1 A2 An n 2 is a subset of the cartesian n n Ai product that is Ai R The degree of R is n i 1 i 1 Example Consider the purchase of a new car which frequently involves a buyer a salesperson a new car and a trade in Thus a car purchase is a relation of degree 4 because it can be considered as a subset of B S N T where B S N and T stand for respectively the sets of buyers salespersons new cars and trade ins 4 2 Dr S Lang We note here that a finite relation of any degree n can be conveniently represented by a two dimensional table of n columns in which the rows of the table represent the tuples of the relation For example a car sales table as described by the preceding example could be depicted as follows Buyer Salesperson New Car Trade in J Smith Mr No nonsense Toyota Tacoma Jeep Cherokee In fact the now popular relational database systems have their origin rooted in the theories and properties of relations as studied in set theory supplemented with implementation techniques 4 1 2 Properties and Manipulations of Binary Relations Binary relations receive the most thorough studies because their simplicity and because that they form the basis for studying relations of higher degrees We will consider the following definitions and notations for binary relations Definition Let R A B and S B C denote two relations The composition of R and S denoted R S is a binary relation over A and C defined as follows R S a c a A and c C and there exists b B such that aRb and bSc 4 3 Dr S Lang Example Let A a b c B 1 2 and C p q r Define the relations R a 1 a 2 b 1 c 2 and S 1 p 1 q 2 r Then R S a p a q a r b p b q c r The composition of two binary relations R A B and S B C can also be conveniently depicted by composing the digraphs corresponding to R and S That is there is a directed edge between x A and y C in R S iff there is a directed path of length 2 connecting vertex x via a vertex z B to vertex y in the composed digraph Example Two digraphs depicting R and S and one digraph for R S of the preceding example a p a p b q c r 1 q b 2 c r R S R S Note that the digraph for the composition relation R S is the composition of the two digraphs corresponding to respectively the relations R and S The following theorems summarize simple properties satisfied by relation compositions 4 4 Dr S Lang Theorem Let R A B S B C and T C D denote three binary relations Then relation compositions satisfy the following associative law R S T R S T Proof We first note that both sides of the equation define a relation over A D We also note the following R S T a d a A and d D and for some c C a c R S and cTd by the definition of T Since a c R S means aRb and bSc for some b B by definition of R S the relation R S T consists of pairs a d A D such that for some b B and some c C aRb bSc and cTd Similarly by the definition of R R S T a d a A and d D and for some b B aRb and b d S T Since b d S T means bSc and cTd for some c C thus the relation R S T also consists of pairs a d A D such that for some b B and some c C aRb bSc and cTd Thus R S T R S T and the theorem is proved Example Define 3 relations over A 1 2 3 R 1 2 1 3 S 2 1 3 2 and T 1 1 2 3 Then R S 1 1 1 2 S T 2 1 3 3 R S T 1 1 1 3 R S T 4 5 Dr S Lang Theorem Let R A B S B C and T B C denote 3 binary relations Then 1 R S T R S R T 2 R S T R S R T In general the two sides of 2 are not equal Proof 1 R S T a c a A and c C and for some b B aRb and b c S T definition of a c a A and c C and for some b B aRb and b c S or b c T definition of a c a A and c C and for some b B aRb and b c S or aRb and b c T distributive law of and over or a c a A and c C and for some b B aRb and b c S a c a A and c C and for some b B aRb and b c T definition …
View Full Document
Unlocking...