Bertrand Russell and the Paradoxes of Set Theory

views updated

Bertrand Russell and the Paradoxes of Set Theory

Overview

Bertrand Russell's discovery and proposed solution of the paradox that bears his name at the beginning of the twentieth century had important effects on both set theory and mathematical logic.

Background

At about the same time in the 1870s, Georg Cantor (1845-1918) developed set theory and Gottlob Frege (1848-1925) developed mathematical logic. These two strains of theory soon became closely intertwined. Cantor recognized from the beginning that set theory was replete with paradoxes. He, along with other mathematicians and logicians or philosophers of mathematics such as Bertrand Russell (1872-1970), Alfred North Whitehead (1861-1947), and Edmund Husserl (1859-1938), tried to resolve these difficulties.

Cantor himself discovered one of the earliest paradoxes of set theory in 1896. The power set of any set S is the set of all subsets of S. The power set of S cannot be a member of S. But consider the set U of all sets. The power set of U would, by the definition of U, be a member of U. This contradiction is Cantor's paradox. One possible solution is to stipulate that the set of all sets cannot itself be a set, but must be treated as something else, a "class."

Burali-Forti's paradox, or the ordinal paradox, discovered in 1897 by Cesare Burali-Forti (1861-1931), is akin to Cantor's. It says that the greatest ordinal is greater than any ordinal and therefore cannot be an ordinal. In set theory ordinal numbers refer to the relationship among the members of a well-ordered set, that is, any set whose non-empty subsets each have a "least" or "lowest" member.

In 1901 Russell discovered the paradox that the set of all sets that are not members of themselves cannot exist. Such a set would be a member of itself if and only if it were not a member of itself. This paradox is based on the fact that some sets are members of themselves and some are not.

Russell's paradox is related to the classic paradox of the liar, attributed to either the Cretan philosopher Epimenides (7th century b.c.) or the Greek philosopher Eubulides (4th century b.c.). Is someone who says, "I am lying," telling the truth or lying? In other words, is that person a member of the set of liars or the set of truth-tellers?

Russell's paradox is effectively illustrated by the barber paradox. Divide all the men in a certain town into two non-intersecting sets: the set X of those who shave themselves and the set Y of those who are shaved by a barber. Such a barber (unless she is a woman) cannot exist. If he exists, then he both shaves and does not shave himself; that is, he is a member of both set X and set Y. He is part of the definition of set Y, but at the same time he is expected to be a member of either set X or set Y.

These paradoxes are self-referential because they conflate the definition with what is being defined. They confound the properties that define a set with the members of the set. They result from their implicit confusion between the "object language," which talks about the individual members of sets, and the "metalanguage," which talks about the sets themselves. Russell's discovery led immediately to much research in set theory and logic to define the nature of sets, classes, and membership more accurately.

Russell's theory of types may solve these paradoxes by clarifying the distinction between object language and metalanguage. It says that if all statements are classified in a hierarchy, or "orders," according to the level of their subject matter, then any talk of the set of all sets that are not members of themselves can be avoided. Thus first-order logic quantifies over individuals; second-order, over sets of individuals; third-order, over sets of sets of individuals; and so on. To confuse orders is to make a "category mistake."

There are many variants of Russell's paradox and many associated paradoxes. Richard's paradox, announced in 1905 by Jules Antoine Richard (1862-1956), deals with problems of defining sets. Berry's paradox, a simplified version of Richard's, was introduced by Russell in 1906 but attributed to George Berry, a librarian at Oxford University. The Grelling-Nelson paradox, sometimes called the heterological paradox, was stated in 1908 by Kurt Grelling (1886-1942) and Leonard Nelson (1882-1927). It says that some adjectives describe themselves and some do not. Adjectives that do not describe themselves are heterological. Is the adjective "heterological" itself heterological? If so, then it is not; and if not, then it is.

Russell first mentioned his theory of types in a 1902 letter to Frege. He published it in 1903 and revised it in 1908. The earlier version is called the simple theory of types, and the later version, specifically directed at the liar and Richard's paradox, is called the ramified theory of types.

Impact

Logical paradoxes are generally of two kinds: set theoretic and semantic. Set theoretic paradoxes such as Cantor's, Burali-Forti's, Russell's, and the barber, expose contradictions or complications in set theory. Semantic paradoxes, such as the liar, Richard's, Berry's, and the Grelling-Nelson, raise questions of truth, definability, and language. The demarcation between these two kinds of paradoxes is not clear. Frank Plumpton Ramsey (1903-1930) believed that all logical paradoxes were set theoretic paradoxes and occurred only in the object language, while semantic paradoxes occurred only in the metalanguage and involved only meanings, not logic.

In the wake of and partially in reaction to Russell's theory of types, mathematicians made several attempts to refine set theory. In 1908 Ernst Zermelo (1871-1953), building upon the work of Cantor and Richard Dedekind (1831-1916), formulated the axioms that became the basis of modern set theory. These axioms, modified by Abraham Fraenkel (1891-1965), are known as "ZF." With the addition of the axiom of choice, which states that for any two or more non-empty sets there exists another non-empty set containing exactly one member from each, they are called "ZFC."

In 1925 John von Neumann (1903-1957) offered an alternative set theory with an axiom disallowing any set containing itself as a member. This theory, modified by Paul Isaac Bernays (1888-1977) and Kurt Gödel (1906-1978) is called "NBG."

The logician Alfred Tarski (1901-1983) refined the distinction between object language and metalanguage and thus was able to resolve semantic paradoxes without relying upon Russell's theory of types. Yet his solution of the liar paradox resembles Russell's and can be regarded as a variant of it.

ERIC V.D. LUFT