# ZFC and Russell's Paradox

1. Nov 8, 2004

### 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.

2. Nov 8, 2004

### 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.

3. Nov 8, 2004

### Hurkyl

Staff Emeritus
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.

4. Nov 8, 2004

### Euclid

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).

5. Nov 8, 2004

### Hurkyl

Staff Emeritus
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)

6. Nov 9, 2004

### Euclid

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

7. Nov 9, 2004

### zefram_c

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.

8. Nov 9, 2004

### 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.

Last edited: Nov 9, 2004
9. Nov 9, 2004

### 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).

10. Nov 9, 2004

### Euclid

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.

Last edited: Nov 9, 2004
11. Nov 9, 2004

### Euclid

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!

12. Nov 9, 2004

### CrankFan

suppose that $$x \in x$$

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

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

Since $$\lbrace x \rbrace$$ has just 1 member $$x$$, it follows that $$\lbrace x \rbrace \cap x = \emptyset$$. Thus (1) is contradicted.

13. Nov 10, 2004

### matt grime

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).

14. Feb 24, 2011

### AdamFiddler

The axiom of extensionality has not been replaced by the "axiom of subsets" as you call it. In fact, it is extensionality that allows the fact that any set created as a subset subject to given properties is unique.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook