A Mathematical Preliminaries and Notation

A.1 Discrete Mathematics

The mathematical concepts we build on include:


A set has elements (members). We write sS if s is an element of set S. The elements in a set define the set, so that two sets are equal if they have the same elements.


An n-tuple is an ordered grouping of n elements, written x1,,xn. A 2-tuple is a pair, and a 3-tuple is a triple. Two n-tuples are equal if they have the same members in the corresponding positions. If S is a set, Sn is the set of n-tuples x1,,xn where xi is a member of S. S1×S2××Sn is the set of n-tuples x1,,xn where each xi is in Si.


A relation is a set of n-tuples. The tuples in the relation are said to be true of the relation. An alternative definition is in terms of the relation’s characteristic function, a function on tuples that is true for a tuple when the tuple is in the relation and false when it is not.


A function, or mapping, f from set D, the domain of f, into set R, the range of f, written f:DR, is a subset of D×R such that for every dD there is a unique rR such that d,rf. We write f(d)=r if d,rf.

While these may seem like obscure definitions for common-sense concepts, you can now use the common-sense concepts comfortable in the knowledge that if you are unsure about something, you can check the definitions.