Bijective Relation (One-to-One Correspondence)

We call a relation or function bijective if it is both injective and surjective. This means that each input corresponds to exactly one output, and each output is connected to exactly one input.

Formal Definition

Let f: A → B be a mapping. f is bijective if:

• Injective: ∀a₁,a₂ ∈ A, f(a₁) = f(a₂) ⇒ a₁ = a₂.
• Surjective: ∀b ∈ B, ∃a ∈ A: f(a) = b.

In other words, the function provides a one-to-one and complete coverage between the two sets.

Examples of Bijective Relations

• The function f(x) = x + 1 on integers: each integer corresponds to exactly one other integer, and every integer is reachable.
• Personal ID numbers assigned to people: each person has a unique number, and each number corresponds to exactly one person.
• One-to-one correspondence between the letters of the English alphabet and the first 26 letters of the Hungarian alphabet.

Counterexamples (Non-Bijective Relations)

• The function f(x) = x² on real numbers: not injective, because f(2) = f(-2).
• The relation between countries and cities: not surjective, because many cities are not capitals.
• The relation between people and their hair color: not injective, because multiple people can have the same hair color.

Connection to One-to-One Correspondence

A bijection is also known as a one-to-one correspondence. This is crucial in mathematics because it allows us to pair elements of two sets one-to-one and thus determine that they have the same number of elements. Bijective functions also form the basis of isomorphisms between different structures.

Summary

The essence of a bijective relation is that each input corresponds to exactly one output, and each output is connected to exactly one input. This one-to-one and complete mapping is an extremely important concept in both mathematics and computer science.

Practice Exercise