Surjections as Sets

So far, we have developed mathematics in the following manner: propositional logic, then predicate logic, then a sufficiently naïve set theory.

When discussing relations, we leaned more on logic than sets. It turns out that there are ways to discuss relations more directly in terms of sets than in terms of raw logic. This motivates us to study functions, likewise, in terms of sets rather than in terms of raw logic, wherever possible.

Firstly, let’s talk about the image of a relation.

Definition 1. Let $K, L$ be sets and $R \subseteq K \times L$ a relation. The domain of $R$ , denoted $\mathrm D_R$ , is the set

$\mathrm D_R := \{x \in K : (x, y) \in R\} \subseteq K.$

For any $M \subseteq K$ , define the image of $M$ under $R$ by

$R(M) := \{y \in L : (\exists x \in M: (x,y) \in R)\}.$

In particular, the range of $R$ is $R(\mathrm D_R)$ . Finally, for any $N \subseteq L$ , the pre-image of $N$ under $R$ is defined to be $R^{-1}(N)$ .

Using these broad definitions, we obtain the main definitions for the sets associated to a function.

Theorem 1. Let $f : K \to L$ be a function. Then the domain of $f$ is $\mathrm D_f = K$ , the range of $f$ is $f(K)$ , and the pre-image of $N \subseteq L$ under $f$ is $f^{-1}(N)$ . Finally, it is clear that $f^{-1}(L) = K$ .

In particular, we can characterise surjections using this notation.

Corollary 1. Let $f : K \to L$ be a function. Then $f$ is surjective if and only if $f(K) = L$ .

Proof. By definition, $f(K)\subseteq L$ unconditionally. Thus, we can relax the right-hand side to $L \subseteq f(K)$ . Notice that both sides of the biconditional are equivalent to the quantified proposition

$\forall y \in L \quad \exists x \in K:\quad y=f(x).$

This implies that every injection is bijective to some set.

Corollary 2. Let $f : K \to L$ be an injection. Then the function $\tilde f : K \to f(K)$ defined by $\tilde f(x) = f(x)$ is bijective. To abbreviate, we write $\tilde f = f$ and say that $f : K \to f(K)$ is bijective.