ZFC and Russell's Paradox

**Euclid** · Nov8-04, 10:41 PM

How does ZFC manage to block Russell's paradox? I've read through the axioms extensively, and it's not clear how to prove Russell's paradox is impossible.
In particular, I'm talking about Russell's paradox that shows {x| x not in x} is not a well-defined set.

**zefram_c** · Nov8-04, 11:06 PM

Basically, what ZFC does NOT have is an axiom that says every predicate can define a set. What it does have in its stead is an axiom that every predicate can define a subset of an existing set, plus a few other axioms to make up for the lost functionality. Hence there is no way to define Russell's set through the axioms of ZFC.

**Hurkyl** · Nov8-04, 11:19 PM

it's not clear how to prove Russell's paradox is impossible.

I presume you see why Russel's construction isn't directly applicable: because the axiom of extensionality has been replaced with the axiom of subsets (and a few other axioms denoting how to "safely" construct sets).

In particular, you are only allowed to say:

{ x in A | x not in x }

and not

{ x | x not in x }

So I guess your asking whether or not there's some clever alternate way to do it. Here, you're getting into some sticky territory: in order to talk about what ZFC can and cannot do, you have to adopt some external theory which is capable of talking about such things, which begs the question of why the external theory is valid... I don't think you can get a completely satisfying answer to your question, just that nobody has yet managed to discover any contradictions in ZFC.

**Euclid** · Nov8-04, 11:28 PM

Originally Posted by zefram_c

Basically, what ZFC does NOT have is an axiom that says every predicate can define a set. What it does have in its stead is an axiom that every predicate can define a subset of an existing set, plus a few other axioms to make up for the lost functionality. Hence there is no way to define Russell's set through the axioms of ZFC.

Yeah I see that, but I'm still confused about something. It seems to me that in ZFC there's no really effective way to prove that something is not a set. I can prove that if x and y are sets then so is {x,y}, and I can prove if {x,y} is a set so are {x} and {y}. But is it the case, according to ZFC, that if x is a set, then x is a proper subset of some set y? If this is so, then I am happy. We can then say Russell's set can't exist, because it's not contained in any larger set (how we would prove that it's not contained in any larger set I guess would be another issue).

**Hurkyl** · Nov8-04, 11:38 PM

Well, in ZFC, Russel's paradox is a proof that the class of sets that do not contain themselves is not, itself, a set. (because if it was a set, then we get a contradiction)

**Euclid** · Nov9-04, 01:04 AM

Originally Posted by Hurkyl

Well, in ZFC, Russel's paradox is a proof that the class of sets that do not contain themselves is not, itself, a set. (because if it was a set, then we get a contradiction)

I agree. Doesn't that make Russell's paradox kind of trivial?

**zefram_c** · Nov9-04, 02:04 AM

Trivial? Only in the sense that it is now a theorem of the system (there is no set that satisfies a certain property), rather than a contradiction within the system.

**matt grime** · Nov9-04, 07:26 AM

Deciding whether something is or isn't a set depends on the model ZF you use.

A model of ZF consists of a S** of things, where S** means a naive collection of objects. This collection must satisfy the axioms of ZF. The things in the collection are called the sets in the model.

You might have seen this idea before if you've studied groups or vector spaces.

A vector space is a set satisfying some axioms, elements in the vector space are vectors. And just as the vector space is not a vector neither is the S** a set.

A common way to show something isn't a set is to demonstrate that it doesn't satisfy some axiom or other, or has cardinality strictly greater than any set cardinal.

Let's do 3 analogies, since they are easier:

Is the 2x2 matrix whose entries are a_11 = 1 a_12 = 1 a_21=0 a_22 = 1 an element of a group? Well, we find a group of which it is an element, which is elementary (it is a member of the group of all two by two invertible matrices under multiplication).

The matrix given by 1,0,0,0 resp in that list can never be a member of a matrix group where the operation is matrix multiplication, but it might be an element in some other model, and indeed is.

Can the elements a,b,c be elements of a group where a,b,c are all distinct and ab=a=ac? No, this can never happen since then b and c would both be distinct identity elements, so no model of GROUP can have elements that behave like that.

Deciding if something is or isn't a set in some model, or if there is a model in which it is a set is very hard, don't expect there to be easy examples.

Note this post owes a lot to an article I read by Tim Gowers.

**CrankFan** · Nov9-04, 03:06 PM

Originally Posted by Euclid

