Corrected exercises: injective, surjective and bijective functions (201-N11)

The functions are (1) and (4). Relation (2) fails EXISTENCE: no arrow leaves the element 2, so $f(2)$ refers to nothing and the notation itself loses its meaning. Relation (3) fails UNIQUENESS: two arrows leave 1, towards $a$ and towards $b$, so $f(1)$ would refer to two objects at once. The test is read at a glance on an arrow diagram: there must be EXACTLY ONE arrow leaving EACH element on the left. Not zero, not two. Nothing at all is required on the codomain side, however: an element of $B$ may receive zero, one or ten arrows without leaving the world of functions. It is precisely this asymmetry between domain and codomain that will produce injectivity and surjectivity in the next exercises.

$f(1) = a$, $f(2) = b$, $f(3) = b$. The image is $f(A) = \{a, b\}$, of cardinality 2. It is not written $\{a, b, b\}$: a set does not count repetitions, and that is exactly why the cardinality of the image can be strictly smaller than that of the domain. Here $\lvert f(A) \rvert = 2 < 3 = \lvert A \rvert$. The lost element is the visible sign that two arrows land in the same place.

Yes, relation (4) is a function: each of the three elements of $A$ has exactly one arrow, and nothing forbids them from all ending at the same point. It is the constant function with value $c$. Its image is $f(A) = \{c\}$, of cardinality 1. The classic error is to reject it on the grounds that $c$ receives three arrows: that condition does not exist. It costs the whole question, when rereading the definition was enough.

Two elements of $A$ can perfectly well have the same image, and relation (4) gives the extreme example. It is in fact exactly the defect that will be called non-injectivity. On the other hand, two elements of $B$ can never have the same preimage: that would mean an element of $A$ has two images, which uniqueness forbids. Remember the asymmetric wording: a function is allowed to COLLAPSE, it is not allowed to SPLIT.

A function from $A$ to $B$ contains exactly $\lvert A \rvert = 3$ pairs, one per element of the domain, never one more or one less. The Cartesian product $A \times B$, on the other hand, has $3 \times 3 = 9$ pairs, and it has $2^{9} = 512$ subsets, so there are 512 relations from $A$ to $B$. Functions are therefore a narrow minority among relations, $3^{3} = 27$ out of 512, or about 5.3 percent. This count comes back in exercise 7, where it is used to count injections and bijections.

$f(E) = \{a, b, c\}$, of cardinality 3. The element $d$ has no preimage: no arrow reaches it, and we say it is not HIT. The image is therefore a proper subset of $F$, and that is exactly what makes $f$ fail to be surjective, in the sense defined in exercise 3. The reflex to build: the image is not the codomain, it is the part of the codomain actually used, and the two coincide only in the surjective case.

