# A.1 Discrete Mathematics

The mathematical concepts we build on include:

sets

A set has elements (members). We write $s\in S$ 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.

tuples

An $n$-tuple is an ordered grouping of $n$ elements, written $\left$. 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, $S^{n}$ is the set of $n$-tuples $\left$ where $x_{i}$ is a member of $S$. $S_{1}\times S_{2}\times\dots\times S_{n}$ is the set of $n$-tuples $\left$ where each $x_{i}$ is in $S_{i}$.

relations

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.

functions

A function, or mapping, $f$ from set $D$, the domain of $f$, into set $R$, the range of $f$, written $f:D\rightarrow R$, is a subset of $D\times R$ such that for every $d\in D$ there is a unique $r\in R$ such that $\left\in f$. We write $f(d)=r$ if $\left\in f$.

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.