Math 2.0

Mathematical logic and foundations Theorem

Russell's paradox

Builds on SetElementProof by contradiction

Statement

There is no set RR such that, for each set xx, x∈Rx \in R if and only if x∉xx \notin x.

Remarks

Proof: if such an RR exists, apply the condition to x=Rx = R. Then R∈RR \in R if and only if R∉RR \notin R, which is a contradiction. So the collection {x∣x∉x}\{x \mid x \notin x\} is not a set. Unrestricted comprehension, which makes a set from each property, is inconsistent. It follows that there is no set of all sets. Otherwise, separation would give RR as a subset of it.

History

Bertrand Russell found the paradox in May 1901. Ernst Zermelo found it independently, by 1902 and possibly in 1899, but he did not publish it. In a 1902 letter, Russell told Gottlob Frege that the paradox arises in the logical system of Frege. Axiomatic set theories, such as Zermelo–Fraenkel set theory, avoid it with a restricted form of comprehension.

Reading path

To understand this page from the ground up, read these 17 pages in order. The foundations come first.

Show the path as a graph
Element, definition, no evidence levelElementdefinitionProposition, concept, no evidence levelPropositionconceptSet, definition, no evidence levelSetdefinitionConjunction, definition, no evidence levelConjunctiondefinitionDisjunction, definition, no evidence levelDisjunctiondefinitionImplication, definition, no evidence levelImplicationdefinitionNegation, definition, no evidence levelNegationdefinitionBiconditional, definition, no evidence levelBiconditionaldefinitionTruth table, concept, no evidence levelTruth tableconceptModus ponens, concept, no evidence levelModus ponensconceptPropositional logic, concept, no evidence levelPropositional logicconceptMathematical proof, concept, no evidence levelMathematical proofconceptTautology, definition, no evidence levelTautologydefinitionLogical equivalence, definition, no evidence levelLogical equivalencedefinitionDouble negation law, statement, no evidence levelDouble negation lawstatementProof by contradiction, concept, no evidence levelProof by contradictionconceptRussell's paradox, statement, no evidence levelRussell's paradoxstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Element definition
  2. Proposition concept
  3. Set definition
  4. Conjunction definition
  5. Disjunction definition
  6. Implication definition
  7. Negation definition
  8. Biconditional definition
  9. Truth table concept
  10. Modus ponens concept
  11. Propositional logic concept
  12. Mathematical proof concept
  13. Tautology definition
  14. Logical equivalence definition
  15. Double negation law statement
  16. Proof by contradiction concept
  17. Russell's paradox statement

Where this leads

19 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Russell's_paradox, lead section
About this page
Tag0HESMMSYEG
URIm2://0HESMMSYEG
Aliasesrussell-paradox
Kindstatement, theorem
WritingW1 stated
MSC03E30
StatusThis copy of the site has no build data. Run m2 status 0HESMMSYEG.
UsesSet, Element, Proof by contradiction
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge about out: the concepts that the statement is about (0 of 1)
  • edge proves in: at least one proof node (0 of 1)
  • edge instance_of or illustrates in: one example that shows the statement at work (0 of 1)
  • explanation L2 (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by