The “no self-defeating object” argument

5 November, 2009 in expository, math.LO | Tags: cantor's theorem, godel incompleteness theorem, halting problem

A fundamental tool in any mathematician’s toolkit is that of reductio ad absurdum: showing that a statement ${X}$ is false by assuming first that ${X}$ is true, and showing that this leads to a logical contradiction. A particulary pure example of reductio ad absurdum occurs when establishing the non-existence of a hypothetically overpowered object or structure ${X}$ , by showing that ${X}$ ‘s powers are “self-defeating”: the very existence of ${X}$ and its powers can be used (by some clever trick) to construct a counterexample to that power. Perhaps the most well-known example of a self-defeating object comes from the omnipotence paradox in philosophy (“Can an omnipotent being create a rock so heavy that He cannot lift it?”); more generally, a large number of other paradoxes in logic or philosophy can be reinterpreted as a proof that a certain overpowered object or structure does not exist.

In mathematics, perhaps the first example of a self-defeating object one encounters is that of a largest natural number:

Proposition 1 (No largest natural number) There does not exist a natural number ${N}$ which is larger than all other natural numbers.

Proof: Suppose for contradiction that there was such a largest natural number ${N}$ . Then ${N+1}$ is also a natural number which is strictly larger than ${N}$ , contradicting the hypothesis that ${N}$ is the largest natural number. $\Box$

Note the argument does not apply to the extended natural number system in which one adjoins an additional object ${\infty}$ beyond the natural numbers, because ${\infty+1}$ is defined equal to ${\infty}$ . However, the above argument does show that the existence of a largest number is not compatible with the Peano axioms.

This argument, by the way, is perhaps the only mathematical argument I know of which is routinely taught to primary school children by other primary school children, thanks to the schoolyard game of naming the largest number. It is arguably one’s first exposure to a mathematical non-existence result, which seems innocuous at first but can be surprisingly deep, as such results preclude in advance all future attempts to establish existence of that object, no matter how much effort or ingenuity is poured into this task. One sees this in a typical instance of the above schoolyard game; one player tries furiously to cleverly construct some impressively huge number ${N}$ , but no matter how much effort is expended in doing so, the player is defeated by the simple response “… plus one!” (unless, of course, ${N}$ is infinite, ill-defined, or otherwise not a natural number).

It is not only individual objects (such as natural numbers) which can be self-defeating; structures (such as orderings or enumerations) can also be self-defeating. (In modern set theory, one considers structures to themselves be a kind of object, and so the distinction between the two concepts is often blurred.) Here is one example (related to, but subtly different from, the previous one):

Proposition 2 (The natural numbers cannot be finitely enumerated) The natural numbers ${{\Bbb N} = \{0,1,2,3,\ldots\}}$ cannot be written as ${\{ a_1,\ldots,a_n\}}$ for any finite collection ${a_1,\ldots,a_n}$ of natural numbers.

Proof: Suppose for contradiction that such an enumeration ${{\Bbb N} = \{a_1,\ldots,a_n\}}$ existed. Then consider the number ${a_1+\ldots+a_n+1}$ ; this is a natural number, but is larger than (and hence not equal to) any of the natural numbers ${a_1,\ldots,a_n}$ , contradicting the hypothesis that ${{\Bbb N}}$ is enumerated by ${a_1,\ldots,a_n}$ . $\Box$

Here it is the enumeration which is self-defeating, rather than any individual natural number such as ${a_1}$ or ${a_n}$ . (For this post, we allow enumerations to contain repetitions.)

The above argument may seem trivial, but a slight modification of it already gives an important result, namely Euclid’s theorem:

Proposition 3 (The primes cannot be finitely enumerated) The prime numbers ${{\mathcal P} = \{2,3,5,7,\ldots\}}$ cannot be written as ${\{p_1,\ldots,p_n\}}$ for any finite collection of prime numbers.

Proof: Suppose for contradiction that such an enumeration ${{\mathcal P} = \{p_1,\ldots,p_n\}}$ existed. Then consider the natural number ${p_1 \times \ldots \times p_n + 1}$ ; this is a natural number larger than ${1}$ which is not divisible by any of the primes ${p_1,\ldots,p_n}$ . But, by the fundamental theorem of arithmetic (or by the method of Infinite descent, which is another classic application of reductio ad absurdum), every natural number larger than ${1}$ must be divisible by some prime, contradicting the hypothesis that ${{\mathcal P}}$ is enumerated by ${p_1,\ldots,p_n}$ . $\Box$

Remark 1 Continuing the number-theoretic theme, the “dueling conspiracies” arguments in a previous blog post can also be viewed as an instance of this type of “no-self-defeating-object”; for instance, a zero of the Riemann zeta function at ${1+it}$ implies that the primes anti-correlate almost completely with the multiplicative function ${n^{it}}$ , which is self-defeating because it also implies complete anti-correlation with ${n^{-it}}$ , and the two are incompatible. Thus we see that the prime number theorem (a much stronger version of Proposition 3) also emerges from this type of argument.

In this post I would like to collect several other well-known examples of this type of “no self-defeating object” argument. Each of these is well studied, and probably quite familiar to many of you, but I feel that by collecting them all in one place, the commonality of theme between these arguments becomes more apparent. (For instance, as we shall see, many well-known “paradoxes” in logic and philosophy can be interpreted mathematically as a rigorous “no self-defeating object” argument.)

— 1. Set theory —

Many famous foundational results in set theory come from a “no self-defeating object” argument. (Here, we shall be implicitly be using a standard axiomatic framework for set theory, such as Zermelo-Frankel set theory; the situation becomes different for other set theories, much as results such as Proposition 1 changes if one uses other number systems such as the extended natural numbers.) The basic idea here is that any sufficiently overpowered set-theoretic object is capable of encoding a version of the liar paradox (“this sentence is false”, or more generally a statement which can be shown to be logically equivalent to its negation) and thus lead to a contradiction. Consider for instance this variant of Russell’s paradox:

Proposition 4 (No universal set) There does not exist a set which contains all sets (including itself).

Proof: Suppose for contradiction that there existed a universal set ${X}$ which contained all sets. Using the axiom schema of specification, one can then construct the set

$\displaystyle Y := \{ A \in X: A \not \in A\}$

of all sets in the universe which did not contain themselves. As ${X}$ is universal, ${Y}$ is contained in ${X}$ . But then, by definition of ${Y}$ , one sees that ${Y \in Y}$ if and only if ${Y \not \in Y}$ , a contradiction. $\Box$

Remark 2 As a corollary, there also does not exist any set ${Z}$ which contains all other sets (not including itself), because the set ${X := Z \cup \{Z\}}$ would then be universal.

One can “localise” the above argument to a smaller domain than the entire universe, leading to the important

Proposition 5 (Cantor’s theorem) Let ${X}$ be a set. Then the power set ${2^X := \{ A: A \subset X \}}$ of ${X}$ cannot be enumerated by ${X}$ , i.e. one cannot write ${2^X := \{ A_x: x \in X \}}$ for some collection ${(A_x)_{x \in X}}$ of subsets of ${X}$ .

Proof: Suppose for contradiction that there existed a set ${X}$ whose power set ${2^X}$ could be enumerated as ${\{ A_x: x \in X \}}$ for some ${(A_x)_{x \in X}}$ . Using the axiom schema of specification, one can then construct the set

$\displaystyle Y := \{ x \in X: x \not \in A_x \}.$

The set ${Y}$ is an element of the power set ${2^X}$ . As ${2^X}$ is enumerated by ${\{ A_x: x \in X \}}$ , we have ${Y = A_y}$ for some ${y \in X}$ . But then by the definition of ${Y}$ , one sees that ${y \in A_y}$ if and only if ${y \not \in A_y}$ , a contradiction. $\Box$

As is well-known, one can adapt Cantor’s argument to the real line, showing that the reals are uncountable:

Proposition 6 (The real numbers cannot be countably enumerated) The real numbers ${{\bf R}}$ cannot be written as ${\{ x_n: n \in {\bf N} \}}$ for any countable collection ${x_1,x_2,\ldots}$ of real numbers.

Proof: Suppose for contradiction that there existed a countable enumeration of ${{\bf R}}$ by a sequence ${x_1,x_2,\ldots}$ of real numbers. Consider the decimal expansion of each of these numbers. Note that, due to the well-known “ ${0.999\ldots=1.000\ldots}$ ” issue, the decimal expansion may be non-unique, but each real number ${x_n}$ has at most two decimal expansions. For each ${n}$ , let ${a_n \in \{0,1,\ldots,9\}}$ be a digit which is not equal to the ${n^{th}}$ digit of any of the decimal expansions of ${x_n}$ ; this is always possible because there are ten digits to choose from and at most two decimal expansions of ${x_n}$ . (One can avoid any implicit invocation of the axiom of choice here by setting ${a_n}$ to be (say) the least digit which is not equal to the ${n^{th}}$ digit of any of the decimal expansions of ${x_n}$ .) Then the real number given by the decimal expansion ${0.a_1a_2a_3\ldots}$ differs in the ${n^{th}}$ digit from any of the decimal expansions of ${x_n}$ for each ${n}$ , and so is distinct from every ${x_n}$ , a contradiction. $\Box$