$f(P) = \{f(1), f(3), f(4)\} = \{a, a, b\} = \{a, b\}$, of cardinality 2 while $\lvert P \rvert = 3$. $f(P') = \{f(2), f(5)\} = \{c\}$, of cardinality 1 while $\lvert P' \rvert = 2$. The general rule is $\lvert f(P) \rvert \le \lvert P \rvert$, with equality exactly when $f$ merges no two elements of $P$. An image never grows: this is the first cardinality result of the chapter, and it is the source of the inequality $\lvert A \rvert \le \lvert B \rvert$ attached to an injection.

$f^{-1}(\{a\}) = \{1, 3, 6\}$, the three elements whose image is $a$. $f^{-1}(\{c\}) = \{2, 5\}$. $f^{-1}(\{d\}) = \varnothing$: no preimage, and the empty set is a perfectly legitimate answer, not a failed computation. Finally $f^{-1}(\{a,b\}) = \{1,3,6\} \cup \{4\} = \{1,3,4,6\}$. The classic trap is to answer with an ELEMENT when $f^{-1}$ returns a SET: $f^{-1}(\{b\})$ is $\{4\}$ and not $4$, and the distinction is the one the chapter on sets already made between $3$ and $\{3\}$.

The four sets are $\{1,3,6\}$, $\{4\}$, $\{2,5\}$ and $\varnothing$. Their union is indeed $\{1,2,3,4,5,6\} = E$, since every element has an image and therefore belongs to exactly one of these subsets, and the cardinalities add up to $3+1+2+0 = 6$. They are pairwise disjoint, because an element cannot have two images. We therefore recover a PARTITION of $E$, up to the empty parts: these are the classes of the equivalence relation having the same image, studied in the chapter on relations. Each set $f^{-1}(\{y\})$ is called a FIBRE of $f$ over $y$, and the word is used as is in exercise 9 on hashing.

No, and this is the most common misreading of the chapter. The notation $f^{-1}(Q)$, with a SET inside the parentheses, is defined for every function without exception: it denotes a subset of the domain, obtained by following the arrows backwards. The inverse FUNCTION $f^{-1} : F \to E$, on the other hand, exists only if $f$ is bijective, and our $f$ is nowhere near that, since $d$ has no preimage and $a$ has three. Two identical notations, two different objects: one takes a set and returns a set, the other would take an element and return an element. Confusing them leads to writing $f^{-1}(a) = 1$, which means nothing here and costs all the marks for the question.

Panel (1): each element of $B$ receives at most one arrow, but $d$ receives none, so the function is INJECTIVE ONLY. Panel (2): all three elements of $B$ are hit, but $a$ receives two arrows, those from 1 and from 2, so SURJECTIVE ONLY. Panel (3): each element of $B$ receives exactly one arrow, so BIJECTIVE. Panel (4): $a$ receives two and $b$ none, so NONE OF THE THREE. Counting the arrows received is the only move to remember for a finite set: at most one gives injectivity, at least one surjectivity, exactly one bijectivity. The arrows LEAVING, on the other hand, are not counted: they have already been used to decide that the object is a function.

From $\mathbb{R}$ to $\mathbb{R}$: not injective, because $f(-2) = f(2) = 4$ with $-2 \ne 2$, and a single counterexample is enough; not surjective either, because $-1$ has no preimage, the square of a real number never being negative. From $\mathbb{R}^{+}$ to $\mathbb{R}$: it becomes INJECTIVE, because if $a$ and $b$ are nonnegative and $a^{2} = b^{2}$ then $a = b$, the candidate $-b$ having been ruled out by the domain; it remains non-surjective, since the codomain has not moved and $-1$ is still not hit.

From $\mathbb{R}$ to $\mathbb{R}^{+}$: it becomes SURJECTIVE, because every $y \ge 0$ has the preimage $\sqrt{y}$, and even two as soon as $y > 0$; it remains non-injective, since the domain has not moved and $-2$ and $2$ still have the same image. From $\mathbb{R}^{+}$ to $\mathbb{R}^{+}$: the two corrections add up, the function is BIJECTIVE, and its inverse is the square root. We have thus obtained all four possible natures with ONE SINGLE computation rule, without ever changing a sign.

From $\mathbb{Z}$ to $\mathbb{N}$: neither one nor the other. Not injective, because $(-3)^{2} = 3^{2} = 9$. Not surjective either, and that is the trap of the question: the codomain $\mathbb{N}$ looks tailor-made, since squares of integers are indeed natural numbers, but 2, 3, 5, 6 and 7 are the squares of no integer. Of the 26 integers from 0 to 25, only 6 are perfect squares and 20 are not. The image is the set of perfect squares, a very thin part of $\mathbb{N}$. Remember that shrinking the codomain is not enough: it must be shrunk ALL THE WAY DOWN to the exact image.

Only the domain and the codomain were changed. The rule $x \mapsto x^{2}$ did not move. The reading rule that follows is the thread of the whole set: LOOK AT THE DOMAIN AND THE CODOMAIN BEFORE ANSWERING. A question that asks whether squaring is injective without specifying the two sets is not a hard question, it is an ill-posed one. The precise mechanism is worth memorizing: shrinking the DOMAIN can only help injectivity and never makes a function surjective; shrinking the CODOMAIN can only help surjectivity and never changes injectivity.

Let $a$ and $b$ be two real numbers such that $f(a) = f(b)$. Then $3a - 7 = 3b - 7$, so $3a = 3b$ by adding 7 to both sides, so $a = b$ by dividing by 3, which is legitimate since $3 \ne 0$. Two elements with the same image are therefore equal: $f$ is injective. The write-up begins with LET and ends with the requested conclusion, in a chain of implications, without a single numerical example. Checking three values proves nothing, it only tests, and that is worth zero on the question.

Let $y$ be an arbitrary real number. We look for $x$ such that $3x - 7 = y$, that is $3x = y + 7$, that is $x = \frac{y+7}{3}$. This number is indeed real, whatever $y$ is, since division by 3 is always possible. Mandatory check: $f\left(\frac{y+7}{3}\right) = 3 \cdot \frac{y+7}{3} - 7 = y + 7 - 7 = y$. So every real number has a preimage and $f$ is surjective. For $y = 5$: $x = \frac{12}{3} = 4$, and $f(4) = 12 - 7 = 5$. The function is therefore bijective, which was predictable: a linear function with nonzero slope, from $\mathbb{R}$ to $\mathbb{R}$, always is.

$g(0) = 1$ and $g(4) = 16 - 16 + 1 = 1$. So $g(0) = g(4)$ with $0 \ne 4$: $g$ is not injective. A single counterexample is enough, because injectivity asserts something for ALL pairs, and the negation of a universal statement is the existence of ONE failing case. This pair is found without trial and error, by noticing that the quadratic has its vertex at $x = 2$ and that two points symmetric about this axis have the same image; $0$ and $4$ are at distance 2 on either side. Writing only that the quadratic is not monotonic disproves nothing: you must produce the two values and their common image.

From $\mathbb{Z}$ to $\mathbb{Z}$: injective, because $2a = 2b$ gives $a = b$; not surjective, because 3 is odd and no integer $n$ satisfies $2n = 3$. From $\mathbb{Z}$ to $2\mathbb{Z}$: the rule and the domain are unchanged, so injectivity still holds without proving anything again, and surjectivity becomes true since every even integer can be written $2k$ with $k$ an integer, this $k$ being the preimage we want. The function is therefore BIJECTIVE from $\mathbb{Z}$ onto $2\mathbb{Z}$. It is the thread of exercise 3 applied once more, and this bijection comes back in exercise 10, where it says something surprising about infinite cardinalities.

Injectivity is a UNIVERSAL statement: for all $a$ and $b$, if $f(a) = f(b)$ then $a = b$. Surjectivity is an EXISTENCE statement: for every $y$, there EXISTS $x$ such that $f(x) = y$, and the write-up must produce this $x$, not merely assert that it exists. Disproving is the only one of the three moves that settles for an example, and that is because it negates a universal statement. The table to remember fits in three lines: to ESTABLISH a universal statement you need a general proof; to DESTROY it one example is enough; to ESTABLISH an existence statement, on the contrary, one example is enough, here the preimage built in b).

