Worked Problems for Proving Injectivity and Surjectivity

📚 What are Injectivity and Surjectivity?

In mathematics, especially in set theory and function theory, injectivity and surjectivity are properties of functions that describe how a function maps elements from its domain to its codomain.

• 🔑 Injectivity (One-to-one): A function $f: A \rightarrow B$ is injective if every element of the codomain $B$ is the image of at most one element of the domain $A$. In simpler terms, different elements in $A$ map to different elements in $B$. Mathematically, if $f(x_1) = f(x_2)$, then $x_1 = x_2$.
• 🎯 Surjectivity (Onto): A function $f: A \rightarrow B$ is surjective if every element of the codomain $B$ is the image of at least one element of the domain $A$. In other words, for every $b \in B$, there exists an $a \in A$ such that $f(a) = b$.
• 🤝 Bijectivity: A function is bijective if it is both injective and surjective.

📜 History and Background

The concepts of injectivity and surjectivity emerged gradually with the formalization of set theory and function theory in the 19th and 20th centuries. Mathematicians like Georg Cantor, Richard Dedekind, and others laid the groundwork for these ideas while exploring the properties of infinite sets and mappings between them.

• 👴 Early Set Theory: Cantor's work on comparing the sizes of infinite sets led to the need for precise definitions of mappings and their properties.
• 📝 Formalization: As set theory became more rigorous, the properties of injectivity and surjectivity were explicitly defined and used in various mathematical proofs.

💡 Key Principles for Proving Injectivity and Surjectivity

Proving injectivity and surjectivity often involves different techniques tailored to the specific function in question.

• 🧪 Proving Injectivity:
  • 📝 Direct Proof: Assume $f(x_1) = f(x_2)$ and show that $x_1 = x_2$.
  • 🚫 Proof by Contradiction: Assume $x_1 \neq x_2$ and show that $f(x_1) \neq f(x_2)$.
• 🎯 Proving Surjectivity:
  • 🏗️ Constructive Proof: For any $y$ in the codomain, find an $x$ in the domain such that $f(x) = y$.

🧮 Worked Problems

1. Linear Function

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be defined by $f(x) = 2x + 3$. Show that $f$ is bijective.

• 🔑 Injectivity: Assume $f(x_1) = f(x_2)$. Then $2x_1 + 3 = 2x_2 + 3$. Subtracting 3 from both sides gives $2x_1 = 2x_2$, and dividing by 2 gives $x_1 = x_2$. Thus, $f$ is injective.
• 🎯 Surjectivity: Let $y \in \mathbb{R}$. We want to find an $x \in \mathbb{R}$ such that $f(x) = y$. So, $2x + 3 = y$. Solving for $x$, we get $x = \frac{y - 3}{2}$. Since $y \in \mathbb{R}$, $x$ is also in $\mathbb{R}$. Thus, $f$ is surjective.
• 🎉 Conclusion: Since $f$ is both injective and surjective, it is bijective.

2. Quadratic Function (Restricted Domain)

Let $g: [0, \infty) \rightarrow [0, \infty)$ be defined by $g(x) = x^2$. Show that $g$ is bijective.

• 🔑 Injectivity: Assume $g(x_1) = g(x_2)$. Then $x_1^2 = x_2^2$. Taking the square root of both sides gives $|x_1| = |x_2|$. Since $x_1, x_2 \geq 0$, we have $x_1 = x_2$. Thus, $g$ is injective.
• 🎯 Surjectivity: Let $y \in [0, \infty)$. We want to find an $x \in [0, \infty)$ such that $g(x) = y$. So, $x^2 = y$. Taking the square root of both sides gives $x = \sqrt{y}$. Since $y \geq 0$, $x$ is also in $[0, \infty)$. Thus, $g$ is surjective.
• 🎉 Conclusion: Since $g$ is both injective and surjective, it is bijective.

3. Function with Absolute Value

Let $h: \mathbb{R} \rightarrow [0, \infty)$ be defined by $h(x) = |x|$. Show that $h$ is surjective but not injective.

• 💔 Not Injectivity: Consider $x_1 = 1$ and $x_2 = -1$. Then $h(1) = |1| = 1$ and $h(-1) = |-1| = 1$. Since $h(1) = h(-1)$ but $1 \neq -1$, $h$ is not injective.
• 🎯 Surjectivity: Let $y \in [0, \infty)$. We want to find an $x \in \mathbb{R}$ such that $h(x) = y$. We can choose $x = y$. Then $h(y) = |y| = y$ since $y \geq 0$. Thus, $h$ is surjective.
• 📝 Conclusion: $h$ is surjective but not injective.

