Enrol to start learning
Reading is open to everyone. Enrolling is free, and it is what unlocks the audio lessons, practice tests and progress tracking.
7.2. Proof by Contradiction
Learn content
Interactive Audio Lesson
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Today, we will explore Cantor's theorem, which tells us something fascinating about the sizes of sets, particularly infinite sets. Can anyone tell me what they think a power set is?
Isn't a power set the set of all possible subsets of a given set?
Exactly! If we have a set A, the power set, denoted P(A), includes every possible subset of A, including the empty set and A itself. Now, what do you think we mean when we talk about cardinality?
I think cardinality is about how many elements are in a set.
Correct! Cardinality refers to the number of elements in a set. Cantor's theorem states that the cardinality of the set A is strictly less than the cardinality of its power set P(A).
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Let's talk about how we can prove Cantor's theorem using contradiction. What does it mean to prove something by contradiction?
I think it means you assume the opposite of what you want to prove and show that it leads to a contradiction.
Exactly! If we assume that the cardinality of A is greater than or equal to the cardinality of P(A), we then must have a surjective function from A to P(A).
But how do we show that such a function can't exist?
Great question! We can construct a specific subset, S, that challenges the existence of this surjective function by using the diagonal argument.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Let's focus on constructing the set S. We will use the values in our surjective function's output, represented in a table. How do we flip the entries to form S?
If the entry for xi is 0, we would include xi in S, right? And if it's 1, we wouldn't include it.
That's correct! For every diagonal entry, we flip it: if it's 0, we include that element in S; if it's 1, we exclude it. This ensures that S will differ from every f(xi)!
Wait, so S can't equal any f(xi)?
Precisely! This leads us to conclude that S lacks a pre-image under f, contradicting the assumption that f is surjective.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
What do you think the implications of Cantor's theorem are? Why is it so significant?
It shows that not all infinities are the same; there are different sizes of infinity!
Exactly! By applying Cantor's theorem to the natural numbers, we find their cardinality is less than that of their power set. This means that infinitely many subsets exist, leading to uncountable infinities.
So there is an infinite hierarchy of infinities?
Yes! This introduces a fascinating world where different infinities coexist, defying our intuitive understanding of infinity.
Overview
Short Summary
Cantor's theorem demonstrates that the cardinality of any set A is strictly less than the cardinality of its power set P(A), using proof by contradiction.
Medium Summary
In this section, we explore Cantor's theorem through proof by contradiction, demonstrating that no surjective function exists from a set A to its power set P(A). This leads to the significant conclusion that there are infinitely many different sizes of infinity.
Detailed Summary
Detailed Summary
In this section, the central focus is Cantor's theorem, which states that for any set A, the cardinality of A is strictly less than the cardinality of its power set P(A). To prove this theorem, we utilize the method of proof by contradiction. Cantor begins by assuming that the cardinality of A is greater than or equal to that of P(A). According to a foundational fact in set theory, if set X has a greater or equal cardinality compared to set Y, then a surjective function must exist from X to Y.
Assuming there is such a surjective function f from A to P(A), we explore the implications of this assumption. By listing the elements of A (let's denote them as x1, x2, x3, ...), we can define corresponding subsets in the power set of A based on f. However, utilizing the diagonalization argument, we create a subset S that contradicts the existence of a surjective function f. S includes or excludes elements based on the entries along the diagonal of the table created by f, ensuring that S cannot be the image of any element of A.
Ultimately, this leads to the conclusion that the original assumption is invalid, confirming that the cardinality of set A is indeed strictly less than that of its power set P(A). As a significant implication, Cantor's theorem illustrates the existence of an infinite hierarchy of different sizes of infinity, demonstrating that infinite sets cannot all be considered equal. This theorem has far-reaching implications in mathematics, particularly in set theory and the understanding of cardinality.
Reference YouTube Videos
Audio Book
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountCantor proved a very interesting result as well. He showed that you take any set A then the cardinality of that set is strictly less than the cardinality of its power set. So remember the notation P(A) denotes the power set of A. Where the power set is the set of all subsets of that set. So of course this statement is true if your set of A is finite namely if your set A has n number of elements then its power set will have 2n elements. And we can always prove that n is always strictly less than 2n.
Detailed Explanation
Cantor's theorem states that for any set A, the number of elements in A (its cardinality) is less than the number of elements in its power set P(A), which includes all possible subsets of A. For a finite set with n elements, its power set contains 2^n subsets. Important to grasp here is that this relationship holds true regardless of whether A is finite or infinite.
Examples & Analogies
Think of a box of different colored balls as set A. If you have 3 balls, the power set includes all combinations of these balls (including combinations with no balls at all). There are 2^3 = 8 possible combinations in the power set, which is greater than the 3 original balls. This means there are always more ways to group the balls together than there are balls.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountWhat if A is an infinite set can we conclude that this theorem is true that is even for infinite set and Cantor showed yes, so the proof is again is contradiction and we will run the diagonalization argument here as well. So we will assume that: let the cardinality of the set A be greater than equal to the cardinality of its power set.
Detailed Explanation
Cantor's proof uses a technique called proof by contradiction. Here, we assume the opposite of what we want to prove: that the cardinality of set A is greater than or equal to the cardinality of its power set P(A). This leads us to derive a contradiction, implying that the original assumption must be false.
Examples & Analogies
Imagine you are in a library with a countable number of books (set A). Suppose you assume it is possible to list all the combinations of books in power sets (P(A)). Trying to prove this leads to contradictions, such as missing out on some combinations, showing that your assumption about having a finite list was wrong.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountThat means there will be some surjective function from the set A to the power of set of A. I do not know what exactly is the structure of the surjective function but I denote the surjective function by f. So now what I have done here is let the elements of A be x1, x2, x3 and so on.
Detailed Explanation
Assuming that there exists a surjective function f that maps every element of set A to the elements in its power set P(A). We denote elements in set A as x1, x2, x3,... Since we are assuming A is infinite, every xi leads to a corresponding subset in P(A). However, the defined properties of surjectivity will lead to contradictions.
Examples & Analogies
Think of a situation where you have a set of names (A) and every name tries to correspond to a unique set of jobs (P(A)). If you think you can match every possible job made from these names, you'll find jobs you can't match, showing gaps in your assumption of surjectivity.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountTo do that I will show that f actually does not exist and how do I show that f is does not exist? I have to show that f is actually not a valid surjective function. To do this, I will show a subset that belongs to the powerset which does not have any pre image.
Detailed Explanation
The diagonalization argument involves constructing a specific subset S of A that cannot be produced by the surjective function f. By examining the 'diagonal' entries of the function output, we create a subset that differs from every element mapped by f. This directly contradicts the surjectivity, proving that f cannot exist.
Examples & Analogies
Imagine again looking to create unique combinations of names for job applications where each name corresponds to a different application form (f). If during your selection you create a form that includes a combination of names none of which directly corresponds to a job, then you can't find a pre-existing match, exposing the flaws in your initial assumption.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountThis means indeed the statement in this theorem is the correct statement. So if I apply it over the set A being the set of positive integers or the set of natural number then I obtain the fact that the cardinality of the set of natural number is strictly less than the cardinality of its power set.
Detailed Explanation
After establishing that f cannot exist and therefore our initial assumption was wrong, we confirm Cantor’s theorem: the cardinality of any set is less than that of its power set. When applied to natural numbers, it reveals that there are multiple levels of infinity, such that the set of all subsets of natural numbers is uncountable.
Examples & Analogies
Think of a family tree where every generation represents a level of existence. The immediate family (natural numbers) has fewer members than the entire family tree (power set). Even if you keep expanding the tree forever, you'll always have more branches (subsets) than there are original family members, demonstrating multiple infinities.
--
Key concepts
Core takeaways and short definitions to help you quickly recall the key ideas from this section.
- Cantor's Theorem:
The cardinality of any set A is strictly less than the cardinality of its power set P(A).
- Proof by Contradiction:
A method of proving propositions by assuming the opposite and showing a contradiction.
- Diagonalization Argument:
A technique for constructing subsets in proofs that leads to contradictions about mappings.
Examples
Step-by-step examples to apply the section's ideas and test your understanding.
If the set A consists of the elements {1, 2}, then its power set P(A) will consist of the subsets {}, {1}, {2}, and {1, 2}. The cardinality of A is 2, while the cardinality of P(A) is 4.
For the set of natural numbers, applying Cantor's theorem shows that the power set of natural numbers is uncountable.
Memory aids
If you’ve a set A, and it’s rather large, its power set will expand, like a starship from Star Trek's charge.
Imagine a party where invitations were sent. If every subset had its own invite, the number of guests would grow exponentially, showing how the power set creates infinite possibilities.
Flash Cards
Glossary
Cardinality
The number of elements in a set.
Power Set (P(A))
The set of all subsets of a set A.
Surjective Function
A function f from set X to set Y such that for every element y in Y, there exists at least one element x in X with f(x) = y.
Diagonalization Argument
A method used in proof by contradiction, particularly in set theory, to demonstrate that a certain set cannot be mapped in a specific way.