Bijections

Definition of Bijections

Basic Concept

Bijection: function f: A → B that is both injective and surjective. One-to-one correspondence between domain A and codomain B. Every element of A maps uniquely to an element of B, and every element of B is image of exactly one element in A.

Formal Definition

Function f: A → B is bijection if ∀b ∈ B, ∃!a ∈ A such that f(a) = b. Here "∃!" denotes existence and uniqueness.

Notation

Bijection often denoted as f: A ↔ B or f: A ⇄ B to emphasize invertibility.

Injective Functions (One-to-One)

Definition

Injective function f: A → B satisfies ∀a1, a2 ∈ A, f(a1) = f(a2) ⇒ a1 = a2. No two distinct elements of A map to the same element of B.

Implications

Ensures uniqueness in mapping from domain to codomain. Injective functions preserve distinctness.

Examples

f(x) = 2x on integers; identity function id(x) = x; inclusion maps.

Surjective Functions (Onto)

Definition

Surjective function f: A → B satisfies ∀b ∈ B, ∃a ∈ A such that f(a) = b. Every element of codomain B is "hit" by some element of domain A.

Implications

Codomain equals image of function. Surjections cover entire codomain.

Examples

f(x) = x³ on real numbers; floor function from reals to integers is surjective but not injective.

Properties of Bijections

Invertibility

Bijections have unique inverses. f⁻¹: B → A satisfies f⁻¹(f(a)) = a and f(f⁻¹(b)) = b.

Cardinality Preservation

Bijection implies |A| = |B| (same cardinality). Used to define equal sizes of infinite sets.

Composition Closure

Composition of bijections is a bijection. If f: A → B and g: B → C are bijections, then g∘f: A → C is bijection.

Identity Function

Identity function id: A → A is trivially bijection.

Inverse Functions

Definition

Inverse of bijection f: A → B is function f⁻¹: B → A with f⁻¹(f(a)) = a and f(f⁻¹(b)) = b.

Existence Condition

Inverse exists if and only if f is bijection.

Construction

Mapping b back to unique a such that f(a) = b.

Properties

Inverse of inverse is original function: (f⁻¹)⁻¹ = f.

f: A → B (bijection)f⁻¹: B → A (inverse)f⁻¹ ∘ f = id_Af ∘ f⁻¹ = id_B

Examples of Bijections

Finite Sets

f: {1,2,3} → {a,b,c} with f(1)=a, f(2)=b, f(3)=c is bijection.

Real-Valued Functions

f(x) = x + 1 on ℝ is bijection. Inverse: f⁻¹(x) = x - 1.

Permutation

Permutation of finite set is bijection from set to itself.

Infinite Sets

f: ℕ → 2ℕ defined by f(n) = 2n is bijection between natural numbers and even numbers.

Role in Discrete Mathematics

Counting and Combinatorics

Bijections used to count sets by establishing one-to-one correspondences.

Equivalence Relations

Bijections relate equivalence classes and quotient sets.

Graph Theory

Bijections between vertex sets illustrate isomorphisms of graphs.

Set Theory

Defines equal cardinalities; distinguishes countable vs uncountable sets.

Composition of Bijections

Definition

Given bijections f: A → B and g: B → C, composition g∘f: A → C defined by (g∘f)(a) = g(f(a)).

Properties

Composition of bijections is bijection. Inverse: (g∘f)⁻¹ = f⁻¹ ∘ g⁻¹.

Associativity

Composition is associative: h∘(g∘f) = (h∘g)∘f.

Identity Element

Identity function acts as neutral element under composition.

Given:f: A → B (bijection)g: B → C (bijection)Then:(g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹

Bijections and Cardinality

Finite Sets

Bijection existence ⇔ equal cardinality. |A| = |B| if bijection f: A → B exists.

Infinite Sets

Bijections used to compare infinite cardinalities (countable vs uncountable sets).

Countability

Set is countably infinite if bijection with ℕ exists.

Uncountability

No bijection exists between ℕ and real interval [0,1] (Cantor's diagonal argument).

Matrix Representation of Bijections

Functions as Matrices

When domain and codomain finite and ordered, function can be represented by matrix M where M[i,j] = 1 if f(a_i) = b_j, else 0.

Bijection Matrix

Matrix representing bijection is a permutation matrix: exactly one 1 in each row and column, else 0.

Properties

Permutation matrices are invertible, inverse is transpose.

Example

Permutation of set {1,2,3} represented as

 1 2 31 0 1 02 0 0 13 1 0 0

Applications of Bijections

Cryptography

Bijections used in encryption algorithms for reversible mappings.

Combinatorics

Counting techniques rely on bijections to simplify enumeration.

Computer Science

Data encoding, hashing, reversible computations modeled by bijections.

Algebra

Isomorphisms between algebraic structures are bijections preserving operations.

Common Misconceptions

Bijection vs Injection

Injection alone does not guarantee surjectivity; bijection requires both.

Bijection vs Surjection

Surjection alone does not guarantee injection; bijection requires both.

Inverse Existence

Inverse function exists only if function is bijection, not otherwise.

Cardinality Confusion

Equal cardinality requires bijection; partial functions or injections insufficient.

References

• Rosen, K. H., Discrete Mathematics and Its Applications, 7th ed., McGraw-Hill, 2012, pp. 85-110.
• Enderton, H. B., Elements of Set Theory, Academic Press, 1977, pp. 45-60.
• Halmos, P. R., Naive Set Theory, Springer, 1974, pp. 21-40.
• Epp, S. S., Discrete Mathematics with Applications, 4th ed., Brooks Cole, 2011, pp. 130-150.
• Grimaldi, R. P., Discrete and Combinatorial Mathematics: An Applied Introduction, 5th ed., Pearson, 2003, pp. 95-120.