Russell's antinomy

from Wikipedia, the free encyclopedia

The Russell's paradox is one of Bertrand Russell and Ernst Zermelo discovered paradox of naive set theory published, the Russell 1903 and therefore bears his name.

Concept and problem

Russell formed his antinomy with the help of the "class of all classes that do not contain themselves as an element", referred to as Russell's class ; he defined it formally as follows:

Russell's class is often defined as "the set of all sets that do not contain themselves as an element"; this corresponds to the set theory of that time, which did not yet differentiate between classes and sets . In contrast to the older antinomies of naive set theory ( Burali-Forti paradox and Cantor's antinomies ), Russell's antinomy is of a purely logical nature and independent of set axioms. Therefore it had a particularly strong effect and suddenly brought about the end of naive set theory.

Russell derived his antinomy as follows: Assumed contains itself, then because of the class property that was used to define that what contradicts the assumption does not contain itself. Assuming the opposite is true and does not contain itself, then the class property fulfills , so that it contains itself against the assumption. Mathematically, this expresses the following contradicting equivalence:

No axioms and theorems of set theory are used to derive this contradiction, but only Frege's abstraction principle , which Russell adopted in his type theory, apart from the definition :

History and solutions

Russell discovered his paradox in mid-1901 while studying Cantor's first antinomy from 1897. He published the antinomy in his book The Principles of Mathematics in 1903. As early as 1902 he informed Gottlob Frege by letter. He was referring to Frege's first volume of the Basic Laws of Arithmetic from 1893, in which Frege tried to build arithmetic on a set-theoretical axiom system. Russell's antinomy showed that this system of axioms was contradicting itself. Frege responded to this in the afterword of the second volume of his Basic Laws of Arithmetic from 1903:

“A scientific writer can hardly encounter anything more undesirable than that, after completing a work, one of the foundations of his structure is shaken. I was put in this position by a letter from Mr. Bertrand Russell as the printing of this volume neared its end. "

- Thank God Frege

Russell solved the paradox as early as 1903 through his type theory ; in it a class always has a higher type than its elements; Statements like “a class contains itself”, with which he formed his antinomy, can then no longer be formulated. So he tried, since he adhered to Frege's principle of abstraction, to solve the problem by a restricted syntax of the admissible class statements. The restricted syntax, however, turned out to be complicated and inadequate for the structure of mathematics and has not become established in the long term.

Parallel to Russell, Zermelo, who found the antinomy to be independent of Russell and knew it even before Russell's publication, developed the first axiomatic set theory with unrestricted syntax. The exclusion axiom of this Zermelo set theory from 1907 only allows a restricted class formation within a given set. He showed by indirect proof with this antinomy that the Russell class is not a set. His solution has prevailed. In the extended Zermelo-Fraenkel set theory (ZF), which today serves as the basis of mathematics , the axiom of foundation also ensures that no set can contain itself, so that here the Russell class is identical to the universal class .

Since Russell's antinomy is of a purely logical nature and does not depend on set axioms, it can already be proven at the level of the first-order consistent predicate logic that Russell's class does not exist as a set. This makes the following argumentation understandable, which converts a second indirect proof of Russell into a direct proof:

The statement is abbreviated with .
The statement supported by is the above contradiction. Therefore, its negation is true: .
Therefore, the existential can be introduced: .
By introducing the universal quantifier follows: .
By rearranging the quantifiers and elimination of the abbreviation is finally obtained the sentence .

This sentence means in the language of predicate logic: There is no set of all sets that do not contain themselves as an element. It applies to all modern axiomatic set theories that are based on first-level predicate logic, for example in ZF. It is also valid in the Neumann-Bernays-Gödel set theory , in which Russell's class exists as a real class . In the class logic of Oberschelp , which is a demonstrably consistent extension of the first-level predicate logic, any class terms can also be formed to any defining statements; in particular, Russell's class is also a correct term with provable nonexistence there. Axiom systems such as ZF set theory can be integrated into this class logic.

Since the theorem was derived in a direct proof, it is also valid in intuitionist logic .

Variants of Russell's antinomy

The 1908 Grelling-Nelson Antinomy is a semantic paradox inspired by Russell's antinomy.

There are numerous popular variations of Russell's antinomy. The best known is the barber's paradox , with which Russell himself illustrated and generalized his train of thought in 1918.

Curry's Paradox of 1942 contains, as a special case, a generalization of Russell's antinomy.

Individual evidence

  1. ^ Bertrand Russell: The principles of Mathematics , Cambridge 1903, chap. X, summary §106.
  2. Russell's own formula (in Peano notation) in the letter to Frege in: Gottlob Frege: Correspondence with D. Hilbert, E. Husserl, B. Russell , ed. G. Gabriel, F. Kambartel, C. Thiel, Hamburg 1980, P. 60. (Correspondence between Russell and Frege online in the Bibliotheca Augustana .)
  3. ^ Bertrand Russell: The principles of Mathematics , Cambridge 1903, § 101.
  4. Gottlob Frege: Grundgesetze der Arithmetik , I, 1893, p. 52 explains this principle of abstraction. In Frege, however, it is not an axiom, but a proposition derived from other axioms.
  5. Bertrand Russell: Mathematical logic as based on the theory of types (PDF; 1.9 MB), in: American Journal of Mathematics 30 (1908), page 250.
  6. Time according to Russell's letter to Frege of June 22, 1902. In: Frege: Wissenschaftlicher Briefwechsel, ed. G. Gabriel, H. Hermes, F. Kambartel, C. Thiel, A. Veraart, Hamburg 1976, pp. 215f.
  7. ^ Bertrand Russell: The Principles of Mathematics , Cambridge 1903, §100
  8. Russell's letter to Frege of June 16, 1902. In: Gottlob Frege: Correspondence with D.Hilbert, E. Husserl, B. Russell , ed. G. Gabriel, F. Kambartel, C. Thiel, Hamburg 1980, pp. 59f . (Correspondence between Russell and Frege online in the Bibliotheca Augustana .)
  9. Gottlob Frege: Fundamentals of Arithmetic , II, 1903, Appendix pp. 253–261.
  10. ^ Bertrand Russell: The Principles of Mathematics , Cambridge 1903, §§497-500.
  11. ^ Russell / Whitehead: Principia mathematica I, Cambridge 1910, p. 26
  12. according to a letter from Hilbert dated November 7, 1903, in: Gottlob Frege: Correspondence with D. Hilbert, E. Husserl, B. Russell , ed. G. Gabriel, F. Kambartel, C. Thiel, Hamburg 1980, p. 23f / 47
  13. Ernst Zermelo: Investigations on the fundamentals of set theory , Mathematische Annalen 65 (1908), pp. 261–281; there p. 265.
  14. ^ Bertrand Russell: The Principles of Mathematics , Cambridge 1903, §102. There is the derivation for any relation R and especially for
  15. ^ Arnold Oberschelp: General set theory , Mannheim, Leipzig, Vienna, Zurich, 1994, p. 37.

Web links