LOGICAL PARADOXES

A paradox is an argument that derives or appears to derive an absurd conclusion by rigorous deduction from obviously true premises. Perhaps the most famous is Zeno's paradox of the runner, who, before she can reach her destination, first has to reach the point halfway there, and who, before reaching the halfway point, has to reach the quarter point, before which she must reach the point one-eighth of the way to the destination, and so on. The conclusion is that no runner ever reaches her goal, or even gets started.

To contemporary ears the argument does not sound so irresistible, since we can attribute its appeal either to an ambiguity in the use of "never" ("at no point in time" versus "at no point in the sequence") or to a dubious hidden premise that it is impossible to perform infinitely many tasks in a finite time, perhaps because there is a positive minimum to the length of time each task requires. To the ancients, however, the paradox was deeply disturbing. The most influential response was that of Aristotle, who concluded that it was not possible to partition the runner's path into infinitely many parts. Any segment of the runner's course can be divided in two, so that there is no finite bound on how many pieces the path contains, but the process of partitioning the path never concludes in a path with infinitely many parts. The number of segments that make up the path is said to be potentially infinite. The moral Aristotle drew from Zeno is that there is, in nature or in mathematics, no actual infinite. "Potentially infinite" is not like "potentially hot." When we say that a poker is potentially hot, we mean that, at some time and circumstance, it could be actually hot, whereas when we say that a line is potentially infinite, we mean that it can always be made longer but not that there is any time at which it is actually infinite.

Aristotle's doctrine commanded wide adherence among philosophers and mathematicians, but toward the end of the nineteenth century it came widely to be seen as too restrictive. New mathematics embraced not only infinitely long lines, but also an analysis of a line as made up of infinitely many points, as well as infinite sets, infinite numbers, and infinite-dimensional geometry.

The new mathematics brought a spate of new paradoxes, which, in their formal structure, resemble the semantic paradoxes, the first of which appeared in the sixth century BCE when Epimenides, himself a Cretan, declared that Cretans always lie. Provided Epimenides' neighbors are sufficiently mendacious, we are driven to the conclusion that, if his statement is true, it is false, and if false, true. Deep problems, or perhaps a single deep problem in different manifestations, afflict the foundations of both mathematics and linguistics.

Counting Beyond the Finite

Broadly speaking there were two reasons for repudiating of Aristotle's prohibition of the actual infinite. First as mathematics became vastly more general, finitistic techniques came to be seen as confining. The ancient Greeks had a marvelously sophisticated theory of polygons and conic sections, but a fully general theory of shapes requires such techniques as approximating an unruly curve by an infinite sequence of curves that are better behaved.

The second reason was the so-called arithmetization of geometry, brought about by the investigation of alternatives to Euclid's axiom that, given a line and a point not on the line, there is on their plane exactly one line through the point that never intersects the given line, no matter how far the two lines are extended. Once alternatives to Euclidean geometry emerged, one could no longer be fully confident that Euclid's axioms correctly described the world around us (and, indeed, these suspicions are confirmed by the general theory of relativity). The theory of real numbers remained at the center of modern mathematics, but since one could no longer identify the positive real numbers as the ratios of lengths of physical line segments, one was no longer sure what the theory referred to.

A strategy for answering this question can be found in William Hamilton's treatment of the complex numbers. Extending the real number system by introducing a fictitious solution to the equation "x ²+ 1 = 0" proves enormously useful mathematically, but one cannot help fretting that addressing algebraic problems with make-believe solutions is more an exercise in wishful thinking than legitimate science. Hamilton proposed to soothe this consternation by taking "complex number" to refer not to new and ontologically dubious entities but to familiar mathematical objects thought of in a new way. Namely, we treat a complex number as an ordered pair of ordinary real numbers, with appropriate operations.

Hamilton's construction presupposed the real numbers, but we can apply the same technique to secure the real numbers on a firmer basis. The starting point is easy enough. We can identify the positive rational numbers as ordered pairs of relatively prime positive integers, but the rationals have gaps—√2, for instance—and the modern theory of continuity and limits requires a number system without gaps. More precisely we want assurance that the least upper bound principle, according to which every nonempty set of real numbers that is bounded above has a least upper bound, is satisfied. Richard Dedekind solved this problem by identifying the real number with pairs 〈A,B 〉 that partition the rationals into nonempty, nonoverlapping sets with every member of A less than every member of B.

Dedekind's construction succeeded in securing the real numbers on a foundation that did not presuppose the truth of Euclidean geometry, but it required the unapologetic acceptance of infinite sets. It permitted real analysis to be seen as built upon a foundation in the theory of sets, and indeed set theory is widely perceived as providing a uniform foundation for all of mathematics.

The elevation of set theory to its central role received its greatest impetus from the work of Georg Cantor (1895, 1897) who extended elementary-school arithmetic so that infinite as well as finite sets could be counted. Doing so required him to confront Galileo's paradox. Two sets have the same number of elements if there is a one-one correspondence by which each member of one set is paired off with one and only one member of the other. It follows that there are just as many perfect squares as there are nonnegative integers, since we can pair off n with n ². But it seems obvious that there are more nonnegative integers than there are squares. A lot more, in fact, since as N grows the proportion of perfect squares among the first N integers becomes vanishingly small. The moral Galileo drew from this is that the notions of more and fewer cannot be applied to the infinite.

