Proving Bijection Between Two Sets: A Comprehensive Guide

In mathematics, particularly in set theory, proving a bijection between two sets A and B is a fundamental concept. A bijection is a function that is both injective (one-to-one) and surjective (onto). This article will guide you through the process step-by-step with detailed explanations and examples.

Understanding the Basics of Bijection

To prove that there is a bijection between two sets A and B, you must show that there exists a function f: A to B that is both injective and surjective.

Injective (One-to-One) Function

A function f is injective if for every pair of elements a_1, a_2 in A, fa_1 fa_2 implies a_1 a_2. This means that different elements in A are mapped to different elements in B.

Surjective (Onto) Function

A function f is surjective if for every element b in B, there exists at least one element a in A such that fa b. This means that every element in B is covered by the function.

Step-by-Step Process of Proving Bijection

1. Define the Function

The first step is to define the function f: A to B. Clearly specify how elements from set A are mapped to set B.

2. Prove Injectivity

To prove that f is injective, follow these steps:

Assume fa_1 fa_2 for a_1, a_2 in A and show that this implies a_1 a_2.

Here is an example to illustrate the technique:

Assume fa_1 fa_2. Since the function is defined such that fa_1 4, fa_2 5, and fa_3 6, we know that if fa_1 fa_2, then fa_1 must be one of these values. If these values are unique, then a_1 a_2.

3. Prove Surjectivity

To prove that f is surjective, follow these steps:

Take an arbitrary element b in B. Show that there exists an element a in A such that fa b.

Here is an example to illustrate the technique:

Let Y {4, 5, 6} and X {1, 2, 3}, with the function f: X to Y defined as f(1) 4, f(2) 5, f(3) 6. For b 4, select a 1 such that f(1) 4. For b 5, select a 2 such that f(2) 5. For b 6, select a 3 such that f(3) 6.

4. Conclude Bijection

If both injectivity and surjectivity are proven, then f is a bijection. This means there is a one-to-one correspondence between the elements of sets A and B.

Example Verification

Using the previous example, let A {1, 2, 3} and B {4, 5, 6}, and define the function f: A to B by f(1) 4, f(2) 5, and f(3) 6.

Injectivity

Assume fa_1 fa_2. Since each output corresponds to a unique input, if fa_1 4 and fa_2 4, then a_1 1 and a_2 1. Similarly, for 5 and 6, a_1 2 and a_2 2, and a_1 3 and a_2 3. Hence, fa_1 fa_2 implies a_1 a_2.

Surjectivity

For each b in B: If b 4, then a 1 such that f(1) 4. If b 5, then a 2 such that f(2) 5. If b 6, then a 3 such that f(3) 6.

Hence, every element in B is covered by the function.

Conclusion

Since both conditions are satisfied, the function f is a bijection between sets A and B.