Show That The Two Given Sets Have Equal Cardinality By Describing A Bijection From One To The Other.
Understanding how to determine whether two sets have the same cardinality is a fundamental concept in set theory and mathematics as a whole. When two sets are said to have equal cardinality, it means there exists a bijection—a one-to-one and onto function—between them. Constructing such a bijection provides a concrete proof that the two sets have the same number of elements, regardless of whether they are finite or infinite. This article offers a comprehensive guide to demonstrating the equality of the cardinalities of two sets through explicit bijections, supported by definitions, examples, and practical techniques.
---
Understanding Cardinality and Bijections
What Is Cardinality?
Cardinality is a measure of the "size" or number of elements of a set. For finite sets, the cardinality corresponds simply to the number of elements. For example, the set {1, 2, 3} has a cardinality of 3. For infinite sets, the concept extends through the notion of countability and uncountability:
- Countably Infinite Sets: Sets whose elements can be listed in a sequence (like natural numbers, integers, rational numbers). These have the same cardinality as the set of natural numbers, denoted ℵ₀ (aleph-null).
- Uncountably Infinite Sets: Sets that cannot be listed in a sequence, such as the set of real numbers between 0 and 1. These sets have a larger cardinality, such as the continuum ℂ.
Determining whether two sets have equal cardinality involves finding an explicit bijection between them, especially in the context of infinite sets.
What Is a Bijection?
A bijection is a function that is both:
- Injective (One-to-One): Each element of the domain maps to a unique element in the codomain; no two elements in the domain map to the same element in the codomain.
- Surjective (Onto): Every element of the codomain has a pre-image in the domain; the function covers the entire codomain.
Mathematically, a function \(f: A \to B\) is a bijection if:
- For all \(a1, a2 \in A\), if \(f(a1) = f(a2)\), then \(a1 = a2\).
- For every \(b \in B\), there exists an \(a \in A\) such that \(f(a) = b\).
When such a bijection exists, sets \(A\) and \(B\) are said to have equal cardinality: \(|A| = |B|\).
---
Strategies for Demonstrating Equal Cardinality via Bijections
Constructing a bijection between two sets can sometimes be straightforward, especially when dealing with finite sets, but it can be more challenging in the case of infinite sets. Here are general strategies:
1. Direct Construction of a Bijection
- When possible, explicitly define a function \(f: A \to B\) that pairs elements of \(A\) with elements of \(B\).
- Verify the function is both injective and surjective.
- This approach provides a concrete proof of equal cardinality.
2. Use of Known Bijections or Isomorphisms
- Leverage existing bijections between familiar sets (e.g., \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{Q}\), \(\mathbb{R}\)).
- For example, the set of integers \(\mathbb{Z}\) is bijective with the natural numbers \(\mathbb{N}\), demonstrating they have the same cardinality.
3. Establishing Countability
- Show that a set is countable by constructing a bijection with \(\mathbb{N}\).
- For uncountable sets, demonstrate that no such bijection exists (not the focus here; instead, we focus on constructing bijections when possible).
4. Using Set Operations and Decompositions
- Break complicated sets into simpler components for which bijections are known or easier to construct.
- Use union, intersection, or Cartesian product to build bijections from simpler bijections.
Examples of Showing Sets Have Equal Cardinality via Bijections
Example 1: Finite Sets
Suppose \(A = \{a, b, c\}\) and \(B = \{1, 2, 3\}\). To show \(|A| = |B|\), define the function:
\[
f: A \to B, \quad f(a) = 1, \quad f(b) = 2, \quad f(c) = 3
\]
This is clearly a bijection because:
- Injective: No two elements of \(A\) map to the same element in \(B\).
- Surjective: Every element in \(B\) is mapped from some element in \(A\).
Hence, \(|A| = |B| = 3\).
---
Example 2: Countably Infinite Sets
Sets: \(\mathbb{N}\) (natural numbers) and \(\mathbb{Z}\) (integers).
Goal: Show \(\mathbb{Z}\) has the same cardinality as \(\mathbb{N}\).
Bijection Construction:
Define \(f: \mathbb{N} \to \mathbb{Z}\) as:
\[
f(n) =
\begin{cases}
\frac{n}{2}, & \text{if } n \text{ is even} \\
-\frac{n-1}{2}, & \text{if } n \text{ is odd}
\end{cases}
\]
Verification:
- For \(n = 1\), \(f(1) = -0 = 0\).
- For \(n = 2\), \(f(2) = 1\).
- For \(n = 3\), \(f(3) = -1\).
- For \(n = 4\), \(f(4) = 2\).
- And so on.
This function is:
- Injective: Different \(n\) produce different integers.
- Surjective: Every integer \(z \in \mathbb{Z}\) is obtained for some \(n\).
Thus, \(\mathbb{N} \sim \mathbb{Z}\).
---
Example 3: Rational Numbers and Natural Numbers
The set of rational numbers \(\mathbb{Q}\) is countable, despite seeming more complex.
Construction:
- List all rational numbers in a systematic way (e.g., using a diagonal argument).
- Map each rational number to a unique natural number.
This process involves creating a bijection between \(\mathbb{Q}\) and \(\mathbb{N}\), demonstrating their equal cardinality.
---
Dealing with Infinite Sets: Common Techniques
Constructing bijections between infinite sets often involves clever enumeration or pairing strategies.
Diagonalization Method
- Used famously by Cantor to prove \(\mathbb{R}\) is uncountable.
- For countable sets, a similar enumeration approach can be used to list elements systematically.
Pairing Elements
- For sets like \(\mathbb{N} \times \mathbb{N}\), define bijections with \(\mathbb{N}\) by pairing elements (e.g., Cantor pairing function).
- Example:
which maps pairs of natural numbers to a single natural number bijectively.
Function Construction via Patterned Mappings
- Establish rules to map elements based on their position or properties.
Key Theorems and Results in Set Cardinality
- Schroeder-Bernstein Theorem: If there exist injective functions \(f: A \to B\) and \(g: B \to A\), then there exists a bijection \(h: A \to B\). This is crucial because sometimes establishing injections is easier than direct bijections.
- Countability and Bijections: Sets are countable if and only if there exists a bijection with \(\mathbb{N}\).
- Equivalence of Infinite Cardinalities: Demonstrates that different infinite sets can have the same cardinality via explicit bijections.
Practical Tips for Constructing Bijections
- Start with Known Bijections: Use familiar mappings between common sets.
- Decompose Complex Sets: Break down complicated sets into simpler components with known bijections.
- Use Pairing Functions: For Cartesian products, pairing functions like Cantor's provide an explicit bijection.
- Check Both Conditions: Confirm that the function is injective and surjective through careful proofs.
- Leverage Symmetries: Symmetries and patterns
