A fundamental tool in any mathematician’s toolkit is that of reductio ad absurdum: showing that a statement 
is false by assuming first that 
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 
, by showing that ’s powers are “self-defeating”: the very existence of 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 
which is larger than all other natural numbers.
Proof: Suppose for contradiction that there was such a largest natural number 
. Then 
is also a natural number which is strictly larger than , contradicting the hypothesis that is the largest natural number. 
Note the argument does not apply to the extended natural number system in which one adjoins an additional object 
beyond the natural numbers, because 
is defined equal to 
. 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 , but no matter how much effort is expended in doing so, the player is defeated by the simple response “… plus one!” (unless, of course, 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 
cannot be written as 
for any finite collection 
of natural numbers.
Proof: Suppose for contradiction that such an enumeration 
existed. Then consider the number 
; this is a natural number, but is larger than (and hence not equal to) any of the natural numbers , contradicting the hypothesis that 
is enumerated by 
. 
Here it is the enumeration which is self-defeating, rather than any individual natural number such as 
or 
. (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 
cannot be written as 
for any finite collection of prime numbers.
Proof: Suppose for contradiction that such an enumeration 
existed. Then consider the natural number 
; this is a natural number larger than 
which is not divisible by any of the primes 
. 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 
must be divisible by some prime, contradicting the hypothesis that 
is enumerated by .
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 
implies that the primes anti-correlate almost completely with the multiplicative function 
, which is self-defeating because it also implies complete anti-correlation with 
, 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 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 which contained all sets. Using the axiom schema of specification, one can then construct the set
of all sets in the universe which did not contain themselves. As is universal, 
is contained in . But then, by definition of 
, one sees that 
if and only if 
, a contradiction.
Remark 2 As a corollary, there also does not exist any set 
which contains all other sets (not including itself), because the set 
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 be a set. Then the power set 
of cannot be enumerated by , i.e. one cannot write 
for some collection _%7Bx+%5Cin+X%7D%7D&bg=ffffff&fg=000000&s=0 "{(A_x)_{x \in X}}")
of subsets of .
Proof: Suppose for contradiction that there existed a set whose power set 
could be enumerated as 
for some _%7Bx+%5Cin+X%7D%7D&bg=ffffff&fg=000000&s=0 "{(A_x)_{x \in X}}")
. Using the axiom schema of specification, one can then construct the set
The set is an element of the power set 
. As is enumerated by , we have 
for some 
. But then by the definition of , one sees that 
if and only if 
, a contradiction.
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 
cannot be written as 
for any countable collection 
of real numbers.
Proof: Suppose for contradiction that there existed a countable enumeration of by a sequence 
of real numbers. Consider the decimal expansion of each of these numbers. Note that, due to the well-known “
” issue, the decimal expansion may be non-unique, but each real number 
has at most two decimal expansions. For each 
, let 
be a digit which is not equal to the 
digit of any of the decimal expansions of 
; this is always possible because there are ten digits to choose from and at most two decimal expansions of 
. (One can avoid any implicit invocation of the axiom of choice here by setting 
to be (say) the least digit which is not equal to the 
digit of any of the decimal expansions of .) Then the real number given by the decimal expansion 
differs in the digit from any of the decimal expansions of for each 
, and so is distinct from every , a contradiction.
Remark 3 One can of course deduce Proposition 6 directly from Proposition 5, by using the decimal representation to embed 
into 
. 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 
which consists precisely of all the ordinals and nothing else. But then 
is an ordinal which is not contained in 
(by the axiom of foundation, also known as the axiom of regularity), a contradiction.
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 
. But one can simply adjoin an additional element not already in 
(e.g. 
) to , 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 
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 
of the countable ordinals. Then the set 
is also a countable ordinal, as is the set 
. But 
is not equal to any of the 
(by the axiom of foundation), a contradiction. 
Remark 8 With the axiom of choice, one can show the existence of uncountable ordinals (e.g. by well-ordering the reals), and then there exists a least uncountable ordinal . By construction, this ordinal consists precisely of all the countable ordinals, but is itself uncountable, much as 
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 
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]}](http://s1.wordpress.com/latex.php?latex=%7B%5B0,1%5D%7D&bg=ffffff&fg=000000&s=0 "{[0,1]}")
will ever be enumerated by this procedure. (Also, the question of whether all real numbers in ![{[0,1]}](http://s2.wordpress.com/latex.php?latex=%7B%5B0,1%5D%7D&bg=ffffff&fg=000000&s=0 "{[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 
, which have a single truth value, but instead with predicates 
, whose truth value depends on a variable 
in some range. For instance, may be “
is thirty-two characters long.”, and the range of may be the set of strings (i.e. finite sequences of characters); then for every string 
, the statement %7D&bg=ffffff&fg=000000&s=0 "{S(T)}")
(formed by replacing every appearance of in with 
) is either true or false. For instance, %7D&bg=ffffff&fg=000000&s=0 "{S(``a'')}")
is true, but %7D&bg=ffffff&fg=000000&s=0 "{S(``ab'')}")
is false. Crucially, predicates are themselves strings, and can thus be fed into themselves as input; for instance, %7D&bg=ffffff&fg=000000&s=0 "{S(S)}")
is false. If however 
is the predicate “
is sixty-five characters long.”, observe that %7D&bg=ffffff&fg=000000&s=0 "{U(U)}")
is true.
Now consider the Quine predicate 
given by
“ is a predicate whose range is the set of strings, and %7D&bg=ffffff&fg=000000&s=0 "{x(x)}")
is false.”
whose range is the set of strings. Thus, for any string 
, %7D&bg=ffffff&fg=000000&s=0 "{Q(T)}")
is the sentence
“ is a predicate whose range is the set of strings, and %7D&bg=ffffff&fg=000000&s=0 "{T(T)}")
is false.”
This predicate is defined non-recursively, but the sentence %7D&bg=ffffff&fg=000000&s=0 "{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 %7D&bg=ffffff&fg=000000&s=0 "{T(x)}")
with the set +%5Chbox%7B+true%7D+%5C%7D%7D&bg=ffffff&fg=000000&s=0 "{\{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 
be the predicate given by
“ is a predicate whose range is the set of strings, and %7D&bg=ffffff&fg=000000&s=0 "{x(x)}")
is not provable”
and whose range is the set of strings. Define the Gödel sentence 
to be the string %7D&bg=ffffff&fg=000000&s=0 "{G := Q(Q)}")
. Then 
is logically equivalent to the assertion “ is not provable”. Thus, if 
were false, then would be provable, which (by the consistency of the system) implies that is true, a contradiction; thus, 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 must be true; thus is provable and 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!)
Remark 11 It is not hard to show that a consistent logical system cannot disprove its own consistency either; thus the consistency of such a system is undecidable within that system. Thus this theorem strengthens the (more well known) first Gödel incompleteness theory, 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 
which takes a string as input, and determines in finite time whether 
is a program (with no input) that halts in finite time.
Proof: Suppose for contradiction that such a program existed. Then one could easily modify 
to create a variant program , which takes a string as input, and halts if and only if is a program (with itself as input) that does not halts in finite time. Indeed, all has to do is call with the string %7D&bg=ffffff&fg=000000&s=0 "{S(S)}")
, defined as the program (with no input) formed by declaring to be the input string for the program . If 
determines that %7D&bg=ffffff&fg=000000&s=0 "{S(S)}")
does not halt, then 
halts; otherwise, if determines that does halt, then performs an infinite loop and does not halt. Then observe that %7D&bg=ffffff&fg=000000&s=0 "{Q(Q)}")
will halt if and only if it does not halt, a contradiction.
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 , when run as a program, halts in finite time, simply by searching for all proofs or disproofs of the statement “ 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).
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 
computable if there exists a computer program which, when given a natural number 
as input, returns %7D&bg=ffffff&fg=000000&s=0 "{f(n)}")
as output in finite time. Define the Busy Beaver function 
by setting %7D&bg=ffffff&fg=000000&s=0 "{BB(n)}")
to equal the largest output of any program of at most characters in length (and taking no input), which halts in finite time. Note that there are only finitely many such programs for any given , so is well-defined. On the other hand, it is uncomputable, even to upper bound:
Proposition 11 There does not exist a computable function 
such that one has +%5Cleq+f(n)%7D&bg=ffffff&fg=000000&s=0 "{BB(n) \leq f(n)}")
for all .
Proof: Suppose for contradiction that there existed a computable function such that for all . 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 , the run time of any halting program of length at most can also be upper bounded by a computable function. This is because if a program of length halts in finite time, then a trivial modification of that program (of length larger than , 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 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 , given by the length of . If the program has not halted by then, then it never will. This provides a program obeying the hypotheses of the halting theorem, a contradiction.
Remark 17 A variant of the argument shows that %7D&bg=ffffff&fg=000000&s=0 "{BB(n)}")
grows faster than any computable function: thus if 
is computable, then +%3E+f(n)%7D&bg=ffffff&fg=000000&s=0 "{BB(n) > f(n)}")
for all sufficiently large . 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 
problem, does not seem to be susceptible to the no-self-defeating-object argument, basically because such arguments tend to be relativisable whereas the 
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 
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 could be used to disprove the existence of an object closely related to the belief that , 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, 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 
. 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 
accordingly. Note that occasionally, the 
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 could lead to a draw as well, a contradiction.) If we denote this stolen strategy by 
, then 
guarantees a win for the naughts player; playing the 
strategy for the naughts player against the strategy for the crosses player, we obtain a contradiction.
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 -dimensional game of naughts and crosses is unable to end in a draw if 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 
in one inertial reference frame, then by the principle of relativity it should be possible to construct an object 
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 
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).
Posted in expository, math.LO Tagged: cantor's theorem, godel incompleteness theorem, halting problem
Alexey Petrov
&bg=ffffff&fg=000000&s=0 "GL_n(\mathbb{F}_q)")
have zeroes in all diagonal entries?![(q-1)^n \sum_{k=0}^n (-1)^k \frac{[n]!}{[k]!}](http://s1.wordpress.com/latex.php?latex=(q-1)%5En+%5Csum_%7Bk=0%7D%5En+(-1)%5Ek+%5Cfrac%7B%5Bn%5D!%7D%7B%5Bk%5D!%7D&bg=ffffff&fg=000000&s=0 "(q-1)^n \sum_{k=0}^n (-1)^k \frac{[n]!}{[k]!}")
doesn’t seem to work for n > 2.
just isn’t the same as the geometry of 
, but a continuous model would be very difficult to design and simulate (or would it?). But perhaps there could be some cleverly chosen simple rule that would tend to protect “clumps” of 1s and allow them to move, and to do complicated things like rotating (whatever that can be made to mean in 
). Or perhaps a complicated ecosystem could develop that was more 
, and put a 1 at every grid point that lies in the annulus. Then in the interior circle of the annulus put a random scattering of not too many 1s. And then slightly move the annulus part, and slightly move all the little particles inside. If the first position of the annulus represents where some very simple structure is at time 1 and the second where it is at time 2, then conservation of mass and momentum would tell us to expect it to continue moving in the same direction (so it would be more sophisticated than a cellular automaton of the kind described earlier because its behaviour would depend not just on how it behaved an instant earlier), and to stay the same size. We might also have “forces” between neighbouring 1s that encouraged them to stay together somewhat, and so on.
be a countable model of a language extending the language of groups, with a universal extension 
be a continuous, invariant Keisler measure that is also invariant under translations. Let +=+1%7D&bg=ffffff&fg=000000&s=0 "{\mu(X) = 1}")
and %7D&bg=ffffff&fg=000000&s=0 "{\mu(X \cdot X)}")
finite, and let 
be the group generated by 
be a wide type over 
contained in %7D&bg=ffffff&fg=000000&s=0 "{a \in q(G)}")
, there exists %7D&bg=ffffff&fg=000000&s=0 "{b \in q(G)}")
such that %7D&bg=ffffff&fg=000000&s=0 "{tp(a/M \cup \{b\})}")
and %7D&bg=ffffff&fg=000000&s=0 "{tp(b/M \cup \{a\})}")
are both wide. 
is a normal subgroup of 
. 
and 
seems to be a statement that there exist plenty of pairs %7D&bg=ffffff&fg=000000&s=0 "{(a,b)}")
in %7D&bg=ffffff&fg=000000&s=0 "{q(G)}")
that are in “general position” somehow. In the case of abelian groups, it seems that this hypothesis not necessary. The hypothesis is for all %7D&bg=ffffff&fg=000000&s=0 "{a \in q(G)}")
, but by homogeneity it suffices to verify it for a single 
(since the action of the automorphism group of %7D&bg=ffffff&fg=000000&s=0 "{q(G)}")
). 
is wide, 
has finite measure, this leads to the consequence that the index of 
in cardinality (i.e. has bounded index, see Lemma 1 of 
disjoint cosets 
in 
, and hence in some finite product 
. By Section 4 of 
-definable, and so is the intersection of countably many definable sets 
. For any distinct 
, 
are disjoint, thus by saturation we have %7D+a_i+%5Ccap+S_%7Bn(i,j)%7D+a_j%7D&bg=ffffff&fg=000000&s=0 "{S_{n(i,j)} a_i \cap S_{n(i,j)} a_j}")
non-empty for some integer %7D&bg=ffffff&fg=000000&s=0 "{n(i,j)}")
. By the 
in which the +=+n%7D&bg=ffffff&fg=000000&s=0 "{n(i,j) = n}")
are constant, thus we have a countable set of disjoint translates 
, which live in some finite product 
. But as 
has positive measure, while 
-definable subgroup of 
and the group is the integers; we normalise 
. Taking ultralimits, we end up with a non-standard discrete interval 
in the non-standard integers, with 
being the counting measure normalised to give 
are definable for any standard natural number 
. Their intersection 
is a wide subgroup; if 
would generate 
be a definable set of positive measure. Then we can refine 
to a wide type 
such that for every 
is covered by two definable sets 
(these are sets of pairs, of course). Then one can refine 
of positive measure, such that at least one of the following holds: 
, the set +%5Cin+C+%5C%7D%7D&bg=ffffff&fg=000000&s=0 "{C_a := \{ b: (a,b) \in C \}}")
has positive measure; or 
, the set +%5Cin+D+%5C%7D%7D&bg=ffffff&fg=000000&s=0 "{D^b := \{ a: (a,b) \in D \}}")
has positive measure.
to be contained in =0%7D&bg=ffffff&fg=000000&s=0 "{\mu(C)=0}")
. We can find a definable set 
between +%3E+1/n+%5C%7D%7D&bg=ffffff&fg=000000&s=0 "{\{ a: \mu(C_a) > 1/n \}}")
and +%5Cgeq+1/n+%5C%7D%7D&bg=ffffff&fg=000000&s=0 "{\{ a: \mu(C_a) \geq 1/n \}}")
. If any of these 
, so we may assume instead that =0%7D&bg=ffffff&fg=000000&s=0 "{\mu(Q_n)=0}")
for all +=+0%7D&bg=ffffff&fg=000000&s=0 "{\mu(C) = 0}")
by Fubini’s theorem (which can be extended to Kiesler measures, at least in the weak form we need here), giving the desired contradiction. 
and refining repeatedly using Lemma 
, so that each pair is revisited infinitely often) one can find a type %7D&bg=ffffff&fg=000000&s=0 "{q({\Bbb U})}")
, and 
is covered by two definable sets 
has positive measure for all 
, or 
has positive measure for all 
. In particular (setting 
and 
empty) this implies that %7D&bg=ffffff&fg=000000&s=0 "{a \in q({\Bbb U})}")
, and define 
to be the type 
for definable 
with =0%7D&bg=ffffff&fg=000000&s=0 "{\mu(C_a)=0}")
, and the complement of the sets of the form 
for definable =0%7D&bg=ffffff&fg=000000&s=0 "{\mu(D^a)=0}")
(note the asymmetry here!). We claim that this collection of sentences is still finitely satisfiable. Indeed, if this were not the case, 
for some definable 
with =%5Cmu(D%5Ea)=0%7D&bg=ffffff&fg=000000&s=0 "{\mu(C_a)=\mu(D^a)=0}")
. Write 
, then the set 
is definable and contains 
, we thus see that 
is a definable set containing 
, contradicting the construction of 
.
over 
, but by construction %7D&bg=ffffff&fg=000000&s=0 "{q_a({\Bbb U})}")
and hence %7D&bg=ffffff&fg=000000&s=0 "{q'_a({\Bbb U})}")
is contained in the complement of %7D&bg=ffffff&fg=000000&s=0 "{tp(a/M \cup \{b\})}")
is wide. For if not, then 
of measure zero for some definable 
and 
has measure zero also, and so 
is contained in the complement of 
by construction. In particular, 
lying in 
. This proves Lemma 
be positive integers. Then for 
sufficiently close to 
is a finite subset of a group 
, where 
, and for a proportion at least 
-tuples +%5Cin+(X+%5Ccdot+X)%5El%7D&bg=ffffff&fg=000000&s=0 "{(a_1,\ldots,a_l) \in (X \cdot X)^l}")
, one has 
(recall that 
). Then there exists a subgroup 
such that 
is contained in at most %7D&bg=ffffff&fg=000000&s=0 "{k(m+1)}")
cosets of 
from 
rather than 
, then one can find a sequence of groups 
of tripling uniformly bounded by 
, such that the proportion of 
-tuples %7D&bg=ffffff&fg=000000&s=0 "{(a_1,\ldots,a_l)}")
in %5El%7D&bg=ffffff&fg=000000&s=0 "{(X \cdot X)^l}")
with 
approaches %7D&bg=ffffff&fg=000000&s=0 "{k(m+1)}")
cosets.
+=+1%7D&bg=ffffff&fg=000000&s=0 "{\mu(X) = 1}")
, +%5Cleq+k+%5Cmu(X_0)%7D&bg=ffffff&fg=000000&s=0 "{\mu(X_0 X X) \leq k \mu(X_0)}")
, and such that the set +%5Cin+(X+%5Ccdot+X)%5El:+%5Cmu(+a_1%5EX+%5Cldots+a_l%5EX+)+%5Cgeq+%5Cmu(X)/(m+0.5)+%5C%7D%7D&bg=ffffff&fg=000000&s=0 "{Q := \{ (a_1,\ldots,a_l) \in (X \cdot X)^l: \mu( a_1^X \ldots a_l^X ) \geq \mu(X)/(m+0.5) \}}")
(say) has measure %5El%7D&bg=ffffff&fg=000000&s=0 "{\mu(X \cdot X)^l}")
. (Strictly speaking, one has to replace +%5Cgeq+%5Cmu(X)/(m+1)%7D&bg=ffffff&fg=000000&s=0 "{\mu( a_1^X \ldots a_l^X ) \geq \mu(X)/(m+1)}")
by a definable predicate between +%5Cgeq+%5Cmu(X)/(m+1)%7D&bg=ffffff&fg=000000&s=0 "{\mu( a_1^X \ldots a_l^X ) \geq \mu(X)/(m+1)}")
and +%3E+%5Cmu(X)/(m+1)%7D&bg=ffffff&fg=000000&s=0 "{\mu( a_1^X \ldots a_l^X ) > \mu(X)/(m+1)}")
, but let’s ignore this technicality.) We then extend 
, in fact), so by Lemma 
is a group. Note that this set is contained in 
, which have positive measure as %5El%7D&bg=ffffff&fg=000000&s=0 "{(X \cdot X)^l}")
, we see that 
for every 
. In particular, there exists 
in +%5Cgeq+%5Cmu(X)/(m+1).&bg=ffffff&fg=000000&s=0 "\displaystyle \mu( a_1^X \ldots a_l^X ) \geq \mu(X)/(m+1).")
lies in +(m+1)+/+%5Cmu(X)+%5Cleq+k(m+1)%7D&bg=ffffff&fg=000000&s=0 "{\mu(X_0 X X) (m+1) / \mu(X) \leq k(m+1)}")
disjoint translates 
, 
. As a consequence, 
can be covered by %5E4%7D&bg=ffffff&fg=000000&s=0 "{k^4 (m+1)^4}")
such translates, including 
-definable (it is the complement of all the other cosets in 
-definable and 
-definable has to be definable. (Proof: we can write 
. By saturation, 
must be empty for at least one 
)
) must intersect if they are sufficiently “generic”; the notion of a wide type is designed, in part, to capture this notion of genericity.
of a language 
, and then consider a universal elementary extension 
of 
is a set of formulae (with 
-definable sets; if 
is a type and 
, then either 
lies in 
) or 
lies in 
) but not both.
is small (i.e. has cardinality less than that of 
, which in particular would be true of %7D&bg=ffffff&fg=000000&s=0 "{p({\Bbb U})}")
of 
that they cut out. In particular, these sets are non-empty. Adding more formulae to a partial type corresponds to shrinking the set that they cut out, and vice versa.
– a type defined over the entire model %7D&bg=ffffff&fg=000000&s=0 "{p({\Bbb U})}")
that they cut out, because these sets are usually empty! However, what we can do is restrict 
over 
.
of 
and 
, we see that 
if and only if %7D%7D&bg=ffffff&fg=000000&s=0 "{p \subset A_{\sigma(b)}}")
, where +%5Cin+A+%5C%7D%7D&bg=ffffff&fg=000000&s=0 "{A_b := \{ a \in {\Bbb U}^n: (a,b) \in A \}}")
is a slice of 
(or in 
). This cuts out a singleton set 
. This is in fact the only invariant global type that cuts out anything at all:
(i.e. %7D&bg=ffffff&fg=000000&s=0 "{p({\Bbb U})}")
is non-empty) if and only if it is realisable in %7D&bg=ffffff&fg=000000&s=0 "{a \in p({\Bbb U})}")
. Since the formula 
is definable in 
, i.e. 
. As 
must then be invariant under all %7D&bg=ffffff&fg=000000&s=0 "{tp(a/M)}")
of 
together with the formulae in %7D&bg=ffffff&fg=000000&s=0 "{tp(a/M)}")
is not satisfiable, hence not finitely satisfiable. Thus there is a finite set of formulae in %7D&bg=ffffff&fg=000000&s=0 "{tp(a/M)}")
that cut out 
is definable over 
carefully; the set +%5Csubset+B(%7B%5CBbb+U%7D')%7D&bg=ffffff&fg=000000&s=0 "{p({\Bbb U}') \subset B({\Bbb U}')}")
holds in all extensions 
of 
by adding in the negations of all the formulae definable over %7D&bg=ffffff&fg=000000&s=0 "{\sigma(\phi)}")
is not in %7D&bg=ffffff&fg=000000&s=0 "{\neg \sigma(\phi)}")
must be in %7D&bg=ffffff&fg=000000&s=0 "{\phi \wedge \neg \sigma(\phi)}")
is in 
fixes %7D&bg=ffffff&fg=000000&s=0 "{\sigma(\phi)}")
does lie in 
, and construct recursively a sequence 
by requiring %7D&bg=ffffff&fg=000000&s=0 "{b_n \in p\downharpoonright_{M \cup \{b_1,\ldots,b_{n-1}\}}({\Bbb U})}")
for all 
. (This is always possible since types are satisfiable once restricted to small sets, by saturation, as discussed earlier). Then 
are indiscernible over %7D&bg=ffffff&fg=000000&s=0 "{(b_{i_1},\ldots,b_{i_k})}")
for 
are elementarily indistinguishable (over 
. 
case is clear since the 
all have type 
over 
case. It suffices to show that %7D&bg=ffffff&fg=000000&s=0 "{(b_1,b_2)}")
and %7D&bg=ffffff&fg=000000&s=0 "{(b_i,b_j)}")
are elementarily indistinguishable over 
.
and 
have the same type over 
, and so %7D&bg=ffffff&fg=000000&s=0 "{(b_1,b_2)}")
and %7D&bg=ffffff&fg=000000&s=0 "{(b_1,b_j)}")
are elementarily indistinguishable over %7D&bg=ffffff&fg=000000&s=0 "{(b_1,b_j)}")
and %7D&bg=ffffff&fg=000000&s=0 "{(b_i,b_j)}")
are elementarily indistinguishable.
and 
have the same type over 
of 
realises 
, we see that +%5Cin+A%7D&bg=ffffff&fg=000000&s=0 "{(b_1,x) \in A}")
, hence by invariance +%5Cin+A%7D&bg=ffffff&fg=000000&s=0 "{(b_i,x) \in A}")
also. Since 
, we conclude +%5Cin+A%7D&bg=ffffff&fg=000000&s=0 "{(b_i,b_j) \in A}")
, as required.
case. The higher 
for some set of constants 
be a sequence of indiscernibles (over 
in this sequence, one can find a type 
such that 
has the same type over 
as 
, for all 
. 
be types over %7D&bg=ffffff&fg=000000&s=0 "{a,a' \in p({\Bbb U})}")
, %7D&bg=ffffff&fg=000000&s=0 "{b,b' \in q({\Bbb U})}")
be realisations of 
such that %7D&bg=ffffff&fg=000000&s=0 "{tp(a'/M \cup \{b'\})}")
are wide. Let 
, 
be +%3E+0%7D&bg=ffffff&fg=000000&s=0 "{\mu(A_a \cap B_b) > 0}")
if and only if +%3E+0%7D&bg=ffffff&fg=000000&s=0 "{\mu(A_{a'} \cap B_{b'}) > 0}")
. 
, and maps 
.
+%3E+%5Cdelta+%3E+0%7D&bg=ffffff&fg=000000&s=0 "{\mu(A_a \cap B_b) > \delta > 0}")
and +=+0%7D&bg=ffffff&fg=000000&s=0 "{\mu(A_{a'} \cap B_{b'}) = 0}")
.
. Observe that for any 
, either one has +%5Cgeq+%5Cepsilon%7D&bg=ffffff&fg=000000&s=0 "{\mu(A_a \cap B_x) \geq \epsilon}")
for all 
, or one has +%5Cleq+%5Cepsilon%7D&bg=ffffff&fg=000000&s=0 "{\mu(A_a \cap B_x) \leq \epsilon}")
for all 
(since there is a 
-definable set between +%5Cgeq+%5Cepsilon+%5C%7D%7D&bg=ffffff&fg=000000&s=0 "{\{ x: \mu(A_a \cap B_x) \geq \epsilon \}}")
and +%3E+%5Cepsilon+%5C%7D%7D&bg=ffffff&fg=000000&s=0 "{\{ x: \mu(A_a \cap B_x) > \epsilon \}}")
. Suppose first that the former option holds for some 
, thus there is a uniform lower bound +%3E+%5Cepsilon%7D&bg=ffffff&fg=000000&s=0 "{\mu(A_a \cap B_x) > \epsilon}")
. We now define a sequence %7D&bg=ffffff&fg=000000&s=0 "{a_1,a_2,\ldots \in p({\Bbb U})}")
and an indiscernible sequence %7D&bg=ffffff&fg=000000&s=0 "{b_1,b_2,\ldots \in q({\Bbb U})}")
as follows:
and 
to be a realisation of 
. 
have been chosen with 
indiscernible. By Lemma %7D&bg=ffffff&fg=000000&s=0 "{a_{n+1} \in p({\Bbb U})}")
that has the same type over 
for all 
. Since +=+0%7D&bg=ffffff&fg=000000&s=0 "{\mu(A_{a'} \cap B_{b'}) = 0}")
, this implies that +=+0%7D&bg=ffffff&fg=000000&s=0 "{\mu( A_{a_{n+1}} \cap B_{b_i} ) = 0}")
for all =0%7D&bg=ffffff&fg=000000&s=0 "{\mu( A_x \cap B_b )=0}")
is a type-definable formula over 
be a realisation of 
. With this construction and Lemma 
is also indiscernible; now we iterate the procedure.
be the set 
, then observe from the above construction that 
lies in +=+0%7D&bg=ffffff&fg=000000&s=0 "{\mu(C_i \cap C_j) = 0}")
for all %7D&bg=ffffff&fg=000000&s=0 "{\mu(C_i)}")
is uniformly bounded away from zero, this contradicts the finite measure of %7D&bg=ffffff&fg=000000&s=0 "{\mu(X)}")
by the pigeonhole principle.
fixing 
. By hypothesis, +%3E+0%7D&bg=ffffff&fg=000000&s=0 "{\mu(A_{a_1} \cap B_{b_1}) > 0}")
, thus there exists a rational 
such that the predicate that models +%3E+r%7D&bg=ffffff&fg=000000&s=0 "{\mu(A_{a_1} \cap B_x) > r}")
is in 
, hence in +%3E+r%7D&bg=ffffff&fg=000000&s=0 "{\mu(A_{a_i} \cap B_x) > r}")
is in +%3E+r%7D&bg=ffffff&fg=000000&s=0 "{\mu(A_{a_i} \cap B_{b_i}) > r}")
, and the claim follows.
+=+0%7D&bg=ffffff&fg=000000&s=0 "{\mu(A_a \cap B_x) = 0}")
for all 
to be a realisation of 
, then set %7D&bg=ffffff&fg=000000&s=0 "{a_n \in p({\Bbb U})}")
so that +%3E+%5Cdelta%7D&bg=ffffff&fg=000000&s=0 "{\mu(A_{a_n} \cap B_{b_n}) > \delta}")
. (This is possible because for any definable set +%5Cgeq+%5Cdelta+%5C%7D%7D&bg=ffffff&fg=000000&s=0 "{\{ x \in C: \mu(A_x \cap B_b) \geq \delta \}}")
contains 
lie in 
be types in 
such that 
has finite measure. Let 
be such that the type of 
is wide. Assume also that the Keisler measure is translation-invariant. Then 
is also wide. 
has zero measure. (Initially, one would need two different definable sets containing %7D&bg=ffffff&fg=000000&s=0 "{a_1, a_2, \ldots \in q({\Bbb U})}")
with %7D&bg=ffffff&fg=000000&s=0 "{tp(a_n/M \cup \{a_1,\ldots,a_{n-1}\})}")
wide for all +=+0%7D&bg=ffffff&fg=000000&s=0 "{\mu(Aa \cap Ab) = 0}")
, we conclude from Lemma =0%7D&bg=ffffff&fg=000000&s=0 "{\mu(A a_n \cap A a_i)=0}")
for all 
. On the other hand, the %7D&bg=ffffff&fg=000000&s=0 "{\mu(Aa_i)}")
all have the same measure as %7D&bg=ffffff&fg=000000&s=0 "{\mu(A)}")
, which is positive. Finally, the 
are all contained in 
, which has finite measure; this leads to a contradictoin. 
+&bg=ffffff&fg=000000&s=0 "\displaystyle \hbox{det} \begin{pmatrix} 1 & x_1 & \ldots & x_1^{n-1} \\ 1 & x_2 & \ldots & x_2^{n-1} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & \ldots & x_n^{n-1} \end{pmatrix} = \prod_{1 \leq i < j \leq n} (x_j - x_i)")
