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