Russell’s Paradox

russellRussell's paradox represents either of two interrelated logical
antinomies. The most commonly discussed form is a contradiction
arising in the logic of sets or classes. Some classes (or sets) seem
to be members of themselves, while some do not. The class of all
classes is itself a class, and so it seems to be in itself. The null
or empty class, however, must not be a member of itself. However,
suppose that we can form a class of all classes (or sets) that, like
the null class, are not included in themselves. The paradox arises
from asking the question of whether this class is in itself. It is if
and only if it is not. The other form is a contradiction involving
properties. Some properties seem to apply to themselves, while others
do not. The property of being a property is itself a property, while
the property of being a cat is not itself a cat. Consider the property
that something has just in case it is a property (like that of being a
cat) that does not apply to itself. Does this property apply to
itself? Once again, from either assumption, the opposite follows. The
paradox was named after Bertrand Russell, who discovered it in 1901.

1. History

Russell's discovery came while he was working on his Principles of
Mathematics. Although Russell discovered the paradox independently,
there is some evidence that other mathematicians and set-theorists,
including Ernst Zermelo and David Hilbert, had already been aware of
the first version of the contradiction prior to Russell's discovery.
Russell, however, was the first to discuss the contradiction at length
in his published works, the first to attempt to formulate solutions
and the first to appreciate fully its importance. An entire chapter of
the Principles was dedicated to discussing the contradiction, and an
appendix was dedicated to the theory of types that Russell suggested
as a solution.

Russell discovered the contradiction from considering Cantor's power
class theorem: the mathematical result that the number of entities in
a certain domain is always smaller than the number of subclasses of
those entities. Certainly, there must be at least as many subclasses
of entities in the domain as there are entities in the domain given
that for each entity, one subclass will be the class containing only
that entity. However, Cantor proved that there also cannot be the same
number of entities as there are subclasses. If there were the same
number, there would have to be a 1-1 function f mapping entities in
the domain on to subclasses of entities in the domain. However, this
can be proven to be impossible. Some entities in the domain would be
mapped by f on to subclasses that contain them, whereas others may
not. However, consider the subclass of entities in the domain that are
not in the subclasses on to which f maps them. This is itself a
subclass of entities of the domain, and thus, f would have to map it
on to some particular entity in the domain. The problem is that then
the question arises as to whether this entity is in the subclass on to
which f maps it. Given the subclass in question, it does just in case
it does not. The Russell paradox of classes can in effect be seen as
an instance of this line of reasoning, only simplified. Are there more
classes or subclasses of classes? It would seem that there would have
to be more classes, since all subclasses of classes are themselves
classes. But if Cantor's theorem is correct, there would have to be
more subclasses. Russell considered the simple mapping of classes onto
themselves, and invoked the Cantorian approach of considering the
class of all those entities that are not in the classes onto which
they are mapped. Given Russell's mapping, this becomes the class of
all classes not in themselves.

The paradox had profound ramifications for the historical development
of class or set theory. It made the notion of a universal class, a
class containing all classes, extremely problematic. It also brought
into considerable doubt the notion that for every specifiable
condition or predicate, one can assume there to exist a class of all
and only those things that satisfy that condition. The properties
version of the contradiction–a natural extension of the classes or
sets version–raised serious doubts about whether one can be committed
to objective existence of a property or universal corresponding to
every specifiable condition or predicate. Indeed, contradictions and
problems were soon found in the work of those logicians, philosophers
and mathematicians who made such assumptions. In 1902, Russell
discovered that a version the contradiction was expressible in the
logical system developed in Volume I of Gottlob Frege's Grundgesetze
der Arithmetik, one of the central works in the late-19th and
early-20th century revolution in logic. In Frege's philosophy, a class
is understood as the "extension" or "value-range" of a concept.
Concepts are the closest correlates to properties in Frege's
metaphysics. A concept is presumed to exist for every specifiable
condition or predicate. Thus, there is a concept of being a class that
does not fall under its defining concept. There is also a class
defined by this concept, and it falls under its defining concept just
in case it does not.

Russell wrote to Frege concerning the contradiction in June of 1902.
This began one of the most interesting and discussed correspondences
in intellectual history. Frege immediately recognized the disastrous
consequences of the paradox. He did note, however, that the properties
version of the paradox was solved in his philosophy by his distinction
between levels of concepts. For him, concepts are understood as
functions from arguments to truth-values. Some concepts, "first-level
concepts", take objects as arguments, some concepts, "second-level
concepts" take these functions as arguments, and so on. Thus, a
concept can never take itself as argument, and the properties version
cannot be formulated. However, classes, or extensions or concepts,
were all understood by Frege to be of the same logical type as all
other objects. The question does arise, then, for each class whether
it falls under its defining concept.

