[PDF] taos
[PDF] tapis de course à pied letix speedrunner pro
[PDF] tapis de course à pied pliable
[PDF] tapis de course ou vélo
[PDF] tapis de course ou vélo d'appartement pour maigrir
[PDF] tapis de course ou vélo elliptique
[PDF] tapis de course pied nu ou basket
[PDF] tardiness and lying are early stage behaviors that indicate a workers possible alcoholism
[PDF] tardive dyskinesia
[PDF] target credit card breach
[PDF] target data breach 2013 case study
[PDF] target data breach 2018
[PDF] target donation request form pdf
[PDF] target market for 24 hour fitness
[PDF] target market health and fitness
Compactness and contradiction
Terence Tao
Department of Mathematics, UCLA, Los Angeles, CA 90095
E-mail address:tao@math.ucla.edu
To Garth Gaudry, who set me on the road;
To my family, for their constant support;
And to the readers of my blog, for their feedback and contributions.
Contents
Preface xi
A remark on notation xi
Acknowledgments xii
Chapter 1. Logic and foundations 1
x1.1. Material implication 1 x1.2. Errors in mathematical proofs 2 x1.3. Mathematical strength 4 x1.4. Stable implications 6 x1.5. Notational conventions 8 x1.6. Abstraction 9 x1.7. Circular arguments 11 x1.8. The classical number systems 12 x1.9. Round numbers 15 x1.10. The \no self-defeating object" argument, revisited 16 x1.11. The \no self-defeating object" argument, and the vagueness paradox 28 x1.12. A computational perspective on set theory 35
Chapter 2. Group theory 51
x2.1. Torsors 51 x2.2. Active and passive transformations 54 x2.3. Cayley graphs and the geometry of groups 56 x2.4. Group extensions 62vii viiiContentsx2.5. A proof of Gromov's theorem 69
Chapter 3. Analysis 79
x3.1. Orders of magnitude, and tropical geometry 79 x3.2. Descriptive set theory vs. Lebesgue set theory 81 x3.3. Complex analysis vs. real analysis 82 x3.4. Sharp inequalities 85 x3.5. Implied constants and asymptotic notation 87 x3.6. Brownian snow akes 88 x3.7. The Euler-Maclaurin formula, Bernoulli numbers, the zeta function, and real-variable analytic continuation 88 x3.8. Finitary consequences of the invariant subspace problem 104 x3.9. The Guth-Katz result on the Erd}os distance problem 110 x3.10. The Bourgain-Guth method for proving restriction theorems 123
Chapter 4. Nonstandard analysis 133
x4.1. Real numbers, nonstandard real numbers, and nite precision arithmetic 133 x4.2. Nonstandard analysis as algebraic analysis 135 x4.3. Compactness and contradiction: the correspondence principle in ergodic theory 137 x4.4. Nonstandard analysis as a completion of standard analysis 150 x4.5. Concentration compactness via nonstandard analysis 167
Chapter 5. Partial dierential equations 181
x5.1. Quasilinear well-posedness 181 x5.2. A type diagram for function spaces 189 x5.3. Amplitude-frequency dynamics for semilinear dispersive equations 194 x5.4. The Euler-Arnold equation 203
Chapter 6. Miscellaneous 217
x6.1. Multiplicity of perspective 218 x6.2. Memorisation vs. derivation 220 x6.3. Coordinates 223 x6.4. Spatial scales 227 x6.5. Averaging 229 x6.6. What colour is the sun? 231 Contentsixx6.7. Zeno's paradoxes and induction 233 x6.8. Jevons' paradox 234 x6.9. Bayesian probability 237 x6.10. Best, worst, and average-case analysis 242 x6.11. Duality 245 x6.12. Open and closed conditions 247
Bibliography 249
Index 255
Preface
In February of 2007, I converted my \What's new" web page of research updates into a blog atterrytao.wordpress.com. This blog has since grown and evolved to cover a wide variety of mathematical topics, ranging from my own research updates, to lectures and guest posts by other mathematicians, to open problems, to class lecture notes, to expository articles at both basic and advanced levels. In 2010, I also started writing shorter mathematical articles on my Google Buzz feed at This book collects some selected articles from both my blog and my Buzz feed from 2010, continuing a series of previous books [Ta2008], [Ta2009], [Ta2009b], [Ta2010], [Ta2010b], [Ta2011], [Ta2011b], [Ta2011c] based on the blog. The articles here are only loosely connected to each other, although many of them share common themes (such as the titular use ofcompactness and contradictionto connect nitary and innitary mathematics to each other). I have grouped them loosely by the general area of mathematics they pertain to, although the dividing lines between these areas is somewhat blurry, and some articles arguably span more than one category. Each chapter is roughly organised in increasing order of length and complexity (in particular, the rst half of each chapter is mostly devoted to the shorter articles from my Buzz feed, with the second half comprising the longer articles from my blog.
A remark on notation
For reasons of space, we will not be able to dene every single mathematical term that we use in this book. If a term is italicised for reasons other thanxi xiiPrefaceemphasis or for denition, then it denotes a standard mathematical object, result, or concept, which can be easily looked up in any number of references. (In the blog version of the book, many of these terms were linked to their Wikipedia pages, or other on-line reference pages.) I will however mention a few notational conventions that I will use throughout. The cardinality of a nite setEwill be denotedjEj. We will use the asymptotic notationX=O(Y),XY, orYXto denote the estimatejXj CYfor some absolute constantC >0. In some cases we will need this constantCto depend on a parameter (e.g.d), in which case we shall indicate this dependence by subscripts, e.g.X=Od(Y) or
XdY. We also sometimes useXYas a synonym forXYX.
In many situations there will be a large parameternthat goes o to innity. When that occurs, we also use the notationon!1(X) or simply o(X) to denote any quantity bounded in magnitude byc(n)X, wherec(n) is a function depending only onnthat goes to zero asngoes to innity. If we needc(n) to depend on another parameter, e.g.d, we indicate this by further subscripts, e.g.on!1;d(X). Asymptotic notation is discussed further in Section 3.5. We will occasionally use the averaging notationEx2Xf(x) :=1jXjP x2Xf(x) to denote the average value of a functionf:X!Con a non-empty nite setX. IfEis a subset of a domainX, we use 1E:X!Rto denote the indicator functionofX, thus 1E(x) equals 1 whenx2Eand 0 otherwise.
Acknowledgments
I am greatly indebted to many readers of my blog and buzz feed, includ- ing Dan Christensen, David Coreld, Quinn Culver, Tim Gowers, Greg Graviton, Zaher Hani, Bryan Jacobs, Bo Jacoby, Sune Kristian Jakobsen, Allen Knutson, Ulrich Kohlenbach, Mark Meckes, David Milovich, Timothy Nguyen, Michael Nielsen, Anthony Quas, Pedro Lauridsen Ribeiro, Jason Rute, Americo Tavares, Willie Wong, Qiaochu Yuan, Pavel Zorin, and sev- eral anonymous commenters, for corrections and other comments, which can be viewed online at terrytao.wordpress.com The author is supported by a grant from the MacArthur Foundation, by NSF grant DMS-0649473, and by the NSF Waterman award.
Chapter 1
Logic and foundations
1.1. Material implication
Thematerial implication\IfA, thenB" (or \AimpliesB") can be thought of as the assertion \Bisat least as true asA" (or equivalently, \Aisat most as true asB"). This perspective sheds light on several facts about the material implication: (1)A falsehood implies anything(theprinciple of explosion). Indeed, any statementBis at least as true as a falsehood. By the same token, if the hypothesis of an implication fails, this reveals nothing about the conclusion. (2)Anything implies a truth. In particular, if the conclusion of an implication is true, this reveals nothing about the hypothesis. (3)Proofs by contradiction. IfAis at most as true as a falsehood, then it is false. (4)Taking contrapositives. IfBis at least as true asA, thenAis at least as false asB. (5)\If and only if" is the same as logical equivalence. \Aif and only ifB" means thatAandBareequally true. (6)Disjunction elimination. Given \IfA, thenC" and \IfB, thenC", we can deduce \If (AorB), thenC", since ifCis at least as true asA, and at least as true asB, then it is at least as true as either AorB. (7)The principle of mathematical induction. IfP(0) is true, and each P(n+ 1) is at least as true asP(n), then all of theP(n) are true. (Note, though, that if one is only 99% certain of each implication1
21. Logic and foundations\P(n) impliesP(n+ 1)", then the chain of deductions can break
down fairly quickly. It is thus dangerous to apply mathematical in- duction outside of rigorous mathematical settings. See also Section
6.9 for further discussion.)
(8)Material implication is not causal. The material implication \IsA, thenB" is a statement purely about the truth values ofAandB, and can hold even if there is no causal link betweenAandB. (e.g. \If 1 + 1 = 2, then Fermat's last theorem is true.".)
1.2. Errors in mathematical proofs
Formally, a mathematical proof consists of a sequence of mathematical state- ments and deductions (e.g. \IfA, thenB"), strung together in a logical fashion to create a conclusion. A simple example of this is a linear chain of deductions, such asA=)B=)C=)D=)E, to create the con- clusionA=)E. In practice, though, proofs tend to be more complicated than a linear chain, often acquiring a tree-like structure (or more generally, the structure of a directed acyclic graph), due to the need to branch into cases, or to reuse a hypothesis multiple times. Proof methods such as proof by contradiction, or proof by induction, can lead to even more intricate loops and reversals in a mathematical argument. Unfortunately, not all proposed proofs of a statement in mathematics are actually correct, and so some eort needs to be put into verication of such a proposed proof. Broadly speaking, there are two ways that one can show that a proof can fail. Firstly, one can nd a \local", \low-level" or \direct" objection to the proof, by showing that one of the steps (or perhaps a cluster of steps, see below) in the proof is invalid. For instance, if the implication C=)Dis false, then the above proposed proofA=)B=)C=) D=)EofA=)Eis invalid (though it is of course still conceivable thatA=)Ecould be proven by some other route). Sometimes, a low-level error cannot be localised to a single step, but rather to a cluster of steps. For instance, if one has a circular argument, in which a statementAis claimed usingBas justication, andBis then claimed usingAas justication, then it is possible for both implications A> BandB> Ato be true, while the deduction thatAandBare then both true remains invalid 1. Another example of a low-level error that is not localisable to a single step arises from ambiguity. Suppose that one is claiming thatA=)B andB=)C, and thus thatA=)C. If all terms are unambiguously1 Note though that there are important and valid examples ofnear-circular arguments, such as proofs by induction, but this is not the topic of my discussion today.
1.2. Errors in mathematical proofs3well-dened, this is a valid deduction. But suppose that the expressionBis
ambiguous, and actually has at least two distinct interpretations, sayB1and B
2. Suppose further that theA=)Bimplication presumes the former
interpretationB=B1, while theB=)Cimplication presumes the latter interpretationB=B2, thus we actually haveA=)B1andB2=)C. In such a case we can no longer validly deduce thatA=)C(unless of course we can show in addition thatB1=)B2). In such a case, one cannot localise the error to eitherA=)BorB=)CuntilBis dened more unambiguously. This simple example illustrates the importance of getting key terms dened precisely in a mathematical argument. The other way to nd an error in a proof is to obtain a \high-level" or \global" objection, showing that the proof, if valid, would necessarily imply a further consequence that is either known or strongly suspected to be false. The most well-known (and strongest) example of this is thecounterexample. If one possesses a counterexample to the claimA=)E, then one instantly knows that the chain of deductionA=)B=)C=)D=)E must be invalid, even if one cannot immediately pinpoint where the precise error is at the local level. Thus we see that global errors can be viewed as \non-constructive" guarantees that a local error must exist somewhere. A bit more subtly, one can argue using the structure of the proof itself. If a claim such asA=)Ecould be proven by a chainA=)B=)C=) D=)E, then this might mean that a parallel claimA0=)E0could then also be proven by a parallel chainA0=)B0=)C0=)D0=)E0of logical reasoning. But if one also possesses a counterexample toA0=)E0, then this implies that there is a aw somewhere in this parallel chain, and hence (presumably) also in the original chain. Other examples of this type include proofs of some conclusion that mysteriously never use in any essential way a crucial hypothesis (e.g. proofs of the non-existence of non-trivial integer solutions toan+bn=cnthat mysteriously never use the hypothesis thatnis strictly greater than 2, or which could be trivially adapted to cover then= 2 case). While global errors are less constructive than local errors, and thus less satisfying as a \smoking gun", they tend to be signicantly more robust. A local error can often be patched or worked around, especially if the proof is designed in a fault-tolerant fashion (e.g. if the proof proceeds by fac- toring a dicult problem into several strictly easier pieces, which are in turn factored into even simpler pieces, and so forth). But a global error tends to invalidate not only the proposed proof as it stands, but also all reasonable perturbations of that proof. For instance, a counterexample to
41. Logic and foundationsA=)Ewill automatically defeat any attempts to patch the invalid argu-
mentA=)B=)C=)D=)E, whereas the more local objection thatCdoes not implyDcould conceivably be worked around. It is also a lot quicker to nd a global error than a local error, at least if the paper adheres to established standards of mathematical writing. To nd a local error in anN-page paper, one basically has to read a signicant fraction of that paper line-by-line, whereas to nd a global error it is often sucient to skim the paper to extract the large-scale structure. This can sometimes lead to an awkward stage in the verication process when a global error has been found, but the local error predicted by the global error has not yet been located. Nevertheless, global errors are often the most serious errors of all. It is generally good practice to try to structure a proof to be fault tolerant with respect to local errors, so that if, say, a key step in the proof of Lemma
17 fails, then the paper does not collapse completely, but contains at least
some salvageable results of independent interest, or shows a reduction of the main problem to a simpler one. Global errors, by contrast, cannot really be defended against by a good choice of proof structure; instead, they require a good choice of proof strategy that anticipates global pitfalls and confronts them directly. One last closing remark: as error-testing is the complementary exercise to proof-building, it is not surprising that the standards of rigour for the two activities are dual to each other. When one is building a proof, one is expected to adhere to the highest standards of rigour that are practical, since a single error could well collapse the entire eort. But when one is testing an argument for errors or other objections, then it is perfectly acceptable to use heuristics, hand-waving, intuition, or other non-rigorous means to locate and describe errors. This may mean that some objections to proofs are not watertight, but instead indicate that either the proof is invalid, or some accepted piece of mathematical intuition is in fact inaccurate. In some cases, it is the latter possibility that is the truth, in which case the result is deemed \paradoxical", yet true. Such objections, even if they do not invalidate the paper, are often very important for improving one's intuition about the subject.
1.3. Mathematical strength
The early twentieth century philosopher Ludwig Wittingstein famously ar- gued that every mathematical theorem was a tautology, and thus all such theorems contained a trivial amount of content. There is a grain of truth to this: when a dicult mathematical problem is nally solved, it is often the case that the solution does make the original problem look signicantly
1.3. Mathematical strength5easier than one had previously thought. Indeed, one could take the some-
what counter-intuitive point of view that progress in mathematics can be measured by how much of mathematics has been made trivial (or at least easier to understand than previously). On the other hand, there is a denite sense that some mathematical theorems are \stronger" than others, even if from a strictly logical point of view they are equivalent. A theorem can be strong because its conclusions are strong, because its hypotheses (or underlying axiom system used in the proof) are weak, or for some combination of the two reasons. What makes a theorem strong? This is not a precise, well-dened con- cept. But one way to measure the strength of a theorem is to test it against a class of questions and problems that the theorem is intended to assist with solving. For instance, one might gauge the strength of a theorem in analytic number theory by the size of the error terms it can give on various number-theoretic quantities; one might gauge the strength of a theorem in PDE by how large a class of initial data the theorem is applicable to, and how much control one gets on the solution as a consequence; and so forth. All other things being equal, universal statements (\P(x) is true for all x") are stronger than existential statements (\P(x) is true for somex"), assuming of course that one is quantifying over a non-empty space. There are also statements of intermediate strength (e.g. \P(x) is true for \many" x", or \P(x) is true for \almost all"x", for suitably precise quantications of \many" or \almost all"). In a similar vein, statements about special types of objects (e.g. about special functions) are usually not as strong as analogous statements about general types of objects (e.g. arbitrary functions in some function space), again assuming all other things are equal 2. Asymptotic statements (e.g. statements that only have content when some parameterNis \suciently large", or in the limit asNgoes to in- nity) are usually not as strong as non-asymptotic statements (which have meaningful content even for xedN). Again, this is assuming that all other things are equal. In a similar vein, approximate statements are not as strong as exact ones. Statements about \easy" or well-understood objects are usually not as strong as statements about \dicult" or poorly understood objects. For instance, statements about solutions to equations over the reals tend to be much weaker than their counterparts concerning equations over the integers; results about linear operators tend to be much weaker than corresponding results about nonlinear operators; statements concerning arithmetic func- tions that are sensitive to prime factorisation (e.g. the Mobius function or2 In practice, there is often a tradeo; to obtain more general statements, one has to weaken the conclusion.
61. Logic and foundationsvon Mangoldt function) are usually signicantly stronger than analogous
statements about non-arithmetical functions (e.g. the logarithm function); and so forth. When trying to read and understand a long and complicated proof, one useful thing to do is to take a look at the strength of various key statements inside the argument, and focus on those portions of the argument where the strength of the statements increases signicantly (e.g. if statements that were only known for a few values of a variablex, somehow became amplied into statements that were true for many instances ofx). Such amplications often contain an essential trick or idea which powers the entire argument, and understanding those crucial steps often brings one much closer to un- derstanding the argument as a whole.
By the same token, if the proof ends up being
awed, it is quite likely that at least one of the aws will be associated with a step where the statements being made became unexpectedly stronger by a suspiciously large amount, and so one can use the strength of such statements as a way to quickly locate aws in a dubious argument. The notion of the strength of a statement need not be absolute, but may depend on the context. For instance, suppose one is trying to read a convoluted argument that is claiming a statement which is true in all dimensionsd. If the argument proceeds by induction on the dimensiond, then it is useful to adopt the perspective that any statement in dimension d+1 should be considered \stronger" than a statement in dimensiond, even if this latter statement would ordinarily be viewed as a stronger statement than the former if the dimensions were equal. With this perspective, one is then motivated to look for the passages in the argument in which statements in dimensiondare somehow converted to statements in dimensiond+1; and these passages are often the key to understanding the overall strategy of the argument. See also the blog post [Go2008] of Gowers for further discussion of this topic.
1.4. Stable implications
A large part of high school algebra is focused on establishing implications which are of the form \IfA=B, thenC=D", or some variant thereof. (Example: \Ifx25x+ 6 = 0, thenx= 2 orx= 3.") In analysis, though, one is often more interested in astabilityversion of such implications, e.g. \IfAis close toB, thenCis close toD". Further- more, one often wants quantitative bounds onhowcloseCis toD, in terms
1.4. Stable implications7of how closeAis toB. (A typical example: ifjx25x+ 6j , how close
mustxbe to 2 or 3?) Hilbert's nullstellensatz(discussed for instance at [Ta2008,x1.15]) can be viewed as a guarantee that every algebraic implication has a stable ver- sion, though it does not provide a particularly ecient algorithm for locating that stable version. One way to obtain stability results explicitly is todeconstructthe proof of the algebraic implication, and replace each step of that implication by a stable analogue. For instance, if at some point one used an implication such as \IfA=B, thenAC=BC" then one might instead use the stable analogue jACBCj=jABjjCj:
If one used an implication such as
\IfA=B, thenf(A) =f(B)" then one might instead use a stable analogue such as jf(A)f(B)j KjABj whereKis theLipschitz constantoff(or perhaps one may use other stable analogues, such as themean-value theoremor thefundamental theo- rem of calculus). And so forth. A simple example of this occurs when trying to nd a stable analogue of the obvious algebraic implication \IfAi=Bifor alli= 1;:::;n, thenA1:::An=B1:::Bn," thus schematically one is looking for an implication of the form \IfAiBifor alli= 1;:::;n, thenA1:::AnB1:::Bn." To do this, we recall how the algebraic implication is proven, namely by successive substitution, i.e. by concatenating thenidentities A
1:::An=B1A2:::An
B
1A2:::An=B1B2A3:::An
:::B
1:::Bn1An=B1:::Bn:
A stable version of these identities is given by the formula B
81. Logic and foundationsfori= 1;:::;n, and so by telescoping all of these identities together we
obtain A
1:::AnB1:::Bn=nX
i=1B
1:::Bi1(AiBi)Ai+1:::An
which, when combined with tools such as the triangle inequality, gives a variety of stability results of the desired form (even in situations in which theA's andB's do not commute). Note that this identity is also the discrete form of the product rule (A1:::An)0=nX i=1A
1:::Ai1A0iAi+1:::An
and in fact easily supplies a proof of that rule.
1.5. Notational conventions
Like any other human language, mathematical notation has a number of implicit conventions which are usually not made explicit in the formal de- scriptions of the language. These conventions serve a useful purpose by conveying additional contextual data beyond the formal logical content of the mathematical sentences. For instance, while in principle any symbol can be used for any type of variable, in practice individual symbols have pre-existing connotations that make it more natural to assign them to specic variable types. For instance, one usually usesxto denote a real number,zto denote a complex number, andnto denote a natural number; a mathematical argument involving a complex numberx, a natural numberz, and a real numbernwould read very strangely. For similar reasons,x2Xreads a lot better thanX2x; sets or classes tend to \want" to be represented by upper case letters (in Roman or Greek) or script letters, while objects should be lower case or upper case letters only. The most famous example of such \typecasting" is of course the epsilon symbol in analysis; an analytical argument involving a quantity epsilon which was very large or negative would cause a lot of unnecessary cognitive dissonance. In contrast, by sticking to the conventional roles that each symbol plays, the notational structure of the argument is reinforced and made easier to remember; a reader who has temporarily forgotten the denition of, say, \z" in an argument can at least guess that it should be a complex number, which can assist in recalling what that denition is. As another example from analysis, when stating an inequality such as X < YorX > Y, it is customary that the left-hand side represents an \unknown" that one wishes to control, and the right-hand side represents a more \known" quantity that one is better able to control; thus for instance
1.6. Abstraction9x <5 is preferable to 5> x, despite the logical equivalence of the two
statements. This is why analysts make a signicant distinction between \upper bounds" and \lower bounds"; the two are not symmetric, because in both cases is bounding an unknown quantity by a known quantity. In a similar spirit, another convention in analysis holds that it is preferable to bound non-negative quantities rather than non-positive ones. Continuing the above example, if the known boundYis itself a sum of several terms, e.g.Y1+Y2+Y3, then it is customary to put the \main term" rst and the \error terms" later; thus for instancex <1 +"is preferable tox < "+ 1. By adhering to this standard convention, one conveys useful cues as to which terms are considered main terms and which ones considered error terms.
1.6. Abstraction
It is somewhat unintuitive, but many elds of mathematics derive their power from strategicallyignoring(or *abstracting* away) various aspects of the problems they study, in order to better focus on the key features ofquotesdbs_dbs17.pdfusesText_23
[PDF] Analysis I by Tao