# Set Theories and Russell’s Paradox

The origin of set theories can be traced back to Georg Cantor’s *Über eine Eigenshaft des Inbegriffes aller reellen algebraischen Zahlen* (“On a Property of the System of all the Real Algebraic Numbers”), published in 1874. He defined a set as follow:

"By a set we are to understand any collection into a whole M of definite and distinguishable objects of our intuition or our thought. These objects are called the elements of M" (Reference: David M. Burton’s “The History of Mathematics” (1997), p591.)

## A simple explanation of set theory and Russell’s paradox

**A set and a set of sets**

The early set theorists, operating in a world of what we now call "naive set theory", loosely defined a set (a class) as a collection of things.

A finite collection of variables, like {x, y, z}, should be a set. An infinite collection of numbers, like the natural numbers N = {1, 2, 3, 4, 5, ...} should also be a set. In geometry, the collection of all points that form a line between two given points is also a set.

A set can also be a collections of sets. The question is can a set contain itself as a member?

If we have a set of all natural numbers, we could certainly have a set of everything that is not a natural number. This set would include quite a few things — the numbers -3, 1/2, and π are all not naturals, and so they would be members. The word "pizza" is not a natural number, so that would be a member. The state of California is not a natural number as well, so we would throw that in there too.

Since this set is itself pretty clearly not a natural number, but instead an enormous collection of everything ever that is not a natural number, it must be a member of itself.

Indeed, with our naive definition of a set, it is tempting to consider a set of everything – “a set of all sets”. Naturally, being itself a set, the set of all sets would also have to contain itself as an element.

**Russell's Paradox**

Let's first look at __the set of all sets that contain themselves as member__, and let's call this set A.

We've seen a couple examples of set A — the set of everything that is not a natural number, and the set of all sets.

Does A contain itself?

According to "naive set theory", if A satisfies the condition we set up for being a member of A, we can say that A contains itself as a member. if A doesn't satisfy the condition for being in A, then A is not a member. There is no paradox here.

The paradox comes in when we build __the set of all sets that do not contain themselves__ as members. Let's call this set B.

Does B contain itself?

If we suppose B contains itself as a member. We defined B, however, as the set of all sets that do not contain themselves. So if B does contain itself, it goes against the condition we used to define B, and thus B does not contain itself.

But then if B does not contain itself, it does satisfy the condition to be a member of itself, and so it would have to contain itself.

This gives us a contradiction — the set of all sets that are

*not*members of themselves simultaneously must and cannot be a member of itself. This contradiction makes "naive set theory" inconsistent — we have a statement that has to be simultaneously true and false.

In 1902, Bertrand Russell identified this problem which is known as Russell's Paradox.

**Modern Set Theory Axiom**

The modern set theory axioms are very specific about how to build sets out of other sets. In particular, the axioms very quickly forbid a set from being a member of itself. We are also much more careful with constructions like "the set of everything that is not a natural number". Rather than using a broad universe of "everything", sets like this must be constructed as subsets of a larger set that we have already defined. So, I can define the set of all real numbers that are not natural numbers, but I cannot make a set of "everything" that is not a natural number.

## The axiomatization of set theory

In order to avoid the paradoxes and put it on a firm footing, set theory had to be axiomatized.

The first axiomatization was due to Zermelo (1908). Zermelo's axiomatization avoids Russell's Paradox by means of the Separation axiom, which is formulated as quantifying over properties of sets, and thus it is a second-order statement.

Further work by Skolem and Fraenkel led to the formalization of the Separation axiom in terms of formulas of first-order.

A further addition, by von Neumann, of the axiom of Foundation, led to the standard axiom system of set theory, known as the Zermelo-Fraenkel axioms plus the Axiom of Choice, or ZFC.

Other axiomatizations of set theory, such as those of von Neumann-Bernays-Gödel (NBG), or Morse-Kelley (MK), allow also for a formal treatment of proper classes.

The axioms of set theory

