Sets on their own just sit there. Functions are how sets talk to each other: they carry elements of one set over to another. Every big idea later in this course (homomorphisms, isomorphisms, group actions) is a function with some extra good behavior, so it pays to get very precise about what a function is, and about the three properties we'll be checking over and over: injective, surjective, and bijective.
Suppose $A$ and $B$ are sets.
A function $f$ from $A$ to $B$ is a rule that assigns to every element $a \in A$ an element $f(a) \in B$.
Notation: $f\colon A \to B$
Two words in there matter more than they look. Every element of $A$ gets an output, with no exceptions. And it gets an element, meaning exactly one: a function never sends one input to two different places. Test both words on a few candidates.
A broken candidate is usually only a couple of arrows away from being a function.
Now the two sets in $f\colon A \to B$ get names of their own.
On the Logic & Equivalence page we'll meet relations, which are just subsets of $A \times B$. A function is a very well-behaved relation: every $a \in A$ shows up in exactly one pair $(a, f(a))$.
The set $A$ that $f$ takes its inputs from is the domain of $f$.
The set on the other side of the arrow is where the outputs are allowed to land.
The set $B$ that $f$ sends its outputs into is the codomain of $f$.
The codomain is where outputs are allowed to land. It doesn't promise that every element of $B$ actually gets hit. The outputs that really do show up get their own name.
The range of $f$ is the set $f(A) = \{f(a) : a \in A\}$, a subset of $B$ (the image of $A$ under $f$).
So the range is always a subset of the codomain, but the two don't have to be equal. Here's a picture of a function where they are equal, and where you can see every arrow at once.
Let $A$ be the set of the six triangles below, and let $B = \{\text{green}, \text{red}, \text{blue}\}$. Each triangle has one vertex of each color, and all six are different (there are exactly $3! = 6$ ways to color the three vertices). Define $f\colon A \to B$ by
Every triangle gets exactly one output (it has one top vertex), so $f$ really is a function. The range is $f(A) = \{\text{green}, \text{red}, \text{blue}\} = B$: each color is on top of two triangles. Hang on to that "two triangles per color" observation. It's about to matter.
Finding a range is a prediction you can check. Guess which outputs get hit, then let the arrows fly.
Two questions come up about every function we'll ever meet. First: can two different inputs collide on the same output?
"One-to-one" sounds like it should mean a perfect matching, one $A$ for each $B$ and nobody left out. It doesn't. That's "one-to-one correspondence," which is a different word for a different thing. Thanks, mathematics.
$f$ is called injective (one-to-one) if every element in its range is the image of exactly one point in its domain.
Equivalently: $f$ is injective if, whenever $f(a) = f(a')$, we have $a = a'$.
Second: does every element of the codomain get hit?
$f$ is called surjective (onto) if $f(A) = B$.
Equivalently: $f$ is surjective if $\forall b \in B$, $\exists a \in A$ such that $f(a) = b$.
And when both answers are the good ones, the function is a perfect matching between $A$ and $B$.
$f$ is called bijective if it is both injective and surjective.
The triangle function above is surjective (every color is on top of some triangle) but not injective (two different triangles share each top color). In an arrow picture, injective means no dot in $B$ gets two arrows, and surjective means no dot in $B$ gets zero. Wire up some functions yourself.
A bijection that also respects a group's operation is called an isomorphism. Two groups with an isomorphism between them are really the same group with the elements renamed.
Every function lands in exactly one of four boxes: injective or not, surjective or not. Sort a few.
When it's time to write proofs, the two "Equivalently" versions are the ones you'll actually use.
To prove $f$ is not injective, one counterexample is enough: two different inputs with the same output. To prove $f$ is injective, start with "Suppose $f(a) = f(a')$" and work until you reach "$a = a'$." Checking a few examples proves nothing. For surjective, start with "Let $b \in B$" and then find an $a$ that works.
Here's the most important lesson in this section: whether a function is injective or surjective depends on the domain and codomain, not just on the formula. Watch the same formula, $x^2$, change its answers.
$f\colon \mathbb{R} \to \mathbb{R}$, $f(x) = x^2$
Both failures came with a single counterexample. Compare that with a function that passes both tests, where we need a general argument for each.
$f\colon \mathbb{R} \to \mathbb{R}$, $f(x) = x^3$
Now back to $x^2$. Throw away the negative numbers on both sides, and both problems go away.
$f\colon [0, \infty) \to [0, \infty)$, $f(x) = x^2$
Same formula as Example 2, opposite answers. Shrinking the domain fixed injectivity (no more $-1$ to collide with $1$), and shrinking the codomain fixed surjectivity (no more $-1$ to miss).
That's worth putting in a box of its own.
The domain and codomain are part of the function. "Is $x^2$ surjective?" isn't a question you can answer: $x^2$ from $\mathbb{R}$ to $\mathbb{R}$ and $x^2$ from $[0, \infty)$ to $[0, \infty)$ are different functions. Always check what's on both sides of the arrow before you answer.
So shrink the sets yourself. Drag the ends of the domain and the codomain until $x^2$ becomes a bijection.
The same thing happens with sets of integers.
$f\colon \mathbb{N} \to \mathbb{Z}$, $f(n) = n - 1$
Notice that the surjectivity argument computed the whole range and compared it to the codomain. That's often the cleanest way. (And remember, in this course $\mathbb{N}$ starts at $1$, which is why the range starts at $0$.)
$f\colon \mathbb{Z} \to \mathbb{Z}_{\ge 0}$, $f(n) = |n|$
Every one of these examples is a graph you could draw. A horizontal line $y = c$ (with $c$ in the codomain) asks "how many inputs land on $c$?" Two or more breaks injectivity, and zero breaks surjectivity. Slide the line around.
Back on the Domain and Range page, the range was "every output the function can produce." Same idea here. What's new is that we also name the set the outputs are allowed to land in: the codomain.
Try one on your own before moving on.
Let $f\colon \mathbb{Z} \to \mathbb{Z}$, $f(n) = 2n$. Is $f$ injective? Is $f$ surjective? Prove your answers.
Injective. Suppose $f(n) = f(m)$ for $n, m \in \mathbb{Z}$. Then $2n = 2m \implies n = m$.
Not surjective. $1 \in \mathbb{Z}$, but there is no $n \in \mathbb{Z}$ with $2n = 1$ (that would need $n = \frac{1}{2}$). In fact, $f(\mathbb{Z})$ is the set of even integers, which is not all of $\mathbb{Z}$.
And one that asks you to choose the sets yourself.
Example 4 made $x^2$ a bijection by using the domain $[0, \infty)$. Find a different domain $D \subseteq \mathbb{R}$ so that $f\colon D \to [0, \infty)$, $f(x) = x^2$ is a bijection.
$D = (-\infty, 0]$ works. If $x, x' \le 0$ and $x^2 = (x')^2$, then $x = \pm x'$, and since both are $\le 0$, $x = x'$. And for every $y \ge 0$, $x = -\sqrt{y} \in D$ has $x^2 = y$.
(There are many other answers. You need exactly one of $\sqrt{y}$ and $-\sqrt{y}$ in $D$ for each $y \ge 0$. For example, $D = [0, 1) \cup (-\infty, -1]$ also works.)
Functions don't have to eat numbers. Here's one whose inputs and outputs are both sets, and it's a great workout for everything from the Sets page.
Let $X$ be a set and, $\forall A \subseteq X$, define $f_A\colon \mathcal{P}(X) \to \mathcal{P}(X)$ by $f_A(B) = A \setminus B$, $\forall B \in \mathcal{P}(X)$.
For what choices of $A$ will $f_A$ be injective? Surjective?
Injective? (note: $f_A(B) = f_A(C) \iff A \setminus B = A \setminus C$)
Conclusion: $f_A$ will be injective if and only if $A = X$.
Surjective? (note: $\forall B \in \mathcal{P}(X), f_A(B) \subseteq A$)
Conclusion: $f_A$ will be surjective if and only if $A = X$.
Look at the trick in the "not injective" half: the element $x$ that $A$ is missing gets thrown away by $f_A$ no matter what, so adding it to $B$ changes nothing. In the "not surjective" half, that same missing $x$ can never show up in an output. One missing element breaks both properties. Here's the whole function with $X = \{1, 2, 3\}$.
On the Sets page, the Power Set Switchboard collected all $2^3 = 8$ subsets of a three-element set. Those same $8$ subsets are the domain and the codomain below.
When the sets are finite, you can count functions the same way you'd count outfits: every input picks its output, one at a time.
Let $A = \{1, 2\}$ and $B = \{a, b, c\}$. How many functions $f\colon A \to B$ are there? How many are injective? How many are surjective?
The input $1$ has $3$ choices of output, and so does $2$, so there are $3 \cdot 3 = 9$ functions.
For an injective function, $2$ can't reuse the output of $1$, so it has only $2$ choices left: $3 \cdot 2 = 6$ injective functions. Here are all six.
None of the $9$ are surjective: two inputs can hit at most two of the three outputs.
If you played with the arrow-drawing widget, you may have noticed two more patterns. A bijection only ever showed up when $A$ and $B$ had the same number of dots. And when they did have the same number of dots, injective and surjective seemed to come as a package deal.
Proof. We use one observation twice. If $A = \{a_1, \dots, a_n\}$ has $n$ elements, then $f(A) = \{f(a_1), \dots, f(a_n)\}$, and this set has exactly $n$ elements if and only if the $f(a_i)$ are all different, that is, if and only if $f$ is injective.
First bullet. Suppose $f$ is a bijection. If $A$ is finite with $n$ elements, then $|f(A)| = n$ because $f$ is injective, and $f(A) = B$ because $f$ is surjective, so $|B| = n = |A|$. If $A$ is infinite, then $f(A)$ is infinite too (an injective $f$ never merges two inputs, so the infinitely many inputs give infinitely many outputs), and $f(A) = B$, so $|B| = \infty = |A|$.
Second bullet. Suppose $|A| = |B| = n < \infty$. Since $f(A) \subseteq B$ and $B$ has $n$ elements, $f(A) = B$ if and only if $f(A)$ has $n$ elements (a subset of a finite set with as many elements as the whole set is the whole set). Combining this with the observation:
The second fact is a pigeonhole argument. If $n$ inputs land on $n$ outputs with no collisions, they fill all $n$ slots. If they fill all $n$ slots, there's no room left over for a collision. The triangle function is a good contrast: six inputs, three outputs, so it can be surjective but never injective. Watch the pigeons find that out the hard way.
The Fact needs both of its conditions, and it's worth seeing each one break.
If $|A| \neq |B|$, the second fact fails: the function $\{1\} \to \{1, 2\}$ sending $1 \mapsto 1$ is injective but not surjective. And for infinite sets it fails too: Example 5 is injective but not surjective, and $|\mathbb{N}| = |\mathbb{Z}| = \infty$. Infinite sets have room to spare.
Back to counting. Every function is a path of choices, one input at a time, so all of them fit on one tree. Grow it, and prune the branches that reuse an output.
The tree turns into two formulas. With $|A| = m$ and $|B| = n$, there are $n^m$ functions ($n$ choices, $m$ times) and $n(n - 1)\cdots(n - m + 1)$ injective ones (one fewer choice each time). Slide $m$ and $n$ and watch the two counts race.
Put the counting to work.
Let $A = \{1, 2, 3\}$ and $B = \{a, b, c\}$. How many functions $f\colon A \to B$ are there? How many are injective? How many are surjective?
Each of the $3$ inputs has $3$ choices of output, so there are $3 \cdot 3 \cdot 3 = 27$ functions.
For an injective function, $1$ has $3$ choices, $2$ has the $2$ remaining choices, and $3$ gets the last one: $3 \cdot 2 \cdot 1 = 6$ injective functions. Since $|A| = |B| < \infty$, the Fact says the surjective functions are exactly the injective ones, so there are also $6$ surjective functions (and all $6$ are bijections).
Two definitions you've seen before in precalculus, now stated carefully. First, running a function backwards.
$f^{-1}$ means "undo $f$." $x^{-1}$ means $\frac{1}{x}$. Same little $-1$, totally different jobs. Whoever decided that owes every precalculus student an apology.
If $f\colon A \to B$ is a bijection then the inverse function $f^{-1}\colon B \to A$ is defined by the rule that, $\forall y \in B$, $f^{-1}(y) = x \iff f(x) = y$.
The inverse only exists for bijections, and both halves of "bijection" are doing a job.
$f$ being a bijection guarantees that $f^{-1}$ is well-defined and $f^{-1}$ is a bijection.
If $f$ isn't surjective, some $y$ has no $x$ with $f(x) = y$, so $f^{-1}(y)$ has no answer. If $f$ isn't injective, some $y$ has two such $x$'s, so $f^{-1}(y)$ has two answers. Either way, $f^{-1}$ isn't a function. (Try the ⇄ Flip button in the arrow-drawing widget on a non-bijection to watch this happen. Proving the Note is the Spicy Bonus at the end of the page.) When $f$ is a bijection, finding $f^{-1}$ means solving $f(x) = y$ for $x$.
Let $f\colon \mathbb{R} \to \mathbb{R}$, $f(x) = 2x + 1$. Find $f^{-1}$.
$f$ is a bijection: if $2x + 1 = 2x' + 1$ then $x = x'$, and every $y \in \mathbb{R}$ is $f\left(\frac{y - 1}{2}\right)$. Solving $y = 2x + 1$ for $x$ gives
Check both directions: $f^{-1}(f(x)) = \frac{(2x + 1) - 1}{2} = x$, and $f\left(f^{-1}(y)\right) = 2 \cdot \frac{y - 1}{2} + 1 = y$.
On a graph, solving for $x$ is the same as reflecting across the line $y = x$: every point $(x, y)$ becomes $(y, x)$. Flip a few graphs and see which ones come out as functions.
Next, chaining two functions together.
If $f\colon A \to B$ and $g\colon B \to C$ then the composite function $g \circ f\colon A \to C$ is defined by $(g \circ f)(x) = g(f(x))$, $\forall x \in A$.
Read $g \circ f$ from right to left: $f$ happens first, then $g$. The codomain of $f$ has to match the domain of $g$, or the chain breaks. Feed the chain a few numbers and try to break it.
The order of the two machines matters, too.
Let $f, g\colon \mathbb{R} \to \mathbb{R}$, $f(x) = x + 1$ and $g(x) = x^2$. Find $g \circ f$ and $f \circ g$.
$(g \circ f)(x) = g(f(x))$ $= g(x + 1) = (x + 1)^2$, and $(f \circ g)(x) = f(g(x))$ $= f(x^2) = x^2 + 1$.
These are different functions: at $x = 1$, $(g \circ f)(1) = 4$ but $(f \circ g)(1) = 2$. So $g \circ f \neq f \circ g$ in general.
Run both orders side by side on any input you like.
There's one subtle point about ranges.
$(g \circ f)(A) = g(f(A))$, but $g(f(A)) \neq g(B)$, in general.
Proof. By definition, $(g \circ f)(A) = \{g(f(a)) : a \in A\}$. The elements $f(a)$ with $a \in A$ are exactly the elements of $f(A)$, so this set is $\{g(b) : b \in f(A)\} = g(f(A))$. For the second half, one counterexample is enough, and the first Exercise below asks you for one. $\blacksquare$
The reason: $g$ only ever gets fed the outputs of $f$, which is $f(A)$, and that can be much smaller than $B$. Rewire the chain below and see for yourself.
That gap between $g(f(A))$ and $g(B)$ is where proofs go wrong.
A common slip in proofs: writing "$g \circ f$ is surjective, so $g(B) = C$, so ..." or computing the range of $g \circ f$ as $g(B)$. The range of $g \circ f$ is $g(f(A))$. You only get to use all of $B$ if $f$ is surjective.
Two exercises on composites.
Find specific finite sets $A$, $B$, $C$ and functions $f\colon A \to B$, $g\colon B \to C$ with $g(f(A)) \neq g(B)$.
One example: $A = \{1\}$, $B = \{a, b\}$, $C = \{x, y\}$, with $f(1) = a$, $g(a) = x$, $g(b) = y$. Then $f(A) = \{a\}$, so $g(f(A)) = \{x\}$, but $g(B) = \{x, y\}$.
The key is that $f$ is not surjective, and $g$ sends the element $f$ misses somewhere new.
The second one is a proof.
Prove that if $f\colon A \to B$ and $g\colon B \to C$ are both injective, then $g \circ f$ is injective.
Proof. Suppose $a, a' \in A$ and $(g \circ f)(a) = (g \circ f)(a')$. Then $g(f(a)) = g(f(a'))$. Since $g$ is injective, $f(a) = f(a')$. Since $f$ is injective, $a = a'$. Therefore $g \circ f$ is injective. $\blacksquare$
Now for a surprise: functions give us a way to define Cartesian products of any number of sets, even infinitely many. The idea is that an ordered pair $(a, b)$ is really a recipe: "slot $1$ gets $a$, slot $2$ gets $b$." That recipe is a function on the set of slots $\{1, 2\}$.
The Sets page defined $A_1 \times \dots \times A_n$ as ordered $n$-tuples and indexed collections $\{A_i\}_{i \in I}$ for big unions. Here the two ideas finally meet.
The generalized Cartesian product of a collection of sets $\{A_i\}_{i \in I}$ is defined by:
Each element of the product is a function that picks one element out of each $A_i$. Let's check that this really matches what we already know.
$I = \{1, 2\}$, $A_1 = A$, $A_2 = B$.
Compare: $A \times B = \{(a, b) : a \in A, b \in B\}$. The function $f$ plays the role of the pair $(f(1), f(2))$.
Every cell of the grid $A_1 \times A_2$ is one of these functions in disguise. Point at a cell to see its arrows.
With an infinite index set, we get infinite sequences.
$I = \mathbb{N}$
Compare: $\{(a_1, a_2, \dots) : \forall n \in \mathbb{N}, a_n \in A_n\}$.
And the index set doesn't even have to be countable. This one is wild.
A more complicated example: $I = \mathcal{P}(\mathbb{R}) \setminus \{\emptyset\}$ (the set of all non-empty subsets of $\mathbb{R}$).
$\forall S \in I$, define $A_S = S$. Then
An element of this product is a function that picks a point out of every non-empty subset of $\mathbb{R}$ at once.
Build some elements of a small product, then try to build one where it isn't so easy.
Question: How do you even know that there is a function like the one in Example 13? For $\mathbb{R}$ itself you could pick $0$, and for $[1, 2]$ you could pick the smallest element, $1$. But $(0, 1)$ has no smallest element, and you'd need a single rule that works for every non-empty subset simultaneously. Nobody has ever written one down, and it has been proved that the other standard axioms of set theory can't produce one.
The Axiom of Choice also lets you cut a solid ball into finitely many pieces and reassemble them, with no stretching, into two balls the same size as the original. (The Banach–Tarski paradox. It's a real theorem.) Free ball!
The non-emptiness of the Cartesian product, for arbitrary collections $\{A_i\}_{i \in I}$ of non-empty sets, is equivalent to the Axiom of Choice.
In other words, no amount of cleverness proves that the product in Example 13 has an element. It's something we assume. Almost all of mathematics assumes it, and you'll be using it quietly from here on.
Let $I = \{1, 2\}$, $A_1 = \{0, 1\}$, and $A_2 = \{a, b, c\}$. List every element of $\prod_{i \in I} A_i$ as a function, and match each one to an ordered pair in $A_1 \times A_2$.
Each function is determined by $f(1) \in \{0, 1\}$ and $f(2) \in \{a, b, c\}$, so there are $2 \cdot 3 = 6$ of them:
That matching, $f \mapsto (f(1), f(2))$, is itself a bijection from $\prod_{i \in I} A_i$ to $A_1 \times A_2$.
Every question below makes a new version each time you press the button, in the same order as the lesson. Every wrong choice is a real mistake, and choosing one tells you which.
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Time to back up the Note about inverses. You'll need both halves of "bijective," and each half does a different job.
Let $f\colon A \to B$ be a bijection. Prove that $f^{-1}\colon B \to A$ is well-defined (each $y \in B$ gets exactly one output) and that $f^{-1}$ is a bijection.
Proof. Well-defined. Let $y \in B$. Since $f$ is surjective, there is some $x \in A$ with $f(x) = y$, so $f^{-1}(y)$ has at least one candidate. If $x'$ also has $f(x') = y$, then $f(x) = f(x')$, and since $f$ is injective, $x = x'$. So there is exactly one $x$ with $f(x) = y$, and $f^{-1}(y) = x$ is well-defined.
Injective. Suppose $y, y' \in B$ and $f^{-1}(y) = f^{-1}(y') = x$. By the definition of $f^{-1}$, $f(x) = y$ and $f(x) = y'$. So $y = f(x) = y'$.
Surjective. Let $x \in A$, and set $y = f(x) \in B$. By the definition of $f^{-1}$, $f^{-1}(y) = x$. So every $x \in A$ is in the range of $f^{-1}$.
Therefore $f^{-1}$ is a well-defined bijection. $\blacksquare$