There is no set of all sets

From Maths
Jump to: navigation, search
Provisional page grade: A*
This page is provisional
This page is provisional and the information it contains may change before this notice is removed (in a backwards incompatible way). This usually means the content is from one source and that source isn't the most formal, or there are many other forms floating around. It is on a to-do list for being expanded.The message provided is:
The "core pages" of set theory need to be unified and designed to be viewed in a specific order so all the precursors actually come before

Statement

We claim there is no set of all sets[1] Claim:

  • [ilmath]\forall X\exists Y[Y\notin X][/ilmath]
    • For any set [ilmath]X[/ilmath] there exists a set [ilmath]Y[/ilmath] such that [ilmath]Y\notin X[/ilmath]

Significance

If we take [ilmath]X[/ilmath] to be the "set of all sets" we'd reach Russell's paradox, this statement shows half of it. The remainder of the paradox shows that [ilmath]Y\notin X[/ilmath] is absurd too.

Proof

  • Let [ilmath]X[/ilmath] be given
    • Define [ilmath]Y:\eq\{x\in X\ \vert\ x\notin x\} [/ilmath] - which exists by the axiom schema of separation, accordingly [ilmath]Y\subseteq X[/ilmath][Note 1]
      • Suppose that [ilmath]Y\in X[/ilmath]
        • We now have two cases (as [ilmath]Y\in Y[/ilmath] is conceivable (as is [ilmath]Y\notin Y[/ilmath]) as [ilmath]Y[/ilmath] is some subset of [ilmath]X[/ilmath]):
          1. [ilmath]Y\in Y[/ilmath]
            • But [ilmath]\forall A\in Y[A\notin A][/ilmath] is the defining property of [ilmath]Y[/ilmath]
              • So then [ilmath]Y\notin Y[/ilmath] (the case where [ilmath]A:\eq Y[/ilmath]) - a contradiction! So we cannot have this!
          2. [ilmath]Y\notin Y[/ilmath]
            • As [ilmath]Y\in X[/ilmath] by hypothesis, if [ilmath]Y\notin Y[/ilmath] then [ilmath]Y\in Y[/ilmath] by definition of what [ilmath]Y[/ilmath] contains from [ilmath]X![/ilmath]
              • A contradiction again! So we cannot have this!
        • Thus [ilmath]Y\notin X[/ilmath]

Note: this is half of Russell's paradox, the other half is showing that [ilmath]Y\notin X[/ilmath] is absurd too!.

Notes

References

  1. Warwick lecture notes - Set Theory - 2011 - Adam Epstein - page 6