$f(1) = a$ then $g(a) = x$, so $(g \circ f)(1) = x$. Likewise $(g \circ f)(2) = g(b) = y$ and $(g \circ f)(3) = g(c) = z$. The three images are distinct, so $g \circ f$ is injective, and they exhaust $C = \{x,y,z\}$, so it is surjective: $g \circ f$ is BIJECTIVE. The computation is always done in this order, following the arrows; writing $(f \circ g)(1)$ would make no sense here, since $g$ does not start from $A$.

$f$ is NOT surjective: $d$ receives no arrow from $A$. $g$ is NOT injective: $b$ and $d$ have the same image $y$. And yet the composition is bijective. The idea that a composition inherits defects is therefore false, and this figure is a complete counterexample: a function that does not hit everything, followed by a function that merges two elements, can give a bijection, because the merging done by $g$ involves precisely the element $d$ that $f$ never reached. What is passed on are the QUALITIES, and not even in both directions, as questions d) and e) show.

INJECTIVITY. Let $a_1$ and $a_2$ be in $A$ with $(g \circ f)(a_1) = (g \circ f)(a_2)$, that is $g(f(a_1)) = g(f(a_2))$. Since $g$ is injective, $f(a_1) = f(a_2)$. Since $f$ is injective, $a_1 = a_2$. So $g \circ f$ is injective. SURJECTIVITY. Let $c$ be in $C$. Since $g$ is surjective, there exists $b$ in $B$ with $g(b) = c$. Since $f$ is surjective, there exists $a$ in $A$ with $f(a) = b$. Then $(g \circ f)(a) = g(b) = c$. So $g \circ f$ is surjective. Notice the difference in movement: the injectivity proof UNWINDS, it starts from an equality and removes the functions one by one; the surjectivity proof BUILDS, it starts from the codomain and works its way back to the domain. Mixing the two movements produces a write-up that proves nothing.

Suppose $g \circ f$ is injective and let $a_1, a_2$ satisfy $f(a_1) = f(a_2)$. Applying $g$ to both sides, $g(f(a_1)) = g(f(a_2))$, so $(g \circ f)(a_1) = (g \circ f)(a_2)$, so $a_1 = a_2$ by injectivity of the composition. So $f$ is injective. The figure does show that $g$ can fail: $g \circ f$ is injective there and yet $g(b) = g(d) = y$. The reason fits in one sentence: the composition only sees $g$ through its restriction to $f(A) = \{a,b,c\}$, and $d$ is invisible to it. Remember the asymmetry: from an injective composition, only the FIRST function inherits.

