Mathematics for Computing Lecture 7: Relations Dr Andrew Purkiss-Trew Cancer Research UK e-mail: [email protected] Material to be covered today Relations Definition of a relation Representation of relations Equivalence relations Partial order relations Partitioning Cartesian Products (from last time) A x B = {(x,y): xA and yB} Example: A = {1,3,5}, B = {2,4} A x B = {(1,2),(1,4),(3,2),(3,4),(5,2),(5,4)} Relations If A and B are sets then A binary relation R, from A to B assigns to each ordered pair (a,b) in A x B only (and only one) of the following statements: i) “a is related to b”, written a R b ii) “a is not related to b”, written a R b Relations 2 A relation R from A to B is a subset (R*) of AxB R* = {(a,b): a is related to b} = {(a,b): a R b} or any subset, R*, of A x B, uniquely defines a relation R from A to B a R b whenever (a,b) R* Relation of set on itself Relation on a set A is a subset of A x A. e.g. A = {1,2,3,4}, relation ‘greater than’ {(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)} Graphical Representation Directed Graph 1 2 3 4 Matrix Representation 1 2 3 4 1 F T T T 2 F F T T 3 4 F F F F F F T F Relation Definitions If R is a relation on a set A then: R is reflexive if x R x for all x A R is irreflexive if there are no elements of A for which x R x R is symmetric if x R y implies y R x, for all x, y A R is antisymmetric if x R y and y R x imply x = y, for all x, y A R is transitive if x R y and y R z imply x R z, for all x, y, z A Equivalence Relation An equivalence relation is one that is: reflexive symmetric and transitive Partial Order Relation An partial order relation is one that is: reflexive antisymmetric and transitive Partitioning and equivalence If A is a set, then a partition of A is a set of subsets such that every element in A is an element of exactly one of the subsets. If A is a set and R is an equivalence relation on A. For each element x of A, let E(x) be the subset of A defined: E(x)={yA: y R x}. The set of all E(x) is a partition of A. The subsets E(x) are the equivalence classes of R