ZFC is an axiom system formulated in first-order logic with equality and with only one binary relation symbol ∈ for membership. Thus, we write A∈B to express that *A* is a member of the set *B*. We state below the axioms of ZFC informally.

The axioms of ZFC

*Extensionality*: If two sets *A* and *B* have the same elements, then they are equal.

*Null Set*: There exists a set, denoted by ∅ and called the *empty set*, which has no elements.

*Pair*: Given any sets *A* and *B*, there exists a set, denoted by {*A*,*B*}, which contains *A* and *B* as its only elements. In particular, there exists the set {*A*} which has *A* as its only element.

*Power Set*: For every set*A* there exists a set, denoted by P(*A*) and called the power set of *A*, whose elements are all the subsets of *A*.

*Union*: For every set *A*, there exists a set, denoted by ⋃*A* and called the union of *A*, whose elements are all the elements of the elements of *A*.

*Infinity*: There exists an infinite set. In particular, there exists a set *Z* that contains ∅ and such that if *A*∈*Z*, then ⋃{*A*,{*A*}}∈*Z*.

*Separation*: For every set *A* and every given property, there is a set containing exactly the elements of *A* that have that property. A property is given by a formula φ of the first-order language of set theory.

Thus, Separation is not a single axiom but an axiom schema, that is, an infinite list of axioms, one for each formula φ.

*Replacement*: For every given *definable function* with domain a set *A*, there is a set whose elements are all the values of the function.

Replacement is also an axiom schema, as definable functions are given by formulas.

*Foundation*: Every non-empty set *A* contains an ∈-minimal element, that is, an element such that no element of *A* belongs to it.

These are the axioms of Zermelo-Fraenkel set theory, or ZF. The axioms of Null Set and Pair follow from the other ZF axioms, so they may be omitted. Also, Replacement implies Separation.

Finally, there is the Axiom of Choice (AC):

*Choice*: For every set *A* of pairwise-disjoint non-empty sets, there exists a set that contains exactly one element from each set in *A*.

The AC was, for a long time, a controversial axiom. On the one hand, it is very useful and of wide use in mathematics. On the other hand, it has rather unintuitive consequences, such as the Banach-Tarski Paradox, which says that the unit ball can be partitioned into finitely-many pieces, which can then be rearranged to form two unit balls. The objections to the axiom arise from the fact that it asserts the existence of sets that cannot be explicitly defined. But Gödel's 1938 proof of its consistency, relative to the consistency of ZF, dispelled any suspicions left about it.

The Axiom of Choice is equivalent, modulo ZF, to the *Well-ordering Principle*, which asserts that every set can be well-ordered, i.e., it can be linearly ordered so that every non-empty subset has a minimal element.

Although not formally necessary, besides the symbol ∈∈ one normally uses for convenience other auxiliary defined symbols. For example,

*A*⊆*B* expresses that *A* is a subset of *B*, i.e., every member of *A* is a member of *B*.

Other symbols are used to denote sets obtained by performing basic operations, such as

*A*∪*B*, which denotes the union of *A* and *B*, i.e., the set whose elements are those of *A* and *B*; or

*A*∩*B*, which denotes the intersection of *A* and *B*, i.e., the set whose elements are those common to *A* and *B*.

The ordered pair (*A*,*B*) is defined as the set {{*A*},{*A*,*B*}}.

Thus, two ordered pairs (*A*,*B*) and (*C*,*D*) are equal if and only if *A*=*C* and *B*=*D*.

And the Cartesian product *A*×*B* is defined as the set of all ordered pairs (*C*,*D*) such that *C*∈*A* and *D*∈*B*.

Given any formula φ(*x*,*y1*,…,*yn*) , and sets *A*,*B1*,…,*Bn* , one can form the set of all those elements of* A* that satisfy the formula φ(*x*, *B1*,…, *Bn*). This set is denoted by {*a*∈*A*:φ(*a*,*B1*,…,*Bn*)}.

In ZF one can easily prove that all these sets exist.

## Russell's Paradox

