--- Video Title: Are there Sets Bigger than the Natural Numbers? Description: Theory of Computation https://uvatoc.github.io 4.4: Are there Sets Bigger than the Natural Numbers? - | pow(S) | is greater than | S | - ...but proof only works for finite sets! David Evans and Nathan Brunelle University of Virginia --- Are there any sets that are bigger? When we talked about this last class, it seemed people's first reaction is it's obvious they're sets that are bigger. Many of you already are aware, and hopefully you've read in the book, that the real numbers are bigger. Now that we've seen this definition from data kind of what an infinite set is, now it should be really non-intuitive that there are sets that are bigger. Because if your definition of an infinite set is one whose cardinality is the same as a proper subset, that means you're adding elements to a set without increasing its cardinality. So once you've got the infinite, it seems like that's as far as you can go. Your definition is, you add an element, it doesn't change the cardinality. Intuition fails once we think about, well, we're not adding just elements one at a time. We're dealing with infinities here, so other strange things can happen. A power set is the set of all subsets of a set. The first theorem we want to prove is for any finite set. The cardinality of the power set is greater than the cardinality of the set. Do we think we can prove this? Yes. Yes. Good. Confidence. There's lots of ways that we could prove this. What's a really easy way to see this? For any set, the power set does include the empty set. What else does the power set also include? The set S. It does, right? It includes a set with all elements of S. That means we've got maybe at least one element in the power set. It contains the set of containing just each individual elements. Yeah, it contains all the singleton sets. For every element of S, the singleton set is in the power set. Every element by itself, there's a singleton set that contains just that element in the power set. So, we've got at least one more. This is N of them. This is the cardinality of A of them, plus one. Because it's also got the empty set. The name power set comes from it actually has two to that cardinality of A. For now, we only care about more. We don't care about the actual number. So, we know it's bigger. If we wanted to be really careful or have more practice with induction, we could prove this using induction. We're going to be doing induction over the natural numbers. The natural numbers are the sizes of the sets. Because we don't care about the actual elements, that covers all the sets, doing induction over the sizes of the sets. For the base case, we'll take size zero, the empty set. The power set contains one element. The set containing just the empty set. Satisfies the base case. The induction, we're going to assume that the property holds for the set of size M and show that it holds for the set of size M plus one. That proof is valid for finite sets. The question I want you to think about is, why does this not work to prove that this property also holds for infinite sets? I want you to think about which steps, and there's more than one, of this proof are invalid if we're claiming that we're not restricting it to finite sets. If we want to prove this now, instead of just for finite sets, we want to prove this for all sets, no restriction on them being finite. So including all the infinite sets. So which lines are wrong? The base case? Okay, what's wrong with the base case? The base case is on the empty set, which is a set. So there's nothing about saying a base case is for the empty set that's inherently wrong. And certainly it's true that that property holds for the empty set has size. The power set cardinality has size one, which is greater than the cardinality of empty set, which is zero. I think that's okay. Okay, good. Yeah. So there's something very wrong with this being an induction proof. The line there, it's also the problem here. We define the principle of induction based on the natural numbers. So we can't use it to prove things that are about infinite things. We can use it to prove about infinitely many natural numbers, but each one is still finite. Each one is bounded. So those things are wrong. Is there anything else that's wrong? Yeah. Yes. This, this is not true. This is only true for finite sets. And in fact, our definition of infinite sets is that these are sets where that's not true. So there's a lot broken. Yeah. How do we even know that's true for finite sets? Like, you know, intuitively I can feel it. How do we know? How do we know that adding an element increases the cardinality? Yeah. The way we define cardinality for finite sets, at least what the numbers mean, was the bijection between the set and the nk set. Natural numbers up to k minus one. If we add an element, that bijection now needs one extra number to match to it. To show that more formally, we have to say we're adding an element that's not in the set. But we had a set that already had a bijection to k. So we had our set that was a bijection to k, and that's how we're defining cardinality of the set, having a bijection to the set of natural numbers up to k. And now we've added some x that was not in the set. So this is x. It doesn't map. The bijection doesn't work anymore. Maybe that's not quite a formal enough proof without defining union more carefully and other things, but that should at least be pretty convincing that the cardinality is increased. So everything about induction doesn't work for infinite sets. We only define the principle of induction for the natural numbers. We have the principle of induction. It is only dealing with subsets of the natural numbers. This proof technique is not going to help us here. We don't have a principle of induction that works on any set. It only works on sets that are subsets of the natural numbers. It really doesn't work on the axis and a super-to-to-to-to. So it has to create a�édment for the natural numbers. So here's a differentizadment forMa1-2 is a crack-to-to-to-to. This means a little curl-to-to-to.