- 2 - Mathematical Preliminaries
- 2.1 - Sets, Relations, and Functions
- 2.1.1 - Sets stuff. Notations, and operations.
- 2.1.2 - Set of natural numbers - N
- 2.1.3 -
**n-place relation**when each element of the sets is related by producing a tuple - 2.1.5 -
**binary relation**- R - produces tuple of two which belongs to R. - 2.1.6 - triple relation
- 2.1.7 - domain the first element of tuple, range is the second (for any second/first respectively)
- 2.1.8 -
**partial function**, when tuples with t1, 2 belong to R, and t1 = t2.**total function**when domain of R is S (ffunc from S to T) - 2.1.9 - partial function is
on s iff s in in domain. the notation with up arrow is used to say that f is undefined. down arrow = defined.*defined* - 2.1.10 - some predicate is preserved when it holds after the relation.

- 2.2 - ordered sets
- 2.2.1 - binary relation is
**reflexive**if R related every element to itself.**symmetric**if sRt => tRs.**transitive**if (sRt / tRu) => sRu.**antisymmetric**: sRt / tRs => s = t - reflexive + transitive =
**preorder**. preorder with antisymmetry = partial order. total order if wither off the two elements are guaranteed to be ordered. - 2.2.3 j is
**join**(lub) iff s <= j, t <= j and for any k in S, s <= k, t <= k we have j <= k.**meet**(glb): m <= s, m <= t. for any n in S, n <= s and n <= t. n <= m - reflexive, transitive, symmetric relation on S –
**equivalence**on S - 2.2.5 reflexive
**closure**, transitive closure. - EX 2.2.6 …
- EX 2.2.7 …
- EX 2.2.8 …
- 2.2.9 we have preorder <= on S
**decreasing chain**in <= is s1, s2, s3… of S : each member of seq is lt its pred (chains can be finite and infinite) - 2.2.10 set with preorder <=. <= is
**well founded**if it contains not infinite decreasing chains. nats are well founded. integers are not. “well founded set”

- 2.2.1 - binary relation is
- 2.3 - Sequences
- 2.3.1 - comma is more like a consbut overloaded for append when used with another seq on lhs.

- 2.4 - Induction: pretty common
- 2.4.1 principle of
**ordinary induction**on natural numbers. P is a pred on nats. If P(0) and for all i, P(i) => P(i + 1), then P(n) holds for all n. - 2.4.2 principle of
**complete induction**on natural numbers. if for each nat n, given P(i) forall i < n, we can show P(n). then P(n) holds for all n.

- 2.4.3
**lexicographical order**on pairs off natural numbers (m, n) <= (m’, n’) iff m < m’ or else m = m’ / n <= n’ - 2.4.4 Principle of
**lexicographic induction**. P is predicate on pairs of natural numbers. If rach pair (m, n) of natural numbers, given P(m’, n’) for all (m’, n’) < (m, n) we can show P(m, n), then P(m, n) holds for all (m, n).

- 2.4.1 principle of
- 2.5 Background reading:
*Winskel*,*David and Priestley*,*Halmos*.

- 2.1 - Sets, Relations, and Functions

see: *Adequacy*