Naïve set theory assumes the so-called naïve or unrestricted Comprehension Axiom, the axiom that for any formula φ(*x*) containing *x* as a free variable, there will exist the set {*x* : φ(*x*)} whose members are exactly those objects that satisfy φ(x). Thus, if the formula φ(*x*) stands for “*x* is prime”, then {*x* : φ(*x*)} will be the set of prime numbers.

But from the assumption of this axiom, Russell’s contradiction follows. For example, if we let φ(*x*) stand for *x* ∈ *x* and let *R *= {x: ~φ(*x*)}, then *R* is the set whose members are exactly those objects that are *not* members of themselves.

Is *R* a member of itself? If it is, then it must satisfy the condition of not being a member of itself and so it is not. If it is not, then it must not satisfy the condition of not being a member of itself, and so it must be a member of itself. Since by classical logic one case or the other must hold – either *R* is a member of itself or it is not – it follows that the theory implies a contradiction.

## Russell's Paradox

**Russell's paradox** (also known as **Russell's antinomy**), discovered by Bertrand Russell in 1901, showed that the naive set theory of Frege leads to a contradiction.

Consider the set *R* of all sets that do not contain themselves as members. In set-theoretic notation:

*R* = {*A* | *A* ∉ *A*}

Assume, as in Frege's *Grundgesetze der Arithmetik*, that sets can be freely defined by any condition. Then *R* is a well-defined set. The problem arises when it is considered whether *R* is an element of itself. If *R* is an element of *R*, then according to the definition, *R* is not an element of *R*; if *R* is not an element of *R*, then *R* has to be an element of *R*, again by its very definition: Hence a contradiction.

Russell's paradox was a primary motivation for the development of set theories with a more elaborate axiomatic basis than simple extensionality and unlimited set abstraction. The paradox drove Russell to develop type theory and Ernst Zermelo to develop an axiomatic set theory, which evolved into the now-canonical Zermelo–Fraenkel set theory.

## Russell's Paradox

According to naive set theory, any definable collection is a set.

Let *R* be the set of all sets that are *not* members of themselves. If *R* is not a member of itself, then its definition dictates that it must contain itself, and if it contains itself, then it contradicts its own definition as the set of all sets that are not members of themselves. This contradiction is Russell's paradox. Symbolically:

Let *R* = {*x* | *x* ∉ *x*}, then *R* ∈ *R* ↔ *R* ∉ *R*

## Set-Theoretic Paradoxes

Russell's paradox arises from considering the Russell set R of all sets that are not members of themselves, that is, the set defined defined by *R* = {*x* | *x* ∉ *x *}.

The contradiction is then derived by asking whether *R* is a member of itself, that is, whether *R* ∈ *R* holds. If *R* ∈ *R* then *R* is a member of itself, and thus *R* ∉ *R*, by definition of *R*. If, on the other hand, *R* ∉ *R* then *R* is not a member of itself, and thus *R* ∈ *R*, again by definition of *R*.

## Russell's Paradox

Russell’s paradox, statement in set theory, devised by the English mathematician-philosopher Bertrand Russell, that demonstrated a flaw in earlier efforts to axiomatize the subject.

Russell found the paradox in 1901 and communicated it in a letter to the German mathematician-logician Gottlob Frege in 1902. Russell’s letter demonstrated an inconsistency in Frege’s axiomatic system of set theory by deriving a paradox within it.

Frege had constructed a logical system employing an unrestricted comprehension principle. The comprehension principle is the statement that, given any condition expressible by a formula ϕ(x), it is possible to form the set of all sets x meeting that condition, denoted {*x* | ϕ(*x*)}. For example, the set of all sets—the universal set—would be {*x* | *x* = *x*}.

It was noticed in the early days of set theory, however, that a completely unrestricted comprehension principle led to serious difficulties. In particular, Russell observed that it allowed the formation of {*x* | *x* ∉ *x*}, the set of all non-self-membered sets, by taking ϕ(*x*) to be the formula *x* ∉ *x*. Is this set—call it *R*—a member of itself? If it is a member of itself, then it must meet the condition of its not being a member of itself. But if it is not a member of itself, then it precisely meets the condition of being a member of itself. This impossible situation is called Russell’s paradox.

