Proof by Contradiction
Enroll to start learning
You’ve not yet enrolled in this course. Please enroll for free to listen to audio lessons, classroom podcasts and take practice test.
Interactive Audio Lesson
Listen to a student-teacher conversation explaining the topic in a relatable way.
Introduction to Countable and Uncountable Sets
🔒 Unlock Audio Lesson
Sign up and enroll to listen to this audio lesson
Today we're diving into countable and uncountable sets. Who can tell me the difference between a countably infinite set and an uncountable set?
A countably infinite set is one that can be listed like the natural numbers, right?
Exactly! Countable sets can be put in one-to-one correspondence with the natural numbers. Now, what about uncountable sets?
Uncountable sets can't be listed in that way. For example, the real numbers...
Correct! And today, we'll see how Cantor's diagonalization argument illustrates this concept using infinite binary strings.
Cantor's Diagonalization Argument
🔒 Unlock Audio Lesson
Sign up and enroll to listen to this audio lesson
Let's explore Cantor's diagonalization argument. Suppose we assume the set of infinite binary strings is countable. What would this mean?
It would mean we can list all the binary strings in a sequence.
Exactly! So let's denote them as r_1, r_2, r_3, ... What happens when we take the diagonal bits and flip them?
We create a new binary string that shouldn't be in the original sequence!
Good point! Since this new string differs from every string in our assumed list, we reach a contradiction. Thus, can we still say the original set is countable?
No, it has to be uncountable.
Differences Between Finite and Infinite Sets
🔒 Unlock Audio Lesson
Sign up and enroll to listen to this audio lesson
Now let's contrast finite binary strings with infinite ones. What's the key difference?
Finite strings have a definite end, while infinite strings do not.
Exactly! Since every finite string must have an end, we can list them, making the set countable. What about integers or rational numbers; can we use the Cantor argument on them?
No, because they're also countable sets!
Right! Cantor's argument showcases the uniqueness of infinite strings in demonstrating uncountability.
Introduction & Overview
Read summaries of the section's main ideas at different levels of detail.
Quick Overview
Standard
The section explains Cantor's diagonalization argument and how it proves that the set of infinite binary strings is uncountable by assuming the opposite and showcasing a missing element. Key distinctions between finite and infinite sets are also emphasized.
Detailed
Proof by Contradiction
In this section, we explore the concept of proof by contradiction through Cantor’s diagonalization argument. The focus is on demonstrating that the set of all infinite binary strings, denoted by {0, 1}^∞, is uncountable. We begin by recalling that previously discussed sets such as the integers and rational numbers were countably infinite; however, it is essential to recognize that infinite binary strings differ in cardinality.
To start, we assume that the set of infinite binary strings is countable, which implies that we can list its elements as r_1, r_2, r_3, ..., in sequence. Each string in this list has an infinite number of bits. Now, we construct a new string by taking the diagonal bits from the sequence and flipping (complementing) each bit of the diagonal string. This newly generated string cannot belong to the original sequence since it differs in at least one position from every string in the list. This leads to a contradiction; therefore, our initial assumption that the set is countable must be false, indicating that the set of infinite binary strings is indeed uncountable. The section also briefly touches on why the same argument fails for finite binary strings as well as integers and rational numbers, clarifying the unique nature of the infinite set.
Youtube Videos
Audio Book
Dive deep into the subject with an immersive audiobook experience.
Assumption of Countability
Chapter 1 of 4
🔒 Unlock Audio Chapter
Sign up and enroll to access the full audio experience
Chapter Content
So we begin with our first set namely set of all binary strings but of infinite length. And this set ∞ is denoted by this notation {0, 1} . So; some examples of binary strings of infinite length if I consider the string x equal to 0 0 0 0 and the sequence of 0’s which never ends then that is a binary string whose length is infinite.
Detailed Explanation
We start by defining what we mean by binary strings of infinite length. This means that there can be strings composed of the digits 0 and 1 that never end. An example of such a binary string is a sequence of 0's that goes on forever. We denote the set of all these infinite binary strings as {0, 1}∞. Understanding this concept is crucial for the next steps.
Examples & Analogies
Imagine writing a never-ending story where you could only use two words: 'yes' and 'no'. If you keep adding to this story without ever stopping, you create an infinite binary string. Just like in our analogy, the story can never truly be finished; there are always more words (0's or 1's) to add.
Contradictory Assumption
Chapter 2 of 4
🔒 Unlock Audio Chapter
Sign up and enroll to access the full audio experience
Chapter Content
So we are supposed to prove that this set is an uncountable set. But we believe the contrary, we assume the contrary and we assume that the set is countable and if it is countable then it must be having a sequencing of elements of the set.
Detailed Explanation
Here, we assume for the sake of argument that the set of all infinite binary strings can be arranged into a sequence. If this set were countable, we would be able to list all elements like r1, r2, r3, etc. This assumption sets the stage to reach a contradiction.
Examples & Analogies
Think of a library where you suppose every book in the library can be arranged neatly on shelves. You are convinced all books can fit in, but then you discover a new valuable book that hasn't been placed on any shelf, creating a contradiction to your initial claim.
Diagonal Argument Construction
Chapter 3 of 4
🔒 Unlock Audio Chapter
Sign up and enroll to access the full audio experience
Chapter Content
I will show that there exist at least 1 string which is of infinite length and which is binary and which is not in the sequence of binary strings that we are assuming exists. So what, exactly that string? So you consider the binary string r which is obtained by focusing on the bits along the diagonal here.
Detailed Explanation
Using Cantor's diagonal argument, we identify a new binary string by examining the diagonal bits from the assumed sequence. For instance, if the first string starts with a 0, we can take another digit that is the opposite (1), and we repeat this for each subsequent string, creating a new binary string that is guaranteed to differ from each string in the original list in at least one position.
Examples & Analogies
Imagine a class of students where you write down each student's name and their favorite number from 1 to 10. If a student named Alex says their favorite number is the second student's favorite plus one, this ensures Alex's favorite differs from one listed before, just like our diagonal construction ensures our new string isn't found in the earlier sequence.
Final Contradiction and Conclusion
Chapter 4 of 4
🔒 Unlock Audio Chapter
Sign up and enroll to access the full audio experience
Chapter Content
Now my claim is that the string r which I have constructed here which I am considering here will be different from all the string r , r , r , r and so on in the sequencing which I am assuming to exist.
Detailed Explanation
Now, we show that the constructed string r, which we derived from the diagonal method, is not in the original sequence of binary strings. This implies that there is at least one infinite binary string that is missing from our sequenced list. Since we found a string that cannot belong to the assumed list, this contradicts our original assumption that the set is countable.
Examples & Analogies
Imagine concluding a race where you have declared all runners' positions, but then a new runner arrives who matches none. The appearance of this new runner breaks your initial declaration of being able to list all participants, illustrating how our initial assumption about countability fails.
Key Concepts
-
Cantor's Diagonalization Argument: A method to demonstrate that some sets are uncountable by showing that a new element cannot be part of any proposed list of that set.
-
Difference between Countably Infinite and Uncountably Infinite Sets: Countable sets can be enumerated while uncountable sets cannot.
Examples & Applications
The set of natural numbers is countable, while the set of all binary strings of infinite length is uncountable.
If we list out the numbers 1, 2, 3... we can define that set; however, no such listing exists for all infinite binary strings.
Memory Aids
Interactive tools to help you remember key concepts
Rhymes
Countable sets can be listed, one to one, / But uncountable sets just cannot be done.
Stories
Imagine trying to catch infinity in a net; you can scoop up finite fish, but uncountable ones just won't get.
Memory Tools
Remember: 'List' stands for Countable, 'Mist' stands for Uncountable. If it's missing from your list, it’s uncountable!
Acronyms
C.U.B.
Countable - Usable
Binary - not. Reflects that only certain structures can be enumerated.
Flash Cards
Glossary
- Countable Set
A set that can be listed in a sequence or has the same cardinality as the set of natural numbers.
- Uncountable Set
A set that cannot be listed in a sequence and has a greater cardinality than the set of natural numbers.
- Cantor's Diagonalization Argument
A method used to show that certain infinite sets are uncountable, by constructing a new element that differs from all elements in a given list.
Reference links
Supplementary resources to enhance your learning experience.