Set which contains all of it's subsets

[Berrius]

Homework Statement

Prove a set which contains all of it's subsets doesn't exist.

The Attempt at a Solution

Suppose such a set P exists. P := {x | x \in \wp(x)}.
P \in \wp(x), so P \in P.
This seems like a paradox to me, so all I have to prove is that a set can't contain itself. But how? I've got a gut feeling it's closely related with Russels paradox, but I can't get it.

 

[nonequilibrium]

Have you proven that the power set of a set is always strictly larger?

There's no need to get involved with fundamental things like Russell's paradox. This is more basic.

 

[Berrius]

Have you proven that the power set of a set is always strictly larger?

There's no need to get involved with fundamental things like Russell's paradox. This is more basic.

Yes I've proven that there doesn't exist a surjection f: S \rightarrow \wp(S), but there exists an injection.

 

[nonequilibrium]

Say X is the set in your problem, the one that contains all its subsets.

How do X and its power set relate in this case?

 

[Fredrik]

I don't know if the axioms rule out the possibility of a set that is a member of itself. I'm guessing that they don't.

I would avoid constructions of the form {x|x has property P}, because that's what's gets us into trouble in the case of Russell's paradox. The axiom schema of comprehension says that {x∈A|x has property P} is allowed when A is a set, but not that {x|x has property P} is allowed. So I would start in a different way, specifically with the sentence "Suppose that there's a set A such that $x\subset A\Rightarrow x\in A$.", and then try to derive a contradiction from that.

Hint: Cardinality. (I think that's a good hint, but I haven't made absolutely sure that my idea works).

 

[Berrius]

Say X is the set in your problem, the one that contains all its subsets.

How do X and its power set relate in this case?

X would be it's power set, and thus there would be a bijection between them. However I've proven there doesn't exist a bijection. In other words, X and it's power set have the same cardinality (if X exists), but I've proven the power set is bigger than X, so there is a contradiction and thus X doesn't exist.

Is this correct?

 

[nonequilibrium]

Yes :) but as you don't seem to be sure of yourself, let me say it more succinctly: there is no surjective function from X to its power set, which there would be if X equaled its power set.

 

[Deveno]

I don't know if the axioms rule out the possibility of a set that is a member of itself. I'm guessing that they don't.

(snip)

yes, they do. this is a consequnce of the axiom of regularity, and the axiom of pairing:

let A be a set. then {A,A} = {A} is a set, by the axiom of pairing.

by the axiom of regularity, {A} contains an element B such that {A} and B are disjoint. but the only element of {A} is A. therefore, A and {A} are disjoint.

since A is in {A}, A cannot be in A (by the definition of "disjoint").

(if a set could be a member of itself, we could form "the set of all sets", which is a problemmatic construction, and quite similar to, but not quite the same as, Russell's paradox).

 

[Fredrik]

yes, they do. this is a consequnce of the axiom of regularity, and the axiom of pairing:

let A be a set. then {A,A} = {A} is a set, by the axiom of pairing.

by the axiom of regularity, {A} contains an element B such that {A} and B are disjoint. but the only element of {A} is A. therefore, A and {A} are disjoint.

since A is in {A}, A cannot be in A (by the definition of "disjoint").

Thanks, that proof was very clear. I've been wondering about this.

if a set could be a member of itself, we could form "the set of all sets"...

I don't see how this implication is true. Because of your proof, it's clear that we can't introduce a set that's a member of itself without first dropping (or weakening) some of the ZF axioms, so suppose that we drop enough of them to make your proof invalid, and then add an axiom that says "there's an A such that A∈A". Does this really imply that there's a set that contains all sets?

 

[micromass]

(if a set could be a member of itself, we could form "the set of all sets", which is a problemmatic construction, and quite similar to, but not quite the same as, Russell's paradox).

ZF with the axiom of regularity is just as consistent as ZF without the axiom. So the axiom of regularity is not the one that prevents problematic constructions. Rather, it is the limited comprehension scheme that prevents a set of all sets, not the regularity axiom.

Furthermore, not all people consider the axiom of regularity as a basic axiom.

 

[Deveno]

ZF with the axiom of regularity is just as consistent as ZF without the axiom. So the axiom of regularity is not the one that prevents problematic constructions. Rather, it is the limited comprehension scheme that prevents a set of all sets, not the regularity axiom.

Furthermore, not all people consider the axiom of regularity as a basic axiom.

yes, many people see regularity as a "useless axiom" (and some people don't even include it, choosing to use the axiom of infinity instead).

and, regularity does not "solve" Russell's paradox. what regularity says is:

all sets are "well-founded". that is, no set is "infinitely recursively defined in terms of smaller sets". every set "starts somewhere". now there are some good reasons for considering "non-well-founded" set theories (just as the natural numbers are (often) defined impredicatively, but this doesn't really lead to any problems), merging data streams is a good example.

you and Fredrik are correct, however, the "absence of regularity" doesn't imply that there is a "set of all sets". i don't know what i was thinking...probably something along the lines of:

if A∈A is allowable, then for all subsets of the class V of all sets, we could have V∈V...but that doesn't even make sense in NGB, because a∈b is undefined if a is not a set.

*****

however, just because two theories are "equi-consistent" is not, in itself, a reason to favor one or the other. ZFC+CH is equi-consistent with ZFC+(¬CH), which leads one to wonder...should we think of the CH as true, untrue, or both/neither? moreover, sometimes a "minimal axiom system" is less useful than a redundant one: classical logic can be reduced entirely to "nands" or "nors", but doing so obscures the ways we think and speak about things we feel are true (although logical circuits don't seem to mind...).