When he received Russell's first letter, the second volume of Frege's
Grundgesetze was already in the latter stages of the publication
process. Frege was forced to quickly prepare an appendix in response
to the paradox. Frege considers a number of possible solutions. The
conclusion he settles on, however, is to weaken the class abstraction
principle in the logical system. In the original system, one could
conclude that an object is in a class if and only if the object falls
under the concept defining the class. In the revised system, one can
conclude only that an object is in a class if and only if the object
falls under the concept defining the class and the object is not
identical to the class in question. This blocks the class version of
the paradox. However, Frege was not entirely happy even with this
solution. And this was for good reason. Some years later the revised
system was found to lead to a more complicated form of the
contradiction. Even before this result was discovered, Frege abandoned
it and seems to have concluded that his earlier approach to the logic
of classes was simply unworkable, and that logicians would have to
make do entirely without commitment to classes or sets.

However, other logicians and mathematicians have proposed other,
relatively more successful, alternative solutions. These are discussed
below.
2. Possible Solutions to the Paradox of Properties

The Theory of Types. It was noted above that Frege did have an
adequate response to the contradiction when formulated as a paradox of
properties. Frege's response was in effect a precursor to what one of
the most commonly discussed and articulated proposed solutions to this
form of the paradox. This is to insist that properties fall into
different types, and that the type of a property is never the same as
the entities to which it applies. Thus, the question never even arises
as to whether a property applies to itself. A logical language that
divides entities into such a hierarchy is said to employ the theory of
types. Though hinted at already in Frege, the theory of types was
first fully explained and defended by Russell in Appendix B of the
Principles. Russell's theory of types was more comprehensive than
Frege's distinction of levels; it divided not only properties into
different logical types, but classes as well. The use of the theory of
types to solve the other form of Russell's paradox is described below.

To be philosophically adequate, the adoption of the theory of types
for properties requires developing an account of the nature of
properties such that one would be able to explain why they cannot
apply to themselves. After all, at first blush, it would seem to make
sense to predicate a property of itself. The property of being
self-identical would seem to be self-identical. The property of being
nice seems to be nice. Similarly, it seems false, not nonsensical, to
say that the property of being a cat is a cat. However, different
thinkers explain the justification for the type-division in different
ways. Russell even gave different explanations at different parts of
his career. For his part, the justification for Frege's division of
different levels of concepts derived from his theory of the
unsaturatedness of concepts. Concepts, as functions, are essentially
incomplete. They require an argument in order to yield a value. One
cannot simply predicate one concept of a concept of the same type,
because the argument concept still requires its own argument. For
example, while it is possible to take the square root of the square
root of some number, one cannot simply apply the function square root
to the function square root and arrive at a value.

Conservatism about Properties. Another possible solution to the
paradox of properties would involve denying that a property exists
corresponding to any specifiable conditions or well-formed predicate.
Of course, if one eschews metaphysical commitment to properties as
objective and independent entities altogether, that is, if one adopts
nominalism, then the paradoxical question is avoided entirely.
However, one does not need to be quite so extreme in order to solve
the antinomy. The higher-order logical systems developed by Frege and
Russell contained what is called the comprehension principle, the
principle that for every open formula, no matter how complex, there
exists as entity a property or concept exemplified by all and only
those things that satisfy the formula. In effect, they were committed
to attributes or properties for any conceivable set of conditions or
predicates, no matter how complex. However, one could instead adopt a
more austere metaphysics of properties, only granting objective
existence to simple properties, perhaps including redness, solidity
and goodness, etc. One might even allow that such properties can
possibly apply to themselves, e.g. that goodness is good. However, on
this approach one would deny the same status to complex attributes,
e.g. the so-called "properties" as having-seventeen-heads,
being-a-cheese-made-England, having-been-written-underwater, etc. It
is simply not the case that any specifiable condition corresponds to a
property, understood as an independently existing entity that has
properties of its own. Thus, one might deny that there is a simple
property being-a-property-that-does-not-apply-to-itself. If so, one
can avoid the paradox simply by adopting a more conservative
metaphysics of properties.
3. Possible Solutions to the Paradox of Classes or Sets

It was mentioned above that late in his life, Frege gave up entirely
on the feasibility of the logic of classes or sets. This is of course
one ready solution to the antinomy in the class or set form: simply
deny the existence of such entities altogether. Short of this,
however, the following solutions have enjoyed the greatest popularity:

The Theory of Types for Classes: It was mentioned earlier that Russell
advocated a more comprehensive theory of types than Frege's
distinction of levels, one that divided not only properties or
concepts into various types, but classes as well. Russell divided
classes into classes of individuals, classes of classes of
individuals, and so on. Classes were not taken to be individuals, and
classes of classes of individuals were not taken to be classes of
individuals. A class is never of the right type to have itself as
member. Therefore, there is no such thing as the class of all classes
that are not members of themselves, because for any class, the
question of whether it is in itself is a violation of type. Once
again, here the challenge is to explain the metaphysics of classes or
sets in order to explain the philosophical grounds of the
type-division.

