Burali-Forti paradox

In set theory, a field of mathematics, the Burali-Forti paradox demonstrates that constructing "the set of all ordinal numbers" leads to a contradiction and therefore shows an antinomy in a system that allows its construction. It is named after Cesare Burali-Forti, who in 1897 published a paper proving a theorem which, unknown to him, contradicted a previously proved result by Cantor. Bertrand Russell subsequently noticed the contradiction, and when he published it in his 1903 book Principles of Mathematics, he stated that it had been suggested to him by Burali-Forti's paper, with the result that it came to be known by Burali-Forti's name.

Contents

• 
  1 Stated in terms of von Neumann ordinals
  


• 
  2 Stated more generally
  


• 
  3 Resolutions of the paradox
  


• 
  4 References
  


• 
  5 External links
  

Stated in terms of von Neumann ordinals

We will prove this by reductio ad absurdum.

1. Let Ω{displaystyle Omega } be a set that contains all ordinal numbers.


2. 
   Ω{displaystyle Omega } is transitive because for every element x{displaystyle x} of Ω{displaystyle Omega } (which is an ordinal number and can be any ordinal number) and every element y{displaystyle y} of x{displaystyle x} (i.e. under the definition of Von Neumann ordinals, for every ordinal number y<x{displaystyle y<x}), we have that y{displaystyle y} is an element of Ω{displaystyle Omega } because any ordinal number contains only ordinal numbers, by the definition of this ordinal construction.


3. 
   Ω{displaystyle Omega } is well ordered by the membership relation because all its elements are also well ordered by this relation.


4. So, by steps 2 and 3, we have that Ω{displaystyle Omega } is an ordinal class and also, by step 1, an ordinal number, because all ordinal classes that are sets are also ordinal numbers.


5. This implies that Ω{displaystyle Omega } is an element of Ω{displaystyle Omega }.


6. Under the definition of Von Neumann ordinals, Ω<Ω{displaystyle Omega <Omega } is the same as Ω{displaystyle Omega } being an element of Ω{displaystyle Omega }. This latter statement is proven by step 5.


7. But we have that no ordinal class is less than itself, including Ω{displaystyle Omega } because of step 4 (Ω{displaystyle Omega } is an ordinal class), i.e. ¬Ω<Ω{displaystyle lnot Omega <Omega }.

We've deduced two contradictory propositions (Ω<Ω{displaystyle Omega <Omega } and ¬Ω<Ω{displaystyle lnot Omega <Omega }) from the sethood of Ω{displaystyle Omega } and, therefore, disproved that Ω{displaystyle Omega } is a set.

Stated more generally

The version of the paradox above is anachronistic, because it presupposes the definition of the ordinals due to John von Neumann, under which each ordinal is the set of all preceding ordinals, which was not known at the time the paradox was framed by Burali-Forti.
Here is an account with fewer presuppositions: suppose that we associate with each well-ordering
an object called its order type in an unspecified way (the order types are the ordinal numbers). The order types (ordinal numbers) themselves are well-ordered in a natural way,
and this well-ordering must have an order type Ω{displaystyle Omega }. It is easily shown in
naïve set theory (and remains true in ZFC but not in New Foundations) that the order
type of all ordinal numbers less than a fixed α{displaystyle alpha } is α{displaystyle alpha } itself.
So the order
type of all ordinal numbers less than Ω{displaystyle Omega } is Ω{displaystyle Omega } itself. But
this means that Ω{displaystyle Omega }, being the order type of a proper initial segment of the ordinals, is strictly less than the order type of all the ordinals,
but the latter is Ω{displaystyle Omega } itself by definition. This is a contradiction.

If we use the von Neumann definition, under which each ordinal is identified as the set of all preceding ordinals, the paradox is unavoidable: the offending proposition that the order type of all ordinal numbers less than a fixed α{displaystyle alpha } is α{displaystyle alpha } itself must be true. The collection of von Neumann ordinals, like the collection in the Russell paradox, cannot be a set in any set theory with classical logic. But the collection of order types in New Foundations (defined as equivalence classes of well-orderings under similarity) is actually a set, and the paradox is avoided because the order type of the ordinals less than Ω{displaystyle Omega }
turns out not to be Ω{displaystyle Omega }.

Resolutions of the paradox

Modern axioms for formal set theory such as ZF and ZFC circumvent this antinomy by not allowing the construction of sets using terms like "all sets with the property P{displaystyle P}", as is possible in naive set theory and as is possible with Gottlob Frege's axioms - specifically Basic Law V - in the Grudgesetze der Arithmetik. Quine's system New Foundations uses a different solution. Rosser (1942) showed that in the original version of Quine's system "Mathematical Logic" (ML), an extension of New Foundations, it is possible to derive the Burali-Forti paradox, showing that this system was contradictory. Quine's revision of ML following Rosser's discovery does not suffer from this defect, and indeed was subsequently proved equiconsistent with NF by Hao Wang.

References

• 
  Burali-Forti, Cesare (1897), "Una questione sui numeri transfiniti", Rendiconti del Circolo Matematico di Palermo, 11: 154–164, doi:10.1007/BF03015911.mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}
  


• 
  Irving Copi (1958) "The Burali-Forti Paradox", Philosophy of Science 25(4): 281-286, doi:10.1086/287617
  


• 
  Moore, Gregory H; Garciadiego, Alejandro (1981), "Burali-Forti's paradox: A reappraisal of its origins", Historia Mathematica, 8 (3): 319–350, doi:10.1016/0315-0860(81)90070-7
  


• 
  Rosser, Barkley (1942), "The Burali-Forti paradox", Journal of Symbolic Logic, 7: 1–17, doi:10.2307/2267550, MR 0006327
  

External links

• 
  Stanford Encyclopedia of Philosophy: "Paradoxes and Contemporary Logic"—by Andrea Cantini.

This page is only for reference, If you need detailed information, please check here