4. A Rational Function

Let $f: \mathbb{R} \setminus \{2\} \rightarrow \mathbb{R} \setminus \{0\}$ be defined by $f(x) = \frac{1}{x-2}$. Show that $f$ is bijective.

• 🔑 Injectivity: Suppose $f(x_1) = f(x_2)$. Then $\frac{1}{x_1 - 2} = \frac{1}{x_2 - 2}$. This implies $x_1 - 2 = x_2 - 2$, and therefore $x_1 = x_2$. So $f$ is injective.
• 🎯 Surjectivity: Let $y \in \mathbb{R} \setminus \{0\}$. We need to find an $x \in \mathbb{R} \setminus \{2\}$ such that $f(x) = y$. That is, $\frac{1}{x-2} = y$. Solving for $x$, we get $x - 2 = \frac{1}{y}$, so $x = \frac{1}{y} + 2$. Since $y \neq 0$, $x$ is well-defined. Also, since $y \neq 0$, $x = \frac{1}{y} + 2 \neq 2$. Thus, for every $y \in \mathbb{R} \setminus \{0\}$, there exists an $x \in \mathbb{R} \setminus \{2\}$ such that $f(x) = y$. Therefore, $f$ is surjective.
• 🎉 Conclusion: Since $f$ is both injective and surjective, it is bijective.

5. Function Mapping Integers

Let $f: \mathbb{Z} \rightarrow \mathbb{Z}$ be defined by $f(n) = n + 5$. Show that $f$ is bijective.

• 🔑 Injectivity: Suppose $f(n_1) = f(n_2)$. Then $n_1 + 5 = n_2 + 5$. Subtracting 5 from both sides, we get $n_1 = n_2$. Thus, $f$ is injective.
• 🎯 Surjectivity: Let $m \in \mathbb{Z}$. We want to find an $n \in \mathbb{Z}$ such that $f(n) = m$. That is, $n + 5 = m$. Solving for $n$, we get $n = m - 5$. Since $m \in \mathbb{Z}$, $n$ is also in $\mathbb{Z}$. Thus, for every $m \in \mathbb{Z}$, there exists an $n \in \mathbb{Z}$ such that $f(n) = m$. Therefore, $f$ is surjective.
• 🎉 Conclusion: Since $f$ is both injective and surjective, it is bijective.

6. A Constant Function

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be defined by $f(x) = 5$. Show that $f$ is neither injective nor surjective.

• 💔 Not Injectivity: Consider $x_1 = 1$ and $x_2 = 2$. Then $f(1) = 5$ and $f(2) = 5$. Since $f(1) = f(2)$ but $1 \neq 2$, $f$ is not injective.
• 💔 Not Surjectivity: Consider $y = 6 \in \mathbb{R}$. There is no $x \in \mathbb{R}$ such that $f(x) = 6$, since $f(x)$ is always 5. Thus, $f$ is not surjective.
• 📝 Conclusion: $f$ is neither injective nor surjective.

7. Function Defined Piecewise

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be defined by $f(x) = \begin{cases} x & \text{if } x \geq 0 \\ x - 1 & \text{if } x < 0 \end{cases}$. Show if the function is injective and/or surjective.

• 🔑 Injectivity: Suppose $f(x_1) = f(x_2)$. We have three cases:
  1. Both $x_1, x_2 \geq 0$: Then $x_1 = x_2$.
  2. Both $x_1, x_2 < 0$: Then $x_1 - 1 = x_2 - 1$, so $x_1 = x_2$.
  3. $x_1 \geq 0$ and $x_2 < 0$: Then $f(x_1) = x_1 \geq 0$ and $f(x_2) = x_2 - 1 < -1$. Thus, $f(x_1) \neq f(x_2)$, a contradiction.
  Therefore, $f$ is injective.
• 🎯 Surjectivity: Let $y \in \mathbb{R}$.
  • If $y \geq 0$, then $x = y$ and $f(x) = y$.
  • If $y < 0$, then $x = y + 1 < 1$, and $f(x) = (y+1) - 1 = y$.
  Therefore, $f$ is surjective.
• 🎉 Conclusion: $f$ is bijective.

🔑 Conclusion

Understanding injectivity and surjectivity is crucial for grasping deeper concepts in mathematics. By understanding the fundamental principles and practicing with various examples, you can master these concepts. Keep practicing, and you'll become more comfortable with these types of proofs! Good luck! 👍