The significance of Russell’s paradox is that it demonstrates in a simple and convincing way that one cannot both hold that there is meaningful totality of all sets and also allow an unfettered comprehension principle to construct sets that must then belong to that totality. (Russell spoke of this situation as a “vicious circle.”)

Set theory avoids this paradox by imposing restrictions on the comprehension principle. The standard Zermelo-Fraenkel axiomatization (ZF) does not allow comprehension to form a set larger than previously constructed sets. (The role of constructing larger sets is given to the power-set operation.) This leads to a situation where there is no universal set—an acceptable set must not be as large as the universe of all sets.

A very different way of avoiding Russell’s paradox was proposed in 1937 by the American logician Willard Van Orman Quine. In his paper “New Foundations for Mathematical Logic,” the comprehension principle allows formation of {*x* | ϕ(*x*)} only for formulas ϕ(*x*) that can be written in a certain form that excludes the “vicious circle” leading to the paradox. In this approach, there is a universal set.

## Fixing Russell's Paradox

Naive set theory allow mathematicians to construct the set of all sets that satisfy any property. The axiom that says that you're allowed to do this was formally introduced by Frege and is called *unrestricted comprehension*.

Russell found out that unrestricted comprehension principle makes it possible for mathematicians to construct __the set of all sets that don't contain themselves__ and this leads to a contradiction.

The now-standard fix is to replace unrestricted comprehension with a weaker axiom called *restricted comprehension*. With restricted comprehension, you're no longer allowed to construct the set of all sets that satisfy some property. Now you're only allowed to construct the set of all elements of some other set that satisfy some property. (In the now-standard approach to set theory, the elements of sets are other sets. It forbids a set from being a member of itself.)

To fix Russell's paradox with restricted comprehension, you need to construct the set of all sets first. And another axiom, *foundation*, prohibits such a set from existing.

## Russell's Paradox and Fixing Russell's Paradox

Russell found the paradox in 1901 and communicated it in a letter to the German mathematician-logician Gottlob Frege in 1902. Russell's letter demonstrated an inconsistency in Frege's axiomatic system of set theory by deriving a paradox within it.

Frege had constructed a logical system employing an unrestricted comprehension principle. The comprehension principle is the statement that, given any condition expressible by a formula ϕ(*x*), it is possible to form the set of all sets *x* meeting that condition, denoted {*x* | ϕ(*x*)}. For example, the set of all sets—the universal set—would be {*x* | *x* = *x*}.

It was noticed in the early days of set theory, however, that a completely unrestricted comprehension principle led to serious difficulties. In particular, Russell observed that it allowed the formation of {*x* | *x* ∉ *x*}, the set of all non-self-membered sets, by taking ϕ(*x*) to be the formula *x* ∉ *x*. Is this set—call it *R*—a member of itself? If it is a member of itself, then it must meet the condition of its not being a member of itself. But if it is not a member of itself, then it precisely meets the condition of being a member of itself. This impossible situation is called Russell's paradox.

The significance of Russell's paradox is that it demonstrates in a simple and convincing way that one cannot both hold that there is meaningful totality of all sets and also allow an unfettered comprehension principle to construct sets that must then belong to that totality. (Russell spoke of this situation as a “vicious circle.”)

Set theory avoids this paradox by imposing restrictions on the comprehension principle. The standard Zermelo-Fraenkel axiomatization does not allow comprehension to form a set larger than previously constructed sets. (The role of constructing larger sets is given to the power-set operation.) This leads to a situation where there is no universal set—an acceptable set must not be as large as the universe of all sets.

A very different way of avoiding Russell's paradox was proposed in 1937 by the American logician Willard Van Orman Quine. In his paper “New Foundations for Mathematical Logic,” the comprehension principle allows formation of {*x* | ϕ(*x*)} only for formulas ϕ(x) that can be written in a certain form that excludes the “vicious circle” leading to the paradox. In this approach, there is a universal set.

**.................................................**

