Relations #
A relation can be defined as a subset of a cross product:
\[R(x, y) \subseteq X \times Y\]The relation is a set of ordered pairs. If \(a R b = R(a, b)\) , then \((a, b) \in R\) .
A binary homogenous relation is a relation where all the elements are from the same set, i.e. \(xRy\) where \(R \subseteq A \times A\) .
A binary relation \(R\) on a set \(A\) is reflexive iff \(aRa\) for all \(a \in A\) . Conversely, a binary relation is irreflexive iff \(\forall x \in A. \lnot(x R x)\) . A function is irreflexive iff its complement is reflexive. Note that a relation can still be reflexive even if objects are unequal and related.
A binary relation \(R\) on a set \(A\) is symmetric iff \(\forall x, y \in A. xRy \leftrightarrow yRx\) . If a relation’s adjacency matrix is equal to its transpose, then the relation is symmetric. A binary relation \(R\) on a set \(A\) is asymmetric iff \(\forall x, y \in A. xRy \rightarrow \lnot(yRx)\) . If a relation’s adjacency matrix is not equal to its transpose, then the relation is asymmetric. A binary relation \(R\) on a set \(A\) is antisymmetric iff \(\forall x, y \in A. (xRy \land yRx) \rightarrow (x = y)\) . Essentially, if an antisymmetric relation gives the same answer both ways, then the arguments must be equal.
A binary relation \(R\) is transitive iff \(\forall x, y, z \in A. (xRy \land yRz) \rightarrow xRz\) .
A binary relation \(R\) on a set \(A\) is an equivalence relation iff it is reflexive, symmetric, and transitive. The equals sign is an example of an equivalence relation.
A binary relation \(R\) on a set \(A\) is a partial order iff it is antisymmetric and transitive. The less than sign is an example of a partial order.
Functions #
A function assigns an element of one set to another set. The notation \(f: A \rightarrow B\) indicates that \(f\) is a function with domain \(A\) and codomain \(B\) . The notation \(f(a) = b\) indicates that \(f\) assigns the element \(b \in B\) to a specific argument \(a \in A\) . \(b\) is the value of \(f\) at argument \(a\) .
A function does not have to be defined for every element in its domain. Such functions are called partial functions. A total function is defined for every element in its domain. (Note that a total function is also partial – partial is more of a catch-all.) A function also does not need to return every element in its codomain. The range of the function is the set of all values that the function returns.
A surjective function is a function that returns every element in its codomain. A injective function is a function that returns a unique value for every argument. A bijective function is a function that is both surjective and injective.