Definition 5.1. An $n$-tuple $(a_1, a_2, \dots, a_n)$ is an ordered collection that has $a_1$ as its first element, $a_2$ as its second element, $\dots$, and $a_n$ as its $n$th element. An ordered pair is a 2-tuple.
Observe that since tuples are ordered, we have $(a_1, \dots, a_n) = (b_1, \dots, b_n)$ if and only if $a_i = b_i$ for $i = 1, \dots, n$.
As a side note, we claimed in the last class that everything in mathematics is just some kind of set, so how would we define tuples using sets? To keep things simple, we'll consider the definition of the pair first. We can define $(x,y)$ to be the set $\{\{x\}, \{x,y\}\}$. In this way, we can distinguish $x$ and $y$ and we have a way to determine the order in which they appear. This definition is due to Kuratowski in 1921. We can then generalize this definition for arity $n \gt 2$.
Definition 5.2. The cartesian product of two sets $A$ and $B$ is $$A \times B = \{(a,b) \mid a \in A, b \in B\}.$$
We can generalize this to products of $n$ sets.
Definition 5.3. The cartesian product of $n$ sets $A_1, A_2, \dots, A_n$, denoted $A_1 \times A_2 \times \cdots \times A_n$ is defined $$A_1 \times A_2 \times \cdots \times A_n = \{(a_1, a_2, \dots, a_n) \mid a_i \in A_i, i = 1, 2, \dots, n\}.$$
We now can use the Cartesian product to define relations.
Definition 5.4. A relation $R$ with domain $X$ and co-domain $Y$ is a subset of $X \times Y$.
We can see from the definition that a relation really is just a subset of the cartesian product of some sets. In other words, it's a set of tuples. This also resembles the set-theoretic definition of predicates and it's not entirely a coincidence that we think of $k$-ary predicates as relations.
A few properties of relations will appear throughout this course. These tend to relate to relations where the domain and range are the same.
Definition 5.5. A relation $R \subseteq A \times A$ is reflexive if $\forall a \in A, R(a,a)$. In contrast, we say that a relation is irreflexive if $\forall a \in A, \neg R(a,a)$.
The equality ($=$) and subset $\subseteq$ relations are reflexive. $<$ is irreflexive.
Definition 5.6. A relation $R \subseteq A \times A$ is symmetric if $\forall a, b \in A, R(a,b) \to R(b,a)$. A relation is asymmetric if $\forall a,b \in A, R(a,b) \to \neg R(b,a)$. Finally, a relation is antisymmetric if $\forall a,b \in A, R(a,b) \wedge R(b,a) \to a = b$.
Equality ($=$) is symmetric, strict subset ($\subset$) is asymmetric and $\subseteq$ is antisymmetric – but so is subset (vacuously)!
Definition 5.7. A relation $R \subseteq A \times A$ is transitive if $\forall a, b, c \in A, R(a,b) \wedge R(b,c) \to R(a,c)$.
Equality, subset and strict subset are all transitive, but containment ($\in$) certainly isn't! Still we could imagine wanting a transitive "is an element of" operation.
Definition 5.8. A reflexive, symmetric, transitive relation is called an equivalence relation. We've actually seen two of these in this course: equality ($=$) and bidirectional implication ($\Leftrightarrow$). We'll see more.
Definition 5.9. A relation $R \subseteq A \times B$ is total if $\forall a \in A, \exists b \in B, R(a,b)$. A relation $R$ is single-valued if $\forall a \in A, \forall b_1, b_2 \in B, R(a, b_1) \wedge R(a,b_2) \rightarrow b_1 = b_2$.
These properties lead us right to a definition for functions.
Definition 5.10. A function $f : A \to B$ is a total, single-valued relation with domain $A$ and co-domain $B$. The set $B$ is also called the range of $f$.
Again, based on the definition, a function is really just a relation that satisfy the properties we just defined, totality and single-valued-ness. And if we go further, a function is just a set, like everything else in mathematics. The restrictions on the domain and co-domain of the function tracks with our intuitive understanding of functions that we may have learned earlier. For instance, totality guarantees that a function gives us something for every value we throw at it, while single-valuedness guarantees that our function will only give us one possible output for every input that we give it.
We also have different kinds of functions that are important and worth distinguishing.
Definition 5.11. A function $f:A \to B$ is injective (also called one-to-one, though this can be ambiguous) if $$\forall x, y \in A, f(x) = f(y) \rightarrow x = y.$$
Example 5.12. The successor function $f:\mathbb N \to \mathbb N$ defined by $f(x) = x+1$ is one-to-one. On the other hand, the function $g:\mathbb N \to \mathbb N$ defined by $g(x) = \left\lfloor \frac x 2 \right\rfloor$ is not injective, since for any even natural number $m$, we have $g(m) = g(m+1)$ but $m \neq m+1$.
Definition 5.13. The image of a function $f : A \to B$ is the set $\operatorname{im} f = \{f(x) \mid x \in A\}$.
Clearly, $\operatorname{im} f \subseteq \operatorname{rng} f$. However, it is not always the case that $\operatorname{im} f = \operatorname{rng} f$. If it is, we get another special kind of function.
Definition 5.14. A function $f:A \to B$ is surjective (or onto) if $\forall y \in B, \exists x \in A, f(x) = y$.
Example 5.15. The function $f:\mathbb N \to \mathbb N$ defined by $f(x) = x^2$ is not surjective (for instance, there is no natural number $n$ such that $n^2 = 2$). On the other hand, the function $g(x) = \left\lfloor \frac x 2 \right\rfloor$ from the above example is surjective.
Definition 5.16. A function $f:A \to B$ is a bijection (or one-to-one correspondence) if $f$ is one-to-one and onto.
A correspondence between two sets $A$ and $B$ uniquely pairs each element of $A$ with an element in $B$. It's easy to see, then, that we can form a bijection between any two sets of finite size. For instance, given the sets $\{71,42,0,100\}$ and ${B, E, R, T}$, we can form the bijection f = {(71,B),(42,E),(0,R),(100,T)} (or any of several other bijections). This gives us a way of saying that two infinite sets have the same cardinality: They have the same cardinality if there is a bijection between them! For instance: $$|\mathbb{N}| = |\{x \in \mathbb{N}| \exists y \in \mathbb{N}, x = 2y \}|$$
We see that the even numbers are the same size as the natural numbers, despite being a subset of them! It turns out that the integers $\mathbb{Z}$ and even rational numbers $\mathbb{Q}$ are the same size, which we call $\aleph_0$. $|\mathbb{R}|$, however, is larger.
Definition 5.17.It should be clear from the above that bijections are bidirectional, in the sense that for any bijection $f$ from $A$ to $B$ we can construct another bijection $f^{-1} = \{(b,a) | (a,b) \in f\}$ from $B$ to $A$. We call this function the inverse and it has the property that $\forall x \in A, f^{-1}(f(x)) = x$ and $\forall y \in B, f(f^{-1}(y)) = y$. We may note that $(f^{-1})^{-1} = f$.
Note that a function must be a bijection in order to have an inverse. If a function $f \subseteq A \times B$ is not injective, then there are distinct $x_1$ and $x_2$ such that $f(x_1) = f(x_2)$. The relation produced by flipping this function would therefore not be single-valued. Similarly, if $f$ is not surjective, the inverse relation wouldn't be total. Either way, we wouldn't get a function. (There are notions of "left-inverses" for injective functions and "right-inverses" for surjective ones, but they don't particularly concern us.)
Definition 5.18.If you have functions $f:A \to B$ and $g: B \to C$, then composition of the two functions, written $g \circ f$ is $\{(a,c) | (a,b) \in f \wedge (b,c) \in g\}$.
Using this notation, we may restate the property of inverses as $f^{-1} \circ f = I_A$ and $f \circ f^{-1} = I_B$, where $I_A$ and $I_B$ are the identity functions on $A$ and $B$.