Remark 3 One can of course deduce Proposition 6 directly from Proposition 5, by using the decimal representation to embed ${2^{\bf N}}$ into ${{\bf R}}$ . But notice how the two arguments have a slightly different (though closely related) basis; the former argument proceeds by encoding the liar paradox, while the second proceeds by exploiting Cantor’s diagonal argument. The two perspectives are indeed a little different: for instance, Cantor’s diagonal argument can also be modified to establish the Arzela-Ascolí theorem, whereas I do not see any obvious way to prove that theorem by encoding the liar paradox.

Remark 4 It is an interesting psychological phenomenon that Proposition 6 is often considered far more unintuitive than any of the other propositions here, despite being in the same family of arguments; most people have no objection to the fact that every effort to finitely enumerate the natural numbers, for instance, is doomed to failure, but for some reason it is much harder to let go of the belief that, at some point, some sufficiently ingenious person will work out a way to countably enumerate the real numbers. I am not exactly sure why this disparity exists, but I suspect it is at least partly due to the fact that the rigorous construction of the real numbers is quite sophisticated and often not presented properly until the advanced undergraduate level. (Or perhaps it is because we do not play the game “enumerate the real numbers” often enough in schoolyards.)

Remark 5 One can also use the diagonal argument to show that any reasonable notion of a “constructible real number” must itself be non-constructive (this is related to the interesting number paradox). Part of the problem is that the question of determining whether a proposed construction of a real number is actually well-defined is a variant of the halting problem, which we will discuss below.

While a genuinely universal set is not possible in standard set theory, one at least has the notion of an ordinal, which contains all the ordinals less than it. (In the discussion below, we assume familiarity with the theory of ordinals.) One can modify the above arguments concerning sets to give analogous results about the ordinals. For instance:

Proposition 7 (Ordinals do not form a set) There does not exist a set that contains all the ordinals.

Proof: Suppose for contradiction that such a set existed. By the axiom schema of specification, one can then find a set ${\Omega}$ which consists precisely of all the ordinals and nothing else. But then ${\Omega \cup \{\Omega\}}$ is an ordinal which is not contained in ${\Omega}$ (by the axiom of foundation, also known as the axiom of regularity), a contradiction. $\Box$

Remark 6 This proposition(together with the theory of ordinals) can be used to give a quick proof of Zorn’s lemma: see these lecture notes of mine for further discussion. Notice the similarity between this argument and the proof of Proposition 1.

Remark 7 Once one has Zorn’s lemma, one can show that various other classes of mathematical objects do not form sets. Consider for instance the class of all vector spaces. Observe that any chain of (real) vector spaces (ordered by inclusion) has an upper bound (namely the union or limit of these spaces); thus, if the class of all vector spaces was a set, then Zorn’s lemma would imply the existence of a maximal vector space ${V}$ . But one can simply adjoin an additional element not already in ${V}$ (e.g. ${\{V\}}$ ) to ${V}$ , and contradict this maximality. (An alternate proof: every object is an element of some vector space, and in particular every set is an element of some vector space. If the class of all vector spaces formed a set, then by the axiom of union, we see that union of all vector spaces is a set also, contradicting Proposition 4.)

One can localise the above argument to smaller cardinalities, for instance:

Proposition 8 (Countable ordinals are uncountable) There does not exist a countable enumeration ${\omega_1, \omega_2, \ldots}$ of the countable ordinals. (Here we consider finite sets and countably infinite sets to both be countable.)

Proof: Suppose for contradiction that there exists a countable enumeration ${\omega_1, \omega_2, \ldots}$ of the countable ordinals. Then the set ${\Omega := \bigcup_n \omega_n}$ is also a countable ordinal, as is the set ${\Omega \cup \{\Omega \}}$ . But ${\Omega \cup \{\Omega \}}$ is not equal to any of the ${\omega_n}$ (by the axiom of foundation), a contradiction. $\Box$

Remark 8 One can show the existence of uncountable ordinals (e.g. by considering all the well-orderings of subsets of the natural numbers, up to isomorphism), and then there exists a least uncountable ordinal ${\Omega}$ . By construction, this ordinal consists precisely of all the countable ordinals, but is itself uncountable, much as ${{\bf N}}$ consists precisely of all the finite natural numbers, but is itself infinite (Proposition 2). The least uncountable ordinal is notorious, among other things, for providing a host of counterexamples to various intuitively plausible assertions in point set topology, and in particular in showing that the topology of sufficiently uncountable spaces cannot always be adequately explored by countable objects such as sequences.

Remark 9 The existence of the least uncountable ordinal can explain why one cannot contradict Cantor’s theorem on the uncountability of the reals simply by iterating the diagonal argument (or any other algorithm) in an attempt to “exhaust” the reals. From transfinite induction we see that the diagonal argument allows one to assign a different real number to each countable ordinal, but this does not establish countability of the reals, because the set of all countable ordinals is itself uncountable. (This is similar to how one cannot contradict Proposition 4 by iterating the ${N \rightarrow N+1}$ map, as the set of all finite natural numbers is itself infinite.) In any event, even once one reaches the first uncountable ordinal, one may not yet have completely exhausted the reals; for instance, using the diagonal argument given in the proof of Proposition 6, only the real numbers in the interval ${[0,1]}$ will ever be enumerated by this procedure. (Also, the question of whether all real numbers in ${[0,1]}$ can be enumerated by the iterated diagonal algorithm requires the continuum hypothesis, and even with this hypothesis I am not sure whether the statement is decidable.)

— 2. Logic —

The “no self-defeating object” argument leads to a number of important non-existence results in logic. Again, the basic idea is to show that a sufficiently overpowered logical structure will eventually lead to the existence of a self-contradictory statement, such as the liar paradox. To state examples of this properly, one unfortunately has to invest a fair amount of time in first carefully setting up the language and theory of logic. I will not do so here, and instead use informal English sentences as a proxy for precise logical statements to convey a taste (but not a completely rigorous description) of these logical results here.

The liar paradox itself – the inability to assign a consistent truth value to “this sentence is false” – can be viewed as an argument demonstrating that there is no consistent way to interpret (i.e. assign a truth value to) sentences, when the sentences are (a) allowed to be self-referential, and (b) allowed to invoke the very notion of truth given by this interpretation. One’s first impulse is to say that the difficulty here lies more with (a) than with (b), but there is a clever trick, known as Quining (or indirect self-reference), which allows one to modify the liar paradox to produce a non-self-referential statement to which one still cannot assign a consistent truth value. The idea is to work not with fully formed sentences ${S}$ , which have a single truth value, but instead with predicates ${S}$ , whose truth value depends on a variable ${x}$ in some range. For instance, ${S}$ may be “ ${x}$ is two characters long.”, and the range of ${x}$ may be the set of strings (i.e. finite sequences of characters); then for every string ${T}$ , the statement ${S(T)}$ (formed by replacing every appearance of ${x}$ in ${S}$ with ${T}$ ) is either true or false. For instance, ${S(``ab'')}$ is true, but ${S(``abc'')}$ is false. Crucially, predicates are themselves strings, and can thus be fed into themselves as input; for instance, ${S(S)}$ is false. If however ${U}$ is the predicate “ ${x}$ is sixty-five characters long.”, observe that ${U(U)}$ is true.

Now consider the Quine predicate ${Q}$ given by

“ ${x}$ is a predicate whose range is the set of strings, and ${x(x)}$ is false.”

whose range is the set of strings. Thus, for any string ${T}$ , ${Q(T)}$ is the sentence

“ ${T}$ is a predicate whose range is the set of strings, and ${T(T)}$ is false.”

This predicate is defined non-recursively, but the sentence ${Q(Q)}$ captures the essence of the liar paradox: it is true if and only if it is false. This shows that there is no consistent way to interpret sentences in which the sentences are allowed to come from predicates, are allowed to use the concept of a string, and also allowed to use the concept of truth as given by that interpretation.

Note that the proof of Proposition 4 is basically the set-theoretic analogue of the above argument, with the connection being that one can identify a predicate ${T(x)}$ with the set ${\{x: T(x) \hbox{ true} \}}$ .

By making one small modification to the above argument – replacing the notion of truth with the related notion of provability – one obtains the celebrated Gödel’s (second) incompleteness theorem:

Theorem 9 (Gödel’s incompleteness theorem) (Informal statement) No consistent logical system which has the notion of a string, can provide a proof of its own logical consistency. (Note that a proof can be viewed as a certain type of string.)

Remark 10 Because one can encode strings in numerical form (e.g. using the ASCII code), it is also true (informally speaking) that no consistent logical system which has the notion of a natural number, can provide a proof of its own logical consistency.