How does ZFC manage to block Russell's paradox? I've read through the axioms extensively, and it's not clear how to prove Russell's paradox is impossible.
In particular, I'm talking about Russell's paradox that shows {x| x not in x} is not a well-defined set.

Did you take a look at the axiom of Regularity/Foundation ?

No set (of ZF) contains itself as a member, thus the "set of all sets not containing themselves as members" is the class of all sets; which isn't a set (in ZF).

**Euclid** · Nov9-04, 11:20 PM

Originally Posted by matt grime

Deciding whether something is or isn't a set depends on the model ZF you use.

A model of ZF consists of a S** of things, where S** means a naive collection of objects. This collection must satisfy the axioms of ZF. The things in the collection are called the sets in the model.

You might have seen this idea before if you've studied groups or vector spaces.

A vector space is a set satisfying some axioms, elements in the vector space are vectors. And just as the vector space is not a vector neither is the S** a set.

A common way to show something isn't a set is to demonstrate that it doesn't satisfy some axiom or other, or has cardinality strictly greater than any set cardinal.

Let's do 3 analogies, since they are easier:

Is the 2x2 matrix whose entries are a_11 = 1 a_12 = 1 a_21=0 a_22 = 1 an element of a group? Well, we find a group of which it is an element, which is elementary (it is a member of the group of all two by two invertible matrices under multiplication).

The matrix given by 1,0,0,0 resp in that list can never be a member of a matrix group where the operation is matrix multiplication, but it might be an element in some other model, and indeed is.

Can the elements a,b,c be elements of a group where a,b,c are all distinct and ab=a=ac? No, this can never happen since then b and c would both be distinct identity elements, so no model of GROUP can have elements that behave like that.

Deciding if something is or isn't a set in some model, or if there is a model in which it is a set is very hard, don't expect there to be easy examples.

Note this post owes a lot to an article I read by Tim Gowers.

Can we think of S** as a structure in the same way we do in group theory? Is a model in ZF the same thing as a group or a vector space in that the things in them are just things that satisfy certain properties, and we just happen to call these things "sets" (I'm just trying to reiterate in my own words what you were saying)? Are there substructures? Could I take the Model generated by {}, for instance?
That is a very interesting analog you make. I'm so used to thinking of some things as sets, and the things in them elements.

**Euclid** · Nov9-04, 11:22 PM

Originally Posted by CrankFan

Did you take a look at the axiom of Regularity/Foundation ?

No set (of ZF) contains itself as a member, thus the "set of all sets not containing themselves as members" is the class of all sets; which isn't a set (in ZF).

I looked at that axiom repeatedly and never been able to make sense of it:
Every non-empty set x contains some element y such that x and y are disjoint sets.
In my naive way of thinking, I thought, {1} is not empty, but 1 and {1} aren't disjoint sets.... 1 isn't even a set!

**CrankFan** · Nov10-04, 12:42 AM

Originally Posted by Euclid

Every non-empty set x contains some element y such that x and y are disjoint sets.

suppose that $LaTeX Code: x \\in x$

(1) Then we have $LaTeX Code: x \\in (\\lbrace x \\rbrace \\cap x)$

By what you state above (regularity) there is a member $LaTeX Code: y \\in \\lbrace x \\rbrace$ whose intersection with $LaTeX Code: \\lbrace x \\rbrace$ is the empty set.

Since $LaTeX Code: \\lbrace x \\rbrace$ has just 1 member

, it follows that $LaTeX Code: \\lbrace x \\rbrace \\cap x = \\emptyset$ . Thus (1) is contradicted.

**matt grime** · Nov10-04, 06:52 AM

When you think of 1 you aren't thinking of it as a set, but there is a formulation of the natural numbers that makes it a set - it is the set containing the empty set - this is the axiom of infinity in action.

I think you're getting the right idea about what a "set theory" is, or a model of one.

The model is the collection of objects that satisfy the axioms, and the elements in the model of a set theory are called sets.

It is slightly different from the usual way round. A model of the group axioms is a group, but the elements in it are group elements. A model of the axioms of vector space is a vector space and the elements in it are vectors. The model of a set theory doesn't have such a nice name, but the elements in it are sets.

Every model of ZF must contain the empty set and an inductive set (something like the Naturals). It's a little tricky to ask for the smallest model generated by these sets since small usually is defined in terms of sets themselves. Ie one model will be smaller if it is contained in another but that's a set property, though you may be able to formulate a way round this. (I'd think of SET as category to get round this).