Relations and Functions in Computer Science

Department of Computer Science, Faculty of Electrical Engineering and Computer Science, VSB - Technical University of Ostrava Relations and functions 1

Contents Theory of sets Relations and mappings Relation Binary relation on a set Mapping Partition & equivalence Orderings Algebras Algebras with one operation Algebras with two operations Lattices 2

Relations n-ary relation between the sets A1, A2, ..., An A r 1 A n A 2 Examples: D = a set of possible days M = a set of V B rooms Z = a set of V B employees A ternary relation meeting (when, where, who): Z 2 r D M 3

Binary relations r A B Inverse relation: 1 = {( , ) : ( , ) } r x y B A y x r Composition of relations , r A B s B C ( )} = {( , ) ( : ) ( , ) and ( , ) r s x y A C z B x z r z y s A r B B s C A r o s C 4

Binary relations Binary relation r on a set A is called: Reflexive: x A: (x,x) r Irreflexive: x A: (x,x) r Symmetric: x,y A: (x,y) r (y,x) r Antisymmetric: x,y A: (x,y) r and(y,x) r x=y Asymmetric: x,y A: (x,y) r (y,x) r Transitive: x,y,z A: (x,y) r and(y,z) r (x,z) r Cyclic: x,y,z A: (x,y) r and(y,z) r (z,x) r Continuous: x,y A: x=y or (x,y) r or (y,x) r 5

Binary relations The important types of binary relations: Tolerance reflexive, symmetric Quasi-ordering reflexive, transitive Equivalence reflexive, symmetric, transitive Partial ordering reflexive, antisymmetric, transitive 6

Binary relations Examples: Tolerance: being similar to on a set of people, being no more than one year older or younger on the set of people, ... Quasi-ordering: on a set of sets: the sets X and Y are related iff |X| |Y|, divisibility relation on the set of integers, not to be older on a set of people, ... Equivalence: being of the same age on the set of people, identity on the set of natural numbers, ... Ordering: Set-theoretical inclusion on a set of sets, divisibility relation on the set of natural numbers, ... 7

Mapping (functions) f A B is called a mappingfrom a set A into a set B (partial mapping), iff: ( x A, y1,y2 B) ( (x,y1) f and(x,y2) f y1 = y2) f is called amapping of a set A into a set B (total mapping, written as: f: A B), iff: f is mapping from A to B ( x A)( y B) ( (x,y) f) If f is a mapping and (x,y) f, then we write f(x)=y 8

Mapping (functions) Examples: r A B s A B t A B A B A B A B u = {(x,y) Z Z; x=y2}, w = {(x,y) Z Z; y=x2} v = {(x,y) N N; x=y2}, r, u are not mappings s, v are partial mappings from A to B, (not total) t, w are total mappings 9

Mapping (functions) Mapping f: A B is called Injection (one to one total mapping of A intoB), iff: x1,x2 A, y B: (x1,y) f and(x2,y) f x1 = x2 Surjection (mapping of A onto B), iff: y B x A: (x,y) f Bijection (one to one mapping of A onto B) (mutually single-valued), iff it is injection and surjection. 10

Mapping (functions) Examples: f : A B g : A B A h : A B i : A B A B B A B A B j: Z Z, j(n)=n2, l: N N, l(n)=n+1, f, j are neither injections nor surjections h, k are surjections, not injections g, l are injections , not surjections I,m are injections and surjections simultaneously bijections k: Z N, k(n)=|n|, m: R R, j(x)=x3 11

Partitions and equivalences Partition on a set A is a system such that: X = { Xi; i I } Xi A for i I Xi Xj= for i,j I, i j U X = A (the union of Xi= A) Xi classes of the partition Fine graining of a partition X = { Xi; i I } is a system such that: Y = { Yj; j J }, iff: j J, i I so that Yj Xi A A 12

Partitions and equivalences Let r be an equivalence relation on a set A, X is a partition on A, then it holds: Xr = {[x]r; x A} a partition on Ainduced by equivalence r; where [x]r is the class of those elements that are equivalent with x quotient set (factor set) of the set A induced by the equivalence r rX = {(x,y); x and y belong to the same class of the partition X} equivalence on A (induced by the partition X) Example: r Z Z; r = {(x,y); 3 divides x-y } X={X1, X2, X3} X1={ -6, -3, 0, 3, 6, } X2={ -5, -2, 1, 4, 7, } X3={ -4, -1, 2, 5, 8, } 13

Orderings If r is an order relation on A, then a couple (A,r) is called an ordered set Examples: (N, ), (2M, ) Cover relation Let (A, ) be an ordered set, (a,b) A a < b( b covers a ), iff: a < b and c A: a c a c b Examples: (N, ), < ={(n,n+1); n N} 14

Orderings Hasse diagram graphical picturing Example: (A, ), A={a,b,c,d,e} r = {(a,b), (a,c), (a,d), (b,d)} idA idA={(a,a): a A} d b c e a 15

Orderings An element a of an ordered set (A, ) is called: The least: for x A: a x The greatest: for x A: x a Minimal: for x A: (x a x = a) Maximal: for x A: (a x x = a) d Example: The least: does not exist The greatest: does not exist Minimal: a, e Maximal: d, c, e b c e a 16

Orderings A mapping of the ordered sets (A, ), (B, ) is called isomorphic, iff there is a bijection f: A B such that: x,y A: x y, iff f(x) f(y) A mapping of the ordered sets (A, ), (B, ) is called isotonef: A B, when the following holds: x,y A: x y f(x) f(y) Examples: f: N Z, f(x)=kx, k Z, k 0 is isotone g: N Z, g(x)=kx, k Z, k 0 is not isotone 17

Orderings Let (A, ) be an ordered set, M A, then LA(M)={x A; m M: x m } The set of lower bounds of M in A UA(M)={x A; m M: m x } The set of upper bounds of M in A InfA(M) The greatest element of the set LA(M) Infimum of the set M in A SupA(M) The least element of the set UA(M) Supremum of the set M in A 18