## Fixing Russell's Paradox

When set theory was invented it was assumed that given any predicate, there was a set containing all the things that satisfied the predicate. This assumption is called naive comprehension. Unfortunately this allowed paradoxes like the set of all sets not containing themselves.

So people invented restricted axioms of comprehension. These are rules that say that only certain predicates give rise to sets. There are different kinds of set theory with different comprehension restrictions.

One idea for limiting comprehension is to say that if the class of things satisfies the predicate is too big, the class is not a set. All the commonly used set theories use this idea. The set of all sets is very large indeed, so it is not a set in these theories.

There are other ways of restricting comprehension that get rid of the paradoxical sets but do allow a universal set. One such set theory was invented by Quine and called New Foundations.

**.................................................**

Russell’s paradox arises if you consider the set *R* = {*x* : *x* ∉ *x*}. Ask yourself if *R* ∈ *R*. If you suppose so, then by the definition of unrestricted set comprehension *R* ∉ *R*. You have a contradiction, so it must be the opposite of what you supposed, that is, *R* ∉ *R*.. But this is the same as saying *R* belongs to the complement of itself, that is, *R* ∈ *R*. You now have another contradiction, but this is far worse, since you have no hypotheses. The whole theory is logically inconsistent.

In set theory there are two ways for getting rid of the Russell’s paradox: either you disallow the set of all sets and other similar sets (see for example the Zermelo-Fraenkel set theory), or you allow them, but you also restrict the way they are used (see for example the Morse-Kelley set theory).

In the first case, set comprehension says if you have a set *A* you can have {*x* ∈ *A* : ϕ(*x*)} (notice: writing {*x* : ϕ(*x*)} is just wrong in this case, because you have to have an initial set). If you now define *R* = {*x* ∈ *A* : *x* ∉ *x*} and you repeat the same passages as before, it only follows that *R* ∉ *A*. There's no contradiction and the theory is consistent.

In the second case, you consider classes, not just sets. Sets are classes that belong to some other class, while proper classes are classes that belong to no class. Set comprehension, in this case, says you can have {*x* : ϕ(*x*)}, but all its members are sets by definition. If try to reproduce Russell’s paradox, you get that *R* ∉ *R*. If you then suppose that *R* is a set, then you have a contradiction, so *R* must be a proper class. This is all you get. No contradictions. The theory is consistent.

## SOLUTIONS TO THE PARADOX

Bertrand Russell devised what he called the theory of types to prevent the paradox. In this theory, a set would be defined as being of a distinct type, like type 1. The elements of type 1 sets can then only be included in a set of type 2 because sets of type 2 are defined as containing only sets of type 1. Thus, we do not need to worry about whether or not a set of type 2 can contain itself because it’s defined as only containing sets of type 1. This theory creates a sort of hierarchy of sets.

The most accepted solution today is that of Zermelo and Fraenkel. Zermelo’s axiom of specification is, "to every set A and every definite property P(x) there corresponds a set whose elements are exactly those elements x in A for which the property P(x) holds" (Burton, 616). What this axiom does is require a preexisting set A and some property P(x) to make a new set. Previously, only the property P(x) was required. This changes the set S to . Now is impossible because it would have to satisfy the two conditions that and , which it clearly cannot. The is clear because we just state that in order for , it must satisfy the property that . If we consider the other possibility that we see that it does satisfy the property P(x), but cannot meet our second requirement that . This is because if then it follows, by our definition, that , which we already reasoned is not true. Therefore we conclude that by the law of excluded middle, which says that every proposition is either true or false (Burton, 612), . Therefore, failed the second of the two requirements to be in the set S so we conclude that and have avoided the paradox.

## Russell’s Early Responses to the Paradoxs

Russell’s own response to the paradox came with his aptly named theory of types. Believing that self-application lay at the heart of the paradox, Russell’s basic idea was that we can avoid commitment to *R* (the set of all sets that are not members of themselves) by arranging all sentences (or, more precisely, all propositional functions, functions which give propositions as their values) into a hierarchy. It is then possible to refer to all objects for which a given condition (or predicate) holds only if they are all at the same level or of the same “type.”