Overcoming Galileo's paradox was largely a matter of raw intellectual courage. Cantor had to resolve to follow the computations where they led, no matter how strongly the results he obtained contravened the intuitions obtained from grade-school experience with finite numbers. Stipulating that the cardinal number of S is equal to the cardinal number of T (in symbols, #(S ) = #(T )) if and only if S and T can be put in one-one correspondence and that #(S ) ≤ #(T ) if and only if S has the same cardinal number as a subset of T, we find that the familiar laws of order carry over directly, with one glaring exception. As Galileo's paradox illustrates, you can have #(S ) ≤ #(T ) even though T is a proper subset of S. Defining, for S and T disjoint, #(S ) + #(T ) = #(S ∪ T ), we find that the familiar laws of addition are largely upheld, but that particular computations yield wildly unexpected results. If we let ℵ₀ be the number of natural numbers, we find that ℵ₀ + ℵ₀ = ℵ₀ Similarly if we define #(S ) · #(T ) to be the cardinal number of the set of ordered pairs 〈s,t 〉 with s ∈ S and t ∈ T, we find ℵ₀ · ℵ₀ = ℵ₀. In fact for any infinite numbers κ and λ, we have κ + λ = κ · λ = max(κ,λ).

It is starting to look as if infinite arithmetic is remarkably easy: Whatever the question, the answer is "ℵ₀." This happy impression is dispelled when we turn to infinite exponentiation. Defining #(S )^#(T) to be the number of functions from T to S, we find that 2^#(T), which is the cardinal number of the power set of T (the set ℘(T ) of subsets of T ), is strictly greater than #(T ). That is, 2^#(T) ≥ (T ) and 2^#(T) ≠ #(T ). That #(℘(T )) ≥ #(T ) is easy; use the function that takes an element x of T to {x }. To see that #(T ) ≠ #(℘(T )), let F be a function from ℘(T ) to T. We want to see that F is not one-one, that is, that there exist distinct subsets U and V of T with F (U ) = F (V ), which we do by assuming F were one-one and deriving a contradiction. Define a binary relation E on T by stipulating that xEy if and only if x is an element of some set W with y = F (W ). Then for any element x of T and any subset V of T, we have xEF (V ) if and only if Vx. (Why? If xEF (V ), then there is a W with F (V ) = F (W ) and Wx ; because F is one-one, we must have V = W, hence Vx. Conversely if Vx, then we can find our set W with F (V ) = F (W ) and Wx by setting W equal to V.) In particular if we let R be the set of all elements of T that do not bear the relation E to themselves, we have, for any x, xEF (R ) if and only if Rx, which happens if and only if not xEx. Taking x equal to F (R ) reveals a contradiction.

In particular, the number of real numbers is 2^ℵ₀ so that there are more real numbers than there are natural numbers. To see that the real numbers are equinumerous with the numbers in the interval from 0 to 1, use the function that takes x to ½(^x _{|x |+1}+1). The proof that the real numbers between 0 and 1 are equinumerous with the sets of natural numbers uses the function that takes a real number to the set of places in its binary decimal expansion where 1s appear, although one has to tinker a bit to make allowance for numbers like ⅝, which has two different binary decimal expansions, 0.10100000000 … and 0.10011111111 ….

There are two fundamental ways we apply the counting numbers: To measure the size of a set, and to mark positions in a queue. For the first purpose we employ the English nouns, "one," "two," "three," and so on, whereas for the second we use the adjectives "first," "second," "third." … To generalize the first concept into the infinite Cantor developed his theory of infinite cardinal numbers, and for the second he introduced a theory of infinite so-called ordinal numbers. First some definitions. A binary relation L on a set S is an ordering if it meets the following three conditions, for any x, y, and z in S : If xLy and yLz, then xLz ; not xLx ; and either xLy, yLx, or x = y. The usual way of ordering the real numbers is an ordering, but it doesn't distinguish a first, second, and third real number. In order for the members of an ordered set to be counted by ordinal numbers, a further condition is required: A binary relation L on a set S is well-founded just in case every nonempty subset R of S has an L -least element, an element x of R such that there in no element y of R with yLx ; equivalently there is no infinite sequence s ₀, s ₁, s ₂, s ₃, … with s _{n +1}Ls _n. A well-founded ordering is a well-ordering. Cantor's second great innovation was to extend the notion of ordinal number to infinite well-orderings.

If L well-orders a set S and M well-orders T, an order isomorphism from L to M is a one-one correspondence that preserves the order relation, so that, for any x and y in S, we have: xLy if and only if f (x )Mf (y ). Two well-orderings have the same ordinal number if and only if they are order isomorphic. If α is the ordinal number of an ordering L on S and β is the ordinal number of an ordering M on T, we say that α ≤ β if and only if L is order-isomorphic to an initial segment of M. This provides a well-ordering of the ordinals, which supplies for each ordinal α a well-ordering of the ordinals less than α; its ordinal number is α. If L is a well-ordering of a set S there is a unique ordinal number associated with each element x of S that marks its position, namely the ordinal number of the well-ordering we get by restricting L to {y ∈ S : yLx and y ≠ x }.

Ernst Zermelo discovered a deep connection between cardinal and ordinal numbers: The cardinal numbers are well-ordered, so that the infinite cardinals can be placed in a sequence, ℵ₀, ℵ₁, ℵ₂, ℵ₃, …, and every cardinal number has the form ℵ_α, for some ordinal α.

Mr. Russell's Barber

The program of securing the theory of sets on a unified axiomatic basis was trenchantly pursued by Gottlob Frege. A prerequisite for such a program is a system of logic that is both highly powerful and fully explicit, and before Frege there was no such logic. Frege's program has a philosophical motive. He wanted to show that the laws of arithmetic are analytic, so that, by providing suitable definitions, the laws of arithmetic can be reduced to pure logic. The key idea is that to say Traveler is a horse and to say that Traveler is an element of {x : x is a horse} are two ways of saying the same thing, just like "Lee rode Traveler" and "Traveler was ridden by Lee."

