Functions: injections, surjections, bijections - Discrete Math

Let $A = \{1, 2, 3, 4\}$ and consider all functions $f: A \to A$ such that $f(f(x)) = x$ for all $x \in A$ . How many of these functions are bijective?
Answer: All such functions are bijective, and there are exactly 10 of them in total A function $f$ satisfying $f(f(x)) = x$ for all $x$ is called an involution. We need to prove that every involution on a finite set is bijective. For injectivity: if $f(a) = f(b)$ , then $a = f(f(a)) = f(f(b)) = b$ . For surjectivity: given any $y \in A$ , we have $f(f(y)) = y$ , so $y = f(f(y))$ , meaning $y$ is the image of $f(y)$ . Thus every involution is bijective. Now we count involutions on $\{1,2,3,4\}$ . An involution partitions the set into fixed points (where $f(x) = x$ ) and 2-cycles (where $f(x) = y, f(y) = x$ with $x \neq y$ ). Possible structures: (1) All 4 fixed points: 1 way. (2) 2 fixed points, 1 two-cycle: $\binom{4}{2} = 6$ ways to choose the 2-cycle. (3) 0 fixed points, 2 two-cycles: $\frac{1}{2!}\binom{4}{2}\binom{2}{2} = \frac{6 \cdot 1}{2} = 3$ ways. Total: $1 + 6 + 3 = 10$ involutions. Choice B gives the wrong count. Choices C and D incorrectly suggest some involutions aren't bijective.
Let $h: \mathbb{Z} \to \mathbb{Z}$ be defined by $h(n) = \begin{cases} 2n & \text{if } n \geq 0 \\ 2n + 1 & \text{if } n < 0 \end{cases}$ . Which property does $h$ satisfy?
Answer: $h$ is bijective because it maps non-negative integers to even integers and negative integers to odd integers Let's analyze both properties. For injectivity: if $n \geq 0$ , then $h(n) = 2n \geq 0$ and even. If $n < 0$ , then $h(n) = 2n + 1 < 1$ and odd (since $2n$ is even). The ranges don't overlap: non-negative even integers vs. negative odd integers. Within each piece, the functions $n \mapsto 2n$ and $n \mapsto 2n+1$ are strictly increasing, so no collisions occur. Thus $h$ is injective. For surjectivity: every non-negative even integer $2k$ equals $h(k)$ where $k \geq 0$ . Every negative odd integer $2k+1 < 0$ can be written as $2k+1$ where $k < 0$ , so it equals $h(k)$ . Every positive odd integer $2k+1 > 0$ equals $h(k)$ where $k = -\frac{2k+1-1}{2} < 0$ . Thus $h$ is surjective. Choice A is wrong about surjectivity and the range. Choice B incorrectly claims $h(0) = h(-1)$ , but $h(0) = 0$ and $h(-1) = -1$ . Choice D incorrectly suggests the ranges overlap.
Let $f: \{0,1,2,\ldots,n-1\} \to \{0,1,2,\ldots,n-1\}$ be defined by $f(x) = ax \bmod n$ where $\gcd(a,n) = d > 1$ . Which statement about the range of $f$ is correct?
Answer: The range has exactly $\frac{n}{d}$ elements, and $f$ is neither injective nor surjective on its full domain Since $\gcd(a,n) = d > 1$ , we can write $a = da'$ and $n = dn'$ where $\gcd(a',n') = 1$ . Then $f(x) = ax \bmod n = da'x \bmod dn'$ . The range of $f$ consists of all values $\{da'x \bmod dn' : x = 0,1,\ldots,n-1\}$ . Since $\gcd(a',n') = 1$ , as $x$ runs through $\{0,1,\ldots,n'-1\}$ , $a'x \bmod n'$ takes all values $\{0,1,\ldots,n'-1\}$ . Therefore, $da'x \bmod dn'$ takes values $\{0,d,2d,\ldots,(n'-1)d\} = \{kd : k = 0,1,\ldots,n'-1\}$ . This gives exactly $n' = \frac{n}{d}$ distinct values. For injectivity: $f(x_1) = f(x_2)$ means $ax_1 \equiv ax_2 \pmod{n}$ , so $a(x_1-x_2) \equiv 0 \pmod{n}$ . This means $n | a(x_1-x_2)$ , so $dn' | da'(x_1-x_2)$ , giving $n' | a'(x_1-x_2)$ . Since $\gcd(a',n') = 1$ , we need $n' | (x_1-x_2)$ . For $x_1,x_2 \in \{0,1,\ldots,n-1\}$ with $x_1 \neq x_2$ , we can have $|x_1-x_2| = n' < n$ , so $f$ is not injective. Since $|\text{range}| = \frac{n}{d} < n$ , $f$ is not surjective. Choice A incorrectly claims injectivity.
Let $h: [0,1] \to [0,1]$ be defined by $h(x) = \begin{cases} 2x & \text{if } 0 \leq x \leq \frac{1}{2} \\ 2-2x & \text{if } \frac{1}{2} < x \leq 1 \end{cases}$ . Analyzing the properties of $h$ , which conclusion is correct?
Answer: $h$ is surjective but not injective, since $h$ achieves every value in $[0,1]$ but $h(x) = h(1-x)$ for all $x$ When analyzing whether a function is injective (one-to-one) or surjective (onto), you need to examine how inputs map to outputs and whether every possible output is achieved. Let's check if $h$ is surjective by finding its range. On $[0, \frac{1}{2}]$ , $h(x) = 2x$ ranges from $h(0) = 0$ to $h(\frac{1}{2}) = 1$ . On $(\frac{1}{2}, 1]$ , $h(x) = 2-2x$ ranges from values approaching $h(\frac{1}{2}) = 1$ down to $h(1) = 0$ . So $h$ achieves every value in $[0,1]$ , making it surjective. For injectivity, notice that $h$ is not one-to-one because different inputs can produce the same output. For example, $h(\frac{1}{4}) = 2 \cdot \frac{1}{4} = \frac{1}{2}$ and $h(\frac{3}{4}) = 2 - 2 \cdot \frac{3}{4} = \frac{1}{2}$ . The pattern $h(x) = h(1-x)$ holds generally, confirming the function is not injective. Choice A is wrong because $h$ is surjective—it does achieve the value 1 at $x = \frac{1}{2}$ . Choice C is wrong because continuity and mapping a compact set to itself doesn't guarantee bijectivity; the function must also be injective. Choice D is wrong because $h$ is surjective—it does achieve its maximum value of 1 and every other value in $[0,1]$ . Study tip: For piecewise functions, check injectivity by looking for symmetries or repeated values, and check surjectivity by carefully finding the range of each piece. The horizontal line test is your friend for visualizing injectivity.
A function $\phi: \mathbb{N} \to \mathbb{N}$ satisfies the property that for any $m, n \in \mathbb{N}$ , if $\gcd(m,n) = 1$ , then $\phi(mn) = \phi(m)\phi(n)$ . Additionally, $\phi(p^k) = p^{k-1}(p-1)$ for any prime $p$ and $k \geq 1$ . Which statement about $\phi$ is correct?
Answer: $\phi$ is not injective because $\phi(3) = \phi(4) = \phi(6) = 2$ , and it is not surjective since some integers like 14 are not in the range This function is Euler's totient function $\phi(n)$ . Let's check specific values: $\phi(3) = 3^{1-1}(3-1) = 1 \cdot 2 = 2$ , $\phi(4) = \phi(2^2) = 2^{2-1}(2-1) = 2 \cdot 1 = 2$ , and $\phi(6) = \phi(2 \cdot 3) = \phi(2)\phi(3) = 1 \cdot 2 = 2$ since $\phi(2) = 2^{1-1}(2-1) = 1$ . So $\phi$ is not injective. For surjectivity, the totient function is known to not be surjective - for example, no positive integer $n$ satisfies $\phi(n) = 14$ . Choice A incorrectly claims injectivity. Choice B incorrectly claims surjectivity. Choice D incorrectly claims surjectivity.
Let $f: \mathbb{R} \to \mathbb{R}$ be defined by $f(x) = x|x|$ . Consider the restriction $g: \mathbb{R} \to [0,\infty)$ where $g(x) = |f(x)|$ . Which statement correctly describes the relationship between the injectivity and surjectivity of $f$ and $g$ ?
Answer: $f$ is bijective and $g$ is surjective but not injective, since $f(x) = x|x|$ is strictly increasing while $g(±x) = x^2$ When analyzing functions for injectivity and surjectivity, you need to examine how inputs map to outputs and whether the mapping covers the entire codomain without repetition. First, let's analyze $f(x) = x|x|$ . For $x \geq 0$ , we have $f(x) = x \cdot x = x^2$ . For $x < 0$ , we have $f(x) = x \cdot (-x) = -x^2$ . This means $f(x) = x^2$ when $x \geq 0$ and $f(x) = -x^2$ when $x < 0$ . The function $f$ is strictly increasing: as $x$ increases, $f(x)$ increases without bound in both directions, mapping $\mathbb{R}$ onto $\mathbb{R}$ with no repeated outputs. Therefore, $f$ is bijective. Now for $g(x) = |f(x)|$ . Since $f(x) = x^2$ for $x \geq 0$ and $f(x) = -x^2$ for $x < 0$ , we get $g(x) = |x^2| = x^2$ for $x \geq 0$ and $g(x) = |-x^2| = x^2$ for $x < 0$ . Thus $g(x) = x^2$ for all $x \in \mathbb{R}$ . Since every non-negative real number has a square root, $g$ is surjective onto $[0,\infty)$ . However, $g$ is not injective because $g(2) = g(-2) = 4$ . Answer choice A incorrectly claims $g$ is injective. Answer choice C wrongly states $g$ is not surjective. Answer choice D incorrectly claims $g$ is bijective when it's clearly not injective. Strategy tip: When dealing with absolute value compositions, always check both positive and negative inputs separately, and remember that absolute values typically destroy injectivity by making $f(x) = f(-x)$ .
Define $g: \mathbb{R} \setminus \{1\} \to \mathbb{R} \setminus \{2\}$ by $g(x) = \frac{2x}{x-1}$ . To show that $g$ is bijective, which of the following correctly identifies both the inverse function and the key step in proving surjectivity?
Answer: The inverse is $g^{-1}(y) = \frac{y}{y-2}$ , and surjectivity follows from solving $y = \frac{2x}{x-1}$ for any $y \neq 2$ When proving a function is bijective, you need to establish both injectivity (one-to-one) and surjectivity (onto). For rational functions like this one, finding the inverse function is often the most efficient approach since it simultaneously proves both properties. To find the inverse of $g(x) = \frac{2x}{x-1}$ , start with $y = \frac{2x}{x-1}$ and solve for $x$ . Cross-multiplying gives $y(x-1) = 2x$ , which expands to $yx - y = 2x$ . Rearranging: $yx - 2x = y$ , so $x(y-2) = y$ , yielding $x = \frac{y}{y-2}$ . Therefore, $g^{-1}(y) = \frac{y}{y-2}$ . For surjectivity, you must show that for every $y \in \mathbb{R} \setminus \{2\}$ , there exists some $x \in \mathbb{R} \setminus \{1\}$ such that $g(x) = y$ . The key step is demonstrating that the equation $y = \frac{2x}{x-1}$ has a solution for any $y \neq 2$ , which we just showed: $x = \frac{y}{y-2}$ . Option A has the wrong inverse function ( $\frac{y+1}{y-2}$ instead of $\frac{y}{y-2}$ ). Option B also gives an incorrect inverse ( $\frac{y+2}{y-2}$ ). Option C has the correct inverse but incorrectly identifies the surjectivity approach—limits don't prove surjectivity directly. Study tip: When proving bijection for rational functions, always find the inverse algebraically by solving $y = f(x)$ for $x$ . This inverse both proves the function is bijective and gives you the explicit formula you need.
Consider the function $F: \mathbb{R}^2 \to \mathbb{R}^2$ defined by $F(x,y) = (2x - y, x + y)$ . Which statement correctly describes the properties of $F$ ?
Answer: $F$ is bijective because its matrix representation has determinant 3, making it invertible as a linear transformation When you encounter a linear function from $\mathbb{R}^2$ to $\mathbb{R}^2$ , the key insight is that its injectivity and surjectivity properties are completely determined by whether its matrix representation is invertible. The function $F(x,y) = (2x - y, x + y)$ can be written as matrix multiplication: $F(\mathbf{v}) = A\mathbf{v}$ where $A = \begin{pmatrix} 2 & -1 \\ 1 & 1 \end{pmatrix}$ . The determinant is $\det(A) = 2(1) - (-1)(1) = 2 + 1 = 3$ . Since the determinant is non-zero, the matrix is invertible, which means $F$ is bijective (both injective and surjective). Looking at the wrong answers: Choice A incorrectly claims $F$ is injective but not surjective. While it correctly notes the positive determinant, it misses that a non-zero determinant guarantees both properties, not just injectivity. Choice B states $F$ is surjective but not injective with non-unique solutions. This contradicts the invertible matrix having exactly one solution for each output. Choice C claims $F$ is neither injective nor surjective with determinant zero. This is factually wrong—we calculated the determinant as 3, not 0. Choice D correctly identifies that the non-zero determinant (specifically 3) makes the linear transformation invertible, ensuring bijectivity. Study tip: For linear transformations between spaces of equal dimension, always compute the determinant first. Non-zero determinant means bijective; zero determinant means neither injective nor surjective. This single calculation tells you everything about the function's properties.
Consider the function $\phi: \mathcal{P}(\{1,2,3\}) \to \{0,1\}^3$ defined by $\phi(S) = (x_1, x_2, x_3)$ where $x_i = 1$ if $i \in S$ and $x_i = 0$ if $i \notin S$ . Here $\mathcal{P}(\{1,2,3\})$ denotes the power set. Which property does $\phi$ have?
Answer: $\phi$ is bijective, since it establishes a one-to-one correspondence between subsets of $\{1,2,3\}$ and binary strings of length 3 The function $\phi$ maps each subset $S \subseteq \{1,2,3\}$ to its characteristic vector. For injectivity: if $S \neq T$ , then there exists $i$ such that $i \in S$ and $i \notin T$ (or vice versa), so $\phi(S)$ and $\phi(T)$ differ in the $i$ -th coordinate. For surjectivity: given any $(x_1,x_2,x_3) \in \{0,1\}^3$ , take $S = \{i : x_i = 1\}$ ; then $\phi(S) = (x_1,x_2,x_3)$ . Since $|\mathcal{P}(\{1,2,3\})| = 2^3 = 8 = |\{0,1\}^3|$ , the bijection can also be seen by counting. Choice A incorrectly claims not all bit strings correspond to subsets. Choice B incorrectly claims multiple subsets can yield the same bit string. Choice D incorrectly states the cardinalities are different.
Consider the function $\Phi: \mathcal{P}(\mathbb{N}) \to \{0,1\}^\mathbb{N}$ that maps each subset $S \subseteq \mathbb{N}$ to its characteristic function $\chi_S$ , where $\chi_S(n) = 1$ if $n \in S$ and $\chi_S(n) = 0$ if $n \notin S$ . Which property does $\Phi$ possess?
Answer: $\Phi$ is bijective, establishing a one-to-one correspondence between subsets of $\mathbb{N}$ and binary sequences When analyzing functions between sets, you need to determine two key properties: injectivity (one-to-one) and surjectivity (onto). For characteristic functions, this connection between subsets and binary sequences is fundamental in discrete mathematics. The function $\Phi$ is bijective because it establishes a perfect one-to-one correspondence. To see why, consider that each subset $S \subseteq \mathbb{N}$ produces a unique binary sequence: for any natural number $n$ , either $n \in S$ (giving $\chi_S(n) = 1$ ) or $n \notin S$ (giving $\chi_S(n) = 0$ ). This makes $\Phi$ injective—different subsets must produce different characteristic functions. Conversely, every possible binary sequence $f: \mathbb{N} \to \{0,1\}$ corresponds to exactly one subset: $S = \{n \in \mathbb{N} : f(n) = 1\}$ . This makes $\Phi$ surjective. Option A incorrectly assumes the mapping only works for finite subsets, but characteristic functions handle infinite subsets perfectly well—like the subset of even numbers producing the sequence $(0,1,0,1,0,1,\ldots)$ . Option B falsely claims multiple subsets can share the same characteristic function, which is impossible since the characteristic function completely determines which elements belong to the subset. Option C incorrectly suggests fundamental incompatibility between sets and functions, missing that this is precisely what characteristic functions elegantly resolve. Remember: characteristic functions create natural bijections between subsets and binary sequences. This bijection is a cornerstone result showing these seemingly different mathematical objects are essentially equivalent.
Let $A = \{1, 2, 3, 4, 5\}$ and consider functions $f: A \to A$ . If $f$ satisfies the condition that $f(f(x)) = x$ for all $x \in A$ , which statement about $f$ must be true?
Answer: $f$ must be bijective, since the condition $f \circ f = \text{id}_A$ implies $f$ is its own inverse function When you encounter a function satisfying $f(f(x)) = x$ for all elements in its domain, you're looking at a function that is its own inverse. This condition is called an involution, and it has powerful implications for the function's properties. The key insight is that if $f(f(x)) = x$ holds for every $x$ in the domain, then $f \circ f = \text{id}_A$ (the identity function). This means $f$ has a left inverse (itself) and a right inverse (also itself). For functions between finite sets of the same size, having both a left and right inverse guarantees the function is bijective. To see why $f$ must be injective: if $f(a) = f(b)$ for some $a \neq b$ , then applying $f$ again gives $f(f(a)) = f(f(b))$ , which means $a = b$ by our condition—a contradiction. To see why $f$ must be surjective: for any $y \in A$ , we have $y = f(f(y))$ , so $y$ is in the range of $f$ (specifically, $y = f(f(y))$ ). Answer choice A incorrectly suggests the condition is too weak to determine $f$ 's properties. Answer choice B wrongly claims $f$ prevents self-mapping (elements can map to themselves in involutions). Answer choice C has the injectivity and surjectivity backwards in terms of what "may not" hold. Answer choice D correctly identifies that $f$ must be bijective since it serves as its own inverse. Remember: when $f \circ f = \text{id}$ , the function $f$ is automatically bijective on finite domains of equal size.
Let $A$ be a finite set with $|A| = n$ , and let $\text{Inj}(A,A)$ denote the set of all injective functions from $A$ to $A$ . If we randomly select a function $f \in \text{Inj}(A,A)$ and then randomly select a distinct function $g \in \text{Inj}(A,A)$ , what is the probability that $g \circ f$ is also injective?
Answer: $1$ , because the composition of any two injective functions is always injective, regardless of the domain and codomain Since $A$ is finite with $|A| = n$ , every injective function $f: A \to A$ is automatically bijective (an injective function from a finite set to itself must be surjective). Similarly, every $g \in \text{Inj}(A,A)$ is bijective. The composition of two bijective functions is always bijective, hence injective. This is true regardless of which specific bijections $f$ and $g$ we choose, as long as they're both in $\text{Inj}(A,A)$ . Therefore, for any choice of distinct $f, g \in \text{Inj}(A,A)$ , the composition $g \circ f$ is guaranteed to be injective (in fact, bijective). The probability is 1. Choice B incorrectly suggests some compositions might not be injective. Choice C gives an arbitrary small probability. Choice D provides a complex expression that doesn't apply to this situation where all compositions are guaranteed to be injective.
Let $f: \mathbb{R} \to \mathbb{R}$ be defined by $f(x) = x^3 - 3x + 2$ . Which statement about $f$ is correct?
Answer: $f$ is surjective but not injective, making it neither bijective nor one-to-one To check injectivity, we examine if $f(x_1) = f(x_2)$ implies $x_1 = x_2$ . Since $f'(x) = 3x^2 - 3 = 3(x^2 - 1)$ , we have $f'(x) = 0$ at $x = \pm 1$ . This creates local extrema: $f(-1) = 4$ (local max) and $f(1) = 0$ (local min). Since $f$ has both a local maximum and minimum, there exist distinct values that map to the same output, so $f$ is not injective. However, as $x \to \pm\infty$ , $f(x) \to \pm\infty$ respectively, and $f$ is continuous, so by the Intermediate Value Theorem, $f$ is surjective. Choice A is wrong because $f'(x)$ is not always positive. Choice B correctly identifies why $f$ is not injective but doesn't address surjectivity. Choice D is wrong because being cubic doesn't guarantee bijectivity.
Let $S = \{(x,y) \in \mathbb{R}^2 : x^2 + y^2 \leq 1\}$ and $T = \{(x,y) \in \mathbb{R}^2 : 0 \leq x \leq 1, 0 \leq y \leq 1\}$ . Consider the function $f: S \to T$ defined by $f(x,y) = \left(\frac{x+1}{2}, \frac{y+1}{2}\right)$ . What can be concluded about $f$ ?
Answer: $f$ is injective but not surjective, since it preserves distinctness but maps the unit disk to only part of the unit square The function $f(x,y) = \left(\frac{x+1}{2}, \frac{y+1}{2}\right)$ is a linear transformation (translation and scaling). Linear transformations are injective, so if $(x_1,y_1) \neq (x_2,y_2)$ , then $f(x_1,y_1) \neq f(x_2,y_2)$ . For surjectivity, note that $S$ is the closed unit disk ( $x^2 + y^2 \leq 1$ ), so $-1 \leq x,y \leq 1$ . Thus $f$ maps $S$ to $\{(u,v) : 0 \leq u,v \leq 1, (2u-1)^2 + (2v-1)^2 \leq 1\}$ , which is a disk inside $T$ , not all of $T$ . So $f$ is not surjective. Choice B reverses the properties. Choice C incorrectly claims bijection. Choice D is wrong - the function is well-defined everywhere.
Define $\psi: \mathbb{R} \setminus \{1\} \to \mathbb{R} \setminus \{2\}$ by $\psi(x) = \frac{2x}{x-1}$ . Which statement about $\psi$ and its inverse is correct?
Answer: $\psi$ is bijective with inverse $\psi^{-1}(y) = \frac{y}{y-2}$ , and the domain exclusions correspond to the codomain exclusions When you encounter a function between restricted domains, you need to verify three things: injectivity (one-to-one), surjectivity (onto), and find the correct inverse formula. To find the inverse of $\psi(x) = \frac{2x}{x-1}$ , start with $y = \frac{2x}{x-1}$ and solve for $x$ . Cross-multiplying gives $y(x-1) = 2x$ , so $yx - y = 2x$ . Rearranging: $yx - 2x = y$ , which factors as $x(y-2) = y$ . Therefore $x = \frac{y}{y-2}$ , making $\psi^{-1}(y) = \frac{y}{y-2}$ . Notice the beautiful symmetry: $\psi$ excludes $x = 1$ from its domain (where the denominator $x-1 = 0$ ), while $\psi^{-1}$ excludes $y = 2$ from its domain (where $y-2 = 0$ ). This isn't coincidental—the domain exclusion of $\psi$ corresponds exactly to the codomain exclusion $\{2\}$ , and vice versa. You can verify bijectivity by checking that $\psi$ maps $\mathbb{R} \setminus \{1\}$ onto $\mathbb{R} \setminus \{2\}$ and that the inverse relationship holds. Choice A has the wrong inverse formula (missing the factor of 2). Choice B has an incorrect inverse $\frac{2y}{y-2}$ and misunderstands the domain-codomain relationship. Choice C incorrectly claims the function isn't bijective—while asymptotes exist, they don't prevent bijectivity between the specified sets. Study tip: For rational functions, the domain exclusions of a function become the codomain exclusions of its inverse, and vice versa. Always check this correspondence when verifying inverse functions.
Let $f: \mathbb{R} \to \mathbb{R}$ be defined by $f(x) = x^3 - 3x + 2$ . Consider the restriction $g: [1, \infty) \to \mathbb{R}$ where $g(x) = f(x)$ . Which statement about $g$ is correct?
Answer: $g$ is injective but not surjective, since $g$ is strictly increasing on $[1, \infty)$ but its range is $[0, \infty)$ First, find critical points: $f'(x) = 3x^2 - 3 = 3(x^2 - 1) = 3(x-1)(x+1)$ . So $f'(x) = 0$ at $x = \pm 1$ . For $x > 1$ , $f'(x) > 0$ , so $g$ is strictly increasing on $[1, \infty)$ , making it injective. Since $g(1) = 1 - 3 + 2 = 0$ and $g$ is increasing with $\lim_{x \to \infty} g(x) = \infty$ , the range of $g$ is $[0, \infty)$ , not all of $\mathbb{R}$ , so $g$ is not surjective. Choice B is wrong because $g$ is injective. Choice C is wrong because $g$ is not surjective onto $\mathbb{R}$ . Choice D is wrong because $g$ is injective.
Let $\mathcal{F} = \{f: \{1,2,3\} \to \{1,2,3\} : f \text{ is injective}\}$ and $\mathcal{G} = \{g: \{1,2,3\} \to \{1,2,3\} : g \text{ is surjective}\}$ . What are $|\mathcal{F}|$ , $|\mathcal{G}|$ , and $|\mathcal{F} \cap \mathcal{G}|$ ?
Answer: $|\mathcal{F}| = 6$ , $|\mathcal{G}| = 6$ , and $|\mathcal{F} \cap \mathcal{G}| = 6$ , since injectivity and surjectivity are equivalent for finite sets of equal size For functions between finite sets of the same size, injectivity and surjectivity are equivalent to bijectivity. Since $|\{1,2,3\}| = |\{1,2,3\}| = 3$ , an injective function from $\{1,2,3\}$ to $\{1,2,3\}$ must also be surjective (if three distinct inputs map to three distinct outputs, all outputs must be used). Similarly, a surjective function must be injective (if all three outputs are achieved by three inputs, no two inputs can map to the same output). Therefore, $\mathcal{F} = \mathcal{G} = \mathcal{F} \cap \mathcal{G}$ = the set of all bijections from $\{1,2,3\}$ to $\{1,2,3\}$ . The number of bijections is the number of permutations of 3 elements, which is $3! = 6$ . So $|\mathcal{F}| = |\mathcal{G}| = |\mathcal{F} \cap \mathcal{G}| = 6$ . Choice B incorrectly calculates $|\mathcal{F}| = 9$ (this would be $3^2$ , but not all functions are injective). Choice C incorrectly calculates $|\mathcal{G}| = 9$ . Choice D gives completely wrong values, including an impossible intersection size larger than either individual set.
Consider the function $g: \{1, 2, 3, 4, 5\} \to \{a, b, c, d\}$ defined by $g(1) = a$ , $g(2) = b$ , $g(3) = c$ , $g(4) = d$ , and $g(5) = b$ . How many elements must be removed from the domain to make $g$ injective while maintaining surjectivity?
Answer: Exactly 1 element, and there are 2 different ways to choose which element Currently $g$ is surjective (every element in codomain is hit) but not injective because $g(2) = g(5) = b$ . To make it injective, we must eliminate this collision by removing either 2 or 5 from the domain. If we remove 2, we get $g: \{1,3,4,5\} \to \{a,b,c,d\}$ with $g(1)=a, g(3)=c, g(4)=d, g(5)=b$ , which is bijective. If we remove 5, we get $g: \{1,2,3,4\} \to \{a,b,c,d\}$ with $g(1)=a, g(2)=b, g(3)=c, g(4)=d$ , which is also bijective. Removing any other single element (1, 3, or 4) would eliminate a unique image and destroy surjectivity. So exactly 1 element must be removed, with exactly 2 choices. Choice B gives wrong count of ways. Choice C suggests removing 2 elements, but this would make $|\text{domain}| < |\text{codomain}|$ , preventing surjectivity. Choice D is incorrect as we showed two valid solutions exist.

Start this quiz