37
$\begingroup$

Russell's paradox, the set of all sets not containing themselves can be broken down to two statements:

A thing that contains all sets that don't contain themselves.

This thing/one such thing would necessarily qualify as a set.

Now, what was the definition of set that Russell went by that mandated the second statement?

$\endgroup$
67
$\begingroup$

The axiom that told Russell that he could consider that to be a set is called the comprehension axiom, which says that for any property $P$, there is a set $X_P$ such that $$ x\in X_P\iff P(x).$$ (We usually write $X_P$ using comprehension notation: $X_P=\{x:P(x)\}$).

The other important axiom here is extensionality, which says two sets are equal if and only if they have the exact same elements: this tells us that the above condition is a valid definition of $X_P.$

Russell applied the comprehension axiom to the property $P(x)=x\notin x$ and then derived his contradiction that $$ X_P\in X_P\iff X_P\notin X_P.$$

The lesson we learned from this is that the comprehension axiom is inconsistent. Thus we do not use it in axiomatic set theory. Instead we use weaker versions, most commonly the separation axiom of ZF that says for any set $A$ and property $P$ that $ \{x\in A:P(x)\}$ is a set.

The reason that Russell thought he could use the comprehension axiom is because it seemed naively true, had been used implicitly before in mathematics with no problems, and had even been singled out as a formal axiom by Frege. His discovery that this seemingly innocuous bit of mathematical reasoning led straightforwardly to an obvious contradiction led to a lot of worry about the formal foundations of mathematics in the ensuing decades, and many interesting things were discovered by logicians trying to interrogate exactly why comprehension failed and how to avoid similar problems.

$\endgroup$
  • 4
    $\begingroup$ Note that this is the unrestricted comprehension axiom. The restricted comprehension axiom state that given a set A, $\{x \in A: P(x) \}$ is a set. $\endgroup$ – Acccumulation Jul 10 at 22:25
  • 2
    $\begingroup$ Could you elaborate on how the extensionality axiom fits into this -- i.e. is necessary for things to fall apart. As far as I can tell, membership through comprehension is enough. $\endgroup$ – user2268997 Jul 11 at 16:25
  • 2
    $\begingroup$ @user2268997 You are correct, the inconsistency follows from the comprehension axiom alone. Extensionality implies that the set $X$ such that $x\in X\iff P(x)$ is unique, which is important to our general conception here (for instance if we even use the notation $\{x: P(x)\}$, we are assuming extensionality), but only existence is required to produce the contradiction. $\endgroup$ – spaceisdarkgreen Jul 11 at 16:42
  • 2
    $\begingroup$ @Acccumulation I've used the terminology "comprehension" vs "separation", which is what's in the bible (Jech), but I've also seen comprehension called "unrestricted comprehension" and separation called "restricted comprehension" and "subset comprehension", "specification" and probably a few other names. $\endgroup$ – spaceisdarkgreen Jul 12 at 1:30
17
$\begingroup$

Russell started from the very trivial axiomatisation of Frege of the concept of set. It consists of only two axioms: one is the estensionality axiom and the other is the comprehension axiom. The point is this axiomatisaton seems very simple and, in the same time, powerful and seems it has captured the real essence of set. In fact the comprehension axiom (often called "unrestricted")

If $\mathcal P$ is a property, then there exists a set $A$ such that $$\forall x \big( x \in A \Leftrightarrow \mathcal P(x)\big)$$

expresses nothing else than our natural (nearly genetical) habit to build any set giving a property to satisfy. Mathematicians before Russell uses that axiomatization before Frege wrote it down, but did so tacitly. This axiom, let me say, is very interesting: it essentially says logic and set theory are the different faces of the same medal, that is, every logical question can be translated in term of sets and vice versa, statements corresponds to sets, and sets corresponds to statements.

Philosophically speaking, this axiom is to too powerful, I can build everything I happen to think, i.e. set of all sets (so $x \in x$?). Briefly, I loose very quickly the control of my constructions. The kiss of death of all that mathematical building is Russell's Antinomy. Just consider the predicate $$x \notin x\,,$$ which allows, cause the comprehension axiom, to consider the set $$R:=\{x \mid x \notin x\}$$ that has the following contradictory property $$R \in R \Leftrightarrow R \notin R\,.$$ This antinomy essentially says you have to pay attention because carefree constructions (as naïve set theory is) can lead to contradictions and antinomies. This paradox is far more than a sophism or a trifle and has an heavy relevance in Mathematics and in Philosophy of Mathematics: we need something with more restrictions, with which you can control what you are doing and avoid antinomies. These are the reasons why axiomatic set theories were born.