The specific form taken by Frege's reduction of arithmetic to logic depends on his doctrine of concepts and objects. Proper names (such as "Traveler"), definite descriptions (such as "the horse Lee rode into battle"), and sentences (such as "Traveler is a horse") are saturated expressions, and they denote objects. Under Frege's rather eccentric usage, sentences are a species of name; they denote either the True or the False, which are objects. Open sentences, like "x is a horse" and "Lee rode x into battle," are unsaturated, and they denote concepts. When we complete an open sentence by replacing the variable by a name, we get a sentence that denotes either the True or the False. Open sentences are a special case of function sign, an unsaturated expression whose completion yields a name. A concept is a special kind of function, one that cannot take any values other than the True and the False. There are, in addition, functions that demand more than one argument, represented by such multiply unsaturated phrases as "x rode y," and so-called second-level functions that take ordinary functions as arguments.

The fundamental principle of Frege's set theory, his Basic Law V (Basic Laws I through IV are unexceptionable principles of logic), associates a set, the object {x : Fx }, with each concept F in such a way that, for any concepts F and G, {x : Fx } is equal to {x :Gx } if and only if, for every object x, we have Fx if and only if Gx. The left-to-right direction of this axiom is the axiom of extensionality, which has proven harmless. Extensionality is what distinguishes sets from properties. The property of being a human being is different from the property of being a featherless biped, even though {x : x is a featherless biped} = {x : x is a human being}. The right-to-left direction has proven deeply problematic. It asserts that the second-level function taking the concept F to {x : Fx } is one-one. On the basis of this axiom we can define "∈": z ∈y if and only if, for some F, y = {x : Fx } and Fz, and we can derive the so-called comprehension principle that, for any F and z, z ∈ {x : Fx } if and only if Fz, just as in the proof of Cantor's theorem, and just as before, we can derive a contradiction by asking whether {x : x ∉ x } is an element of itself.

Bertrand Russell discovered the paradox and communicated it to Frege just as the second volume of Frege's monumental Grundegesetze der Arithmetic was going to press. Frege regarded it as devastating. "With the loss of my Basic Law V," he wrote in reply to Russell (1902, pp. 127–128), "not only the foundations of my arithmetic, but also the sole possible foundations of arithmetic, seem to vanish." Later scholarship, led by George Boolos, has seen the devastation as not quite so complete as Frege took it. Roughly speaking there are two principal components to the Grundgesetze : First the employment of Basic Law V (together with suitable definitions) to derive what Frege calls Hume's Principle, that, for any concepts F and G, the numbers associated with F and G are equal if and only if there is a one-one correspondence between the objects that fall under F and those that fall under G ; and second the derivation from Hume's Principle of the fundamental laws of arithmetic. The latter component is a substantial mathematical accomplishment that is unharmed by Russell's paradox.

A couple of other set-theoretic paradoxes emerged at about the same time, one, due to Cantor, involving cardinal numbers, and the other, due to Cesare Burali-Forti, about ordinal numbers.

For Cantor's paradox, let V be the set of all sets. Since every set of sets is a set, ℘(V ) is a subset of V, and so #(℘(V )) ≤#(V ). Yet Cantor's theorem tells us that #(℘(V )) > #(V ). Cantor concluded from the contradiction that there is no set of all sets, invoking a distinction reminiscent of Aristotle's distinction of potentially and actually infinite. The sets measured by the ℵ_αs are transfinite, whereas the set of all sets, if there were such a thing, would be absolutely infinite. There is no such thing as V because the sets do not form a completed whole. There is no absolute infinity in mathematics; absolute infinity is the province of God alone.

For Burali-Forti's paradox, consider that the ordinals are well-ordered, and so they have an ordinal number. Call it α. α also the ordinal of the collection of ordinals less than α and so there is an order-isomorphism f from the collection of all the ordinals to the collection of ordinals less than α. f (α) < α, and so, since the ordering on the ordinals is well-founded, there has to be a least ordinal β with f (β) ≠ β. We have f (β) = the least ordinal greater than all the members of {f (γ): γ < β} = the least ordinal greater than all the members of {γ: γ < β}; = β.

Mirimanoff's paradox emerged a little later. Let us say that a set is hereditarily well-founded if it belongs to a collection C with the following properties: Every element of an element of C is an element of C ; and the elements of C are well-founded (that is, the restriction to an element of C of the elementhood relation is well-founded). It is easy to verify that the collection of all hereditarily well-founded sets is hereditarily well-founded. But this gives us the absurd prospect of a well-founded set that is an element of itself.

Russell illustrated the logical structure of his paradox with an amusing example. Imagine a village whose barber (an adult male villager) shaves all and only the adult male villagers who do not shave themselves. A contradiction arises when we inquire whether the barber shaves himself, by reasoning exactly analogous to the thinking that gets Russell's paradox. Unlike the set-theoretic paradox, however, the puzzle about the barber has an easy solution. There can be no such barber, however plausible the story that said there was one sounded on first hearing. One would like to obtain a similar resolution to Russell's paradox, denying that there is such a set as {x : x ∉ x } (and, presumably, also that there are such sets as V, the set of all ordinals, and the set of all hereditarily well-founded sets) by restricting the range of open sentences that can be substituted for "F " in the comprehension principle. The trick is to do this in a principled, credible way that avoids contradictions while maintaining the set existence principles required to do mathematics. Before asking how this might be done, let us examine the semantic analogues of the set-theoretic paradoxes.

Semantic Paradoxes

Semantics, as Alfred Tarski characterized it, is the branch of linguistics that studies the connections between expressions of a language and the things or states of affairs those expressions refer to. Its principal theoretical concepts are truth, reference, and satisfaction. A name, like "Traveler" or "Robert E. Lee's horse," refers to (or names or denotes ) an object, in this case a stallion. An open sentence, like "x is a horse," represents a concept. The sentence got by substituting a name for the variable in an open sentence is true just in case the object referred to by the name falls under the concept represented by the open sentence. Because Traveler falls under the concept horse, the sentence "Traveler is a horse" is true. The reason for using the variable "x " to mark the place in the open sentence where a name needs to be supplied is to accommodate open sentences like "x rode y into battle," which represent concepts with more than one argument. The account of satisfaction needs to be complicated a bit to allow for such open sentences, but that need not concern us here.