Proof: (Informal sketch only) Suppose for contradiction that one had a consistent logical system inside of which its consistency could be proven. Now let ${Q}$ be the predicate given by

“ ${x}$ is a predicate whose range is the set of strings, and ${x(x)}$ is not provable”

and whose range is the set of strings. Define the Gödel sentence ${G}$ to be the string ${G := Q(Q)}$ . Then ${G}$ is logically equivalent to the assertion “ ${G}$ is not provable”. Thus, if ${G}$ were false, then ${G}$ would be provable, which (by the consistency of the system) implies that ${G}$ is true, a contradiction; thus, ${G}$ must be true. Because the system is provably consistent, the above argument can be placed inside the system itself, to prove inside that system that ${G}$ must be true; thus ${G}$ is provable and ${G}$ is then false, a contradiction. (It becomes quite necessary to carefully distinguish the notions of truth and provability (both inside a system and externally to that system) in order to get this argument straight!) $\Box$

Remark 11 It is not hard to show that a consistent logical system which can model the standard natural numbers cannot disprove its own consistency either (i.e. it cannot establish the statement that one can deduce a contradiction from the axioms in the systems in ${n}$ steps for some natural number ${n}$ ); thus the consistency of such a system is undecidable within that system. Thus this theorem strengthens the (more well known) first Gödel incompleteness theorem, which asserts the existence of undecidable statements inside a consistent logical system which contains the concept of a string (or a natural number). On the other hand, the incompleteness theorem does not preclude the possibility that the consistency of a weak theory could be proven in a strictly stronger theory (e.g. the consistency of Peano arithmetic is provable in Zermelo-Frankel set theory).

Remark 12 One can use the incompleteness theorem to establish the undecidability of other overpowered problems. For instance, Matiyasevich’s theorem demonstrates that the problem of determining the solvability of a system of Diophantine equations is, in general, undecidable, because one can encode statements such as the consistency of set theory inside such a system.

— 3. Computability —

One can adapt these arguments in logic to analogous arguments in the theory of computation; the basic idea here is to show that a sufficiently overpowered computer program cannot exist, by feeding the source code for that program into the program itself (or some slight modification thereof) to create a contradiction. As with logic, a properly rigorous formalisation of the theory of computation would require a fair amount of preliminary machinery, for instance to define the concept of Turing machine (or some other universal computer), and so I will once again use informal English sentences as an informal substitute for a precise programming language.

A fundamental “no self-defeating object” argument in the subject, analogous to the other liar paradox type arguments encountered previously, is the Turing halting theorem:

Theorem 10 (Turing halting theorem) There does not exist a program ${P}$ which takes a string ${S}$ as input, and determines in finite time whether ${S}$ is a program (with no input) that halts in finite time.

Proof: Suppose for contradiction that such a program ${P}$ existed. Then one could easily modify ${P}$ to create a variant program ${Q}$ , which takes a string ${S}$ as input, and halts if and only if ${S}$ is a program (with ${S}$ itself as input) that does not halts in finite time. Indeed, all ${Q}$ has to do is call ${P}$ with the string ${S(S)}$ , defined as the program (with no input) formed by declaring ${S}$ to be the input string for the program ${S}$ . If ${P}$ determines that ${S(S)}$ does not halt, then ${Q}$ halts; otherwise, if ${P}$ determines that ${S(S)}$ does halt, then ${Q}$ performs an infinite loop and does not halt. Then observe that ${Q(Q)}$ will halt if and only if it does not halt, a contradiction. $\Box$

Remark 13 As one can imagine from the proofs, this result is closely related to, but not quite identical with, the Gödel incompleteness theorem. That latter theorem implies that the question of whether a given program halts or not in general is undecidable (consider a program designed to search for proofs of the inconsistency of set theory). By contrast, the halting theorem (roughly speaking) shows that this question is uncomputable (i.e. there is no algorithm to decide halting in general) rather than undecidable (i.e. there are programs whose halting can neither be proven nor disproven).

On the other hand, the halting theorem can be used to establish the incompleteness theorem. Indeed, suppose that all statements in a suitably strong and consistent logical system were either provable or disprovable. Then one could build a program that determined whether an input string ${S}$ , when run as a program, halts in finite time, simply by searching for all proofs or disproofs of the statement “ ${S}$ halts in finite time”; this program is guaranteed to terminate with a correct answer by hypothesis.

Remark 14 While it is not possible for the halting problem for a given computing language to be computable in that language, it is certainly possible that it is computable in a strictly stronger language. When that is the case, one can then invoke Newcomb’s paradox to argue that the weaker language does not have unlimited “free will” in some sense.

Remark 15 In the language of recursion theory, the halting theorem asserts that the set of programs that do not halt is not a decidable set (or a recursive set). In fact, one can make the slightly stronger assertion that the set of programs that do not halt is not even a semi-decidable set (or a recursively enumerable set), i.e. there is no algorithm which takes a program as input and halts in finite time if and only if the input program does not halt. This is because the complementary set of programs that do halt is clearly semi-decidable (one simply runs the program until it halts, running forever if it does not), and so if the set of programs that do not halt is also semi-decidable, then it is decidable (by running both algorithms in parallel; this observation is a special case of Post’s theorem).

Remark 16 One can use the halting theorem to exclude overly general theories for certain types of mathematical objects. For instance, one cannot hope to find an algorithm to determine the existence of smooth solutions to arbitrary nonlinear partial differential equations, because it is possible to simulate a Turing machine using the laws of classical physics, which in turn can be modeled using (a moderately complicated system of) nonlinear PDE. Instead, progress in nonlinear PDE has instead proceeded by focusing on much more specific classes of such PDE (e.g. elliptic PDE, parabolic PDE, hyperbolic PDE, gauge theories, etc.).

One can place the halting theorem in a more “quantitative” form. Call a function ${f: {\bf N} \rightarrow {\bf N}}$ computable if there exists a computer program which, when given a natural number ${n}$ as input, returns ${f(n)}$ as output in finite time. Define the Busy Beaver function ${BB: {\bf N} \rightarrow {\bf N}}$ by setting ${BB(n)}$ to equal the largest output of any program of at most ${n}$ characters in length (and taking no input), which halts in finite time. Note that there are only finitely many such programs for any given ${n}$ , so ${BB(n)}$ is well-defined. On the other hand, it is uncomputable, even to upper bound:

Proposition 11 There does not exist a computable function ${f}$ such that one has ${BB(n) \leq f(n)}$ for all ${n}$ .

Proof: Suppose for contradiction that there existed a computable function ${f(n)}$ such that ${BB(n) \leq f(n)}$ for all ${n}$ . We can use this to contradict the halting theorem, as follows. First observe that once the Busy Beaver function can be upper bounded by a computable function, then for any ${n}$ , the run time of any halting program of length at most ${n}$ can also be upper bounded by a computable function. This is because if a program of length ${n}$ halts in finite time, then a trivial modification of that program (of length larger than ${n}$ , but by a computable factor) is capable of outputting the run time of that program (by keeping track of a suitable “clock” variable, for instance). Applying the upper bound for Busy Beaver to that increased length, one obtains the bound on run time.

Now, to determine whether a given program ${S}$ halts in finite time or not, one simply simulates (runs) that program for time up to the computable upper bound of the possible running time of ${S}$ , given by the length of ${S}$ . If the program has not halted by then, then it never will. This provides a program ${P}$ obeying the hypotheses of the halting theorem, a contradiction. $\Box$

Remark 17 A variant of the argument shows that ${BB(n)}$ grows faster than any computable function: thus if ${f}$ is computable, then ${BB(n) > f(n)}$ for all sufficiently large ${n}$ . We leave the proof of this result as an exercise to the reader.

Remark 18 Sadly, the most important unsolved problem in complexity theory, namely the ${P \neq NP}$ problem, does not seem to be susceptible to the no-self-defeating-object argument, basically because such arguments tend to be relativisable whereas the ${P \neq NP}$ problem is not; see this earlier blog post for more discussion. On the other hand, one has the curious feature that many proposed proofs that ${P \neq NP}$ appear to be self-defeating; this is most strikingly captured in the celebrated work of Razborov and Rudich, who showed (very roughly speaking) that any sufficiently “natural” proof that ${P \neq NP}$ could be used to disprove the existence of an object closely related to the belief that ${P \neq NP}$ , namely the existence of pseudorandom number generators. (I am told, though, that diagonalisation arguments can be used to prove some other inclusions or non-inclusions in complexity theory that are not subject to the relativisation barrier, though I do not know the details.)

— 4. Game theory —

Another basic example of the no-self-defeating-objects argument arises from game theory, namely the strategy stealing argument. Consider for instance a generalised version of naughts and crosses (tic-tac-toe), in which two players take turns placing naughts and crosses on some game board (not necessarily square, and not necessarily two-dimensional), with the naughts player going first, until a certain pattern of all naughts or all crosses is obtained as a subpattern, with the naughts player winning if the pattern is all naughts, and the crosses player winning if the pattern is all crosses. (If all positions are filled without either pattern occurring, the game is a draw.) We assume that the winning patterns for the cross player are exactly the same as the winning patterns for the naughts player (but with naughts replaced by crosses, of course).

