Relations and Functions — chapter notes

A relation $R$ from $A$ to $B$ is a subset of $A \times B$; a relation on $A$ is a subset of $A \times A$. We write $a\,R\,b$ for $(a, b) \in R$.

• Empty relation: no pairs ($R = \varnothing$).
• Universal relation: every pair ($R = A \times A$).
• Identity relation: $I_A = \{(a, a) : a \in A\}$.

If $n(A) = n$, then $A \times A$ has $n^2$ pairs and there are $2^{n^2}$ relations on $A$.

• Reflexive: $(a, a) \in R$ for every $a \in A$.
• Symmetric: $(a, b) \in R \Rightarrow (b, a) \in R$.
• Transitive: $(a, b) \in R$ and $(b, c) \in R \Rightarrow (a, c) \in R$.

The three properties are independent: any combination can occur. The empty relation on a non-empty set is symmetric and transitive (vacuously) but not reflexive. "Is perpendicular to" on lines is symmetric only; "divides" on $\mathbb{N}$ is reflexive and transitive but not symmetric.

To show a property fails, give one counterexample. To show it holds, argue with general elements.

A relation that is reflexive, symmetric and transitive is an equivalence relation. The equivalence class of $a$ is $[a] = \{x \in A : x\,R\,a\}$.

Facts: $a \in [a]$; $[a] = [b]$ if $a\,R\,b$; otherwise $[a] \cap [b] = \varnothing$. The classes form a partition of $A$: disjoint, non-empty, and covering $A$.

Shortcut: a relation of the form "$x$ and $y$ have the same value of some property" (same remainder, same digit sum, same room, same birth year) is always an equivalence relation, because equality is.

Example: on $\{1, \dots, 9\}$, "same remainder on division by $3$" has classes $\{1, 4, 7\}$, $\{2, 5, 8\}$, $\{3, 6, 9\}$.

To make a relation an equivalence relation with the fewest additions: add all $(a, a)$, the reverses, then whatever transitivity forces.

Model: on $\mathbb{Z}$, $a\,R\,b \iff 6 \mid (a + 5b)$.

1. Reflexive: $a + 5a = 6a$, divisible by $6$.
2. Symmetric: if $a + 5b = 6k$, then $b + 5a = 6(a + b) - (a + 5b) = 6(a + b - k)$.
3. Transitive: if $a + 5b = 6k$ and $b + 5c = 6m$, then $a + 5c = 6(k + m - b)$.

Write each condition as "$= 6 \times$ integer", rearrange, and finish each line with the conclusion ($a\,R\,a$, $b\,R\,a$, $a\,R\,c$). Use general letters, never only numbers.

A function $f : A \to B$ gives each $x \in A$ exactly one image $f(x) \in B$. Range $= \{f(x) : x \in A\} \subseteq B$.

• One-one (injective): $f(x_1) = f(x_2) \Rightarrow x_1 = x_2$ (no element of $B$ gets two arrows).
• Onto (surjective): for every $y \in B$ there is $x \in A$ with $f(x) = y$ (range $= B$).
• Bijective: one-one and onto.

Not one-one: give $x_1 \ne x_2$ with $f(x_1) = f(x_2)$. Not onto: give $y \in B$ with no pre-image. For real functions, the horizontal line test is a guide: a line meeting the graph twice means not one-one.

One-one: assume $f(x_1) = f(x_2)$ and simplify to $x_1 = x_2$ (for rational functions, cross-multiply).

Onto: take any $y$ in the codomain, solve $f(x) = y$, and check that $x$ is in the domain (real, not an excluded value, a natural number or integer where required).

The domain and codomain matter: $x^2$ is neither one-one nor onto on $\mathbb{R} \to \mathbb{R}$, onto for $\mathbb{R} \to [0, \infty)$, and bijective for $[0, \infty) \to [0, \infty)$. Linear $ax + b$ ($a \ne 0$) and $x^3$ are bijections of $\mathbb{R}$. On $\mathbb{N}$, $n + 1$ and $2n$ are one-one but not onto.

Example: $f(x) = \dfrac{x + 2}{x - 1}$ on $\mathbb{R} - \{1\} \to \mathbb{R} - \{1\}$ has pre-image $x = \dfrac{y + 2}{y - 1}$, so it is a bijection.

Let $n(A) = m$ and $n(B) = n$.

• All functions $A \to B$: $n^m$.
• One-one: $n(n - 1)(n - 2) \cdots (n - m + 1)$ if $m \le n$; none if $m > n$.
• Onto: none if $m < n$. To $2$ elements: $2^m - 2$. To $3$ elements: $3^m - 3 \cdot 2^m + 3$.
• Bijections $A \to A$ with $n(A) = n$: $n!$. Between finite sets of equal size, one-one $\iff$ onto.

Examples: $\{1, 2, 3\} \to \{a, b, c, d\}$: $64$ functions, $24$ one-one, $0$ onto. $\{1, 2, 3, 4\} \to \{a, b, c\}$: $81$ functions, $36$ onto.