Preliminaries and Notation xvii where each member set is the names of people in a family: {{Fred,Mary,John},{Alf,Claire,Sue,Joe},...,{Jim,Anne}} Relations A relation R on S1,S2,...,Sn is defined as a subset of the cartesian product of these sets: TCS1 *S2*...*Sn R is called an n-ary relation.When n =2,R is called a binary relation.When n 3,R is called a ternary relation.For example relation age ={(Fred,25),(Jim,16),(Mary,25)} where S1={Fred,Jim,Mary}and S2 ={25,16}. Mappings (or Functions) A mapping or a function,F,from set Si to set S2 is a binary relation on S and S2 such that for every element x in S1 there is at most one element y in S2 such that (x,y)e F.This is denoted as F(x)=y.In other words,if F(x)=y and F(x)=z,then y must be equal to z.For instance,age is a function from the set {Fred,Jim,Mary}to the set {16,25}.Set S1 is called the domain of the map- ping F and set S2 is called the range of F.This is usually represented as F:S1→S2 Thus age {Fred,Jim,Mary}{16,25} An injective or one-to-one mapping,F,is one such that F(a)=F(b)if and only if a =b.If F is not injective,it is called a many-to-one function. A surjective mapping,F,is one such that for each y e S2,there exists an x∈S1 such that F(x)=y. A bijective mapping,F,is one which is both injective and surjective. Permutation and Combinations A permutation of m-ary tuples on a set S={a1,a2,...,an}is a set of ordered tuples(xi,x2,.·,xm)such thatxi∈S(for all)andx:≠x if i≠i A combination of m-ary tuples on a set S={a1,a,....an}is a set of un- ordered tuples(x1,x2,,,xm)such thatx∈S,x≠x if i≠i.For example, for S={1,2,3)and m=2: