Table of Contents
In mathematics, understanding whether two sets have the same cardinality is fundamental in set theory. Cardinality measures the “size” of a set, especially when dealing with infinite sets. Proving that two sets have the same cardinality involves demonstrating a specific type of relationship called a bijection.
What Is Cardinality?
The cardinality of a set is a way to compare the sizes of sets. For finite sets, it is simply the number of elements. For infinite sets, mathematicians use the concept of bijections to compare their sizes.
How to Prove Two Sets Have the Same Cardinality
The main method to prove two sets, A and B, have the same cardinality is to find a bijection between them. A bijection is a function that is both injective (one-to-one) and surjective (onto). This means each element of set A pairs with exactly one element of set B, and every element of B is paired with some element of A.
Steps to Establish a Bijection
- Define a function f: A → B.
- Show that f is injective: no two different elements in A map to the same element in B.
- Show that f is surjective: every element in B has a pre-image in A.
If such a function exists, then sets A and B have the same cardinality. If no such function can be found, the sets may have different sizes.
Examples
For example, consider the set of natural numbers N = {0, 1, 2, 3, …} and the set of even natural numbers E = {0, 2, 4, 6, …}. A simple bijection is the function f(n) = 2n. This function is both injective and surjective, demonstrating that N and E have the same cardinality, even though E appears “smaller”.
Summary
To prove two sets have the same cardinality, find a bijection between them. This approach works for both finite and infinite sets and is a cornerstone of set theory. Understanding this concept helps clarify the nature of infinity and the sizes of different sets.