Another, more substantial, complication is that one should not really speak of a sentence being true, but rather of a sentence being true in a language in a context, or perhaps of a sentence expressing, in a language in a context, a proposition that is true. "I am now riding Traveler" is true when Lee says it while riding his horse, but it is false in most other contexts. This complication too can be set aside here.

Here our concern is with the semantic paradoxes. Epimenides is credited with the earliest formulation, although it is doubtful that he recognized that his statement was paradoxical. Someone acutely aware of the paradox was Eubulides of Miletas (a contemporary of Aristotle), who asked, "A man says that he is lying; is what he says true or false?" Eubulides formulated other notorious paradoxes, among them the Bald Man (The observation that plucking a single hair from a man who is not bald will not make him bald leads, by multiple application, to the conclusion that not even a man with no hair at all is bald) and the Hooded Man (You know who your father is, and you do not know who the hooded man is, even though, unknown to you, the hooded man is your father; this violates the law of identity, which allows the exchange of names that denote the same thing).

To avoid fretting about indexicals and also to avoid consternation that only purposefully false statements count as "lies," let us consider what we may call the Liar Sentence, the sentence "The Liar Sentence is not true." We would naively expect the notion of truth to be governed by the (T)-schema, "'__________' is true if and only if __________;" "Traveler is a horse," for example, is true if and only if Traveler is a horse. However filling the blank with "The Liar Sentence is not true," and noting that "The Liar Sentence is not true" = the Liar Sentence, results in contradiction.

The Liar paradox does not have a direct set-theoretic analogue, but there are paradoxes involving satisfaction and reference that have such analogues. The analogue to Russell's paradox is due to Kurt Grelling. We would intuitively expect satisfaction to be governed by a principle exactly parallel to the comprehension principle in set theory, telling us, for example, that, for any y, y satisfies "x is a horse" if and only if y is a horse. The phrase "x is a horse" is not a horse, and so "x is a horse" does not satisfy itself, whereas "x is an open sentence" does satisfy itself. For any y, y satisfies "x is an open sentence that does not satisfy itself" if and only if y is an open sentence that does not satisfy itself. Taking y to be the open sentence "x is an open sentence that does not satisfy itself" yields a contradiction.

Cantor's paradox is obtained by generalizing Cantor's argument that there are more real numbers between 0 and 1 than there are positive integers, which proceeds by assuming for reductio ad absurdum that there were a list that enumerated all the real numbers between 0 and 1, then asking where on the list there appears the number r given by stipulating that the n th digit in the binary decimal expansion of r is equal to one if and only if zero is the n th digit in the binary decimal expansion of the n th number on the list. Richard's paradox invites us to consider, in particular, the list gotten by enumerating the English expressions that denote real numbers between 0 and 1 in alphabetical order. Cantor's argument gives us a real number between 0 and 1 that is not named by any expression of English. But is Cantor's number not named by the expression "the number r, between 0 and 1, such that the n th binary digit of r is equal to one if and only if zero is the n th binary digit of the number named by the alphabetically n th English phrase that names a real number between 0 and 1"?

The number of English expressions that name ordinal numbers is ℵ₀ since the expressions are finite strings of words from a finite vocabulary. There are more than ℵ₀ ordinals, so there are ordinals not named by an expression of English, and hence a least ordinal number not named by an expression of English. But "the least ordinal number not named by an expression of English" names it. This is König's paradox. Berry's paradox is the finitary version, got by noting that "the least natural number that cannot be named by an English expression of fewer than thirty syllables" is an English expression that names a natural number in twenty-eight syllables.

Principia Mathematica

Alfred North Whitehead and Bertrand Russell undertook to solve simultaneously both the set-theoretic paradoxes and the semantic paradoxes. The aim of their highly ambitious Principia Mathematica was to secure all of mathematics on a basis in pure logic. In their system the role hitherto played by sets was taken over by propositional functions, which are a kind of amalgam of Frege's concepts and Frege's propositions. Propositions are, for Frege, the objects of belief and judgment, the sort of thing referred to by "that" clauses in English. According to Russell if you prefix the word "that" to an open sentence, you get an expression that names a propositional function, a function taking objects to propositions. If you supply an object as argument, the output is the proposition you would express if you substituted a name of that object into the open sentence. With Traveler as argument, the propositional function designated by "that Lee rode x into battle" yields the proposition that Lee rode Traveler into battle.

This account was considered and rejected by Frege on the basis that it would yield the result that the proposition that Traveler is white is identical to the proposition that the horse Lee rode into battle is white, in spite of the fact that someone who did not realize that Traveler is the horse Lee rode into battle might believe one but not the other. For Frege, the argument of the propositional function is not the horse Traveler but the sense (Sinn ) of the name "Traveler." Russell thought he could thwart Frege's objection by a logical analysis according to which "the horse Lee rode into battle" is, despite appearances, not a denoting phrase. The relative merits of Frege's and Russell's conceptions of propositional functions have been much debated.

Whitehead and Russell proposed to avert the paradoxes by adopting the vicious circle principle (which they attribute to Henri Poincaré), according to which you cannot have a proposition that refers to itself since before you could formulate such a proposition you would have to already possess the proposition you were trying to formulate. You cannot have a propositional function that has itself or any of its values as argument, nor can you have a propositional function in whose formulation you are required to talk about the propositional function or any of its arguments. To formulate an analogue to Russell's paradox in terms of propositional functions, you would have to suppose that the phrase "that x is a propositional function not true of itself" denoted a propositional function, and such a propositional function would violate the vicious circle principle. Whitehead and Russell adopted a (maddeningly elaborate) formalism in which such phrases were grammatically ill-formed.

The vicious circle principle evades the paradoxes (as far an anyone knows), but it also rules out ordinary mathematics. If r is the least upper bound of a given collection of real numbers then it is the least element of a totality that includes r itself.

