Proving Nothing Contains Everything: Set Theory and Russell's Paradox

[evagelos]

how do we prove in set theory that ,nothing contains everything

 

[enigmahunter]

We prove "There is no set that contains every set.".
For an arbitrary set U, we construct a set A not belonging to U.

Let A = {x∈U | x ∉ x }.
Then, x∈A <--> x∈U & x ∉ x (Axiom schema of specification).
Let x be A.
Then, A∈A <--> A∈U & A∉A.
If A∈U, then this reduces to
A∈A <--> A∉A, which is impossible.
Thus, A ∉ U.

 

[HallsofIvy]

that is, of course, a play on words. You can interpret "nothing contains everything" as "everything is contain in (something we call) nothing" or, with a slight change in meaning, there is nothing (no set as enigmahunter said) that contains everything.

A non-mathematical variation: $1 is better than nothing, and nothing is better than a milliion dollars. Therefore $1 is better than a million dollars.
(Actually, I've "cleaned" that up a bit.)

 

[evagelos]

In this forum when another guy asked for the ZFC axioms to be written down so any proof coming out of those axioms could be checked for its logical reasoning the reactions he got where:

a) no person in the right mind would prove this straight from the axioms

b) leave set theory to the set theorists

So when you write , Axiom schema of specification,please write down this Axiom schema and show please how you formed set A out of this schema

 

[Hurkyl]

Do you have a question, or are you just trolling?

 

[evagelos]

Please get rid of that expression,my question is how he gets A using the Axiom schema of specification

 

[enigmahunter]

Let B = $$\{x \in A | P(x)\}$$.

Axiom schema of specification (comprehension) says,

"Let P(x) be a property of x. For any set A, there is a set B such that $$x \in B$$ iff $$x \in A$$ and P(x)."

The above proof basically used x $$\notin$$x for P(x).

If we simply define B = {x | P(x)} and x $$\notin$$ x for P(x), as you know, it ends up with a "http://en.wikipedia.org/wiki/Russell_paradox" " (B is not a set).

 

[LukeD]

The problem isn't that someone is asking for them; it's that they're asking the people on the forum when you can just look them up very easily. Mathematicians get worried when someone asks for help with looking up something that they believe the person already knows how to find.

 

[Dragonfall]

In this forum when another guy asked for the ZFC axioms to be written down so any proof coming out of those axioms could be checked for its logical reasoning the reactions he got where:

a) no person in the right mind would prove this straight from the axioms

b) leave set theory to the set theorists

So when you write , Axiom schema of specification,please write down this Axiom schema and show please how you formed set A out of this schema

Trooooooooooooooooolllllllllllllllllllllllllllll.

 

[evagelos]

Let B = $$\{x \in A | P(x)\}$$.

Axiom schema of specification (comprehension) says,

"Let P(x) be a property of x. For any set A, there is a set B such that $$x \in B$$ iff $$x \in A$$ and P(x)."

The above proof basically used x $$\notin$$x for P(x).

If we simply define B = {x | P(x)} and x $$\notin$$ x for P(x), as you know, it ends up with a "http://en.wikipedia.org/wiki/Russell_paradox" " (B is not a set).

If what you wrote can be taken as one of the axioms of ZFC theory,why then when PoutsosA asked the forum to mention the axioms of ZFC theory as a point of reference,instead of that he/she got the answers that i mentioned in my post #4??

 

[Dragonfall]

how do we prove in set theory that ,nothing contains everything

We can prove in my set theory, in which there is only 1 set, and it contains itself, that there is in fact something containing everything!

 

[evagelos]

I believe you can do everything, you can even call other people names and get away with it,but there is one thing you cannot do is to give a formal proof of the above

 

[CRGreathouse]

We can prove in my set theory, in which there is only 1 set, and it contains itself, that there is in fact something containing everything!

Sure. Take predicate calculus with equality, add extensionality and the axiom
$$\exists x\forall y, y\in x\wedge y=x.$$

The axioms of union and choice follow; the axioms of power set, infinity, and regularity (of course!) fail.

 

[Dragonfall]

Does infinity really fail? I got to think about this a bit...

 

[OmCheeto]

that is, of course, a play on words. You can interpret "nothing contains everything" as "everything is contain in (something we call) nothing" or, with a slight change in meaning, there is nothing (no set as enigmahunter said) that contains everything.

