Russell's paradox, ZF and Gödel's undecidability

[quasar987]

I'll be giving a small talk to the graduate students of my university on the topic of "counter-examples" and my first counter-example is Russell's paradox.

I want to put the theorem in context, but admitedly, I have no idea what I'm talking about when it comes to logic and set theory. I want to know if what I wrote is not too much nonsense.

I first cite the definition of set given by Cantor:

"By a "set" we mean any collection M into a whole of definite, distinct objects m (which are called the "elements" of M) of our perception or of our thought."

Then I say that this vague definition leads to paradoxes and presents Russell's paradox.

Then I say that it is paradoxes of this kind that led mathematicians to look for an axiomatic theory of sets. I say that the commonly used set theory today is that of Zermelo and Fraenkel, in which the problematic "set" in Russell's paradox is not one in the ZF theory. However, I add, according to the works of Gödel, it is impossible to determine if the ZF set theory is or is not free of pardoxes.

Given that what I wrote is not wrong, do you have suggestions for improvements or things I could add?

Thanks!

 

[Timmo]

Then I say that this vague definition leads to paradoxes and presents Russell's paradox.

How is Russell's paradox supposed to provide a counter-example to Cantor's "definition" of a set? As Cantor says, a set is a collection of distinct objects. (One can also study multi-sets, collections in which some of the objects may be identical to one another.)

Russell's paradox appears in Naive Set Theory, which is based on the following two principles:

(A) For every property P, there is a set S whose members are exactly those things which are P.

(B) For every set S and T, if S and T have the same members, then they are identical S = T.

Together (A) and (B) form an intuitively appealing basis for set theory, and they are powerful enough to serve as a "foundation" for mathematics. According to (A), if you are given some property or condition, you can collect together the things which have that property or satisfy that condition into a single set. So, there is a set whose members are all and only those things which are wolves, or a set whose members are all and only those things which are singletons, or whatever -- For every property P, there is a set of P's.

What makes this approach to set theory "naive" is that a number of logical contradictions follow from (A), including Russell's Paradox. Here's how it goes:

(1) For every property P, there is a set S such that: for every x, x is a member of S if and only if x is P. [from (A)]

(2) There is a set S such that: for every x, x is a member of S if and only if x is not a member of x. [from (1)]

(3) For every x, x is a member of R if and only if x is not a member of x. [naming the set mentioned in (2) as R]

(4) R is a member of R if and only if R is not a member of R. [from (3)]

(5) R is a member of R and R is not a member of R. [from (4)].

Contradiction! The problem is just this: if for every property P, there is a set of the P's, then there will be a set R whose members are exactly those things which are not members of themselves. We can then ask about R whether it is a member of itself or not. R is a member of itself if and only if it ain't a member of itself!

What this shows is that a natural and intuitive principle (A) is, in fact, problematic. To formulate a consistent axiomatic basis for set theory, one needs to search for other principles. ZF set theory is based on a set of principles which have been selected precisely because they are believed to avoid this kind of problem.

However, it is unclear to me how the inconsistency of Naive Set Theory shows that Cantor's notion of a set is inconsistent. A set is just a collection of distinct objects. This is part of ZF, too.

"However, I add, according to the works of Gödel, it is impossible to determine if the ZF set theory is or is not free of pardoxes."

The Gödel results require that ZF is either inconsistent or incomplete. It does not mean we cannot determine which. After all, somebody tomorrow might find out of that ZF has a hidden contradiction buried inside it by accidentally deducing it -- this is possible!

 

[daveyinaz]

...and why are you giving a talk on things you have "no idea" about? Seems like you should find a demonstration in which you have a better understanding of...

 

[Preno]

Then I say that it is paradoxes of this kind that led mathematicians to look for an axiomatic theory of sets. I say that the commonly used set theory today is that of Zermelo and Fraenkel, in which the problematic "set" in Russell's paradox is not one in the ZF theory. However, I add, according to the works of Gödel, it is impossible to determine if the ZF set theory is or is not free of pardoxes.

Well, what do you mean "determine"? You have to be more subtle here.

If by determining the consistency of a formal theory you mean proving its own consistency within the theory itself, you're right, of course. But that's an irrelevant notion of determining a theory's consistency. For one thing, every inconsistent theory can prove its own consistency. So proving the consistency of ZF within ZF wouldn't imply that ZF is consistent (unless you already believed it is). For another, you can prove that consistency of Peano Arithmetic cannot be proved within Peano Arithmetic, but that doesn't mean that yo can't determine whether it's consistent or not. (One could argue that) PA is consistent, because its axioms are clearly true (and predicate logic cannot lead from truths to falsehoods such as contradictions).

 

[quasar987]

Did Cantor invent the axioms (A) and (B) of naive set theory? The fact that he gave a definition of "set" led me to believe that he did not work axiomatically, but rather, just from this idea that anything could be brought into a "set". And Russell's paradox show that doing this leads to contradictions.

Thanks for correcting me on the Gödel thing.

 

[quasar987]

I changed the text to the following:

The beginning is unchanged. I cite Cantor's definition and say that such a non rigorous treatment of set theory leads to contradiction such as Russell's paradox. I then describe Russel's paradox and add,

In fact, Frege first axiomatized the set theory of Cantor, giving birth to the so-called "naive set theory", and it is on the basis of this theory that Russell formulated his paradox.

The set theory commonly used nowadays is that of Zermelo and Fraenkel. It has been constructed precisely in order to circumvent the paradoxes of naive set theory. Let us note however that is it nonetheless possible that a paradox lurks in ZF set theory.

Better?