Russell's Paradox

[lawtonfogle]

So, what dare your opinions on it.

For those who don't know what it is, I would suggest this link:
http://en.wikipedia.org/wiki/Russell's_paradox

The basics of it is that given no assumptions, we achieve a contradiction in a formal proof. Proof by contradiction states that one of our assumptions must then be incorrect, but since we had not assumptions, we must turn to the one thing which is otherwise never brought into question, which is the assumption which is set logic.

The actual paradox works likes this.
Let A be defined as all containing all x which do not contain x.
Stated formally: A contains x if and only if x does not contain x.
Now, since we are dealing with all x, one instance of x is A. Therefore A contains A if and only if A does not contain A.

The first thing which looks like it could be the problem with this is how we define A, but I see no reason that A cannot be defined as it is without a change to logic which states A cannot be defined as it is.

So, what is your take on it?

 

[Hnefi]

My "take" is that the paradox relies on an old, flawed definition of set theory. It is no longer valid, because set theory requires that A be a proper set, a definition it does not meet.

 

[lawtonfogle]

Supposedly that it was a proper set, unless I missed something. Do you mind stating what part of being a proper set it doesn't meet?

I have only had a single semester of logic and a single semester of
discrete mathematics. So I was actually surprised when I understood the contradiction.

 

[Hnefi]

It depends on which set theory you are talking about, but the most widely used is Zermelo-Fränkel set theory. It states that for any proper set, all subsets of that set are definable using regular first-order logic. It is impossible to define subsets of the proposed set A you describe in your OP in such a fashion. Wikipedia has more details, I believe.

Really, when you think about it, the position of naive set theory that a "set" can be defined by any property and any condition is not defensible. Such a flexible and unrigorous definition is highly likely to result in an unsound system; which is exactly what we observe in Russel's paradox.

 

[lawtonfogle]

I read the majority of that as saying "I need to take more logic courses," which is pretty true. Wikipedia does mention that there are set theories by which one avoids this. What I want to do is sit down with my notes from my logic class that Dr. Sris taught and see if I can 'generate' (for lack of a better term) this paradox. If I do, I think I'll shoot Dr. Sris an email and ask him about it. It is just, up until I faced this thing, I have never thought about limits on what a set can and cannot be.

 

[Hnefi]

Sounds like a plan. In my experience, experimenting with a subject and asking questions to someone with a Ph.d. in said subject is a very good way to learn (and sometimes to open up opportunities for future careers).

 

[acropolis]

Paradox is present in any sufficiently strong axiomatic system, in the sense that there will always be theorems whose truth is undecidable within the system. Moreover, the completeness and consistency of a formal system cannot be proven within system. This is a result of Gödel’s incompleteness theorem, which is explained on Wikipedia and elsewhere much better than I could. The Zermelo-Fränkel set theory already mentioned falls under the category of ‘sufficiently strong’, and although it is immune from Russell’s Paradox and most others, it is still inherently incomplete (unless it is inconsistent).

You should read Douglas Hofstadter’s Gödel, Escher, Bach if you have any interest in logical paradox.

 

[StrugglingSceptic]

The following is just a quick overview of modern set theory and Russell's paradox, and if you have only started studying logic, I do not expect you to follow it all. But please ask any questions, and I'll elaborate on whatever point you want more information about. You won't get that from Wikipedia.

The original problem arose in a formal logic being developed by Gottlob Frege. Russell was extremely impressed with this work, but wrote to Frege pointing out a contradiction, that it was possible to consider the class of all classes that do not belong to themselves. As far as Frege was concerned, this was the end of his programme, and he gave up on his research.

A few other paradoxes were uncovered in these logics. Cantor's set theory, for instance, included the set of all things, or the universal set. From this, we can consider the set of all subsets of the universal set. But being a set of mere things, this new set can only be a subset of the universal set itself. Cantor had previously shown that such a situation was impossible, and hence we have another paradox.

These paradoxes motivated the development of modern set theory, based upon carefully chosen axioms. The idea is that an axiomatic approach can limit what can be said about paradoxical objects and so avoid contradictions.

So Russell's paradox is avoided by carefully defining the so-called "comprehension axiom." The naive comprehension scheme of Frege's theory said that given a predicate, it was always possible to consider the set of elements satisfying this predicate. This allows us to construct the Russell set by considering the predicate "does not contain itself." The revised comprehension axiom prevents this because it only allows us to use a predicate to construct subsets of an already constructed set.

The class of all things that do not contain themselves still shows up in some set theories. For instance, it is possible to construct the Russell class in NBG set theory. No paradox can be deduced from its existence, however, since the Russell class, as with all proper classes, cannot be contained in itself or any other class.

 

[StrugglingSceptic]

Paradox is present in any sufficiently strong axiomatic system, in the sense that there will always be theorems whose truth is undecidable within the system.

That's not a paradox. A paradox is a contradiction, a statement both provable and disprovable in a theory.

 

[acropolis]

That's not a paradox. A paradox is a contradiction, a statement both provable and disprovable in a theory.

Is there a word for something which is proven to be impossible to prove within a theory?

 

[StrugglingSceptic]

Is there a word for something which is proven to be impossible to prove within a theory?

You would just say that the statement is unprovable in the theory.

There would be no point in having a more glamorous term, because there is nothing special or generally surprising about unprovable sentences, and, in fact, we often want some sentences to be unprovable in theories.

For instance, when coming up with a set of axioms, it is often desired that the axioms be independent of one another. That means that each axiom is provably unprovable in the theory formed by the others. So it is in this sense, for example, that the Parallel Postulate is independent of the other axioms of geometry.

We also want some theories to have many different interpretations. Take elementary group theory. This theory is supposed to prove exactly those statements true of all groups. But groups may still differ significantly, and so we expect that many statements cannot be proven in this theory, such as the claim that every element is the identity. We would certainly not want to prove this, because it would imply that all groups are the trivial group!

And then there is the theory of first-order logic. This theory proves only the logical truths, and so all non-logical truths must be unprovable in it. The theory is trivially incomplete [1]. You cannot, for instance, prove that 1+1=2 from it, nor would you want to.

Godel's Incompleteness Theorems do not merely tell us that provably unprovable sentences exist. We already knew that. Instead, the theorems tell us us that they must exist in a very large class of important theories, namely, all consistent theories whose proofs can be checked by machine, and which are powerful enough to prove just a small number of truths of number theory. Such theories are necessarily incomplete, and there is no way to extend them to make them complete.

[1] FOPL is sometimes said to be complete by virtue of Godel's Completeness Theorem, but this is an annoying confusion of terminology.

 

[acropolis]

nothing special

Isn't there something special about Godel's theorems? Combining axioms with rules of inference shouldn't yield undecidable theorems, and yet they do.

 

[StrugglingSceptic]

Isn't there something special about Godel's theorems? Combining axioms with rules of inference shouldn't yield undecidable theorems,

But of course it can. Mathematicians and logicians knew about undecidable statements in axiomatic theories long before Godel. And as I explained in the post above, in many cases, undecidable statements are exactly what you want.

What Godel showed was that no matter how many axioms you have, if the validity of all proofs is machine checkable, and you can prove enough arithmetic, your theory must contain undecidable statements. That was a surprise. It was presumed that a complete theory for arithmetic and mathematics in general was possible if you supplied enough axioms or axiom schemes, but this is not the case.