This solution to Russell’s paradox is motivated in large part by adoption of the so-called *vicious circle principle*. The principle in effect states that no propositional function can be defined prior to specifying the function’s scope of application. In other words, before a function can be defined, one must first specify exactly those objects to which the function will apply (the function’s domain). For example, before defining the predicate “is a prime number,” one first needs to define the collection of objects that might possibly satisfy this predicate, namely the set, N, of natural numbers.

As Whitehead and Russell explain,

An analysis of the paradoxes to be avoided shows that they all result from a kind of vicious circle. The vicious circles in question arise from supposing that a collection of objects may contain members which can only be defined by means of the collection as a whole. Thus, for example, the collection of *proposition*s will be supposed to contain a proposition stating that “all propositions are either true or false.” It would seem, however, that such a statement could not be legitimate unless “all propositions” referred to some already definite collection, which it cannot do if new propositions are created by statements about “all propositions.” We shall, therefore, have to say that statements about “all propositions” are meaningless. … The principle which enables us to avoid illegitimate totalities may be stated as follows: “Whatever involves *all* of a collection must not be one of the collection”; or, conversely: “If, provided a certain collection had a total, it would have members only definable in terms of that total, then the said collection has no total.” We shall call this the “vicious-circle principle,” because it enables us to avoid the vicious circles involved in the assumption of illegitimate totalities. (1910, 2nd edn 37)

If Whitehead and Russell are right, it follows that no function’s scope of application will ever be able to include any object presupposed by the function itself. As a result, propositional functions (along with their corresponding propositions) will end up being arranged in a hierarchy of the kind Russell proposes.

Although Russell first introduced his theory of types in his 1903 *Principles of Mathematics*, he recognized immediately that more work needed to be done since his initial account seemed to resolve some but not all of the paradoxes.

## 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.

## Russell's Theory of Types

Theory of types, in logic, a theory introduced by the British philosopher Bertrand Russell in his *Principia Mathematica* to deal with logical paradoxes arising from the unrestricted use of predicate functions as variables.

Arguments of three kinds can be incorporated as variables: (1) In the pure functional calculus of the first order, only individual variables exist. (2) In the second-order calculus, propositional variables are introduced. (3) Higher orders are achieved by allowing predicate functions as variables. The type of a predicate function is determined by the number and type of its arguments. By not allowing predicate functions with arguments of equal or higher type to be used together, contradictions within the system are avoided.

In the system of Russell and Whitehead, the formal objects of the theory are divided into types. The lowest type consists of all individuals, the next type is composed of all predicates, the succeeding type is composed of all predicates of predicates, and so on.

In order to avoid the paradox which he discovered, Russell formulated a Theory of Types. It was wrong to treat classes as randomly classifiable objects. Classes and individuals were of different logical types, and what can be true or false of one cannot be significantly asserted of the other. ‘The class of dogs is a dog’ should be regarded not as false but as meaningless. Similarly, what can meaningfully be said of classes cannot meaningfully be said of classes of classes, and so on through the hierarchy of logical types. If the difference of type between the different levels of the hierarchy is observed, then the paradox will not arise. (Antony Kenny”s *A Brief History of Western Philosophy* (1998 Blackwell Publishers Ltd), p325.)

## Simple Type Theory

The types can be defined as

1.*i* is the type of individuals

2.( ) is the type of propositions

3.if *A*_{1},…,*A _{n}* are types then (

*A*

_{1},…,

*A*) is the type of

_{n}*n*-ary relations over objects of respective types

*A*

_{1},…,

*A*

_{n}For instance, the type of binary relations over individuals is (

*i*,

*i*), the type of binary connectives is (( ),( )), the type of quantifiers over individuals is ((

*i*)).

For forming propositions we use this type structure: thus

*R*(

*a*

_{1},…,

*a*) is a proposition if

_{n}*R*is of type (

*A*

_{1},…,

*A*) and

_{n}*a*is of type

