Statement and Proof of Cantors Theorem with Examples
If there is a bijection between two sets, they have the same number of elements (are equinumerous, or have the same cardinality). Arrangements: A mapping, also known as a function, is a rule that associates elements from one set with elements from another. This is how we write it: f : X → Y , f is referred to as the function/mapping, the set X is referred to as the domain, and Y is referred to as the codomain. We specify the rule by writing f(x) =y or f : x 7→ y. e.g. X = {1, 2, 3}, Y = {2, 4, 6}, the map f(x) = 2x associates each element x ∈ X with the element in Y which means to double it.
In this article we are going to discuss cantor's intersection theorem, state and prove cantor's theorem, cantor's theorem proof.
A bijection is a mapping that is injective as well as surjective.
Injective (one-to-one): A function is injective if it takes each element of the domain and applies it to no more than one element of the codomain. It never maps more than one domain element to the same codomain element. Formally, if f is known to be a function between namely set X as well as set Y , then f is injective iff ∀a, b ∈ X, f(a) = f(b) → a = b
Surjective (onto): If a function maps something onto every element of the codomain, it is surjective. It can map multiple things to the same element in the codomain, but it must hit every element in the codomain.Formally, if f is known to be a function between set X and set Y , then f is surjective (if and only if) iff ∀y ∈ Y, ∃x ∈ X, f(x) = y
The Heine-Cantor theorem The cardinality of any set A is strictly less than the cardinality of A's power set : |A| < |P(A)|
Proof: To prove this, we will show (1) that |A| ≤ |P(A)| and then (2) that ¬(|A| = |P(A)|). This is equivalent to the strictly less than phrasing in the statement of the given theorem. (1) |A| ≤ |P(A)| : Now , to show this, we just need to produce a bijection between A as well as a subset of P(A). Then we'll know A is the same size as that subset, which cannot be larger than P. (A).
Consider the set E = {{x} : x ∈ A}, the set of all single-element subsets of A. Clearly E ⊂ P(A), because it is made up of various subsets of A. Incidentally, it is a proper subset, since we know it doesn’t contain ∅.
The map g : A → E defined by g(x) = {x} is one-to-one and onto. How do we know this? (This is laboured, but useful to be certain that you understand this!)
One-to-one: Let’s suppose we have x, y ∈ A and g(x) = g(y). Then by the definition of injectiveness above, we want to be sure that this means x = y, if g is going to be one-to-one. g(x) = {x} and g(y) = {y}, so, g(x) = g(y) means {x} = {y}. These two one-element sets can only be equal if their members are equal, so x = y. Therefore g is one-to-one.
Onto: Is it true that ∀y ∈ E, ∃x ∈ A, g(x) = y? Yes. We know that E = {{x} : x ∈ A} so ∀y ∈ E, ∃x ∈ A such that y = {x}. And that is because each element of E just is a set with an element from A as its sole member. And since g(x) = {x}, we have ∀y ∈ E, ∃x ∈ A, g(x) = y, so g is surjective.
Therefore |A| = |E| ≤ |P(A)| .
Importance of Cantor's Theorem
Cantor's theorem had immediate and significant implications for mathematics philosophy. For example, taking the power set of an infinite set iteratively and applying Cantor's theorem yields an infinite hierarchy of infinite cardinals, each strictly larger than the one before it.
Cantor was successful in demonstrating that the cardinality of the power set is strictly greater than that of the set for all sets, including infinite sets. (In fact, the cardinality of the Reals is the same as the cardinality of the Integers' power set.) As a result, the power set of the Reals is larger than that of the reals.
FAQs on Cantors Theorem and the Power Set Principle
1. What is Cantor’s Theorem?
Cantor’s Theorem states that for any set A, the power set of A has strictly greater cardinality than A itself. In symbols, |A| < |P(A)|, where P(A) is the set of all subsets of A.
- This means no set can have the same size as its power set.
- The theorem applies to both finite and infinite sets.
- It is a fundamental result in set theory and the study of infinite cardinalities.
2. What is the power set in Cantor’s Theorem?
The power set of a set A, denoted P(A), is the set of all possible subsets of A.
- If A = {1, 2}, then P(A) = {∅, {1}, {2}, {1,2}}.
- If A has n elements (finite), then |P(A)| = 2ⁿ.
- For infinite sets, the power set is always strictly larger than the original set by Cantor’s Theorem.
3. Why is the power set always larger than the original set?
The power set is always larger because no function from a set A to P(A) can be onto (surjective), which proves |A| < |P(A)|.
- Cantor’s diagonal argument constructs a subset not in the image of any proposed function.
- This guarantees at least one subset is "missing."
- Therefore, a one-to-one correspondence between A and P(A) is impossible.
4. What is Cantor’s diagonal argument?
Cantor’s diagonal argument is a proof technique showing that certain sets, like the real numbers, are uncountable.
- Assume all elements are listed in a sequence.
- Construct a new element by changing the nth digit of the nth entry.
- This new element differs from every listed element, creating a contradiction.
5. Does Cantor’s Theorem apply to infinite sets?
Yes, Cantor’s Theorem applies to both finite and infinite sets, and it shows that infinite sets also have strictly larger power sets.
- For example, the set of natural numbers ℕ is infinite.
- Its power set P(ℕ) has greater cardinality than ℕ.
- This leads to different "sizes" of infinity, such as ℵ₀ and larger cardinal numbers.
6. What is the cardinality result of Cantor’s Theorem?
The cardinality result of Cantor’s Theorem is that |P(A)| = 2^{|A|} and this is strictly greater than |A|.
- If |A| = n (finite), then |P(A)| = 2ⁿ.
- If |A| = ℵ₀ (countably infinite), then |P(A)| = 2^{ℵ₀}, which is uncountable.
- This establishes a hierarchy of infinite cardinal numbers.
7. How does Cantor’s Theorem prove that real numbers are uncountable?
Cantor’s Theorem implies that the set of real numbers has the same size as P(ℕ), which is strictly larger than ℕ.
- The interval (0,1) can be put in one-to-one correspondence with subsets of ℕ.
- Since |P(ℕ)| > |ℕ|, the real numbers cannot be countable.
- Thus, the set of real numbers is uncountable.
8. What is a simple example illustrating Cantor’s Theorem?
A simple example is the set A = {a, b}, whose power set has more elements than A.
- A has 2 elements.
- P(A) = {∅, {a}, {b}, {a,b}} has 4 elements.
- Since 4 > 2, we see that |P(A)| > |A|.
9. What is the difference between countable and uncountable sets in Cantor’s Theorem?
A set is countable if it can be put in one-to-one correspondence with ℕ, and uncountable if it cannot.
- ℕ (natural numbers) is countable.
- P(ℕ) and ℝ (real numbers) are uncountable.
- Cantor’s Theorem guarantees that P(A) is always strictly larger, often making it uncountable if A is infinite.
10. Why is Cantor’s Theorem important in mathematics?
Cantor’s Theorem is important because it establishes that there are different sizes of infinity and forms the foundation of modern set theory.
- It introduced the concept of cardinality for infinite sets.
- It proved that not all infinities are equal.
- It plays a key role in logic, real analysis, and the theory of infinite sets.