Stratification: In 1937, W. V. Quine suggested an alternative solution
in some ways similar to type-theory. His suggestion was rather than
actually divide entities into individuals, classes of individuals,
etc., such that the proposition that some class is in itself is always
ill-formed or nonsensical, we can instead put certain restrictions on
what classes are supposed to exist. Classes are only supposed to exist
if their defining conditions are so as to not involve what would, in
type theory, be a violation of types. Thus, for Quine, while "x is not
a member of x" is a meaningful assertion, we do not suppose there to
exist a class of all entities x that satisfy this statement. In
Quine's system, a class is only supposed to exist for some open
formula A if and only if the formula A is stratified, that is, if
there is some assignment of natural numbers to the variables in A such
that for each occurrence of the class membership sign, the variable
preceding the membership sign is given an assignment one lower than
the variable following it. This blocks Russell's paradox, because the
formula used to define the problematic class has the same variable
both before and after the membership sign, obviously making it
unstratified. However, it has yet to be determined whether or not the
resulting system, which Quine called "New Foundations for Mathematical
Logic" or NF for short, is consistent or inconsistent.

Aussonderung: A quite different approach is taken in Zermelo-Fraenkel
(ZF) set theory. Here too, a restriction is placed on what sets are
supposed to exist. Rather than taking the "top-down" approach of
Russell and Frege, who originally believed that for any concept,
property or condition, one can suppose there to exist a class of all
those things in existence with that property or satisfying that
condition, in ZF set theory, one begins from the "bottom up". One
begins with individual entities, and the empty set, and puts such
entities together to form sets. Thus, unlike the early systems of
Russell and Frege, ZF is not committed to a universal set, a set
including all entities or even all sets. ZF puts tight restrictions on
what sets exist. Only those sets that are explicitly postulated to
exist, or which can be put together from such sets by means of
iterative processes, etc., can be concluded to exist. Then, rather
than having a naive class abstraction principle that states that an
entity is in a certain class if and only if it meets its defining
condition, ZF has a principle of separation, selection, or as in the
original German, "Aussonderung". Rather than supposing there to exist
a set of all entities that meet some condition simpliciter, for each
set already known to exist, Aussonderung tells us that there is a
subset of that set of all those entities in the original set that
satisfy the condition. The class abstraction principle then becomes:
if set A exists, then for all entities x in A, x is in the subset of A
that satisfies condition C if and only if x satisfies condition C.
This approach solves Russell's paradox, because we cannot simply
assume that there is a set of all sets that are not members of
themselves. Given a set of sets, we can separate or divide it into
those sets within it that are in themselves and those that are not,
but since there is no universal set, we are not committed to the set
of all such sets. Without the supposition of Russell's problematic
class, the contradiction cannot be proven.

There have been subsequent expansions or modifications made on all
these solutions, such as the ramified type-theory of Principia
Mathematica, Quine's later expanded system of his Mathematical Logic,
and the later developments in set-theory made by Bernays, Gödel and
von Neumann. The question of what is the correct solution to Russell's
paradox is still a matter of debate.

See also the Russell-Myhill Paradox article in this encyclopedia.
4. References and Further Reading

* Coffa, Alberto. "The Humble Origins of Russell's Paradox."
Russell 33 (1979): 31-7.
* Frege, Gottlob. The Basic Laws of Arithmetic: Exposition of the
System. Edited and translated by Montgomery Furth. Berkeley:
University of California Press, 1964.
* Frege, Gottlob. Correspondence with Russell. In Philosophical
and Mathematical Correspondence. Translated by Hans Kaal. Chicago:
University of Chicago Press, 1980.
* Geach, Peter T. "On Frege's Way Out." Mind 65 (1956): 408-9.
* Grattan-Guinness, Ivor. "How Bertrand Russell Discovered His
Paradox." Historica Mathematica 5 (1978): 127-37.
* Hatcher, William S. Logical Foundations of Mathematics. New
York: Pergamon Press, 1982.
* Quine, W. V. O. "New Foundations for Mathematical Logic." In
From a Logical Point of View. 2d rev. ed. Cambridge, MA: Harvard
University Press, 1980. (First published in 1937.)
* Quine, W. V. O. "On Frege's Way Out." Mind 64 (1955): 145-59.
* Russell, Bertrand. Correspondence with Frege. In Philosophical
and Mathematical Correspondence, by Gottlob Frege. Translated by Hans
Kaal. Chicago: University of Chicago Press, 1980.
* Russell, Bertrand. The Principles of Mathematics. 2d. ed.
Reprint, New York: W. W. Norton & Company, 1996. (First published in
1902.)
* Zermelo, Ernst. "Investigations in the Foundations of Set Theory
I." In From Frege to Gödel, ed. by Jean van Heijenoort. Cambridge, MA:
Harvard University Press, 1967. (First published in 1908.)