1 Relations
Relations, naturally, describe relationships between objects in sets.
The Cartesian product of \(A\) and \(B\), denoted \(A \times B\), is the set of all possible ordered pairs \((a,b)\) such that \(a \in A\) and \(b \in B\).
A relation from \(A\) to \(B\), generally denoted by \(R\), is a subset of \(A\times B\), that is a sub-collection of ordered pairs \((a,b)\) satisfying some specified property. We often use the notation \[ aRb\equiv (a,b) \in R. \] If \(B = A\) we typically speak of a relation on \(A\). The most important types of relations are:
- [[]];
- [[]]; and
- [mappings].
1.0.1 Equivalence Relations
Equivalence relations define the most general concept of equivalence between sets.
An equivalence relation on \(A\) is a relation \(R\) on \(A\) that satisfies for all \(a,b,c\in A\): 1. \(aRa\) for all \(a \in A\) 2. \(aRb\iff b R a\); and 3. \(a R c\) whenever \(aRb\) and \(bRc\) for some \(b\).
The equivalence class of an element \(a\) is \(\{ b \in A:aRb \}\). Note that equivalence classes are by definition disjoint and therefore partition \(A\).
1.0.2 Orderings
Orderings introduce the intuitive idea of order to sets through binary relations.
A partial ordering on a nonempty set \(A\) is a relation \(R\) on \(A\) satisfying the following properties: 1. \(aRb\) and \(bRc \implies aRc\); 2. \(a R b\) and \(b R a \implies a=b\); and 3. \(aRa\) for all \(a\).
A partial ordering becomes a linear (total) ordering if it also satisfies \[ a,b \in A\implies aRb~~~\text{or}~~~bRa. \]
Note that \(\mathbb{R}\) is linearly ordered by its usual ordering. Taking this example as a model, we shall usually denote partial orderings by \(\leq\) and we write \(x<y\) to mean that \(x \leq y\) but \(x \neq y\). We observe that a partial ordering on \(A\) naturally induces a partial ordering on every nonempty subset of \(A\).
Two partially ordered sets \(A\) and \(B\) are said to be order isomorphic if there is a bijection \(f:A \to B\) such that \[ a_{1}\leq a_{2} \iff f(a_{1})\leq f(a_{2}). \]
If \(A\) is partially ordered by \(\leq\), a maximal (respectively minimal) element of \(A\) is an element \(a \in A\) such that the only \(b \in A\) satisfying \(a \leq b\) (respectively \(b \leq a\)) is \(a\) itself. Maximal and minimal elements may or may not exist, and they need not be unique unless the ordering is linear.
If \(B \subset A\), an upper (respectively lower) bound for \(B\) is an element \(a \in A\) such that \(b \leq a\) (respectively \(a \leq b\)) for all \(b \in B\). An upper bound for \(B\) need not be an element of \(B\) and unless \(B\) is linearly ordered a maximal element of \(B\) need not be an upper bound for \(B\). If \(A\) is linearly ordered by \(\leq\) and every nonempty subset of \(A\) has a (necessarily unqiue) minimal element, \(A\) is said to be well ordered by \(\leq\). Here \(\leq\) is called a well ordering on \(A\).
Every partially ordered set has a maximal linearly ordered subset.
In more detail, this means that if \(A\) is partially ordered by \(\leq\), there is a set \(B \subset A\) that is linearly ordered by \(\leq\), such that no subset of \(A\) that properly includes \(B\) is linearly ordered by \(\leq\). Another version of this principle is Zorn’s Lemma.
Every nonempty set \(A\) can be well ordered.
Proof:
If \(\{ X_{\alpha} \}_{\alpha \in A}\) is a nonempty collection of nonempty sets, then \(\prod_{\alpha \in A}{X_{\alpha}}\) is non-empty.
Proof:
1.0.3 Mappings
A mapping \(f:X \to Y\) is a relation \(R\) from \(X\) to \(Y\) with the property that for every \(x \in X\) there is a unique \(y \in Y\) such that \(xRy\), in which case we write \(y = f(x)\). Mappings are sometimes called maps or functions however we typically reserve the latter for the case when \(Y=\mathbb{C}\) or some subset thereof.
If \(f:X \to Y\) and \(g:Y \to Z\) are mappings, we define their composition by \[ g\circ f:X \to Z\quad\text{i.e.}\quad g\circ f(x)=g(f(x)). \] If \(D \subset X\) and \(E \subset Y\), we define the image of \(D\) and the inverse image of \(E\) under the mapping \(f:X \to Y\) by \[ \begin{align} f(D) & =\{ f(x):x \in D \}, \\ f^{-1}(D) & =\{ x:f(x) \in E \}. \end{align} \] ## Injective and Surjective Mappings