Suppose $g \circ f$ is surjective and let $c$ be in $C$. There exists $a$ in $A$ with $g(f(a)) = c$. Then the element $b = f(a)$ of $B$ satisfies $g(b) = c$, so $c$ has a preimage under $g$: $g$ is surjective. The figure confirms it and shows that $f$, for its part, can fail: $g \circ f$ is surjective there while $f$ misses $d$. It is the mirror image of the previous asymmetry: from a surjective composition, only the SECOND function inherits. Both results sum up in one sentence, and that is the form to memorize: injectivity travels back to the input, surjectivity travels forward to the output.

The table gives $c(A)=C$, $c(B)=E$, $c(C)=A$, $c(D)=B$, $c(E)=D$. The five images are $C$, $E$, $A$, $B$ and $D$: they are pairwise distinct, so $c$ is injective, and they exhaust $\Sigma$, so $c$ is surjective. It is a bijection. Since the domain and the codomain have the same finite cardinality here, one of the two checks would have been enough, a result proved in exercise 7. There are $5^{5} = 3{,}125$ functions from $\Sigma$ to $\Sigma$, of which $5! = 120$ are bijections, that is $3.84$ percent. In other words, more than 96 functions out of 100 are useless as a cipher, so drawing a table at random is not good enough.

Reverse each arrow. $c(C)=A$ gives $c^{-1}(A)=C$; $c(D)=B$ gives $c^{-1}(B)=D$; $c(A)=C$ gives $c^{-1}(C)=A$; $c(E)=D$ gives $c^{-1}(D)=E$; $c(B)=E$ gives $c^{-1}(E)=B$. EDBCA is decrypted letter by letter: $E \to B$, $D \to E$, $B \to D$, $C \to A$, $A \to C$, which gives BEDAC. Check in the other direction: $c$ applied to BEDAC does give back $E$, $D$, $B$, $C$, $A$. The trap is to read the table in the wrong direction, which produces meaningless text without any visible computation error: checking by re-encrypting is therefore mandatory.

$c(B) = E$ and $c^{-1}(E) = B$: the first equality holds. $c^{-1}(B) = D$ and $c(D) = B$: so does the second. Both are required because they do not say the same thing. The equality $c^{-1} \circ c = \mathrm{id}_{\Sigma}$ says that you always get back the ORIGINAL message, which corresponds to the injectivity of $c$; the equality $c \circ c^{-1} = \mathrm{id}_{\Sigma}$ says that every possible encrypted letter does come from a plaintext letter, which corresponds to surjectivity. A function satisfying only one of the two has only a left inverse or a right inverse, never an inverse, and on an infinite set both situations really occur: the doubling map $n \mapsto 2n$, taken from $\mathbb{N}$ to $\mathbb{N}$, has the left inverse $m \mapsto \lfloor m/2 \rfloor$ but no right inverse, since $1$ has no preimage.

Apply $c$ then $d$: $A \to C \to D$, $B \to E \to A$, $C \to A \to B$, $D \to B \to C$, $E \to D \to E$. The table of $d \circ c$ is therefore $A \to D$, $B \to A$, $C \to B$, $D \to C$, $E \to E$, and its five images are distinct: it is a bijection, as guaranteed by the result of exercise 5 on the composition of two bijections. Its inverse is $(d \circ c)^{-1} = c^{-1} \circ d^{-1}$, and the order is reversed: to undo two chained operations, you first undo the LAST one performed. Writing $d^{-1} \circ c^{-1}$ is the classic error, and it shows up immediately: in the general case where the three sets differ, that composition does not even start from the right set.

The function $e$ is not injective: $A$ and $B$ have the same image $A$, $C$ and $D$ have the same image $C$. To obtain AAAAA, each of the five positions must contain a letter whose image is $A$, so $A$ or $B$: that makes $2^{5} = 32$ different plaintext messages that give the same ciphertext. Decryption is therefore impossible, not for lack of cleverness but on principle: $e$, not being injective, has no inverse, and a recipient who must choose among 32 messages has no way to decide. It is exactly the argument the chapter on proof techniques uses against the universal lossless compressor, and here it is the same property, read on the function rather than on a count.