How To Prove Function Is Onto

How to Prove a Function is Onto (Surjective)

This article will guide you through understanding and proving whether a function is onto, also known as surjective. Understanding onto functions is crucial in various areas of mathematics, particularly within set theory and abstract algebra. This guide provides clear explanations, examples, and strategies to help you master this concept.

What does it mean for a function to be onto?

A function f: A → B is onto (or surjective) if every element in the codomain B is mapped to by at least one element in the domain A. In simpler terms, for every element 'b' in B, there exists at least one element 'a' in A such that f(a) = b. The range of the function must equal the codomain. If even one element in the codomain is not mapped to, the function is not onto.

Methods for Proving a Function is Onto

There are several approaches to proving a function's surjectivity. The best method depends on the specific function and its complexity.

1. Direct Proof

This is the most straightforward method. It involves taking an arbitrary element from the codomain and showing that there exists an element in the domain that maps to it.

Steps:

1. Start with an arbitrary element: Let 'b' be an arbitrary element in the codomain B.
2. Solve for 'a': Solve the equation f(a) = b for 'a'. This will express 'a' in terms of 'b'.
3. Show 'a' is in the domain: Demonstrate that the value of 'a' you found belongs to the domain A.
4. Conclusion: Conclude that since you found an 'a' in A for any arbitrary 'b' in B, the function f is onto.

Example:

Let's prove that the function f: ℝ → ℝ defined by f(x) = 2x + 1 is onto.

1. Let 'b' be an arbitrary element in ℝ.
2. We need to solve f(a) = b, which means 2a + 1 = b. Solving for 'a', we get a = (b - 1)/2.
3. Since 'b' is a real number, (b - 1)/2 is also a real number. Therefore, 'a' belongs to the domain ℝ.
4. Thus, for every 'b' in ℝ, there exists an 'a' in ℝ such that f(a) = b. Therefore, f(x) = 2x + 1 is onto.

2. Proof by Contradiction

This method assumes the function is not onto and then demonstrates a contradiction.

Steps:

1. Assume the function is not onto: Assume there exists an element 'b' in B such that there is no 'a' in A with f(a) = b.
2. Derive a contradiction: Use the properties of the function and the sets A and B to show that this assumption leads to a contradiction (e.g., a violation of the function's definition or properties of the sets).
3. Conclusion: Since the assumption leads to a contradiction, the assumption must be false. Therefore, the function is onto.

3. Using Properties of the Function

Sometimes, the function's properties can directly demonstrate its surjectivity. For instance, if you can show the function is a bijection (both injective and surjective), then surjectivity is proven. Other specific function types might have inherent properties that guarantee surjectivity.

Common Mistakes to Avoid

• Confusing onto with one-to-one (injective): Onto refers to the codomain; one-to-one (injective) refers to whether distinct elements in the domain map to distinct elements in the codomain. They are distinct concepts.
• Not considering the entire codomain: You must show that every element in the codomain is mapped to, not just some elements.
• Failing to show 'a' is in the domain: Simply solving for 'a' isn't enough; you must verify that 'a' is a valid member of the domain A.

Conclusion

Proving a function is onto requires a rigorous approach. By understanding the definition and employing appropriate proof techniques, you can effectively demonstrate whether a given function maps to every element in its codomain. Remember to always clearly define your steps and justify each conclusion to create a robust and convincing proof.