In Principia Mathematica, the propositional functions are arrayed in layers, where the level of a given function is determined by the levels of its possible arguments and also by the levels of the propositional functions utilized in defining the given function. A propositional function is said to be predicative if it is at the lowest level it could possibly be at, given what its arguments are. Either it is defined without referring to anything beyond its potential arguments (say, by giving a list), or the things referred to are sufficiently low-level that they do not affect the level of the function. Whitehead and Russell obtained the least upper bound principle by adopting the axiom of reducibility, according to which for every propositional function there is a predicative propositional function true of the same things. Given a collection C of real numbers, take a predicative function Fx that is coextensive with "x is an upper bound of C," we get the least upper bound of C as the least number that satisfies Fx.

The justification of the axiom of reducibility is purely pragmatic—it is needed for mathematics—and its adoption seriously undermines Whitehead and Russell's claim to have reduced mathematics to logic.

Once we have the axiom of reducibility on board, there in no longer any useful purpose in having the position in the hierarchy of a propositional function depend on the positions of the things we refer to in defining the function as well as on the positions of the potential arguments. We can obtain both the same mathematical results and the same degree of insulation from paradox simply by taking the type of a propositional function to be immediately above the types of its arguments, no matter how the propositional function is defined. Frank Ramsey first recognized this, effecting an enormous simplification in the system. W. V. Quine took the observation a step further, noticing that there was no longer any benefit in supposing coextensive propositional functions to be distinct, so that we could take the things the "Ramseyfied" theory was about to be sets and relations, rather than propositional functions of one or more variables.

The system can be further streamlined by replacing talk about binary relations between individuals with talk about sets of ordered pairs of individuals, replacing talk about ternary relations with talk about sets of ordered triples, and so on. There is no need to take ordered triples as primitive, since we can define 〈a,b,c 〉 as the ordered pair 〈a,〈b,c 〉〉. In fact—this is an ingenious observation of Norbert Weiner—there is no need to take ordered pairs as primitive, since we can define 〈a,b 〉 as {{{a },∅},{{b }}}}. This stipulation enables us to derive the principle that, for any a, b, c, and d, 〈a, b 〉 = 〈c,d 〉 if and only if a =c and b =d, which is the only thing one ever needs to know about ordered pairs. The resulting system is arrayed in a simple hierarchy. There are individuals, sets of individuals, set of sets of individuals, and so on. It is this hierarchical structure, rather than the vicious circle principle, that precludes paradox.

Zermelo-Fraenkel Set Theory

The most prominent of Principia Mathematica 's rivals originates, not in a philosophical analysis of methods of reasoning that lead to the paradoxes, but in a mathematical examination of ways of reasoning that never cause problems. Zermelo's 1904 proof that every set can be well-ordered, with its corollary that the cardinal numbers are well-ordered, met considerable resistance. It was felt that it skirted too close the edge of the newly discovered paradoxes. Poincaré, for example, complained about vicious circularity. Zermelo replied that the methods of forming sets that figure in the paradoxes are far removed from the methods that are gainfully employed by working mathematicians, and that the principles that figure in the deduction of the well-ordering theorem fall into the latter category. To make this reply more precise Zermelo wrote down axioms of set theory sufficient to derive the well-ordering theorem, in the hope that all could see that the proof required only well-established principles of workaday mathematics that had never been implicated in paradox.

Zermelo's axioms did not come equipped with a diagnosis of the paradoxes, but a couple of widely accepted further principles do have diagnostic import. Although Zermelo's axioms are immensely powerful, they omit some common and apparently harmless mathematical practices, like forming infinite sequences of the form 〈s ₀, s ₁, s ₂, s ₃…〉. Abraham Fraenkel proposed to rectify this situation by adopting the replacement axiom schema, which says that for any open sentence that defines a function, if the inputs to the function form a set, so do the outputs. In Frege's logic, in which there was one style of variables ranging over sets and other objects and another style ranging over functions, the replacement axiom would be expressed by saying the restriction of a function to a set domain invariably has a set as its range. Fraenkel is only able to produce a schema that applies to definable functions because his logical resources are restricted to the first-order predicate calculus, which only has variables ranging over individuals. The new principle is formulated as a formula that contains a schematic letter, so understood that the formulas of the language of set theory obtained by substituting a formula for the schematic letter are regarded as axiomatic. This retreat to first-order logic results from relinquishing the program of trying to produce a logic so powerful that set theory can be reduced to it. The existence of sets cannot be established by logic alone, and the first-order formulation makes set theory's existence assumptions fully explicit.

The replacement axioms assure us that an open sentence has a set as its extension unless the things that satisfy it are more numerous than the members of any set. The doctrine of limitation of size has it that things form a set unless there are too many of them, and that the paradoxes arise from attempts to form sets that are too large to hang together. The Burali-Forti paradox, for example, tells us that the ordinals are too numerous to form a set.

Mirimanoff's paradox distinguishes the hereditarily well-founded sets—what Mirimanoff calls the ordinary sets —from the others. It turns out that extraordinary sets (if there are any) are never needed for mathematics, and if we restrict our attention to ordinary sets, adopting an axiom that the elementhood relation is well-founded, an attractive picture of the universe of set appears. Sets are built up in stages. At the bottom level the so-called urelements are whatever non-sets you may want to count or measure. (For pure, as opposed to applied, mathematics, no urelements are needed.) At the second level are sets of urelements. At the third level are sets whose elements are urelements and sets of urelements. And so on. At each stage the available building blocks are the urelements and the sets built at earlier stages, and every set is constructed at some, possibly transfinite, stage. Because new sets and new ordinals are added at every stage, there is no stage at which one constructs a set that contains all the ordinals or a set that contains all the sets that do not contain themselves (which would be a set that contained all sets). The purported sets that threaten paradox never appear.

