PROFESSOR: Let's take a quick look at the axioms of Zermelo-Frankel Set Theory With Choice. So the axioms of ZFC define the standard theory of sets, which is now accepted by most mathematicians as a reliable and simple basis for developing and justifying all of mathematics. Among the axioms, maybe a simple want to understand and really the motivation for this short video is twofold. One is practice with writing predicate formulas, and the other is to think a little bit more about self application.
So one of the basic axioms of set theory is called extensionality, which is capturing the idea that a set is determined by its members. So let's consider the assertion that two sets x and y have the same elements, which we could write as a predicate formula in set theory as for all x, x is a member of y, if and only if x is a member of z. Now we could use this is a definition of equality. It's what we mean by y and z are equal. But we don't really need to even introduce equality as a basic part of the language and add axioms about how it behaves.
There's one axiom that covers things adequately, and that is that if two sets have the same members, then they are members of the same sets. So if all the members of x and y are the same, then x and y are members of exactly the same thing, which we could say this way, for every x, y is an x, if and only if z is an x. So that is one of the basic axioms of Set Theory, maybe the starting one.
Another one is the Power Set axiom, which simply says that every set has a power set. How would you say that in the language of predicate set theory? Well, you'd say that for every x, there is a p, which is going to be the power set effects, such that for every set s, s is a subset of x, if and only if s is a member of p. Remember, we know how to express s as a subset of s in the language of predicate calculus, mentioning only membership. So this is a good axiom that says, yes, there is a set p consisting of precisely the subsets of x. That set p called the powers set of x.
When you're trying to deal with the Russell's paradox kind of issue, where you define a set of element or a collection of sets that satisfies some property, the safe conservative version of saying that a set of elements that satisfy some property really is a set, a collection of elements that satisfy some property, really is a set, the comprehension axiom's a simple version of an axiom that allows you to do that. So basically, it says that if s is a set and p of x is an arbitrary predicate of set theory, which might in fact be one of these dangerous things like x is not a member of x, nevertheless, if you look at those elements in the set S that satisfy P of x, that's a set.
In other words, the set of x and s, such that P of x is a set, it means that any definable collection of elements within a set also form a proper subset. And the reason why this matters is, remember, if I just talked about not the set of x in a particular set s the satisfied P of x, if I just talked about the collection of x's that satisfied P of x, that's when I start getting into Russell's paradox areas, when I declare that the set of x such that P of x is a set for unrestricted P of x. But all I get to do is put a bound on the elements that x ranges over, that x is a member of some particular set. Then it's safe to take all of those x's that satisfy P of x.
Now another particularly interesting axiom of ZF which addresses this issue of self membership and self reference is that the intuitive idea that the elements of a set have to come before the set itself. They have to be simpler than the set itself, if you think about sort of building up a set from successively simpler elements to more complicated ones. In particular, you can't have a set be a member of itself because then it's not being built from things that are simpler than it is or that came before it.
In fact, you can't even have a set that's a member of a member of itself. All of that kind of indirect membership is forbidden. Now, how do you say that is a nice axiom? Well, there's a very elegant way to do it, and that is to say that all sets are well founded under membership, which means that you can't find an infinite sequence of sets where each one has the next one as a member.
Let's give a precise way to formulate that. It's also good practice with the formulas of set theory. Let me say that x is membership minimal, epsilon minimal, in y means that x is a member of y, but there's no element of x that's also in y. In other words, x is built out of things that are not in y, but x itself is in y. So x kind of comes before any of the other elements in y. It's built out of non-y stuff. So to say this with a formula we could just say that x is in y, and for every z, if it's in x, then it's not in y. So that's the definition of x is membership minimal in y.
And then the basic axiom of ZF, called the Foundation Axiom, simply says that every nonempty set has a membership minimal element. This is actually a kind of generalization of the well ordering principle that says that every nonempty set of non-negative integers has a least element. This is a direct analogy. Just as the in principle for integers implies that you can't have an infinite decreasing sequence of non-negative integers, the Foundation Axiom actually implies that you can't have an infinite sequence of sets, each of which is a member of the previous one.
Here is a formula that's asserting Foundation. For every x, if x is not empty, that implies that there is a y, such that y is membership minimal in x. What is the Foundation got to do with membership? Well, the Foundation Axiom actually will very quickly let us conclude that no set is a member of itself. How does that work? Well, suppose that you are interested in some set, and you'd like to verify that the set can't be a member of itself. Well, let R be the set consisting of just this set S that you're interested in. R is the singleton S, its only element in S. Well, R is not empty. And by the Foundation Axiom, it must have a membership minimal element.
Now suppose that S isn't S. We're going to reach a contradiction. The claim is that R has no membership minimal element, and that violates the Foundation Axiom, so you can't have S is a member of S. Why does this follow? Well, look, R is supposed to have a membership minimal element. Well, R's only got one element. So if it's got any membership element, it's got to be S.
But S this can't be membership minimal because S is in R, which means that S has an element in R in it. So S is not R minimal. And the Foundation Axiom then immediately implies that you can't have S be a member of S. S is not membership minimal in R. And this argument extends in a nice way to member of a member and member of a member, and we'll throw a feedback on one question about that at you shortly.
So looking at the Foundation Axiom and the conclusion that no set is a member of itself, what we can immediately conclude is that, first of all, the collection of all sets can't be a set because if the collection of all sets was a set, then it would be a member of itself, and that's forbidden by the S can't be a member of S consequence of the Foundation Axiom. The second thing it tells us is remember the set W from Russell's paradox? W was the collection of those sets which are not members of themselves. Well, now we've just figured out that this is all sets because no set is a member of itself. So the sets that are not members of themselves is everything, and that's why W is not a set and not a member of itself, which explains finally how the Foundation Axiom resolves the Russell paradox.