Proposition 12 In any generalised version of naughts and crosses, there is no strategy for the second player (i.e. the crosses player) which is guaranteed to ensure victory.

Proof: Suppose for contradiction that the second player had such a winning strategy ${W}$ . The first player can then steal that strategy by placing a naught arbitrarily on the board, and then pretending to be the second player and using ${W}$ accordingly. Note that occasionally, the ${W}$ strategy will compel the naughts player to place a naught on the square that he or she has already occupied, but in such cases the naughts player may simply place the naught somewhere else instead. (It is not possible that the naughts player would run out of places, thus forcing a draw, because this would imply that ${W}$ could lead to a draw as well, a contradiction.) If we denote this stolen strategy by ${W'}$ , then ${W'}$ guarantees a win for the naughts player; playing the ${W'}$ strategy for the naughts player against the ${W}$ strategy for the crosses player, we obtain a contradiction. $\Box$

Remark 19 The key point here is that in naughts and crosses games, it is possible to play a harmless move – a move which gives up the turn of play, but does not actually decrease one’s chance of winning. In games such as chess, there does not appear to be any analogue of the harmless move, and so it is not known whether black actually has a strategy guaranteed to win or not in chess, though it is suspected that this is not the case.

Remark 20 The Hales-Jewett theorem shows that for any fixed board length, an ${n}$ -dimensional game of naughts and crosses is unable to end in a draw if ${n}$ is sufficiently large. An induction argument shows that for any two-player game that terminates in bounded time in which draws are impossible, one player must have a guaranteed winning strategy; by the above proposition, this strategy must be a win for the naughts player. Note, however, that Proposition 12 provides no information as to how to locate this winning strategy, other than that this strategy belongs to the naughts player. Nevertheless, this gives a second example in which the no-self-defeating-object argument can be used to ensure the existence of some object, rather than the non-existence of an object. (The first example was the prime number theorem, discussed earlier.)

The strategy-stealing argument can be applied to real-world economics and finance, though as with any other application of mathematics to the real world, one has to be careful as to the implicit assumptions one is making about reality and how it conforms to one’s mathematical model when doing so. For instance, one can argue that in any market or other economic system in which the net amount of money is approximately constant, it is not possible to locate a universal trading strategy which is guaranteed to make money for the user of that strategy, since if everyone applied that strategy then the net amount of money in the system would increase, a contradiction. Note however that there are many loopholes here; it may be that the strategy is difficult to copy, or relies on exploiting some other group of participants who are unaware or unable to use the strategy, and would then lose money (though in such a case, the strategy is not truly universal as it would stop working once enough people used it). Unfortunately, there can be strong psychological factors that can cause people to override the conclusions of such strategy-stealing arguments with their own rationalisations, as can be seen, for instance, in the perennial popularity of pyramid schemes, or to a lesser extent, market bubbles (though one has to be careful about applying the strategy-stealing argument in the latter case, since it is possible to have net wealth creation through external factors such as advances in technology).

Note also that the strategy-stealing argument also limits the universal predictive power of technical analysis to provide predictions other than that the prices obey a martingale, though again there are loopholes in the case of markets that are illiquid or highly volatile.

— 5. Physics —

In a similar vein, one can try to adapt the no-self-defeating-object argument from mathematics to physics, but again one has to be much more careful with various physical and metaphysical assumptions that may be implicit in one’s argument. For instance, one can argue that under the laws of special relativity, it is not possible to construct a totally immovable object. The argument would be that if one could construct an immovable object ${O}$ in one inertial reference frame, then by the principle of relativity it should be possible to construct an object ${O'}$ which is immovable in another inertial reference frame which is moving with respect to the first; setting the two on a collision course, we obtain the classic contradiction between an irresistible force and an immovable object. Note however that there are several loopholes here which allow one to avoid contradiction; for instance, the two objects ${O, O'}$ could simply pass through each other without interacting.

In a somewhat similar vein, using the laws of special relativity one can argue that it is not possible to systematically generate and detect tachyon particles – particles traveling faster than the speed of light – because these could be used to transmit localised information faster than the speed of light, and then (by the principle of relativity) to send localised information back into the past, from one location to a distant one. Setting up a second tachyon beam to reflect this information back to the original location, one could then send localised information back to one’s own past (rather than to the past of an observer at a distant location), allowing one to set up a classic grandfather paradox. However, as before, there are a large number of loopholes in this argument which could let one avoid contradiction; for instance, if the apparatus needed to set up the tachyon beam may be larger than the distance the beam travels (as is for instance the case in Mexican wave-type tachyon beams) then there is no causality paradox; another loophole is if the tachyon beam is not fully localised, but propagates in spacetime in a manner to interfere with the second tachyon beam. A third loophole occurs if the universe exhibits quantum behaviour (in particular, the ability to exist in entangled states) instead of non-quantum behaviour, which allows for such superluminal mechanisms as wave function collapse to occur without any threat to causality or the principle of relativity. A fourth loophole occurs if the effects of relativistic gravity (i.e. general relativity) become significant. Nevertheless, the paradoxical effect of time travel is so strong that this physical argument is a fairly convincing way to rule out many commonly imagined types of faster-than-light travel or communication (and we have a number of other arguments too that exclude more modes of faster-than-light behaviour, though this is an entire blog post topic in its own right).

88 comments

Comments feed for this article

5 November, 2009 at 2:23 am

Giovanni Peccati

Nice post !

Minor remark : it is my impression that the proof of Proposition 3 is not concluded – as it merges into some further discussion.

All the best

Giovanni

[Fixed, thanks – T.]

5 November, 2009 at 3:55 am

Anonymous

Interesting post. A quick thought on “it is much harder to let go of the belief that, at some point, some sufficiently ingenious person will work out a way to countably enumerate the real numbers”:

this may be tied up with the notion of infinity itself, since (not thinking precisely at all) finite things are things that can be laid out in a field and counted and “infinity” is already larger than anything that can be concretely visualized and hence, how can there be a bigger “infinity” than “infinity”?

There appears to be a broken link in Remark 8 [Fixed, thanks – T.]

5 November, 2009 at 6:06 am

Rune

You comment on chess reminds me of this question: If two computationally unbounded players play Chess, does White win? Is it a draw? Does Black win?

5 November, 2009 at 6:49 am

The omnipotence paradox « Cam's Blog

[…] omnipotence paradox Filed under: Uncategorized — cfranc @ 2:49 pm Just read Terrence Tao’s latest post over at his blog. He mentioned the omnipotence paradox, which is likely familiar to […]

5 November, 2009 at 6:58 am

Bruno

In Remark 14, the proposition you use (if a set is both recursively-enumerable and co-recursively-enumerable, then it is recursive) is often referred as Post’s Theorem.

5 November, 2009 at 7:13 am

Doug

Thanks for this nice post.

I have a question about the proof of Proposition 12.

You suppose that the second player has a winning strategy W, and then write “The first player can then steal that strategy by placing a naught arbitrarily on the board, and then pretending to be the second player and using W accordingly.” Remark 18 explains that this kind of strategy stealing depends on the fact that it is possible in naughts and crosses to play a “harmless move.”

What I do not follow is how can it be possible for there to be such a
“harmless move” under the assumption that the other player has a
winning strategy? If we assume the second player has a winning strategy, then she can win regardless of the move (arbitrarily placed, “harmless” or whatever) made by the first player.

A related question is the following. How does one prove that a given game has a “harmless move” or prove that it does not?

5 November, 2009 at 8:33 am

Peter LeFanu Lumsdaine

Doug: As you say, the existence of a “harmless move” for one player is incompatible with the existence of a winning strategy for the other. So by proving directly that there _is_ a harmless move (and TT’s argument for noughts and crosses gives the essentials of such a proof), we get a contradiction, which shows the assumption can’t have been right.

5 November, 2009 at 7:26 am

Manjil P. Saikia

Thanks for the nice post, it is really stimulating to read this in your blog.

5 November, 2009 at 7:26 am

andrescaicedo

Hi Terry,
It looks like a line was left out at the end of Prop. 3.

5 November, 2009 at 8:55 am

Ulrich

Tery, can you please check if you have put the html-code in the graphics mode to WordPress? I can see the original code (, ..) and not the formatted one.

Thanks

Ulrich

5 November, 2009 at 8:58 am

Ulrich

… has gone. Mysteriously.

Ulrich [Sorry, that was a temporary glitch while trying to fix an earlier error. It should all be OK now – T.]

5 November, 2009 at 9:25 am

Doug

Peter, Thanks. The way you wrote it is better than my ramblings. Now I just need to see a precise definition of a “harmless move” and a proof that naughts and crosses has one.

5 November, 2009 at 10:17 am

Ted

I’m not entirely sure of the distinction being made in Remark 13. What’s the essential difference between uncomputable and undecidable here?

At first, I thought perhaps uncomputable might mean that it’s not even recursively enumerable, but that cannot be right in this context. (The halting set is r.e., as you state in remark 15.)

5 November, 2009 at 10:54 am

Terence Tao

Well, the distinction I had in mind was this: I could conceive, in principle, of a world in which the halting theorem failed but the incompleteness theorem held. Namely, imagine that there was some miraculous algorithm that could decide whether any given program halted in finite time, but nobody could explain why it worked (in particular, there was no proof that the answers it gave were correct). Then one could ask the algorithm whether a demonstration of (say) the inconsistency of ZFC existed, and it would give the correct answer (which would be NO, assuming that ZFC is consistent), but this would not constitute a proof that ZFC is consistent, because one could not prove the soundness of the algorithm.

The halting theorem excludes the existence of such miraculous algorithms, even if their soundness is unproven. (But perhaps there is a clever way to arrange things so that one could use the incompleteness theorem to prove the halting theorem or vice versa. I wasn’t able to come up with one, though.)

It’s a little unfortunate that the term “decidable” has two different contexts here (existence of a proof or disproof of a statement, vs. existence of an algorithm that can correctly answer a class of yes-no questions), though of course they are very closely related.

6 November, 2009 at 1:53 am

luca

You can deduce the incompleteness theorem from the undecidability of the halting problem as follows: consider all statements of the form “machine M halts on input w” and “machine M does not halt on input w” over all machines M and possible inputs w.

I claim that, assuming consistency, there is some M,w such that neither the statement “machine M halts on input w” nor its negation are provable, and hence the statement is undecidable (in the logical sense).

Otherwise, given a machine M and a string w, I could enumerate all possible strings P, and check if P happens to be a valid proof of “M halts on input w” or of “M does not halt on input w.” This search would always terminate, and so I would have an algorithm for the halting problem.

This can be made more constructive by exhibiting a specific true and unprovable (assuming consistency) statement, rather than having a non-constructive existence argument above, by folding the above argument with the proof of undecidability of the halting problem.

Consider the machine D that, on input the description of a machine M, enumerates all strings P, and halts if P happens to be a proof of the statement “machine M does not halt when given the description of M as an input”

Consider the statement “D does not halt when given D as an input.” Assuming consistency, neither this statement nor its negation can be provable.

At this point we can also get the Second Incompleteness Theorem, by noting that if consistency were provable, then we could formalize the above argument, prove the statement “there exists no proof P that D does not halt when given D as an input,” and then realize then suddenly we do in fact have a proof that “D does not halt when given D as an input,” leading to a contradiction. (Hence if consistency of our logical system is provable within the logical systems itself, then our logical system must be inconsistent.)

These arguments are due to Turing. I don’t know if there is a way to deduce the halting Theorem from the incompleteness theorem.

6 November, 2009 at 7:50 am

Terence Tao

Thanks Luca, that is quite clarifying! I will adjust the remark accordingly.

5 November, 2009 at 10:32 am

Henry

I have one small quibble, with your statement that the proof of the existence of a winning strategy for naughts-and-crosses is highly nonconstructive. The proof does give a strategy: exhaustively analyze all possible plays of the (finite!) game, and then play along a winning one. (The strategy is, of course, useless for practical purposes except when n is small, but mathematically valid.)

It isn’t entirely obvious that this strategy is the one witnessing the claim, because the argument here is given by contradiction, but the methods used in the proof are entirely elementary, so metatheorems guarantee that there are finitely many possible witnesses hidden in the proof. It’s not hard to check that this rather boring strategy is the one in question.

5 November, 2009 at 10:56 am

Terence Tao

Fair enough. I guess what I wanted to say is that the proof that naughts has a winning strategy is no more constructive than the general statement that any two-player deterministic game without draws has a winning strategy for one side, in that the knowledge that naughts wins is of essentially zero help in actually constructing a winning strategy (though I suppose it might prune the strategy tree by a factor of two, at best).

5 November, 2009 at 11:09 am

Joshua Zelinsky

Note that although the behavior of naughts and crosses (which I think many Americans call xs and ohs) does have a surprisingly counterintuitive result. Namely there are boards one can construct such that the first player has a winning strategy but there is an expansion of the board such that the second player can force a draw.

Also note that in regards to the connection between the Halting Theorem and Godel’s Undecidability can be thought of as a bit closer. Godel’s result follows from showing that any sufficiently powerful axiomatic system can model Turing machines and that one can construct a Turing machine which enumerates all the theorems in a given axiomatic system. Thus, Halting theorem implies Godel’s theorem. It isn’t that hard to see that the other direction also goes through.

6 November, 2009 at 7:32 am

Qiaochu Yuan

Can you sketch the argument that Godel’s theorem implies the Halting theorem?

5 November, 2009 at 1:11 pm

Miguel Lacruz

Consider the following modification of chess. Every player makes two moves in a row. White can start by moving a knight and returning it to its initial square. This harmless move shows that there is no winning strategy for black.

A common technique in regular chess is called zugzwang. The fact that a player must make a move leads to a loss. This is the opposite notion of a harmless move.

5 November, 2009 at 1:43 pm

John Armstrong

@Zelinsky How is that counterintuitive? 1 needs to pin down 2, and extra spaces may give 2 enough room to wiggle out of it.

Also, “although the behavior has a ‘counterintuitive result’…” what?

5 November, 2009 at 4:16 pm

Joshua Zelinsky

Er, there’s a clause missing after “although” I meant to say something of the form “although the intuition that the second player never has a winning strategy is correct.” Some sort of brain to keyboard error there.

I’m not sure what you mean about pinning down and wiggling out. In a standard xs and ohs game the goal is to get a configuration of your pieces lying in a certain set of patterns. The issue then becomes that there are boards which are winning boards for the first player that become drawn boards when expanded. Note that this doesn’t happen for well-behaved boards. If one is using fairly symmetric configurations on a square board and that board is a win for the first player then larger square boards is also a win. The boards that don’t do this are a bit pathological.

6 November, 2009 at 1:56 am

John Armstrong

The winning paths through game trees generally consist of restricting the possible good plays of 2. 1 plays in such a way as to constantly threaten a win, which gives 2 only one option of where to play next, and effectively gives 1 a free move.

5 November, 2009 at 2:51 pm

V. V. Volkov

Dear Prof. Tao,

Thank you for the elegant and straightforward exposition! Even for an undergrad and non-mathematician like myself, these types of explanatory posts and talks (the “Distance Ladder” slides, for example) are fascinating and inviting to read through.

With regards to Remark 2: is it fair to say that, by definition, the hypothetical almost-universal set Z would have to contain the universal set X as a member, a priori? (Because X =/= Z, and Z supposedly contains “all” sets other than Z itself…) Otherwise, how could one claim that X = Z U {Z} is a universal set, which must contain itself?

Thank you again for the thought-provoking post and references!
– Vasiliy

6 November, 2009 at 7:52 am

Terence Tao

Yes, this is correct. By hypothesis, Z consists of all sets other than Z itself, so by adding Z, one obtains all sets.

6 November, 2009 at 1:00 am

Anonymous

Your way of unifying mathematical topics by focusing on a single underlying trick is very enlightening. All the math books should be rewritten to emphasize the recurring tricks.

6 November, 2009 at 6:55 am

T. Tao: „Self Defeating Object Argument“ « UGroh's Weblog

[…] November 2009 in Mathematik | Tags: tao mathematik grundwissen Ich kann nur empfehlen, diesen Artikel von Terence Tao zu studieren. Zum Inhalt zitiere ich den Anfang: „A fundamental tool in any […]

6 November, 2009 at 8:59 am

kunal

Great post!

While I have always seen the proof of non-enumerbility of reals as above, I find the details dealing with recurring decimals very distracting. After all, the theorem still holds if you wrote the reals in binary, but this proof fails.
Why don’t we use something like the following argument:
Lemma 1: If the reals are enumerable, then so is the set of all decimal representations. (There are at most two per real).
Lemma 2: The set of all decimal representations is no enumerable. (This is now much shorter.)

Isn’t this proof didactically better?

6 November, 2009 at 10:24 am

Jonathan Vos Post

Wonderful thread! I discussed “… by other primary school children…” with my Physics professor wife, after posting a link to this for my roughly 500 Facebook friends.

I have seen primary school children argue in the schoolyard variations of “can God make a rock so big that he can’t lift it?” which I’ve heard expressed, not as Theophysics, but as pop culture: “can Superman fly to a planet so big that he can’t move it?”

6 November, 2009 at 10:59 am

Jonathan Vos Post

I also once heard a child, puzzled by perspective or optics, ask another child: “Is there something so big that when you stand so far away from it that you can see all of it, you’re so far away that you can’t see it at all?”

But that’s a single datum, and does not diminish Terry Tao’s great point: “ROUTINELY taught to primary school children by other primary school children…”

6 November, 2009 at 9:43 pm

Richard Borcherds

The statement “It is not hard to show that a consistent logical system cannot disprove its own consistency either” in remark 11 is a little misleading. One can take a consistent system, say Peano arithmetic, and add the statement that it is inconsistent as a new axiom. This produces a system which is consistent (otherwise Peano arithmetic would prove its own inconsistency) but which in some sense asserts its own inconsistency! Models of this give rather strange non-standard models of Peano arithmetic. I have a vague memory that there is something called omega-consistency which may be relevant.

7 November, 2009 at 9:40 pm

Terence Tao

Ah yes, one does have to restrict attention to systems which actually model the standard natural numbers (or more generally, to omega-consistent systems), otherwise a proof of inconsistency within the system does not actually imply that one can establish inconsistency in a finite amount of time. I’ve reworded the text accordingly.

7 November, 2009 at 6:12 am

Anonymous

This was a really nice post!

To ask about something less interesting:
Do you find that proofs by contradiction like these can be a bit confusing in the way they tend to be presented? For example, one sometimes uses the words “Assume” or “Suppose” to precede all assumptions (including those which will later be contradicted), but then it is unclear the proof will proceed by contradiction, and sometimes even unclear what will be contradicted (since this matter can be quite subtle). For example, bootstrap arguments in PDE can sometimes be proofs by contradiction, which can be obscured in casual presentations.

Using the phrase “Suppose for contradiction” (as you have done) or “assume by contradiction” seems to clarify that there will be a contradiction and exactly which assumption will create the contradiction. To a mathematician it’s clear what this phrase means, but it seems to require that one already be familiar with it.

Using the phrase “Pretend” seems to serve the same purpose, it’s brief and I think it resembles more familiar English, but perhaps it is not sufficiently precise or otherwise why it’s not as common.

7 November, 2009 at 2:28 pm

Richard

A variation of this that I use is “Anticipating a contradiction, suppose that …”.

8 November, 2009 at 8:35 am

timur

Minor point, but in general proof by contradiction will imply that one or more of the assumptions you make is false. When it is not so obvious that all the other assumptions are true, I think it can be misleading to place “Suppose for contradiction” or “Pretend” on a single assumption.

7 November, 2009 at 4:13 pm

Top Posts « WordPress.com

[…] The “no self-defeating object” argument A fundamental tool in any mathematician’s toolkit is that of reductio ad absurdum: showing that a statement is […] […]

8 November, 2009 at 12:31 pm

null

I think prop 2 is to close to the foundation to be proved in such a manner. Formally prop 2:: does not exist f surjective f:{1..n}->N since image(f) is N we have a question if that sum f(i) is well defined. Also the introduction of + function is not necessary. I suggest: does not exist f bijection f:{1..n}->{1..n+1} then prop 2 follows (prop 8 “Algebra By Saunders Mac Lane, Garrett Birkhoff” p.158)

8 November, 2009 at 6:55 pm

Terence Tao

One can define $\sum_{i=1}^n f(i)$ for any function $f: \{1,\ldots,n\} \to {\Bbb N}$ by induction on n (and a small amount of set theory), using the fact that the natural numbers are closed under addition. Of course, this is inconsistent with the hypothesis that the natural numbers are finitely enumerated, but that’s the whole point – we’re trying to establish a contradiction!

One can prove Proposition 2 without use of the addition function, but I chose this proof in order to motivate the proof of Proposition 3.

8 November, 2009 at 2:21 pm

crosslegged

Hello. In the proof of proposition 5, why is it “Y = A_y with y in Y” and not “Y = A_x with x in X”?

8 November, 2009 at 6:51 pm

Terence Tao

One could use any dummy variable here. I chose to call this particular element $y$ to emphasise that it is the element that indexes $Y$ in the enumeration, but one could of course give it another name if one pleased.

9 November, 2009 at 8:28 am

crosslegged

Thank you for replying professor Tao. My problem is not the name of the variable, but the fact that the element that indexes Y is in particular in Y, and not just in X. I think it should just be in X. [Ah, I see now. Corrected, thanks – T.]

14 September, 2011 at 9:33 am

Varun

By your definition of {Y}, {y \in Y} iff {y \not \in A_x}, not {A_y}. So your contradiction doesn’t readily follow.

I’m sure one can still somehow complete the argument from here, but I don’t immediately see how.

14 September, 2011 at 9:59 am

Terence Tao

In the definition of Y, x is a bound variable, and may be substituted for any other expression if desired, by the rule of universal instantiation. Thus, for instance, if $x \in X$ , then $x \in Y$ if and only if $x \not \in A_x$ ; if $y \in X$ , then $y \in Y$ if and only if $y \not \in A_y$ ; if $57 \in X$ , then $57 \in Y$ if and only if $57 \not \in A_{57}$ ; and so forth.

8 November, 2009 at 4:39 pm

Kenny Easwaran

The set-theoretic arguments of course all assume that we’re working in something like ZFC, with either an axiom of separation or an axiom of foundation or both. Of course, there are consistent set theories (like Quine’s “New Foundations” and one discussed in a recent article by Thomas Forster) where there is a universal set. (When I say “consistent”, in the one case there are explicit relative consistency results showing that this theory is consistent iff ZFC is. For NF, I don’t think there is such a relative consistency result yet, but I think people are nearly as confident of consistency here as they are of ZFC.)

Also, for the elimination of faster-than-light communication in relativity, I don’t see why the grandfather paradox is a strong enough paradox to rule any of this out. What you’d need to do is show that it’s possible to send arbitrary messages, and to set up devices that respond to arbitrary messages in inconsistent ways.

That is, you might set up two devices such that one of them is guaranteed to send a message at some time, which is different from any message it receives one second earlier, if there is such a message. Meanwhile, you can make sure that there is a machine at its destination that is guaranteed to send out a message identical to the one that it receives, in such a way that its message reaches the input time of the device it receives from. If the construction of a tachyon device allowed this sort of construction, it would clearly be contradictory.

But this sort of argument wouldn’t rule out a tachyon device that only sends messages if it receives a message (neither device would send a message then), or a device that can only send messages that agree with its input in some way, or a device that can’t respond to inputs in any way, or devices with other sorts of restrictions.

The initial grandfather paradox assumes a strong conception of free will (that is, one that assumes that every single action of a certain class is possible for an ordinary human). But if you only assume a version of free will that is compatible with a deterministic universe, then there is no grandfather paradox.

8 November, 2009 at 4:43 pm

Kenny Easwaran

Oh, and in Remark 14, I don’t see what work Newcomb’s paradox is doing here. The problem there is just a paradox involving two concepts of rationality (one says that it’s rational to perform an act iff it has the highest expected payoff; the other says that it’s rational to perform an act if it increases your payoff conditional on any state the universe outside of you may already be in). Without a notion of rationality, there is no paradox. (You can take one box or both, and both have consistent outcomes.) Since there is no notion of rationality involved in a formal logical system, I don’t see the relevance here. Maybe I’m misunderstanding the metaphor?

8 November, 2009 at 8:15 pm

Terence Tao

1. Yes, the discussion in Section 2 is specific to ZFC-type systems (see the first paragraph). And yes, there are certainly plenty of loopholes in the grandfather paradox (I mention a few in the post), though it’s hard to come up with a plausible realisation of such loopholes which continues to give the tachyon device any sort of physical influence on the world while always avoiding the possibility of paradox.

2. Regarding Newcomb’s paradox, the point is that if one assumes free will, together with causality (one’s present choices, made of one’s free will, cannot influence the prior state of the universe), then there is no distinction between the two types of rationality you mention, at the time one “chooses” whether to take one box or both. The paradox shows that a robot programmed using a language L that can be simulated in advance by another entity cannot always be both rational (i.e. always acting to increase expected payoff) and logically consistent while assuming both free will and causality. To me, this is a convincing demonstration that such a robot does not, in fact, have free will.

9 November, 2009 at 3:19 am

David Corfield

You mention the extended natural numbers, which are the terminal coalgebra for the functor on the category of sets, $F: X \to 1 + X$ . Both terminal coalgebras and initial algebras are fixed points of the relevant functors, respectively greatest and least. The initial $F$ -algebra is of course the natural numbers, from which induction and recursion follow.

Peter Aczel in his book ‘Non-well-founded sets’ shows what can be done when giving up well-foundedness. One current formulation of this in ‘algebraic set theory’ is that the class of well-founded sets form an initial algebra, and the class of non-well-sets a terminal coalgebra for the functor on the category of classes which takes a class to the class of set-sized subclasses.

Aczel speaks of maximalising and minimalising axiomatisations. One example of a maximalising axiomatisation was Paul Finsler’s 1926 definition of the system of sets as the maximal system satisfying certain properties (this is more or less Aczel’s class of non-well-founded sets). Not understanding this kind of definition, Baer argued using a self-defeating argument that there could be no such thing – for any system of sets satisying Finsler’s axioms, a new set could be found which when added would still be a Finslerian system.

Maximalising axiomatisations exist throughout mathematics, for example, one of Hilbert’s axioms of Euclidean geometry states:

V.2: Line completeness. To a system of points, straight lines, and planes, it is impossible to add other elements in such a manner that the system thus generalized shall form a new geometry obeying all of the five groups of axioms. In other words, the elements of geometry form a system which is not susceptible of extension, if we regard the five groups of axioms as valid.

The real interval has only recently (a decade ago) been characterised in a coalgebraic fashion as a terminal coalgebra for a certain functor on bipointed spaces.

10 November, 2009 at 4:29 am

Peter Gerdes

The reason people have so much difficulty with the cardinality of the real numbers is that most people understand cardinality as ‘size’ and this is easily confused with the notion of size provided by extent (kinda a half-assed version of measure). I mean we can enumerate the rationals and in terms of extent this has the same size as the reals.

I suspect if you asked the same question about \omega^\omega people wouldn’t find it so troubling because they don’t start with any preconceived notion of size in the baire space.

10 November, 2009 at 11:29 am

konradswanepoel

In Remark 8 you don’t need the axiom of choice. The ordinals can be defined in ZF as sets that are well ordered by the $\varepsilon$ relation and whose elements are also subsets. Then the first uncountable ordinal is simply the set of all countable ordinals. Other properties such as transfinite induction also hold in ZF.

Of course Choice comes in when showing that an arbitrary set can be given a well ordering (with its consequences such as Zorn’s Lemma).

11 November, 2009 at 11:11 am

Terence Tao

I can see why the class of countable ordinals is a class, but in ZF how does one ensure that it is actually a set? If one tries to use transfinite induction it seems that one needs an uncountable ordinal to begin with in order to ensure that it is a set rather than merely a class, which seems circular…

11 November, 2009 at 11:34 am

andrescaicedo

Hi Terry. Just look at the collection of well-orderings of subsets of ${\mathbb N},$ thought of as binary relations. This is a set. Consider the equivalence relation where 2 such well-orderings are equivalent iff they are (order) isomorphic. The quotient is a set. Well-order this quotient by saying that $[(A,<_1)]$ is below $[(B,<_2)]$ iff $(A,<_1)$ is order isomorphic to a proper initial segment of $(B,<_2)$ (this is well-defined). The resulting well-order is uncountable, but all its initial segments are countable. Choice was not used in this construction.

11 November, 2009 at 1:23 pm

konradswanepoel

Yes! This idea goes back to Hartogs. And note that this argument needs the most powerful axioms in ZF: the power set axiom and the axiom scheme of replacement.

12 November, 2009 at 10:30 am

Terence Tao

Thanks for the argument (which I was not aware of). I’ve updated the remark accordingly.

13 November, 2009 at 7:23 am

scineram

I would add that none of the ordinal statements require axiom of regularity or foundation by definition of ordinals as stets well-ordered by the element relation.

13 November, 2009 at 7:57 pm

Anonymous

I have always had a problem with Prop 6 proof.

It is not clear to me why the new decimal expansion you constructed in NOT is the enumerated list. It seems to me all you have done is created a number which is different from x_n. Why is the new decimal not in the enumerated list somewhere?

13 November, 2009 at 8:11 pm

Terence Tao

The new decimal expansion is, by construction, distinct from $x_n$ for every n: distinct from $x_1$ (because of the way the first digit was chosen), distinct from $x_2$ (because of the way the second digit was chosen), distinct from $x_{37}$ (because of the way the 37th digit was chosen) and so forth. It is thus distinct from every real number already in the enumeration.

14 November, 2009 at 4:32 am

Reductio ad absurdum

[…] Reductio ad absurdum […]

17 November, 2009 at 1:20 pm

sirval

Very nice post!
I would like to make a comment about the application of the “no self-defeating object” to physics, and is that I believe that proofs of the non-existence of a deterministic theory compatible with the results of experiments such as GHZ or EPR are good examples of the use of a “reductio ad absurdum” method.
It is possible to argue that locality can be violated, or the existence of dependence in the state of the particles related to the measuring apparatus, but I believe that this one is also a good example.

18 November, 2009 at 3:06 pm

piergiorgio odifreddi

dear tao,

a propos of the relationships between incompleteness and the halting problem, it is known that while the latter implies the former, as correctly stated in the post, the converse is not true.

more precisely, the halting problem corresponds to proving undecidability (and hence incompleteness, for formal systems) by showing that SOME (and actually, the most complicated, in a precise sense) non computable, computably enumerable set is representable in the system.

but it is als possible to prove undecidability (and hence incompleteness) of a formal system by showing that ALL computable sets are representable in it.

now, it was proven in the ’60s by shoenfield (and this was, historically, the first application of the so-called “infinite injury method” in computability theory) that there is a formal system in which all recursive sets are representable, but the halting problem is not.

if you want details, discussions and references see my “classical recursion theory” (north holland, 1989 and 1999), in particular pp. 352-353 of volume I.

ciao!

george odifreddi

28 November, 2009 at 4:05 am

hyangchun's me2DAY

향천의 생각…

The “no self-defeating object” argument « What’s new…

30 November, 2009 at 12:56 pm

artur

For generalizing the tic-tac-toe example, I guess one should also specify that the winning pattern is monotone. For instance, if the winning pattern for the first player required that certain squares should have crosses, then I don’t see how the harmless move idea can be implemented.

[Added a clarification that the winning pattern is a subpattern only, and consists entirely of naughts or entirely of crosses. -T]

19 March, 2010 at 9:53 pm

A computational perspective on set theory « What’s new

[…] computational resources and the latter in the case of unlimited computational resources. (See also my previous blog post for further discussion of these “no self-defeating object” […]

9 May, 2010 at 1:02 pm

The Hilbert Hotel - Opinionator Blog - NYTimes.com

[…] wishing to go deeper into infinity might enjoy Terry Tao’s blog post about “self-defeating objects.” In a very accessible way, he presents and elucidates a lot of fundamental arguments about […]

18 October, 2010 at 9:38 am

The “no self-defeating object” argument, revisited « What’s new

[…] Some time ago on this blog, I collected a family of well-known results in mathematics that were proven by contradiction, and specifically by a type of argument that I called the “no self-defeating object” argument; that any object that was so ridiculously overpowered that it could be used to “defeat” its own existence, could not actually exist. Many basic results in mathematics can be phrased in this manner: not only Cantor’s theorem, but Euclid’s theorem on the infinitude of primes, Gödel’s incompleteness theorem, or the conclusion (from Russell’s paradox) that the class of all sets cannot itself be a set. […]

23 October, 2010 at 10:48 am

Luke Grecki

I don’t follow your reasoning in Remark 16.

Suppose one had an algorithm to determine the existence of smooth solutions to arbitrary nonlinear partial differential equations. I don’t see how this implies you would know whether the Turing machine you were modeling with such equations halts. You would know there existed solutions describing it’s behavior, but you wouldn’t necessarily be able to compute them or prove that they had certain properties.

23 October, 2010 at 11:37 am

Terence Tao

The idea is to set up a PDE problem which admits smooth solutions if and only if a certain Turing machine halts. One way to do this is to create an analog Turing machine that takes $2^{-n}$ units of time to do the $n^{th}$ step of the computation. If the machine does not halt, then the evolution of this machine will develop a singularity at time $1$ , but otherwise it will exist and be smooth for all time.

23 October, 2010 at 11:50 am

Luke Grecki

Gotcha. Thanks.

2 May, 2011 at 2:23 am

plm

This is a really nice construction. And it looks like there would be alot more to investigate (and some of it has already been investigated) on PDE and classical/Church-Turing computation -like computability of certain qualitative properties of solutions, and relations between chaos, stability and generalized Church-Turing theses.

Relevant links:

http://mathoverflow.net/questions/15309/simulating-turing-machines-with-o-pdes

http://mathoverflow.net/questions/15292/why-cant-there-be-a-general-theory-of-nonlinear-pde

Questions:

Can you precise slightly the kind of ODE/PDE you have in mind that would yield $2^{-n}$ unit of time computations?

Also, in general I have a hard time figuring what is folklore, what is known to you and a few others, and what you have just discovered. These are important data when trying to learn. So is the present construction yours? When did you come up with it?

If you could indicate when an argument is yours that would be of great ultility. Or are there canonical rules to determine this that I am missing -maybe this question was asked or I should ask on mathoverflow?

I guess it does not look too good repeating “…, my idea”. So when you do not put references I tend to attribute the result to you. I.e. I assume you give references for things that look nontrivial and are not your ideas.

But in the end the phenomenon here is probably one of those irreducible/unavoidable losses of information/entropy increases responsible for the economic crisis we are in and I should just live with it. :)

For instance I find your last post on the limiting absorption principle extremely illuminating (and thank you for it) but it is difficult for me to figure what makes that post so relevant to you now. I understand you are developing a generalization of the limiting absorption principle. Are there other reasons? And why/whence the generalization?
Well I comment profusely just in case this may be useful. Sorry if it is not.

2 May, 2011 at 7:16 am

Terence Tao

One can start with an ODE or PDE that performs each step of a Turing machine calculation in unit time, and then perform a change of variables in the time coordinate (with the new time variable t’ related to the old one t by, say, $t' = 1 - 2^{-t}$ ). This will give a new ODE or PDE (which, admittedly, will not be autonomous, but can be converted to an autonomous one by the usual trick of adding a “clock” variable to the system to keep track of the time variable autonomously).

One can think of an evolutionary ODE or PDE as a kind of (imperative) programming language, except that it is being executed using a continuous time model rather than a discrete time one; each equation one places in the system can be viewed as analogous to a line of instruction in a more traditional programming language.

In general, I would classify most of my commentary on my blog that is not otherwise explicitly attributed to be “folklore” by default. Indeed, making mathematical folklore explicit has always been one of the objectives of this blog.

For the specific idea that PDE and ODE can model just about any computation, I think I picked this up from multiple informal conversations with other differential equations experts (and I think I was also influenced by this this blog post by Alan Rendall on a closely related topic). The Math Overflow threads you cite give more formal references to this idea, though (in particular, Smale seems to have been one of the first mathematicians to prominently push this point of view).

2 May, 2011 at 10:39 am

plm

Thank you.

My poor ODE skills make me slow here but it seems to me there is a problem with taking a nonsurjective change of variables. The resulting ODE, say du/dy=g(u,y) would not have a well-defined RHS for y>1, with y(t)=1-2^{-t}.

So the equation has “a priori” no solution extending past 1, a “singularity”, but solutions may be differentiably continued iff the simulated TM halts/stabilizes/tends to a limit at y=1 (t=\infty). But this does not yield a differential equation with a well-defined RHS that has smooth solutions for all time iff the corresponding TM halts.

However no need to reply. I guess I am probably mistaken, and there must be tons of fancy and insightful constructions in the literature that I should read, before abusing further.

Thank you again.

2 November, 2010 at 1:47 pm

The “no self-defeating object” argument, and the vagueness paradox « What’s new

[…] is the third in a series of posts on the “no self-defeating object” argument in mathematics – a powerful […]

16 December, 2010 at 2:47 pm

Matt C.

All I will say is that Cantor’s results are highly suspect, given that he assumed completed infinity to make the argument. Using reductio ad absurdum means that at least one premise is incorrect. Ridding the idea of a mapping hardly gets rid of paradox. Assuming the results about transfinite ordinals by way of Cantor’s argument, we can see that it defeats itself in relying on the ordering of the list. Getting rid of completed infinity, on the other hand, does eliminate many paradoxes. Infinite sets in extension and completed infinite processes were ridded from mathematics for a very good reason.

“we can, I think, convince ourselves that all the remarkable problems and discoveries of the Foundations of Mathematics, the paradoxes of the theory of aggregates, Russell’s theory of types, with its axiom of reducibility, Cantor’s arithmetic of transfinite numbers, with its insoluble problems such as the ” continuum problem “, the problems connected with functions in extension and the multiplicative axiom- all these merely express in one way or another the well-known difficulties which arise when we attempt to treat an infinite process as completed.”

http://www.jstor.org/stable/2250384

19 February, 2011 at 9:53 am

Finite Sets | Poincare's Paradise

[…] links are link1,link2,link3. By going through these links we can understand how this method has been used in […]

23 July, 2011 at 4:17 pm

Self-Defeating Sentences « Gödel’s Lost Letter and P=NP

[…] that straightforward attempts to prove circuit lower bounds are self-defeating. This suggests the need for new ideas. In a fight-fire-with-fire mood, we hope that exploring the arena of self-defeat will […]

25 August, 2011 at 7:51 am

Itai Bar-Natan

In remark 11 you claim that a consistent axiom system cannot prove it’s own inconsistency. This is incorrect. For example, the system PA+not(Con(PA)) is consistent, because if it isn’t consistent then it is possible to prove in PA the statement Con(PA) (by contradiction). However, not(Con(PA)) implies not(Con( PA+not(Con(PA)) )), so this system disproves it’s own consistency. Note that while in this system it’s possible to prove “There is an n which is a Godel number of a proof of 0=1 in PA”, for any specific n it is possible to prove that “n isn’t a Godel number of a proof of 0=1 in PA”.

25 August, 2011 at 8:03 am

Terence Tao

PA + not(Con(PA)) does not model the standard natural numbers ${\bf N}$ (all its models are nonstandard).

14 September, 2011 at 10:49 am

Varun

Ahh, I had failed to notice that the x in A_x is the same as the one in the set’s membership definition. Thanks.

5 October, 2011 at 2:28 am

Basic logic — relationships between statements — converses and contrapositives « Gowers's Weblog

[…] and from that you proceed to deduce a contradiction: that is, you deduce a statement and its negation. There is an interesting discussion of this difference at Mathoverflow, which also contains a link to a highly recommended blog post of Terence Tao. […]

18 October, 2011 at 12:01 pm

indirect proofs: contrapositives vs. proofs by contradiction « Sebastian Pokutta’s Blog

[…] https://terrytao.wordpress.com/2009/11/05/the-no-self-defeating-object-argument/ Advertisement Eco World Content From Across The Internet. Featured on EcoPressed "Something in the Environment" Share this:DiggRedditFacebookTwitterLike this:LikeBe the first to like this post. […]

20 October, 2011 at 9:14 pm

Doglas

thank you for this interesting article.. have learnt a lot.

23 October, 2011 at 8:17 am

Ray Cheung

About the proof for Theorem 10 (Halting problem):

Why doesn’t the proof show only that it is impossible for Q to exist? If P -> Q, and Q leads to a contradiction, P is impossible – which I suppose is what the proof is. However, it is unclear to me why P -> Q.

If, on the other hand, the proof is supposed to use Q as a counterexample to P’s ability in determining whether a programme halts (for all programmes), one may simply reply that Q is not a (possible) programme.

23 October, 2011 at 8:26 am

Terence Tao

The third and fourth sentences of the proof describe how the existence of a program P that can solve the halting problem implies the existence of a program Q that halts on S iff S(S) does not halt. Because of this implication, the non-existence of the latter program implies the nonexistence of the former program.

23 October, 2011 at 8:21 am

Ray Cheung

Sorry: “P -> Q” reads if P exists, Q exists, etc

20 March, 2012 at 3:47 pm

Carnival of Mathematics #59 « The Number Warrior

[…] Can an omnipotent deity create a rock he can’t lift? Terry Tao tackles mathematical equivalents when considering the “no self-defeating object” argument. […]

20 May, 2012 at 2:58 pm

Heuristic limitations of the circle method « What’s new

[…] be used to conspire against itself (in the spirit of “self-defeating object” arguments, discussed previously several times on this blog). This is actually a fairly common technique in analytic number theory […]

25 August, 2012 at 9:30 am

Trevor Wilson

Dear Professor Tao, I noticed that your proof that the set of countable ordinals is uncountable uses the axiom of choice and in fact proves the stronger statement that omega_1 is regular, for which some some amount of choice is required to prove. But one can prove the original statement in ZF: the set of countable ordinals is itself an ordinal, so if it were countable then it would contain itself as an element.

26 September, 2014 at 4:11 am

My great WordPress blog – Weekend Econlinks

[…] nice recap post of Terry Tao on the “no self-defeating object” argument in mathematical […]

	elegantrium on 254A, Notes 3: The operator no…
	Bharath Ramsundar on 254A, Supplement 6: A cheap ve…
	Avi Levy on 254A, Supplement 6: A cheap ve…
	Terence Tao on 254A, Supplement 6: A cheap ve…
	254A, Supplement 6:… on 254A, Notes 6: Large values of…
	Anonymous on 254A, Supplement 6: A cheap ve…
	arch1 on 254A, Notes 4: Some sieve…
	Anonymous on 254A, Supplement 6: A cheap ve…
	254A, Supplement 6:… on 254A, Notes 7: Linnik’s…
	254A, Supplement 6:… on 254A, Supplement 4: Probabilis…
	254A, Supplement 6:… on 254A, Notes 1: Elementary mult…
	254A, Supplement 6:… on The Katai-Bourgain-Sarnak-Zieg…
	254A, Supplement 6:… on 254A, Notes 2: Complex-analyti…
	Terence Tao on 254A, Notes 7: Linnik’s…
	Anonymous on 254A, Notes 7: Linnik’s…

The “no self-defeating object” argument

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

Google+ feed

The Polymath Blog

Mathematics in Australia

88 comments

Leave a Reply Cancel reply

For commenters

Follow “What's new”

The “no self-defeating object” argument

Share this:

Like this:

Related

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

Google+ feed

The Polymath Blog

Mathematics in Australia

88 comments

Leave a Reply Cancel reply

For commenters

Follow “What's new”