The two strategies for blocking the paradoxes—limitation of size and construction in stages—are by no means in conflict. Indeed one could argue (although it is certainly not obvious) that the stage construction ensures that no stage ever produces a set large enough to violate the limitation of size. On the other hand Peter Aczel (1988) has devised an alternative to standard set theory, provably consistent if ordinary set theory is, that upholds limitation of size but allows non-well-founded sets in great profusion.

The Whitehead-Russell system and the Zermelo-Fraenkel system are by no means the only extant responses to the set-theoretic paradoxes—Quine, for example, devised a method for restricting the comprehension principle so as to allow a universal set, without apparent contradiction—but they are the most prominent. Their rivalry is not so implacable as first appears. Indeed Kurt Gödel (1944/1983) has noted that we can think of the Zermelo-Fraenkel system as obtained from Principia Mathematica, as simplified by Ramsey, Quine, and Weiner, by generalizing in two directions. First we allow the types to be cumulative, so that the possible elements at a type level are not just the sets of the immediately preceding type but sets of all the preceding types. Second we allow the type levels to extend into the transfinite.

One question the axiomatizations leave unanswered is how comprehensive the theory of sets is intended to be. Not all collections are sets. A stamp collection for example can survive the acquisition of a new stamp, whereas when you add a stamp to a set of stamps, you get a different set. But perhaps set theory accounts for all extensional collections. If not then the set theorist has two tasks: To say what extensional collections there are, and to say which of the extensional collections are sets. John von Neumann gave such an account. His theory has two kinds of classes, namely, sets and proper classes. Classes are made up of sets and urelements, and a class is a set if and only if it is not equinumerous with the class of all ordinals. The proper classes form the top element of the cumulative hierarchy.

Zermelo has a different perspective, reminiscent of Aristotle's doctrine that a line or the integers never form a completed whole. The universe of set theory does not form a completed whole, according to Zermelo. Candidates for the "universe" of set theory are only provisional, and one can always advance to a higher perspective from which a candidate universe is seen as a set within a larger universe.

Semantic Paradoxes

In looking at possible solutions to the set-theoretic paradoxes, the semantic paradoxes have been set aside. One cannot happily say about the Liar Sentence the same thing one wants to say about the alleged set of all ordinals, namely, that there is no such sentence. One might want to say that what goes wrong with the Liar Sentence is that it does not express a proposition, but any satisfaction this gives us is short-lived. A propositionalist theory of truth has to account for two things, the truth conditions for propositions and the connection between a sentence and the proposition it expresses, and the latter relation remains troublesome. Consideration of the Propositional Liar Sentence ("The Propositional Liar Sentence does not express a true proposition") seems to force us the self-defeating conclusion that the Propositional Liar Sentence does not express a proposition, and hence that it does not express a true proposition.

The standard response to the semantic paradoxes was given by Alfred Tarski, who insists that, in developing a semantic theory, the language one employs (the metalanguage ) must be richer in expressive power than the language one is talking about (the object language ), so that one can never formulate the theory of truth, reference, and satisfaction for a language within the language itself.

