What is Russell paradox?

Bertrand Russell portraitEven if we restrict ourselves to select only sets that do not include the membership loop, we cannot avoid a paradox on a kind of naive formal systems such that contains inside the infinity or the totality. See the following formula, unrestricted comprehension principle.

Ax [ ( xA ) ⇔ φ(x) ][1]
   where φ(x) has free x and no free A

This principle states that there is a set that satisfies any attribute φ(x) . Suppose we settle the attribute of set φ(x) such that inhibits the membership loop, or xx. Then, the formula is

Ax [ ( xA ) ⇔ ( xx ) ].

In case of a particular A for any x, this formula turns to

( AA ) ⇔ ( AA ) .

It contradicts. Namely, if we suppose that a set s is not a member of s itself (ss ), this s should be a member of s, because it satisfies the set attribute condition. Oppositely, if we suppose that a set s is a member of s itself, this s should not be a member of s, because it does not satisfy the condition. This is called Russell paradox.

“Bertrand Russell discovered what became known as the Russell paradox in June 1901 […]. In the letter [to Frege], written more than a year later and hitherto unpublished, he communicates the paradox to Frege[2]. The paradox shook the logicians’ world, and the rumbles are still felt today.” (Letter to Frege, From Frege to Gödel, Jean van Heijenoort, 1967)

Russell paradox is deeply related to the infinity of set or the totality of system, whereas it is not explicitly observed. To work around this paradox, Ernst Zermelo placed separation (aussonderung) principle as the foundation of set theory instead of Cantor’s unrestricted comprehension principle. See the following.

B Ax [ ( xA ) ⇔ ( xB ) ⋀ φ(x) ]   where A does not occur in φ(x)

In this formula, another set B is introduced in order to make a set A, so that a member of A should be a member of B, beforehand or afterward. It might be said that the solution of paradox is left on the shelf and postponed with introducing a set B somewhat uncertain. However, based on this separation principle and other several basic axioms, Zermelo modernized the set theory that is opened by Georg Cantor. It is today called Zermelo Fraenkel (ZF) set theory.

On the other hand, Russell himself tried to solve the paradox with other many paradoxes by capturing it as a variation of notorious ‘vicious circle’. He invented the first type theory in the epoc-making three-volume books Principia Mathematica. So, I would like next to see the infinity in Zermelo Fraenkel set theory, and after that I would like to go to Russell’s ramified type theory later on.

[1] These modern logical expression of formulae are from the lecture of set theory at University of Amsterdam “Zermelo-Fraenkel Set Theory” (H.C. Doets 2002).
[2] Russell pointed the paradox by Frege in the expression of functions rather than sets, whereas it is equivalent the paradox in sets.


About seijikoide

Please check my page as researcher of computer scientist.
This entry was posted in LOD, OWL, RDF, Semantic Web and tagged , , , , . Bookmark the permalink.

One Response to What is Russell paradox?

  1. Great post, I think website owners should acquire a lot from this web site its very user pleasant.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s