Re:List of unusual Wikipedia articles
by martincmartin on Saturday January 02, 2010 @05:10PM
(#1027752)
Yes, and that's not a contradiction.
The problem comes with the set of all sets that don't contain themselves. Does that set contain itself? Both "yes" and "no" lead to contradiction. That contradiction is the basis of Godel's Incompleteness Theorem, the Halting Problem and others.
Re:List of unusual Wikipedia articles
by gambling8nt on Saturday January 02, 2010 @09:15PM
(#1028069)
The collection of all sets is not a set under ZF set theory, regardless of choice.
Such a collection, if it were a set, would imply the existence of a set of all sets that did not contain themselves from the axiom schema of specification.
Re:List of unusual Wikipedia articles
by gambling8nt on Saturday January 02, 2010 @09:39PM
(#1028093)
As noted above, the collection of all sets cannot be a set in any set theory with specification, regardless of regularity:
Call the collection of all sets S. We specify T by
T=\{x| x \in S \wedge \neg x \in x\}
T is then the subclass of S of sets that do not contain themselves. Thus with specifiction (provable from replacement, or as an axiom by itself), it is contradictory for S to be a set.
If you reject the law of excluded middle, you can have a intuitionist set theory where S is neither a set nor not a set; alternatively, you can have a set theory without specification one constructed based on a type theory might meet this requirement.
Back to the main topic, I think in naive set theory a set of all sets will contains itself. Russell Paradox is problematic when asking the negated statement, i.e. whether a list of all lists that do not contain themselves contains itself.
Does the set that contain all sets contain itself?
The problem comes with the set of all sets that don't contain themselves. Does that set contain itself? Both "yes" and "no" lead to contradiction. That contradiction is the basis of Godel's Incompleteness Theorem, the Halting Problem and others.
Such a collection, if it were a set, would imply the existence of a set of all sets that did not contain themselves from the axiom schema of specification.
http://en.wikipedia.org/wiki/Axiom_of_regularity
But there may well be set theories where it is well-defined, hence does contain itself.
Call the collection of all sets S. We specify T by
T=\{x| x \in S \wedge \neg x \in x\}
T is then the subclass of S of sets that do not contain themselves. Thus with specifiction (provable from replacement, or as an axiom by itself), it is contradictory for S to be a set.
If you reject the law of excluded middle, you can have a intuitionist set theory where S is neither a set nor not a set; alternatively, you can have a set theory without specification one constructed based on a type theory might meet this requirement.
Back to the main topic, I think in naive set theory a set of all sets will contains itself. Russell Paradox is problematic when asking the negated statement, i.e. whether a list of all lists that do not contain themselves contains itself.