A number of ingenious extensions of Tarski's basic idea have been developed. Notable among them is Saul Kripke's (1975) demonstration that, thinking of such troubled sentences as the Liar as neither true nor false, one can add the predicate "true" to a language and partition the sentences of the resulting language in such a way that a sentence S is counted as true, false, or undecided according as the statement that S is true is accounted true, false, or undecided. The enriched language cannot, however, express the equivalence of S with the statement that S is true, nor can it express the proof that the Kripke construction yields the equivalence. These things can only be said within a richer metalanguage. Indeed, in the best known version (there are a number of variants), the addition of the truth predicate results in a drastic restriction in the range of truth-preserving inferences, so that the object language has an enervated logic in which nothing resembling ordinary mathematical or philosophical reasoning can be carried on (as Solomon Feferman's investigations have made abundantly clear). Hartry Field (2003) has proposed enriching the Kripke construction by adding a new, nonclassical conditional, which behaves enough like the everyday "if…, then" to accommodate a substantial range of familiar inferences. With Field's novel interpretation of "if and only if," the (T)-sentences are all counted as true.

Field's construction is too complicated to describe here, but its key idea comes from revision theory, which employs full classical logic but regards the "if and only if" that appears in the (T)-sentences as a special connective that represents definitional equivalence. Developed by Anil Gupta and Nuel Belnap (1993) on a foundation laid down independently by Gupta and Hans Herzberger, revision theory treats the (T)-sentences as defining "true," and it ascribes to the "if and only if" of definition a special logic that allows for circular definitions. If "F " is defined by "F (x ) if and only if __________," where the defined predicate "F " appears in the blank, and if C is proposed as a possible candidate for the extension of "F," then the map that takes C to {x : x satisfies __________ when C is taken as the extension of "F "} gives us, by iteration, better and better candidates for the extension of "F." Throughout the revision process, the Liar sentences keeps flip-flopping between true and false, but sentences that have an intuitively correct truth value eventually settle down to their intuitively expected values, even in the presence of extensive self-reference and cross-reference. Tarski's restriction is still observed, inasmuch as the entire construction is developed within a richer metalanguage.

Tarski's doctrine works happily for formal languages, but it leaves us unable to understand how the notion of truth and reference apply to natural languages, since "true in English" is a phrase of English and not some unnatural metalanguage.

Some progress has been made by adapting the Principia Mathematica idea of subscripted "true"s. There is a predicate "true₀" that applies to sentences that contain no semantic notions; a predicate "true₁" that applies to sentences with no semantic notions other than "true₀;" "true₂" that applies to sentences with no semantic notion other than "true₀" and "true₁" and so on. Tyler Burge (1979) and Charles Parsons (1974) have proposed applying this notion to English by supposing that the English word "true" is ambiguous, and that disambiguating subscripts are tacitly ascribed by contexts in such a way that a truth attribution is supplied a subscript one greater than the maximum of those that appear in the sentences one is talking about. Eubulides's derivation of a contradiction is seen as committing a fallacy of equivocation, inasmuch as the tacit subscript changes during the course of his argument.

The Principia -inspired approach still has limitations. For one thing there does not appear to be any uniform, non-arbitrary way of coping with situations in which A talks about all the things B says at the same time B talks about all things A says. For another the description of the subscripting machinery lies outside the object language, so that we are provided with no good way of dealing with "This sentence is not true_α, for any α."

A different approach tries to consolidate the Liar paradox and the Bald Man by developing the idea that, if Harry is a borderline case of "bald," "Harry is bald" should be neither true nor false. "'Harry is bald' is either true or false" follows logically (defining falsity as truth of the negation) from the conditionals we get by substituting "Harry is bald" and "Harry is not bald" into the right-to-left direction of the (T)-schema. Allowing that "Harry is bald" is neither true nor false requires restricting the right-to-left direction of (T) so that it does not apply to such things as border applications of vague terms, which are semantically defective. This restriction yields an attractive response to the Bald Man, but the answer to the Liar is problematic. The left-to-right direction of (T) ("If 'The Liar Sentence is not true' is true then the Liar Sentence is not true") suffices to yield the conclusion that the Liar Sentence is untrue, and hence, because the right-to-left (T)-schema fails for it, that the statement that Liar Sentence is untrue is semantically defective. This result is unwelcome, because it tells us that a conclusion can be derived by rigorous, careful deduction from secure premises and still be semantically defective.

The argument of the previous paragraph is adapted from Richard Montague's (1960) argument that a Liar-type paradox can be obtained for necessity in place of truth. Also, as Montague and David Kaplan (1960) showed, for knowledge. It seems safe to say that the semantic paradoxes are currently less well-managed than the set-theoretic paradoxes.

See also Aristotle; Cantor, Georg; Frege, Gottlob; Galileo Galilei; Gödel, Kurt; Hamilton, William; Kaplan, David; Kripke, Saul; Liar Paradox, The; Montague, Richard; Neumann, John Von; Poincaré, Jules Henri; Quine, Willard van Orman; Ramsey, Frank Plumpton; Relativity Theory; Russell, Bertrand Arthur William; Set Theory; Tarski, Alfred; Whitehead, Alfred North; Zeno of Elea.

Bibliography

Aczel, Peter. Non-Well-Founded Sets. Stanford, CA: CSLI, 1988.

Aristotle. Physics. 2 vols. Translated by Philip H. Wicksteed and Francis M. Cornford. Cambridge, MA: Harvard University Press, 1929 and 1934.

Boolos, George S. Logic, Logic, and Logic. Cambridge, MA, and London: Harvard University Press, 1998.

Burali-Forti, Cesare. "Una Questione sui Numeri Transfiniti." Rendiconti del Circolo Matematico di Palermo 11 (1897): 154–164. English translation by Jean van Heijenoort in van Heijenoort, 104–111.

Burge, Tyler. "Semantical Paradox." Journal of Philosophy 76 (1979): 169–198. Reprinted in Martin, 83–117.

Cantor, Geog. "Beiträge zur Begründung der transfiniten Mengenlehre." Mathematische Annalen 46 (1895): 481–512 and 49 (1897): 312–356. English translation by Philip E. B. Jourdain. New York: Dover, 1955.

Dedekind, Richard. Stetigkeit und irrationale Zahlen. Braunschweig: F. Veiwig, 1872. English translation by Wooster W. Beeman in Dedekind Essays on the Theory of Numbers, 1–27. New York: Dover, 1963.

Feferman, Solomon. "Toward Useful Type-Free Theories, I." Journal of Symbolic Logic 49 (1984): 75–111. Reprinted in Martin, 237–287.

Field, Hartry. "A Revenge-Immune Solution to the Liar Paradox." Journal of Philosophical Logic 32 (2003): 139–177.

Fraenkel, Abraham. "Über die Zermelosche Begründung der Mengenlehre." Jahresbericht der Deutchen Mathematiker-Vereinigung 3011 (1921): 97–98.

Fraenkel, Abraham. "Zu den Grundlagen der Cantor-Zermeloschen Mengenlehre." Mathematische Annalen 86 (1922): 230–237.

Frege, Gottlob. Begriffsschrift. Halle: Nebert, 1879. Translated by Stefan Bauer-Mengelberg in van Heijenoort, 1–82.

Frege, Gottlob. "Funktion und Begriff." 1881. English translation by Peter Geach and Max Black in Translations, 21–41.

Frege, Gottlob. "Über Sinn und Bedeutung." Zeitschrift für Philosophie und philosophische Kritik 50 (1892): 25–50. English Translation by Peter Geach and Max Black in Translations, 56–78.

Frege, Gottlob. Grundgesetze der Arithmetik, 2 vols. Jena: Pohle, 1893 and 1903. Partial translation by Montgomery Furth. Berkeley and Los Angeles: University of California Press, 1964.

Frege, Gottlob. "Letter to Russell." 1902. English translation by Beverly Woodward in van Heijenoort, 126–128.

Frege, Gottlob. Translations from the Philosophical Writings. 2nd. ed. Oxford: Basil Blackwell.

Galileo Galilei. Discorsi e dimostrazioni matematiche. Translated by Henry Crew and Alfonso de Salvio. New York: Dover, 1956.

Gödel, Kurt. "Russell's Mathematical Logic." In The Philosophy of Bertrand Russell, edited by Paul A. Schilpp, 125–153. Evanston and Chicago: Northwestern University Press, 1944. Reprinted in Paul Benacerraf and Hilary Putnam, eds., Philosophy of Mathematics 2nd ed., 447–469. Cambridge, U.K.: Cambridge University Press, 1983.

Grelling, Kurt, and Leonard Nelson. "Bemerkungen zu den Paradoxien von Russell und Burali-Forti." Abhandlungen der Fries'schen Schule neue Folge 2 (1908): 301–334.

Gupta, Anil. "Truth and Paradox." Journal of Philosophical Logic 11 (1982): 1-60. Reprinted in Martin, 175–235.

Gupta, Anil, and Nuel Belnap. The Revision Theory of Truth. Cambridge, MA: MIT Press, 1993.

Hallett, Michael. Cantorian Set Theory and Limitation of Size. Oxford: Clarendon, 1984.

Herzberger, Hans G. "Notes on Naïve Semantics." Journal of Philosophical Logic 11 (1992): 61-102. Reprinted in Martin, 133–174.

König, Julius. "Über die Grundlagen der Mengenlehre und das Kontinuumproblem." Mathematische Annalen 61 (1905): 156–160. Translated by Stefan Bauer-Mengelberg in van Heijenoort, 145-149.

Keefe, Rosanna, and Peter Smith, eds. Vagueness: A Reader. Cambridge, MA, and London: MIT Press, 1996.

Kripke, Saul A. "Outline of a Theory of Truth." Journal of Philosophy 72 (1975): 690–716. Reprinted in Martin, 53–81.

McGee, Vann. Truth, Vagueness, and Paradox. Indianapolis: Hackett, 1991.

Martin, Robert L., ed. Recent Essays on Truth and the Liar Paradox. Oxford and New York: Oxford University Press.

Mirimanoff, Dimitry. "Les antinomies de Russell et de Burali-Forti et le problème fondamental de la théorie des ensembles." L'enseignement Mathématique 19 (1917): 37–52.

Montague, Richard. Formal Philosophy. New Haven, CT: Yale, 1974.

Montague, Richard. "Syntactic Treatments of Modality, with Corollaries on Reflection Principles and Finite Axiomatizability." Acta Philosophical Fennica 16 (1963): 153–167. Reprinted in Montague, Formal Philosophy, 286–302.

Montague, Richard, and David Kaplan. "A Paradox Regained." Notre Dame Journal of Formal Logic 1 (1960): 79–90. Reprinted in Montague, Formal Philosophy, 270–285.

Parsons, Charles. "The Liar Paradox." Journal of Philosophical Logic 3 (1974): 381–412. Reprinted in Martin, 9–45.

Quine, Willard van Orman. "New Foundations for Mathematical logic." American Mathematical Monthly 44 (1937): 70–80. Reprinted in Quine, From a Logical Point of View. Cambridge, MA: 1953, 80–101.

Quine, Willard van Orman. The Logic of Sequences: Harvard Dissertations in Philosophy. New York: Garland, 1990.

Ramsey, Frank Plumpton. "The Foundations of Mathematics." Proceedings of the London Mathematical Society 25 (1925): 338–384. Reprinted in Ramsey, The Foundations of Mathematics and Other Logical Essays. London: Routledge and Kegan Paul, 1931: 1–61, and in Ramsey, Philosophical Papers. Cambridge, U.K.: Cambridge University Press, 1990, pp. 164–224.

Richard, Jules. "Les principes de mathématiques et le problème de ensembles." Revue Générale des Sciences Pures et Appliquées 16 (1905): 541. English translation by Jean van Heijenoort in van Heijenoort, 142–144.

Russell, Bertrand. "Letter to Frege." 1902. In van Heijenoort, 124–125.

Russell, Bertrand. "On Denoting." Mind n. s. 14 (1905): 479–493. Reprinted in Russell, Logic and Knowledge. London: Allen and Unwyn, 1956: 41–56.

Tarski, Alfred. "Grundlegung der wissenschaftenlichen Semantik." Actes du Congrès International de Philosophie Scientifique 3 (1930): 1–8. English translation by J. H. Woodger in Tarski, Logic, Semantics, Metamathematics, 401–408.

Tarski, Alfred. Logic, Semantics, Metamathematics. 2nd ed. Indianapolis: Hackett, 1983.

Tarski, Alfred. "Der Wahrheitsbegriff in den formalisierten Sprachen." Studia Philosophica 1 (1935): 261–405. English translation by J. H. Woodger in Tarski, Logic, Semantics, Metamathematics, 152–278.

Van Heijenoort, Jean, ed. From Frege to Gödel. Cambridge, MA, and London: Harvard University Press, 1967.

Von Neumann, John. "Eine Axiomatisierung der Mengenlehre." Journal für die reine und angewandte Mathematik 154 (1925): 219–240. English translation by Stefan Bauer-Mengelberg and Dagfinn Føllesdal in van Heijenoort, 393–413.

Whitehead, Alfred North, and Bertrand Russell. Principia Mathematica. 2nd ed. 3 vols. Cambridge, U.K.: Cambridge University Press, 1925 and 1927.

Wiener, Norbert. "A Simplification of the Logic of Relations." Proceedings of the Cambridge Philosophical Society 17 (1914): 387–390. Reprinted in van Heijenoort, 224–227.

Zermelo, Ernst. "Beweis, daß jede Menge wohlgeordnet werden kann." Mathematische Annalen 59 (1904): 514–516. English translation by Stefan Bauer-Mengelberg in van Heijenoort, 139–141.

Zermelo, Ernst. "Neuer Beweis für die Möglichkeit einer Wohlordnung." Mathematische Annalen 65 (1908): 107–28. English translation by Stefan Bauer-Mengelberg in van Heijenoort, 183–198.

Zermelo, Ernst. "Über Grenzzahlen und Mengenbereiche." Fundamenta Mathematicae 16 (1930): 29–37.

Zermelo, Ernst. "Untersuchungen über die Grundlagen der Mengenlehre I." Mathematische Annalen 65 (1908): 261–281. English translation by Stefan Bauer-Mengelberg in van Heijenoort, 199–215.

Vann McGee (2005)