A non-mathematical variation: $1 is better than nothing, and nothing is better than a milliion dollars. Therefore $1 is better than a million dollars.
(Actually, I've "cleaned" that up a bit.)

That reminds me of a paradox my brother told me about several decades ago.

He said that the inside of the house was much larger than the outside of the house.

This is because when you are inside, the entire house surrounds you. You cannot even touch the edges with your arms outstretched.

But when you go outside, walk a bit away, and face the house with your arm held out straight, you can squash the house like a little bug with just your thumb and forefinger.

I've yet to run across the proof though.

 

[Bob3141592]

A non-mathematical variation: $1 is better than nothing, and nothing is better than a milliion dollars. Therefore $1 is better than a million dollars.
(Actually, I've "cleaned" that up a bit.)

Can I borrow that dollar to buy a ham sandwich?

 

[CRGreathouse]

Does infinity really fail? I got to think about this a bit...

I guess it depends on how you define the axiom. The usual version asserts the existence of sets we don't have, like the empty set and the ordinals up to omega.

I think of the axiom of infinity as "there exists an inductive set containing the empty set" which requires an empty set.

 

[Dragonfall]

I guess it depends on how you define the axiom. The usual version asserts the existence of sets we don't have, like the empty set and the ordinals up to omega.

I think of the axiom of infinity as "there exists an inductive set containing the empty set" which requires an empty set.

I think so too, since Aczel's non-well-founded set theory still requires the infinity axiom.

I was thinking that if you have, say, $x\in x$, then you can "expand" it into x->x->x->x->... (an accessible pointed graph, as Aczel calls it), and then use "replacement" to change each x into a different set, then define a set that contains all of them, which is infinite.

But I'm guessing if we modify the axiom of replacement to be able to do what I suggest, it would probably be equivalent to infinity anyway.

 

[Hurkyl]

For an amusing aside, there are characterizations of the empty set that would allow it to exist in Dragonfall's one-set universe. e.g

. Z is the empty set iff, for any set Y, there is exactly one function Z --> Y
. Z is the empty set iff Z is a subset of every set

And even the usual characterization:

. Z is the empty set iff every x is not an element of Z

holds in one-valued logic.

 

[evagelos]

We prove "There is no set that contains every set.".
For an arbitrary set U, we construct a set A not belonging to U.

Let A = {x∈U | x ∉ x }.
Then, x∈A <--> x∈U & x ∉ x (Axiom schema of specification).
Let x be A.
Then, A∈A <--> A∈U & A∉A.
If A∈U, then this reduces to
A∈A <--> A∉A, which is impossible.
Thus, A ∉ U.

From A<--->AεU & Aε'Α, and AεU how do you get AεΑ <----> Aε'A ( A does not belong to A)

I am sorry i cannot follow.

Aε'Α means A does not belong to A

 

[CRGreathouse]

For an amusing aside, there are characterizations of the empty set that would allow it to exist in Dragonfall's one-set universe. e.g

. Z is the empty set iff, for any set Y, there is exactly one function Z --> Y
. Z is the empty set iff Z is a subset of every set

Yes, that is amusing. With either of those definitions the axiom of infinity holds in the model, of course, along with the null set axiom.

I tried to be cautious in my phrasing, since it wasn't obvious what the null set would represent in this one-set universe.

 

[enigmahunter]

From A<--->AεU & Aε'Α, and AεU how do you get AεΑ <----> Aε'A ( A does not belong to A)

& is used for a logical operater 'AND', so if AεU is true, AεU & Aε'Α <--> Aε'Α

 

[enigmahunter]

Interesting conversations are going on here ( I could not follow some of them).
It is known that "http://en.wikipedia.org/wiki/ZFC" ". Anyhow, ZFC still has some strengh over naive set theory as shown above (ex.Russell's paradox).

I am interested in constructive set theory (rather than ZFC) embed their set axioms in intuitionistic logic. I still don't know what advantages we can expect from it over traditional set theory (ex. ZFC) and first order logic.

Any opinion or example?

 

[Hurkyl]

Interesting conversations are going on here ( I could not follow some of them).
It is known that "Consistency of ZFC cannot be proved in ZFC", but still I don't know why.

Gödel's second incompleteness theorem.

I am interested in constructive set theory (rather than ZFC) embed their set axioms in intuitionistic logic. I still don't know what advantages we can expect from it over traditional set theory (ex. ZFC) and first order logic.

Any opinion or example?

I don't know if this is related to your interests, but the 'natural' internal logic of Cartesian categories is intuitionistic. (Most interesting mathematical theories take place in Cartesian categories) By internal, I mean that there is a way to interpret logical statements in terms of objects and arrows in the category. (As opposed to interpreting them in terms of sets and functions) Topos theory subsumes the idea of intuitionistic set theory (the ordinary category of sets, for example, is a topos. Don't forget that Boolean logic is intuitionistic!) -- which is very interesting because toposes describe other things too, such as the category of sheaves on a topological space.

While I don't know the field of constructive set theory, I would have imagined its logic would actually be weaker than intuitionistic logic...

 

[jcearley]

We prove "There is no set that contains every set.".
For an arbitrary set U, we construct a set A not belonging to U.

Let A = {x∈U | x ∉ x }.
Then, x∈A <--> x∈U & x ∉ x (Axiom schema of specification).
Let x be A.
Then, A∈A <--> A∈U & A∉A.
If A∈U, then this reduces to
A∈A <--> A∉A, which is impossible.
Thus, A ∉ U.

I understand how this answer was derived, but can anyone tell me how this holds up it seems that the definition of A doesn't holds up from the start violating the initial restraints of A not belonging to U. any help is appreciated Thanks

 

[disregardthat]

We prove "There is no set that contains every set.".
For an arbitrary set U, we construct a set A not belonging to U.

Let A = {x∈U | x ∉ x }.
Then, x∈A <--> x∈U & x ∉ x (Axiom schema of specification).
Let x be A.
Then, A∈A <--> A∈U & A∉A.
If A∈U, then this reduces to
A∈A <--> A∉A, which is impossible.
Thus, A ∉ U.

I understand how this answer was derived, but can anyone tell me how this holds up it seems that the definition of A doesn't holds up from the start violating the initial restraints of A not belonging to U. any help is appreciated Thanks

A not belonging to U was not a restraint, but what enigmahunter set out to prove.

 

[Owen4x]

We prove "There is no set that contains every set.".
For an arbitrary set U, we construct a set A not belonging to U.

Let A = {x∈U | x ∉ x }.
Then, x∈A <--> x∈U & x ∉ x (Axiom schema of specification).
Let x be A.
Then, A∈A <--> A∈U & A∉A.
If A∈U, then this reduces to
A∈A <--> A∉A, which is impossible.
Thus, A ∉ U.

I don't agree.
You have not shown that "There is no set that contains every set".
You have shown that {x:x∉x} is not a member of U, but you admit
that {x:x∉x} is not a set! To be a member of the set of all sets (U)
is to be an existent set.

To be a member of a set {x:Fx}, is to satisy Fx and {x:Fx} exists.
{x:x∉x} is not a set, indeed, there is no thing that {x:x∉x} is, including itself.
~({x:x∉x}={x:x∉x})

That is to say, {x:x∉x} does not exist, even though there are instances of the function
x∉x, eg. the set of cups is not a member of the set of cups, {cups}∉{cups}, and there is no set/class of those sets that are not members of themselves. {cups}∈{x:x∉x}, is false,
even though {cups}∉{cups} is true.

That {x:x∉x} does not exist, does not show that "There is no set that contains every set".

imo, There is a set that contains every set.
U =df ({x:x=x} & {x:x=x}exists).

 

[Hurkyl]

Let A = {x∈U | x ∉ x }.

the definition of A doesn't holds up from the start

What part of the definition do you have a problem with? This is well-formed set-builder notation for specifying the subset of an existing set. The left half indicates the superset, in this case U (which exists by hypothesis), and introduces the variable used in the predicate on the right-hand side which is again well-formed.

 

[Hurkyl]

Own4x, your post doesn't really make sense.

You have shown that {x:x∉x} is not a member of U,

On the hypothesis that U exists, it does indeed follow that {x:x∉x} is not a member of U.

but you admit that {x:x∉x} is not a set!

This is indeed a theorem of (standard) set theory that this notation does not define a set.

To be a member of the set of all sets (U)
is to be an existent set.

On the hypothesis that such U exists, it is a trivial exercise to show that {x:x∉x} is a set.

You don't appear to make sense talking about "existent sets" -- what could you possibly mean by a claim such as "S is a set, but S doesn't exist"?!

Anyways, it's a trivial exercise of logic to prove that if S is a set, then there exists a set to which S is equal.

no set/class of those sets that are not members of themselves.

What definition of "class" are you using? For the ones I'm familiar with from ZFC or from NBG, it is an utterly trivial fact that there is a class of sets that are not members of themselves. (and by the axiom of foundation, this class is equal to the class of all sets)

imo, There is a set that contains every set.
U =df ({x:x=x} & {x:x=x}exists).

The right hand side of this definition is not in a notation I'm familiar with...

 

[Owen4x]

Hurkyl: "Own4x, your post doesn't really make sense."

?

Originally Posted by Owen4x
You have shown that {x:x∉x} is not a member of U,

Hurkyl "On the hypothesis that U exists, it does indeed follow that {x:x∉x} is not a member of U."

Whether 'U exists' or not, {x:x∉x} is not a member of any set/class...{x:x∉x} does not exist.but you admit that {x:x∉x} is not a set!

Hurkyl "This is indeed a theorem of (standard) set theory that this notation does not define a set."To be a member of the set of all sets (U) is to be an existent set.

Hurkyl "On the hypothesis that such U exists, it is a trivial exercise to show that {x:x∉x} is a set."

Nonsense! There is no entity that is equal to {x:x∉x} is provable within FOPL=
~EyAx(xRy <-> ~(xRx)) is a theorem. That is, ~EyAx(x e y <-> ~(x e x)) is true.


Hurkyl "You don't appear to make sense talking about "existent sets" -- what could you possibly mean by a claim such as "S is a set, but S doesn't exist"?!"

I guess you have not heard about "purported" entities.
Any purported entity described by a contradictory predication does not exist.
Non-referring descriptions are not unheard of.

For example ... The present king of France, describes a purported person who does not exist.
That natural number between 2 and 3, describes a purported natural number which does not exist.
The x such that Fx & ~Fx, describes a purported object which does not exist.

The 'purported' set {x:x∉x} does not exist.no set/class of those sets that are not members of themselves.

Hurkyl "What definition of "class" are you using? For the ones I'm familiar with from ZFC or from NBG, it is an utterly trivial fact that there is a class of sets that are not members of themselves. (and by the axiom of foundation, this class is equal to the class of all sets)"

Classes are sets, ..collections of entities. If {x:x∉x} does not exist, then surely there is no set or class that it is equal to.
IMO, You, Zermelo, and von Neumann are wrong on this point. {x:x=x} is the class/set of all classes/sets
imo, There is a set that contains every set.
U =df ({x:x=x} & {x:x=x}exists).

Hurkyl "The right hand side of this definition is not in a notation I'm familiar with... "

What?! You have used this expression in your reply,
"On the hypothesis that U exists..."

(x exists) <-> EF(Fx), (x exists) <-> Ey(x=y), (x exists) <-> x=x, etc..

 

[Hurkyl]

Your post would be easier to follow if you used the quote feature...

(In my writing, I use "class" in standard set-theoretic fashion, rather than the way you are using it)

Whether 'U exists' or not, {x:x∉x} is not a member of any set/class...{x:x∉x} does not exist.

It is true that "the class {x:x∉x} is not a set" is a theorem of ZFC.

It is also (vacuously) true that "If the class of all sets is itself a set, then the class {x:x∉x} is a set" is also a theorem of ZFC.

There is no entity that is equal to {x:x∉x} is provable within FOPL=
~EyAx(xRy <-> ~(xRx)) is a theorem. That is, ~EyAx(x e y <-> ~(x e x)) is true.

"~S is a theorem" does not imply "S is not a theorem". You are implicitly assuming consistency -- an assumption that fails for the hypotheses "ZFC + there is a set of all sets".

Not to be flippant, but you do know what a "proof by contradiction" is, right?

I guess you have not heard about "purported" entities.
Any purported entity described by a contradictory predication does not exist.
Non-referring descriptions are not unheard of.

I'm more familiar with the phrase "well-formed" -- and a set of symbols that violates the grammar of the formal language of interest.

In this case, however, {x:x∉x} is well-formed, denoting a class of sets. On the hypothesis that there is a set of sets, direct application of the axiom of subsets implies that {x:x∉x} actually defines a set.

Now, {x:x∉x} isn't what was originally written. What was originally written was

{x∈U | x ∉ x }​

which is plain ordinary set-builder notation. Given any set S and any formula P, the notation

{x∈S | P(x) }​

denotes a set, specifically the particular set whose existence is guaranteed by the axiom of subsets.



For example ... The present king of France, describes a purported person who does not exist.
That natural number between 2 and 3, describes a purported natural number which does not exist.
The x such that Fx & ~Fx, describes a purported object which does not exist.

The 'purported' set {x:x∉x} does not exist.

Classes are sets, ..collections of entities. If {x:x∉x} does not exist, then surely there is no set or class that it is equal to.

If you mean "set", then why the heck are you using the word "class", particularly since you are not using the word to mean what (standard) set-theory means by the word?

{x:x=x} is the class/set of all classes/sets

Class. Not a set. And {x:x=x} = {x:x∉x}.

What?! You have used this expression in your reply,

The main thing I was complaining about is that the types don't make sense -- you are applying the operator "&" when the left argument is a class and the right argument is a predicate.

Of course, I would also complain about the odd logic you are using -- one that allows strings of symbols that would ordinarily be ill-formed, instead using some sort of modal operator to capture the notion. I know such things are possible, but such a thing is definitely not first-order predicate logic.

 

[xxxx0xxxx]

how do we prove in set theory that ,nothing contains everything

The proof is by contradiction, see Suppes, 1960. It is the result of Russell's paradox, because the existence of the set of everything would make the axiom schema of separation unnecessary, and in fact reduces the schema of separation to the schema of abstraction; but the schema of abstraction leads to Russell's paradox which is contradictory.

BTW, this is a result found in ZF and NBG; In NBG the class of all things exists, but it is not a set.