Fun Fact: Russel's Paradox is incorrectly referenced in chapter 7 of Portal 2. GLaDOS and Chell find a poster which reads In the event of rouge AI: 1) Stand still 2) Remain Calm 3) Scream - "This Sentence is False" - "New Mission: Refuse this Mission" - "Does a set of all sets contain itself?"
Agreed! As an adult hobbyist who has never formally studied mathematics, I have trouble wrapping my head around the Axiom of Choice, which pops up quite a bit.
If you are going to be digging into the fundamentals of set theory, can I make a request for a video on the axiom of choice? The consequences of both including it and excluding it are both fascinating.
Cool video! I've seen Russell's Paradox before, and been told that ZF set theory removes sets like R, but this is the first time I've been given any clear sense of how it does so. As an aside, I've always liked the idea of R': The set of all sets that contain themselves. There is no reason for R' to be in this exclusive club, but if it is let in by mistake, it can never be kicked out, as it now meets the entry requirement!
If we accept the Axiom of Foundation (which is standard), then R' is the empty set, as no set can contain itself. Conversely, one can work with alternate axioms (e.g. Aczel's Anti-Foundation Axiom) which allow it.
A fun curiosity: there are alternative set theories in which the set of all sets exist. A prime example would be W. v. O. Quine’s New Foundations. These set theories avoid Russell’s paradox, Cantor’s paradox, Burali-Forti’s paradox and others in very different way compared to standard ZF(C). As an even more esoteric curiosity, there are even set theories in which the Russell’s set exist. It is inconsistent (it does and does not contain itself at the same time), which is okay since the underlying logic rejects the principle that from a contradiction, anything follows. Try looking up paraconsistent set theory, or directly Zach Weber’s paper ”Transfinite numbers in paraconsistent set theory”.
new intro? it's very nice! reading more about Russel's Paradox led me to the distinction between sets and classes, and specifically proper classes. Would you be interested in making a video about those?
From a layman's perspective: since the set of all sets contains itself, that creates a new set with itself. This spirals out of control because of self-referencing, kind of like an endlessly recursive function, right? Under set theory, this results in some sort of weird psuedo-infinite set, right?
I think there is no problem with a “pseudo infinite” set existing. The problem is there has to be some set which a set of sets cannot contain. Thus the set of all sets does not exist.
Well... we could kinda have set theory with this kind of infinite nested sets. The thing is that, even allowing the existence of this kind of sets, the set of all sets is still imposible. That being said, there is actually another axiom (axiom of regularity) by which one can easily deduce that no set is an element of itself. So in that sense, you are right.
The mention of all sets just reminded me of a story I read long ago ("The Roaring Trumpet" I believe, by L. Sprague de Camp and Fletcher Pratt) which invoked "Ferg's Definition of Number" to wit: "The number of elements in a set is the set of all sets that are similar to the given set." Either that definition is a fictional creation or my Google-fu is weak. But it amused me.
Something that I've had always find a bit strange is the implicit usage of the principle of excluded middle in this argument. When Russel's paradox is explained, once it is concluded that the first case is contradictory the next one is analyzed (despite the fact that there are only two cases). You don't just assume that the other must be true. So why not proceed in the same way for the "set of all sets"? For the argument to be complete, shouldn't you show that the non-existence of V does not lead to contradictions?
@@KaedennYT What I am saying is that the proposition "there is no set of all sets" should not be seen as the conclusion, but as a second case. To be able to accept it the non-existence of that set must be consistent with the rest of the theory.
@@andersok I get what you're saying, I noticed the same. The thing is, in the first proof, the existence of the contradiction led to the conclusion that the general comprehension principle was not valid, because we were supposing first that it was valid; however, if while trying to make the second proof you get a contradiction, what would you conclude? That all set theory is wrong? Well, maybe, but in my opinion, it's safe to assume here that simply there is no set of all sets
Well, not really. The theory here is ZFC, Zermelo-Fränkel set theory with the axiom of choice. It has 9 axioms: Extensionality, Separation, Pairing, Union, Power set, Regularity, Replacement, Choice. From this theory, you can just prove that there is no set of all sets, as is done in the video, so asking whether the statement “There is no set of all sets” is consistent with the axioms is the same as simply asking whether the axioms are consistent (since the statement is a logical consequence of the axioms). And you can’t prove the consistency of ZFC because of Gödel’s Second Incompleteness Theorem (well, you could prove it via a strictly stronger theory, but then you’re just stuck proving the consistency of this new theory, for which you would need an even stronger theory, and so on ad infinitum).
Andres C said "You don't just assume that the other must be true." But you do. You not only assume that the other must be true, but you have actually proved that the other statement is true. In effect, the other statement is indeed true (in such a system with those axioms). Andres C asked 'So why not proceed in the same way for the "set of all sets"?' One could, but there is no known proof that a contradiction can be derived. It is indeed possible that one could proceed in the same way getting a contradiction: then ZFC axioms would be inconsistent. Andres C asked "For the argument to be complete, shouldn't you show that the non-existence of V does not lead to contradictions?" No this is not required (since the principle of excluded middle is assumed to be true in the logic used by ZFC). In number theory, if I prove that 2 is the only even prime, I don't need to prove that this does not lead to a contradiction also.
What is meant here by a "definite condition"? Instead of ruling out the existence of the set of all sets, what if we say that the contradiction arises because the "entry fee into R" needs to be ruled out as a "definite condition"? Maybe this is equivalent?
I think a good way to look at this is the Axiom of Separation says “Every set has a Definite Condition to define it”, while the General Comprehension Principle says “Every Definite Condition defines a set”. And what Russel’s Paradox shows is that in fact there are some Definite Conditions which don’t define a set.
@@Bodyknock There's *something* which is not defining a set, but there's still the question of whether that rule qualifies as a "definite condition" and what that even means in the first place. You could reasonably argue that a rule that fails to define a set isn't really a "definite condition". That's a little circular but so is Russell's Paradox.
_"Definite condition"_ doesn't mean anything different from _"condition."_ I think Prof. Penn used _"definite"_ just for emphasis when explaining math to us, the general public. The technical term is _"predicate."_ A predicate P(x) is either true or false depending on its argument (or parameter) x. That's all. The contradiction is not due to the predicate. It's just that you should not use arbitrary predicates (unrestricted comprehension) to define sets. (However, you can use predicates to define subsets-that's perfectly fine.) Secondly, there is no "set of all sets." As the video explains, if you try to do either of those, you get contradictions.
@@peterg76yt Like the response above says, Definite Condition is synonymous with a statement that is logically true or false. The axiom of separation says every set has a logical predicate that defines what elements are in the set. But what Russel’s Paradox demonstrates is that not every logical predicate defines a set.
@@Bodyknock No, Russel's Paradox defines a set recursively in terms of its own membership. The reason it's not a set is that Its predicate is not well-defined. That's true of the set of all sets but it's a much more interesting example because it has problems beyond that.
On operation "Bertrand", J Edgar Hoover instructs each of his agents to go into an allocated room of a building and take a photo of everyone in that room at the time. Some agents also take a photo of themselves since of course they too are in the room at the time, and some don't because they aren't the subject of surveillance so what's the point for heaven's sake. Hoover disagrees, and tells one of the agents to take a photo of all and only those agents who didn't take a photo of themselves. Knowing how suspicious Hoover is, that agent figures he should also take a photo of himself, except that would mean he didn't take a photo of himself. But if he did take a photo of himself, then he shouldn't take one of himself now. Is there a paradox?
@@pierreabbat6157 Thanks for giving it a go. I'd say you're right, if the agent took a photo of himself then he clearly shouldn't take one now, so no paradox. But equally, if he didn't then he should now if he's to comply with Hoover's instructions, so no paradox there either. My point is that there's no contradiction as long as we explicitly separate off by means of grammatical tense (or other time markers) the two stages in time, what happened then and what happens now. This also applies in the better known "barber" version which can be reworded as the man who shaves now all and only those men who didn't shave themselves before, and the Russell set itself, the set which includes now all and only those sets which didn't include themselves previously. If it included itself before then it doesn't now, but if it didn't then it does. Russell isn't about sets and set inclusion particularly, any more than the barber is about shaving or mine about taking photos, but about the relative tenses of those actions or operations. The paradox only emerges when we collapse all those tenses into one. Another example in math is the expression 2 * 3 + 4. It yields two contradictory results, 10 and 14, only as long as we fail to indicate (with brackets or whatever) whether we want the * or + to be done first. But we don't usually dignify that with the term "paradox".
Russell wrote to Gottlob Frege about this paradox just as the latter's masterwork (Begriffschrift?) was about to be published and Frege commented ruefully in its preface how disheartening it was to have the whole foundation of the work collapse as it was nearly through the press.
*@ Michael Penn* -- You misspelled "Russell's" both times that you wrote it on the chalkboard. And, apparently many people in the comments section are following your lead and misspelling it in the same way.
Perhaps it would be instructive to show how the disproof of the General Comprehension Principle doesn't work when applied to the Axiom of Separation using the same condition (x is a set and x does not contain itself). You sort of have to assume that there is no "set of all sets" and so no set to use as S in the Axiom. It all seems rather circular.
could you explain a little bit more about the proof @ 5:30? I don't understand what you mean by the set of Natural # containing natural numbers but it doesn't contain itself(I understand the first portion where set of Natural # contains all natural numbers). Why doesn't it contain itself?
Rejecting axiom schema of separation, though, will result in a set theory that may have an universal set, like in new foundations (NF). Russel's paradox fails in NF because {x | x ∉ x} is not a valid set as the formula is not stratified.
In other words the “set of all sets” would necessarily need to contain the “set of all sets which do not contain themselves” and since Russell’s paradox proves that such a set contains itself only if it does not, then it also proves that a set of all sets cannot exist because it would contain an impossible set. Am I following this correctly in simplistic terms?
No! :P If the barber is bald, meant that he doesn't cut his hair. So from the definition, he cut's his hair ( He cuts the hair of all people doesn't cut their hair). The barber doesn't cut his hair it self, because he cut's the hair all people who doesn't cut his hair.
non of them are false the conjonction of the two statements is the one that is false because it leads to a contradiction so in a systeme where you have a set of all sets the specification axiom would be false the same if you consider the later to be true you would have "there is no set of all sets"
Great question! First of all, you should know that _"Set Theory"_ is a misnomer-there are _many_ set theories, not just one. They all differ in their axioms. As Prof. Penn explained, you don't prove axioms. You accept them as true without proof. For any theory, the selected axioms are the starting point for proving (or disproving) other mathematical statements. In the most commonly used set theory-known as ZFC-the Axiom of Separation is accepted as true without proof. In fact, ZFC has nine axioms, including the Axiom of Separation. Using these axioms, it is easy to prove that V, the Universal Set (aka Set of All Sets), does not exist. (BTW, you can prove it in many different ways. You don't have to use the Axiom of Separation. Instead you can use two other axioms-Regularity and Pairing-to show that a set cannot contain itself. That immediately excludes V, which, by definition, must contain itself.) Now coming to your question. Yes, you can use a different set of axioms where V exists, and the Axiom of Separation is false. In fact, set theories such as Willard Van Orman Quine's *_New Foundations_* and the *_positive set theory_* do exactly that. Regardless of what axioms underlie any theory, remember, for a theory to be useful, it must agree with our everyday experiences. Like 1+1=2 and 2x2=4. And they must not allow contradictions, like 1+1=3. All the theories I've mentioned behave properly in those respects. Turns out that the question of V's existence is not important after the initial stages.
If mathematics is a game, then axioms are the rules of the game. You can choose whatever rules you like, but the most interesting ones are the ones where it’s not trivial to prove things. If you don’t have enough axioms, you can run out of things to prove. If you choose contradictory axioms (such as if we allowed General Comprehension along with the other axioms), then you introduce something called the Principle of Explosion - every statement is automatically true, even the ones that are false. So you *could* have a system that allows for a set of all sets, but to avoid the Principle of Explosion it would need to adjust other axioms so that the proof in this video doesn’t work. And that’s fine, and such systems apparently exist, but they’re not as commonly used.
Why does it prove that the principle is invalid rather than the assumption of the definite condition? What I mean is, why can this not be taken as a proof that the condition was not definite?
"x not in x" is a definite condition by proof: it is not an assumption. More formally, "x not in x" is shorthand for "not (x in x)". Since "x in x" is a definite statement by definition, then "not (x in x)" is a definite statement by definition. A definite statement (in ZFC) means a well-formed-formula using the language of ZFC (where "x in y" is a wff and well formed first order logical formulas of wff's are wffs).
@@billh17 i see, thanks! So do mathematicians deal with this kind of self-referential statement in a similar way to indeterminate forms? You know.. like x/x is well formed but indeterminate if x=0. Is there a concept like that in set theory? Can the paradox crop up in people's work and how would they deal with it? Sorry, I'm not a mathematician so have so many questions. Now reading about zfc...
@@jimiwills Informally, we talk about the expression x / x and say that the expression is indeterminate if x = 0. But, formally this type of question of being "indeterminate" doesn't occur because we cannot "express" it formally. Suppose we want to informally consider the subset of real numbers S = { w in R | (Ex)(x in R and w = x / x) }. Apparently we would have to worry about the "indeterminate" expression x / x when x = 0. But, "x / x" cannot really be stated formally. Rather, one would have to write something like: S = { w in R | (Ex)(Ey)( x in R and y in R and x * y = 1 and w = x * y}. Then taking x = 0 would make the inner condition false since there is no y in R such that 0 * y = 1: hence, we can forget about the case of x being 0 in R to see whether w would be in S. That is, (Ey)( y in R and x * y = 1) is the definition of 1 / x being such a y. When x = 0, there is no such y that x * y = 1: hence, x = 0 does not have a multiplicative inverse. The above may not be the correct explanation. What I am trying to say is that when you "unwind" the definition of what 1 / x means, you will just get to some statement like (Ey)( y in R and x * y = 1) just being false when x = 0 (rather than being meaningless like 1 / 0).
yes, so there's a set not contained by V, and thus V can't be the set containing all sets, ergo such a set doesn't exist (at least as long as we're labouring under the axiom of separation)
@@martintoilet5887 I think it's more that if V exists then, by the axiom of separation, you can create any set out of the members of V by imposing a definite condition on V. If we choose the condition that x isn't a member of itself, then by definition of R, that creates the set R. But since it was already shown R doesn't exist, we made a false assumption along the way. And because we've chosen the axiom of separation to underlie (ZF) set theory, we've therefore decided that all "definite conditions" imposed on existing sets must create further sets. So the rejected assumption then must be "V exists", since you can still impose the same definite condition on smaller sets and create sets that don't contain R. (Someone correct me if I have that wrong).
The idea of a set containing itself seems rather weird to me, given that I can't think of any non-esoteric set that would be considered to contain itself.
If a set is defined by the property that it obeys the principle of separation doesn't that basically exclude the idea of a single set of all sets? There always would be a recursively defined counterexample. Every first set can always be contained within a set containing this first set and a second set containing this first set.
You can define a set of all set but you have to give up axiom of separation. In a universe where set of all set exist axiom of separation cannot exist. But axiom of separation is a lot more useful than having a set of all set. Having a set of all set is not really needed to prove things.
I think one reason there can be no set of all sets is that such a container cannot contain itself. Like the set of all parabolas is not a parabola (it is a set instead), the set of all sets can always become a member of a larger set of all sets.
If you define a set as a container that makes sense. But if you define a set as a collection of things having similar properties. Then a set having similar properties to it's members make sense.
It seems to me that you should add a comment that you are talking about Zermelo-Frankel set theory (ZF) and related theories. This does not apply to other theories such as NBG, which avoids Russell's paradox in another way and has a *theorem* of separation. You may also want to explain how your statement of the axiom of separation differs from Wikipedia's, Wolfram MathWorld's, etc.
Frege war right and Russell was wrong. If I may...................That below will demonstrate that the set of all sets that do not contain themselves does not and cannot contain itself.............First, Here is the resolution to the barber paradox which is by definition, reflective of the logical issues in the mathematical and if the former were defeated, so too would be the mathematical. In this paradox, there was a town in which all men were required to be beardless. In this town, there was a set of men who shaved themselves and another separate set who did not shave themselves. For that latter set of men there was a barber who posted a sign which instructed that he only shaved men who did not shave themselves. The paradoxical aspect becomes visible when considering who would shave the barber, there being only two sets of men to which he could be a member by virtue of whether or not he did or did not shave himself. He had to be beardless so he had to shave himself but his sign instructed that he did not shave men who shaved themselves, thus the paradox. Though confusing to some, the resolution is clear and simple. The two sets of men were defined as such by virtue of only one, unique criterion, i.e., for the one that they shaved themselves and for the other that they did not but rather visited the barber. Each set of men shared three other criteria for membership which were identical. In each they were men. In each they lived in town and in each they had to be beardless. The only means of the definition of their membership into the two separate sets of men (the deciding factor) was the inclusion of their respective relationships to shaving. That being the case, the barber would necessarily have to be defined as a member of a third set of men (which would not preclude him from shaving himself), i.e., those who shaved others. Consider, he too was a man, lived in town and had to be beardless and like the first two sets of men, if the same logic were to hold throughout the paradox (which it must), was designated a member of a separate, third set of men by his unique relationship to shaving, the only defining factor in the first two and thus necessarily for the third. Deny this and you deny the very means by which the first two groups of men were defined as members of their separate sets and the paradox fails. Accept this and the paradox fails. That is because it is not a paradox. Likewise, (if you prefer the Nelson-Grelling paradox, the words which were heterological were defined by that they did not describe themselves, as homological or autological words did, i.e., there was a material aspect which was peculiar to the category in which they were contained, i.e., autological. But they too described themselves and not other words. The terms autological and heterological were set definitions, words that defined other words, not themselves (the barber). The words they described, described only themselves and not other words. Apples and oranges. So there must be by definition a third set of words to which autological and heterological belong for the criteria by which the words they contain are defined as belonging to one set or the other are not part of what describe the terms autological and heterological. It is that simple. No paradox, no contradictions and no challenges to logic. You guys are ignoring the contexts in which all of this is considered. Frege was right, Russell was wrong and Nelsen/Grelling were wrong.
Only in set theories which contain classes, though, such as von Neumann-Bernays-Gödel set theory. Classes don't exist in Zermelo-Fraenkel set theory except as syntactical shorthand for predicates.
I may be way off here but if the set of all sets existed would that imply it is CLOSED? Hence that would imply EVERY set (subset) in the set of all sets would be CLOSED also which is obviously false hence the "set of all sets" can't exist.
I've always found Russel's Paradox to be a particularly weak argument. What the contradiction proves is that EITHER the general comprehension principle is not valid OR that P(x) is not a well-defined "definite condition" (which wasn't defined in the first place). The usual examples seem to be sets that are merely poorly defined, not sets illustrating fundamental flaws in 19th-century set theory. It gets more interesting with the set of all sets example when you start asking questions like does this set contain its own power set.
Peter Grey said '... OR that P(x) is not a well-defined "definite condition" (which wasn't defined in the first place).' P(x) being a well-defined "definite condition" means that P(x) is a well-formed statement in the language of ZFC (which uses first order logic and the undefined predicate "in"). As an aside, the set of all people who voted in the last US presidential election is not a set in ZFC since it is not a well-formed statement in the language of ZFC (since 'people' or 'person' or 'US' or 'election' etc cannot be defined in ZFC).
No, not at all ... he was just explaining the meaning of the word 'axiom.' What made you think he said anything at all about the consistency of ZF? I'm pretty sure he knows Gödel's theorems and wouldn't make mistakes like that.
@@nHans If ZF is inconsistent, i.e. can prove a contradiction, then every statement can be proved from it (this is the logical Principle of Explosion). Therefore in particular, ZF is inconsistent => its axioms can be proved true(and simultaneously proved false), so by taking the contrapositive, if the axioms of ZF can't be proved true(/false) then ZF is consistent. (Note: whenever I say "proved" I mean "proved within ZF itself"; the axioms of ZF *can* be proved true by more powerful set theories, whose axioms can be proved true by yet more powerful set theories, and so on. But no sufficiently-expressive theory can prove its own axioms true by Goedel's incompleteness theorems)
@@schweinmachtbree1013 I appreciate the effort you took to reply. But unfortunately you're wrong. Axioms _cannot_ be proved. That's by definition. *_Consistency_* of a theory is a different issue. Gödel proved that a sufficiently-expressive theory: - if it is _consistent,_ it *cannot* prove its own _consistency._ - if it is _inconsistent,_ paradoxically, it can prove that it is _consistent._ Kinda like a liar saying _"I always tell the truth."_ It is not known whether ZF(C) is consistent or not. However, it is generally believed to be consistent, because no inconsistencies or contradictions have been found till date. The OP thought that Prof. Penn assumed that ZF was consistent. I assured them that Prof. Penn had made no such assumption.
@@nHans Axioms _can_ be proved. In a theory T with an axiom p, the proof of p is the one line proof "p". Hence T ⊢ p. The motto "axioms cannot be (non-trivially) proved" is not a definition; it is just a description which gives intuition for what an axiom is. I will reiterate (replacing "true/false" by "false" since I have just explained that a theory entails its axioms): ZF is inconsistent => ZF ⊢ ¬Seperation (by Explosion), and hence by contraposition, ZF ⊬ ¬Separation (i.e. Separation cannot be proved false) => ZF is consistent. Therefore Michael's claim that "the Axiom of Separation is not provable to be false" implies the consistency of ZF/ZFC.
You just have to think of ‘does 5 belong to two sets’ to see that this is arbitrarily wrong. Anything can belong to anything in mathematics because it’s all imaginary, and any construction of a set is fine, it’s just a matter whether it is useful or not.
1 Corinthians 15:27 in the Bible is interesting in that it recognizing this type of contradiction where all has something referencing itself. It clears that up by limiting “all” to not include itself. Not sure I said that right. “For he hath put all things under his feet. But when he saith all things are put under him, it is manifest that he is excepted, which did put all things under him.”
The super set paradox is such a better name than the arrogant ignorant filth term our planets main trash species uses for it instead. Though that naming is very much indicative of human ideation in general, and explains so much of what is wrong with us nowadays. We honestly think we create math, and that concepts can be owned, what exploitative jokes
Fun Fact: Russel's Paradox is incorrectly referenced in chapter 7 of Portal 2. GLaDOS and Chell find a poster which reads
In the event of rouge AI:
1) Stand still
2) Remain Calm
3) Scream - "This Sentence is False"
- "New Mission: Refuse this Mission"
- "Does a set of all sets contain itself?"
Lmao that was on my mind as I was watching this
Great video, would love to see a series on ZF set theory!
Agreed! As an adult hobbyist who has never formally studied mathematics, I have trouble wrapping my head around the Axiom of Choice, which pops up quite a bit.
I haven't watched it, but Richard Borcherds has a recent series on this
@@Alex_Deam thanks I'll check it out!
10:06 Yo, my favorite paradox!
If you are going to be digging into the fundamentals of set theory, can I make a request for a video on the axiom of choice? The consequences of both including it and excluding it are both fascinating.
The axiom of choice is clearly true, and the axiom of choice is clearly false!
@@sammyboy7094 👀
It's good to know that now if someone asks the paradox "Does a set of all sets contain itself?", we can properly answer "Your question isn't valid" :D
Cool video! I've seen Russell's Paradox before, and been told that ZF set theory removes sets like R, but this is the first time I've been given any clear sense of how it does so.
As an aside, I've always liked the idea of R': The set of all sets that contain themselves. There is no reason for R' to be in this exclusive club, but if it is let in by mistake, it can never be kicked out, as it now meets the entry requirement!
If we accept the Axiom of Foundation (which is standard), then R' is the empty set, as no set can contain itself. Conversely, one can work with alternate axioms (e.g. Aczel's Anti-Foundation Axiom) which allow it.
A fun curiosity: there are alternative set theories in which the set of all sets exist. A prime example would be W. v. O. Quine’s New Foundations. These set theories avoid Russell’s paradox, Cantor’s paradox, Burali-Forti’s paradox and others in very different way compared to standard ZF(C). As an even more esoteric curiosity, there are even set theories in which the Russell’s set exist. It is inconsistent (it does and does not contain itself at the same time), which is okay since the underlying logic rejects the principle that from a contradiction, anything follows. Try looking up paraconsistent set theory, or directly Zach Weber’s paper ”Transfinite numbers in paraconsistent set theory”.
BROOOO SEND LINKSSSSSSSSSS. U AWAKENED MY CURIOSITY NOW
@@khaledchatah3425agreed
Yet another great presentation. I have recommended your videos to many others.
They are among the best available!
This talk showed proper class.
This is some choice wording.
That's completely consistent with my own observation. You're in your element today.
In a village a barber shaves all those villagers who doesn't shave themselves then who shaves barber. One of forms of Russell paradox
Maybe the barber is a girl? Or a young person, or a chemotherapy patient, or someone who otherwise doesn't need to shave? :D
@@TonyHammitt still a paradox
I know a spicy variant. The setting Is a ship where a sailor masturbates sailors who do not masturbate themself
This is an extremely poor example.
new intro? it's very nice!
reading more about Russel's Paradox led me to the distinction between sets and classes, and specifically proper classes. Would you be interested in making a video about those?
The clearest explanation of Russel's Paradox
From a layman's perspective: since the set of all sets contains itself, that creates a new set with itself. This spirals out of control because of self-referencing, kind of like an endlessly recursive function, right? Under set theory, this results in some sort of weird psuedo-infinite set, right?
I think there is no problem with a “pseudo infinite” set existing. The problem is there has to be some set which a set of sets cannot contain. Thus the set of all sets does not exist.
Well... we could kinda have set theory with this kind of infinite nested sets. The thing is that, even allowing the existence of this kind of sets, the set of all sets is still imposible. That being said, there is actually another axiom (axiom of regularity) by which one can easily deduce that no set is an element of itself. So in that sense, you are right.
We indeed need a full set theory playlist 🙏
Really great video! Super clear explanations
The mention of all sets just reminded me of a story I read long ago ("The Roaring Trumpet" I believe, by L. Sprague de Camp and Fletcher Pratt) which invoked "Ferg's Definition of Number" to wit: "The number of elements in a set is the set of all sets that are similar to the given set." Either that definition is a fictional creation or my Google-fu is weak. But it amused me.
That sounds a lot like Frege's Definition of Number, yes. Indeed, the video is basically about Frege's "Basic Law V". See "Frege's Theorem".
Quote from the book:
"That's almost as bad as Frege's definition of number." Bayard droned: "The number of things in a given class..."
@@renerpho Ah. "Frege's" not "Ferg's". Misremembered the name after al these years. That's why I couldn't find it.
Something that I've had always find a bit strange is the implicit usage of the principle of excluded middle in this argument. When Russel's paradox is explained, once it is concluded that the first case is contradictory the next one is analyzed (despite the fact that there are only two cases). You don't just assume that the other must be true.
So why not proceed in the same way for the "set of all sets"? For the argument to be complete, shouldn't you show that the non-existence of V does not lead to contradictions?
There is no second case. It contains itself, because it's a set. If it didn't contain itself, it wouldn't be the set of all sets.
@@KaedennYT What I am saying is that the proposition "there is no set of all sets" should not be seen as the conclusion, but as a second case. To be able to accept it the non-existence of that set must be consistent with the rest of the theory.
@@andersok I get what you're saying, I noticed the same. The thing is, in the first proof, the existence of the contradiction led to the conclusion that the general comprehension principle was not valid, because we were supposing first that it was valid; however, if while trying to make the second proof you get a contradiction, what would you conclude? That all set theory is wrong? Well, maybe, but in my opinion, it's safe to assume here that simply there is no set of all sets
Well, not really. The theory here is ZFC, Zermelo-Fränkel set theory with the axiom of choice. It has 9 axioms: Extensionality, Separation, Pairing, Union, Power set, Regularity, Replacement, Choice. From this theory, you can just prove that there is no set of all sets, as is done in the video, so asking whether the statement “There is no set of all sets” is consistent with the axioms is the same as simply asking whether the axioms are consistent (since the statement is a logical consequence of the axioms). And you can’t prove the consistency of ZFC because of Gödel’s Second Incompleteness Theorem (well, you could prove it via a strictly stronger theory, but then you’re just stuck proving the consistency of this new theory, for which you would need an even stronger theory, and so on ad infinitum).
Andres C said "You don't just assume that the other must be true." But you do. You not only assume that the other must be true, but you have actually proved that the other statement is true. In effect, the other statement is indeed true (in such a system with those axioms).
Andres C asked 'So why not proceed in the same way for the "set of all sets"?' One could, but there is no known proof that a contradiction can be derived. It is indeed possible that one could proceed in the same way getting a contradiction: then ZFC axioms would be inconsistent.
Andres C asked "For the argument to be complete, shouldn't you show that the non-existence of V does not lead to contradictions?" No this is not required (since the principle of excluded middle is assumed to be true in the logic used by ZFC). In number theory, if I prove that 2 is the only even prime, I don't need to prove that this does not lead to a contradiction also.
More videos like this!!
What is meant here by a "definite condition"? Instead of ruling out the existence of the set of all sets, what if we say that the contradiction arises because the "entry fee into R" needs to be ruled out as a "definite condition"? Maybe this is equivalent?
I think a good way to look at this is the Axiom of Separation says “Every set has a Definite Condition to define it”, while the General Comprehension Principle says “Every Definite Condition defines a set”. And what Russel’s Paradox shows is that in fact there are some Definite Conditions which don’t define a set.
@@Bodyknock There's *something* which is not defining a set, but there's still the question of whether that rule qualifies as a "definite condition" and what that even means in the first place. You could reasonably argue that a rule that fails to define a set isn't really a "definite condition". That's a little circular but so is Russell's Paradox.
_"Definite condition"_ doesn't mean anything different from _"condition."_ I think Prof. Penn used _"definite"_ just for emphasis when explaining math to us, the general public.
The technical term is _"predicate."_ A predicate P(x) is either true or false depending on its argument (or parameter) x. That's all.
The contradiction is not due to the predicate. It's just that you should not use arbitrary predicates (unrestricted comprehension) to define sets. (However, you can use predicates to define subsets-that's perfectly fine.) Secondly, there is no "set of all sets." As the video explains, if you try to do either of those, you get contradictions.
@@peterg76yt Like the response above says, Definite Condition is synonymous with a statement that is logically true or false. The axiom of separation says every set has a logical predicate that defines what elements are in the set. But what Russel’s Paradox demonstrates is that not every logical predicate defines a set.
@@Bodyknock No, Russel's Paradox defines a set recursively in terms of its own membership. The reason it's not a set is that Its predicate is not well-defined. That's true of the set of all sets but it's a much more interesting example because it has problems beyond that.
On operation "Bertrand", J Edgar Hoover instructs each of his agents to go into an allocated room of a building and take a photo of everyone in that room at the time. Some agents also take a photo of themselves since of course they too are in the room at the time, and some don't because they aren't the subject of surveillance so what's the point for heaven's sake. Hoover disagrees, and tells one of the agents to take a photo of all and only those agents who didn't take a photo of themselves. Knowing how suspicious Hoover is, that agent figures he should also take a photo of himself, except that would mean he didn't take a photo of himself. But if he did take a photo of himself, then he shouldn't take one of himself now. Is there a paradox?
Very cute example
If Hoover picked an agent who already took a photo of himself, then no.
@@pierreabbat6157 Thanks for giving it a go. I'd say you're right, if the agent took a photo of himself then he clearly shouldn't take one now, so no paradox. But equally, if he didn't then he should now if he's to comply with Hoover's instructions, so no paradox there either.
My point is that there's no contradiction as long as we explicitly separate off by means of grammatical tense (or other time markers) the two stages in time, what happened then and what happens now. This also applies in the better known "barber" version which can be reworded as the man who shaves now all and only those men who didn't shave themselves before, and the Russell set itself, the set which includes now all and only those sets which didn't include themselves previously. If it included itself before then it doesn't now, but if it didn't then it does.
Russell isn't about sets and set inclusion particularly, any more than the barber is about shaving or mine about taking photos, but about the relative tenses of those actions or operations. The paradox only emerges when we collapse all those tenses into one. Another example in math is the expression 2 * 3 + 4. It yields two contradictory results, 10 and 14, only as long as we fail to indicate (with brackets or whatever) whether we want the * or + to be done first. But we don't usually dignify that with the term "paradox".
Russell's* paradox; double "l" in his name.
Oh, well. I'll settle for the set of almost all sets.
Russell wrote to Gottlob Frege about this paradox just as the latter's masterwork (Begriffschrift?) was about to be published and Frege commented ruefully in its preface how disheartening it was to have the whole foundation of the work collapse as it was nearly through the press.
Surely the universe is a set which contains all sets.
*@ Michael Penn* -- You misspelled "Russell's" both times that you wrote it on the chalkboard.
And, apparently many people in the comments section are following your lead and misspelling
it in the same way.
Hi,
Ok, great! And happy new year to every body!
Perhaps it would be instructive to show how the disproof of the General Comprehension Principle doesn't work when applied to the Axiom of Separation using the same condition (x is a set and x does not contain itself).
You sort of have to assume that there is no "set of all sets" and so no set to use as S in the Axiom. It all seems rather circular.
You need to define the universe first. So it will be x is a member of … and … by starting from a set one avoid the paradox
This is a new subject for me and I would like you to make more videos about this
Can you do a video on the Axiom of Choice?
could you explain a little bit more about the proof @ 5:30? I don't understand what you mean by the set of Natural # containing natural numbers but it doesn't contain itself(I understand the first portion where set of Natural # contains all natural numbers). Why doesn't it contain itself?
he is just saying that the set of natural numbers {0, 1, 2, 3, ...} does not contain itself (the set {0, 1, 2, 3, ...}) as an element
@@schweinmachtbree1013 I appreciate the clarification! Makes perfect sense now
@schweinmachtbrie 0 (zero) does not seem natural to me. Can you take that out please? Thx.
@@deltalima6703 no :P
Oh! Somebody already did. ;-)
New mission: refuse this mission
Portal?
I really love this video
Thanks a lot !!!!!!!!!!
the name "Unrestricted Comprehension" has a better ring to it than "General Comprehension" imo
Rejecting axiom schema of separation, though, will result in a set theory that may have an universal set, like in new foundations (NF).
Russel's paradox fails in NF because
{x | x ∉ x} is not a valid set as the formula is not stratified.
This reminded me of Raymond Smullyan’s book titled “What is the Name of this Book”
Who's on first
What?
In other words the “set of all sets” would necessarily need to contain the “set of all sets which do not contain themselves” and since Russell’s paradox proves that such a set contains itself only if it does not, then it also proves that a set of all sets cannot exist because it would contain an impossible set.
Am I following this correctly in simplistic terms?
Lots of videos about Ramanujan lately, now a Russell's video. Maybe one of the next video will be about Hardy and Littlewood.
I’m taking foundations of mathematics next semester, and would love a series on that
A town barber shaves all men who do not shave themselves. Does this barber shave himself?
Example:
There is the barber that cuts all hair of all people who doesn't cut their own hair. Who does cut, the barbers hair?
The answer is the barber itself
The barber is bald.
No! :P
If the barber is bald, meant that he doesn't cut his hair. So from the definition, he cut's his hair ( He cuts the hair of all people doesn't cut their hair).
The barber doesn't cut his hair it self, because he cut's the hair all people who doesn't cut his hair.
Another barber :)
What about the set of all sets except itself?
Just a noob question: could it be that thw AXIOM OF SEPARATION is the false asumption, instead of tge existance of V=set of all sets?
No, we consider the axiom of separation true by assertion. Set theory breaks down completely without it.
non of them are false the conjonction of the two statements is the one that is false because it leads to a contradiction so in a systeme where you have a set of all sets the specification axiom would be false the same if you consider the later to be true you would have "there is no set of all sets"
Great question!
First of all, you should know that _"Set Theory"_ is a misnomer-there are _many_ set theories, not just one.
They all differ in their axioms. As Prof. Penn explained, you don't prove axioms. You accept them as true without proof. For any theory, the selected axioms are the starting point for proving (or disproving) other mathematical statements.
In the most commonly used set theory-known as ZFC-the Axiom of Separation is accepted as true without proof. In fact, ZFC has nine axioms, including the Axiom of Separation. Using these axioms, it is easy to prove that V, the Universal Set (aka Set of All Sets), does not exist.
(BTW, you can prove it in many different ways. You don't have to use the Axiom of Separation. Instead you can use two other axioms-Regularity and Pairing-to show that a set cannot contain itself. That immediately excludes V, which, by definition, must contain itself.)
Now coming to your question. Yes, you can use a different set of axioms where V exists, and the Axiom of Separation is false. In fact, set theories such as Willard Van Orman Quine's *_New Foundations_* and the *_positive set theory_* do exactly that.
Regardless of what axioms underlie any theory, remember, for a theory to be useful, it must agree with our everyday experiences. Like 1+1=2 and 2x2=4. And they must not allow contradictions, like 1+1=3. All the theories I've mentioned behave properly in those respects. Turns out that the question of V's existence is not important after the initial stages.
If mathematics is a game, then axioms are the rules of the game. You can choose whatever rules you like, but the most interesting ones are the ones where it’s not trivial to prove things.
If you don’t have enough axioms, you can run out of things to prove. If you choose contradictory axioms (such as if we allowed General Comprehension along with the other axioms), then you introduce something called the Principle of Explosion - every statement is automatically true, even the ones that are false.
So you *could* have a system that allows for a set of all sets, but to avoid the Principle of Explosion it would need to adjust other axioms so that the proof in this video doesn’t work. And that’s fine, and such systems apparently exist, but they’re not as commonly used.
Why does it prove that the principle is invalid rather than the assumption of the definite condition? What I mean is, why can this not be taken as a proof that the condition was not definite?
"x not in x" is a definite condition by proof: it is not an assumption. More formally, "x not in x" is shorthand for "not (x in x)". Since "x in x" is a definite statement by definition, then "not (x in x)" is a definite statement by definition. A definite statement (in ZFC) means a well-formed-formula using the language of ZFC (where "x in y" is a wff and well formed first order logical formulas of wff's are wffs).
@@billh17 i see, thanks! So do mathematicians deal with this kind of self-referential statement in a similar way to indeterminate forms? You know.. like x/x is well formed but indeterminate if x=0. Is there a concept like that in set theory? Can the paradox crop up in people's work and how would they deal with it? Sorry, I'm not a mathematician so have so many questions. Now reading about zfc...
@@jimiwills Informally, we talk about the expression x / x and say that the expression is indeterminate if x = 0. But, formally this type of question of being "indeterminate" doesn't occur because we cannot "express" it formally.
Suppose we want to informally consider the subset of real numbers S = { w in R | (Ex)(x in R and w = x / x) }. Apparently we would have to worry about the "indeterminate" expression x / x when x = 0. But, "x / x" cannot really be stated formally. Rather, one would have to write something like: S = { w in R | (Ex)(Ey)( x in R and y in R and x * y = 1 and w = x * y}. Then taking x = 0 would make the inner condition false since there is no y in R such that 0 * y = 1: hence, we can forget about the case of x being 0 in R to see whether w would be in S. That is, (Ey)( y in R and x * y = 1) is the definition of 1 / x being such a y. When x = 0, there is no such y that x * y = 1: hence, x = 0 does not have a multiplicative inverse.
The above may not be the correct explanation. What I am trying to say is that when you "unwind" the definition of what 1 / x means, you will just get to some statement like (Ey)( y in R and x * y = 1) just being false when x = 0 (rather than being meaningless like 1 / 0).
I see you can't have a set containing all sets. Can there be any set which contains itself? (under the popular sets of axioms, or otherwise?)
Wait, but if R is a set and also not a set, wouldn't that make it nonexistent? And if R doesn't exist then V shouldn't have contained R right?
yes, so there's a set not contained by V, and thus V can't be the set containing all sets, ergo such a set doesn't exist
(at least as long as we're labouring under the axiom of separation)
@@xCorvus7x Oh, so a nonexisting set still counts as a set?
@@martintoilet5887 I think it's more that if V exists then, by the axiom of separation, you can create any set out of the members of V by imposing a definite condition on V. If we choose the condition that x isn't a member of itself, then by definition of R, that creates the set R. But since it was already shown R doesn't exist, we made a false assumption along the way. And because we've chosen the axiom of separation to underlie (ZF) set theory, we've therefore decided that all "definite conditions" imposed on existing sets must create further sets. So the rejected assumption then must be "V exists", since you can still impose the same definite condition on smaller sets and create sets that don't contain R. (Someone correct me if I have that wrong).
Hey Michael!
Could you do a video on the real (and complex) analysis of the infinite relation
y = root(x+root(x+root(x+...)))
Or (y=root(x+y)
?
so the set of all sets, is the same as the set which does not contain itself. a box made out of all *other* boxes
The idea of a set containing itself seems rather weird to me, given that I can't think of any non-esoteric set that would be considered to contain itself.
If a set is defined by the property that it obeys the principle of separation doesn't that basically exclude the idea of a single set of all sets? There always would be a recursively defined counterexample. Every first set can always be contained within a set containing this first set and a second set containing this first set.
But couldnt we just define the set containing all sets as we just went ahead and defined sqrt(-1)?
You can define a set of all set but you have to give up axiom of separation. In a universe where set of all set exist axiom of separation cannot exist. But axiom of separation is a lot more useful than having a set of all set. Having a set of all set is not really needed to prove things.
@@kazedcat Cool ! Thank you!
I think one reason there can be no set of all sets is that such a container cannot contain itself. Like the set of all parabolas is not a parabola (it is a set instead), the set of all sets can always become a member of a larger set of all sets.
If you define a set as a container that makes sense. But if you define a set as a collection of things having similar properties. Then a set having similar properties to it's members make sense.
Wow nice
NB: *Russell's* Paradox
It seems to me that you should add a comment that you are talking about Zermelo-Frankel set theory (ZF) and related theories. This does not apply to other theories such as NBG, which avoids Russell's paradox in another way and has a *theorem* of separation. You may also want to explain how your statement of the axiom of separation differs from Wikipedia's, Wolfram MathWorld's, etc.
A video on NBG and MK would be cool.
Frege war right and Russell was wrong. If I may...................That below will demonstrate that the set of all sets that do not contain themselves does not and cannot contain itself.............First, Here is the resolution to the barber paradox which is by definition, reflective of the logical issues in the mathematical and if the former were defeated, so too would be the mathematical. In this paradox, there was a town in which all men were required to be beardless. In this town, there was a set of men who shaved themselves and another separate set who did not shave themselves. For that latter set of men there was a barber who posted a sign which instructed that he only shaved men who did not shave themselves. The paradoxical aspect becomes visible when considering who would shave the barber, there being only two sets of men to which he could be a member by virtue of whether or not he did or did not shave himself. He had to be beardless so he had to shave himself but his sign instructed that he did not shave men who shaved themselves, thus the paradox. Though confusing to some, the resolution is clear and simple. The two sets of men were defined as such by virtue of only one, unique criterion, i.e., for the one that they shaved themselves and for the other that they did not but rather visited the barber. Each set of men shared three other criteria for membership which were identical. In each they were men. In each they lived in town and in each they had to be beardless. The only means of the definition of their membership into the two separate sets of men (the deciding factor) was the inclusion of their respective relationships to shaving. That being the case, the barber would necessarily have to be defined as a member of a third set of men (which would not preclude him from shaving himself), i.e., those who shaved others. Consider, he too was a man, lived in town and had to be beardless and like the first two sets of men, if the same logic were to hold throughout the paradox (which it must), was designated a member of a separate, third set of men by his unique relationship to shaving, the only defining factor in the first two and thus necessarily for the third. Deny this and you deny the very means by which the first two groups of men were defined as members of their separate sets and the paradox fails. Accept this and the paradox fails. That is because it is not a paradox.
Likewise, (if you prefer the Nelson-Grelling paradox, the words which were heterological were defined by that they did not describe themselves, as homological or autological words did, i.e., there was a material aspect which was peculiar to the category in which they were contained, i.e., autological. But they too described themselves and not other words. The terms autological and heterological were set definitions, words that defined other words, not themselves (the barber). The words they described, described only themselves and not other words. Apples and oranges. So there must be by definition a third set of words to which autological and heterological belong for the criteria by which the words they contain are defined as belonging to one set or the other are not part of what describe the terms autological and heterological. It is that simple. No paradox, no contradictions and no challenges to logic. You guys are ignoring the contexts in which all of this is considered.
Frege was right, Russell was wrong and Nelsen/Grelling were wrong.
Um ackchyually separation is not an axiom
There is a class of all sets though, which must be pretty big lol.
Only in set theories which contain classes, though, such as von Neumann-Bernays-Gödel set theory. Classes don't exist in Zermelo-Fraenkel set theory except as syntactical shorthand for predicates.
I may be way off here but if the set of all sets existed would that imply it is CLOSED? Hence that would imply EVERY set (subset) in the set of all sets would be CLOSED also which is obviously false hence the "set of all sets" can't exist.
Wait... what... Did he just prove that "there is no spoon" or that there is absolutely a spoon.
Sabine Hossenfelder must see this.
I've got no sets from sushi WOK which could be the set of all sets...
I've always found Russel's Paradox to be a particularly weak argument. What the contradiction proves is that EITHER the general comprehension principle is not valid OR that P(x) is not a well-defined "definite condition" (which wasn't defined in the first place). The usual examples seem to be sets that are merely poorly defined, not sets illustrating fundamental flaws in 19th-century set theory. It gets more interesting with the set of all sets example when you start asking questions like does this set contain its own power set.
Peter Grey said '... OR that P(x) is not a well-defined "definite condition" (which wasn't defined in the first place).'
P(x) being a well-defined "definite condition" means that P(x) is a well-formed statement in the language of ZFC (which uses first order logic and the undefined predicate "in").
As an aside, the set of all people who voted in the last US presidential election is not a set in ZFC since it is not a well-formed statement in the language of ZFC (since 'people' or 'person' or 'US' or 'election' etc cannot be defined in ZFC).
3:23 Yo did this man just assume that ZF set theory is consistent? That's cringe, bro.
No, not at all ... he was just explaining the meaning of the word 'axiom.'
What made you think he said anything at all about the consistency of ZF? I'm pretty sure he knows Gödel's theorems and wouldn't make mistakes like that.
@@nHans If ZF is inconsistent, i.e. can prove a contradiction, then every statement can be proved from it (this is the logical Principle of Explosion). Therefore in particular, ZF is inconsistent => its axioms can be proved true(and simultaneously proved false), so by taking the contrapositive, if the axioms of ZF can't be proved true(/false) then ZF is consistent.
(Note: whenever I say "proved" I mean "proved within ZF itself"; the axioms of ZF *can* be proved true by more powerful set theories, whose axioms can be proved true by yet more powerful set theories, and so on. But no sufficiently-expressive theory can prove its own axioms true by Goedel's incompleteness theorems)
@@schweinmachtbree1013 I appreciate the effort you took to reply. But unfortunately you're wrong.
Axioms _cannot_ be proved. That's by definition.
*_Consistency_* of a theory is a different issue. Gödel proved that a sufficiently-expressive theory:
- if it is _consistent,_ it *cannot* prove its own _consistency._
- if it is _inconsistent,_ paradoxically, it can prove that it is _consistent._ Kinda like a liar saying _"I always tell the truth."_
It is not known whether ZF(C) is consistent or not. However, it is generally believed to be consistent, because no inconsistencies or contradictions have been found till date.
The OP thought that Prof. Penn assumed that ZF was consistent. I assured them that Prof. Penn had made no such assumption.
@@nHans Axioms _can_ be proved. In a theory T with an axiom p, the proof of p is the one line proof "p". Hence T ⊢ p. The motto "axioms cannot be (non-trivially) proved" is not a definition; it is just a description which gives intuition for what an axiom is.
I will reiterate (replacing "true/false" by "false" since I have just explained that a theory entails its axioms): ZF is inconsistent => ZF ⊢ ¬Seperation (by Explosion), and hence by contraposition, ZF ⊬ ¬Separation (i.e. Separation cannot be proved false) => ZF is consistent. Therefore Michael's claim that "the Axiom of Separation is not provable to be false" implies the consistency of ZF/ZFC.
Too many x's. Try better variable names. Thanks!
3SECONDS LATE
Cheese and Rice - at least spell his name correctly. It is Russell !!!!!!
What do you call a guy with no arms and no legs in a pile of leaves?
Rustle! :-D
You just have to think of ‘does 5 belong to two sets’ to see that this is arbitrarily wrong. Anything can belong to anything in mathematics because it’s all imaginary, and any construction of a set is fine, it’s just a matter whether it is useful or not.
1 Corinthians 15:27 in the Bible is interesting in that it recognizing this type of contradiction where all has something referencing itself. It clears that up by limiting “all” to not include itself. Not sure I said that right.
“For he hath put all things under his feet. But when he saith all things are put under him, it is manifest that he is excepted, which did put all things under him.”
The super set paradox is such a better name than the arrogant ignorant filth term our planets main trash species uses for it instead. Though that naming is very much indicative of human ideation in general, and explains so much of what is wrong with us nowadays. We honestly think we create math, and that concepts can be owned, what exploitative jokes
Calm down bro
Can I define you to not exist?
@ firefool125 -- You need to remove your propaganda from here. It certainly has nothing to do with this subject matter.