## 16.1 Discrete Mathematics

The mathematical concepts we build on include:

- sets
- A
**set**has elements (members). We write*s ∈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*⟨x*. A 2-tuple is a_{1},...,x_{n}⟩**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*is the set of^{n}*n*-tuples*⟨x*where_{1},...,x_{n}⟩*x*is a member of_{i}*S*.*S*is the set of_{1}×S_{2}×...×S_{n}*n*-tuples*⟨x*where each_{1},...,x_{n}⟩*x*is in_{i}*S*._{i} - relations
- A
**relation**is a set of n-tuples. The tuples in the relation are said to be*true*of the relation. - functions
- A
**function**, or**mapping**,*f*from set*D*, the**domain**of*f*, into set*R*, the**range**of*f*, written*f:D →R*, is a subset of*D×R*such that for every*d∈D*there is a unique*r∈R*such that*⟨d,r⟩ ∈f*. We write*f(d)=r*if*⟨d,r⟩∈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.