$\endgroup$
  • $\begingroup$ And on the flip side of the coin, these are the reasons why we stratify logic into first-order, second-order (and higher-order) logic; develop it into type theory; and so forth. $\endgroup$ – Hurkyl Jul 11 at 11:01
  • $\begingroup$ Yeah, these are further developements. I just want to explain the importance of such a antinomy. In fact it emeges we should interregate ourselves better about the nature of the objects (brutally, what is the meaning of "$x$ is a set"?) we deal with. From such a situation Type Theory was born. $\endgroup$ – Indrjo Dedej Jul 11 at 11:23
7
$\begingroup$

The orignal formulation of the "Contradiction" was in the context of the "theory of classes", corresponding (with a certain approximation) to Cantor's original Mengenlehre.

See Russell's letter to Frege (16 June 1902) :

Let $w$ be the predicate: to be a predicate that cannot be predicated of itself. Can $w$ be predicated of itself? From each answer its opposite follows. Therefore we must conclude that $w$ is not a predicate. Likewise there is no class (as a totality) of those classes which, each taken as a totality, do not belong to themselves. From this I conclude that under certain circumstances a definable collection [Menge] does not form a totality. [...]

The above contradiction, when expressed in Peano's ideography, reads as follows:

$$w = \text {Cls} \cap x \backepsilon (x \sim ε \ x). \supset : w \ ε \ w .=. w \sim ε \ w$$

[that can be approximately rewritten in moder notation : $w = \{ x \mid x \notin x \} \Rightarrow (w \in w \leftrightarrow w \notin w)$].

See also Bertrand Russell, Principles of Mathematics (1903), Chapter 6 : Classes (page 67-on) :

§68. In Chapter 2 we regarded classes as derived from assertions, i.e. as all the entities satisfying some assertion, whose form was left wholly vague. [...] for the present, we may confine ourselves to classes as they are derived from predicates, leaving open the question whether every assertion is equivalent to a predication.

§69. [...] it is plain that when two class-concepts are equal, some identity is involved, for we say that they have the same terms. Thus there is some object which is positively identical when two class-concepts are equal; and this object, it would seem, is more properly called the class. Neglecting the plucked hen, the class of featherless bipeds, every one would say, is the same as the class of men; the class of even primes is the same as the class of integers next after $1$.

§71. Class may be defined either extensionally or intensionally. That is to say, we may define the kind of object which is a class, or the kind of concept which denotes a class: this is the precise meaning of the opposition of extension and intension in this connection.

§73. Great difficulties are associated with the null-class, and generally with the idea of nothing. [...] In Symbolic Logic the null-class is the class which has no terms at all; and symbolically it is quite necessary to introduce some such notion.

§76. Something must be said as to the relation of a term to a class of which it is a member, and as to the various allied relations. One of the allied relations is to be called $ε$, and is to be fundamental in Symbolic Logic.

§77. A relation which, before Peano, was almost universally confounded with $ε$, is the relation of inclusion between classes, as e.g. between men and mortals.

§78. Among predicates, most of the ordinary instances cannot be predicated of themselves, though, by introducing negative predicates, it will be found that there are just as many instances of predicates which are predicable of themselves. One at least of these, namely predicability, or the property of being a predicate, is not negative: predicability, as is evident, is predicable, i.e. it is a predicate of itself. But the most common instances are negative: thus non-humanity is non-human, and so on. The predicates which are not predicable of themselves are, therefore, only a selection from among predicates, and it is natural to suppose that they form a class having a defining predicate. But if so, let us examine whether this defining predicate belongs to the class or not [emphasis added].

In Appendix A : THE LOGICAL AND ARITHMETICAL DOCTRINES OF FREGE, we can found the discussion of the "Contradiction" in terms of Frege's formal system.

In conclusion, for Russell a class is the extension of a predicate.

$\endgroup$
  • $\begingroup$ Thanks for the great excerpts. $\endgroup$ – user2268997 Jul 12 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.