_{i}*A*for i = 1,…,

_{i}*n*. This restriction makes it impossible to form a proposition of the form

*P*(

*P*): the type of

*P*should be of the form (

*A*), and

*P*can only be applied to arguments of type

*A*, and thus cannot be applied to itself since

*A*is not the same as (

*A*).

Russell observes, that it becomes necessary “to distinguish (1) terms, (2) classes, (3) classes of classes, and so on *ad infinitum*”. Moreover, these
collections will be disjoint, and to able to assert *x* ∈ *u* requires that the collection to which *x* belongs should be of a degree one lower than that to which *u* belongs. This expedient leads to a resolution of the paradox, since *x* ∈ *x* has now been rendered a meaningless proposition. The hierarchy of collections (1), (2), (3), ... is the germ of the doctrine of types.

## Self-Reference

In the context of language, *self-reference* is used to denote a statement that refers to itself or its own referent. The most famous example of a self-referential sentence is the *liar sentence*: “This sentence is not true.” Self-reference is often used in a broader context as well. For instance, a picture could be considered self-referential if it contains a copy of itself (see the animated image); and a piece of literature could be considered self-referential if it includes a reference to the work itself. In philosophy, self-reference is primarily studied in the context of language. Self-reference within language is not only a subject of philosophy, but also a field of individual interest in mathematics and computer science, in particular in relation to the foundations of these sciences.

The philosophical interest in self-reference is to a large extent centered around the paradoxes. A *paradox* is a seemingly sound piece of reasoning based on apparently true assumptions that leads to a contradiction. The liar sentence considered above leads to a contradiction when we try to determine whether it is true or not. If we assume the sentence to be true, then what it states must be the case, that is, it cannot be true. If, on the other hand, we assume it not to be true, then what it states is actually the case, and thus it must be true. In either case we are led to a contradiction. Since the contradiction was obtained by a seemingly sound piece of reasoning based on apparently true assumptions, it qualifies as a paradox. It is known as the* liar paradox*.

Most paradoxes of self-reference may be categorised as either *semantic*, *set-theoretic* or *epistemic*. The semantic paradoxes, like the liar paradox, are primarily relevant to theories of truth. The set-theoretic paradoxes are relevant to the foundations of mathematics, and the epistemic paradoxes are relevant to epistemology. Even though these paradoxes are different in the subject matter they relate to, they share the same underlying structure, and may often be tackled using the same mathematical means.

In the present entry, we will first introduce a number of the most well-known paradoxes of self-reference, and discuss their common underlying structure. Subsequently, we will discuss the profound consequences that these paradoxes have on a number of different areas: theories of truth, set theory, epistemology, foundations of mathematics, computability. Finally, we will present the most prominent approaches to solving the paradoxes.

•1. Paradoxes of Self-Reference

◦1.1 Semantic Paradoxes

◦1.2 Set-Theoretic Paradoxes

◦1.3 Epistemic paradoxes

◦1.4 Common Structures in the Paradoxes

◦1.5 A Paradoxes without Self-Reference

•2. Why the Paradoxes Matter

◦2.1 Consequences of the Semantic Paradoxes

◦2.2 Consequences of the Set-Theoretic Paradoxes

◦2.3 Consequences of the Epistemic Paradoxes

◦2.4 Consequences Concerning Provability and Computability

•3. Solving the paradoxes

◦3.1 Building Explicit Hierarchies

◦3.2 Building Implicit Hierarchies

■3.2.1 Kripke's Theory of Truth

■3.2.2 Extensions and Alternatives to Kripke's Theory of Truth

■3.2.3 Implicit Hierarchies in Set Theories

◦3.3 General Fixed Point Approaches

## Barber’s Paradox

Russell's Paradox is sometimes explained by the easier understood example known as Barber’s Paradox: "If a barber shaves all and only those men who do not shave themselves, does he shave himself?".

If he does, then he mustn't, because he doesn't shave men who shave themselves, and if he doesn't, then he must, because he shaves every man who doesn't shave himself. Both possibilities lead to a contradiction.