WIXLIB

The Good Old Days30Up to this point, mathematics was doing just fine. There were fiercedebates, but no one doubted the fundamental soundness of mathematicalreasoning. Practitioners might and did blunder; other than that, resultswere good in perpetuity.E.g., Euclid’s old argument for the infinitude of primes is unassailable(unless you are a dyed in the wool constructivist). And his system ofgeometry was obviously correct.C.G.J. JacobiIntuition versus AbstractionIt was standard to follow in Kant’s footsteps (who, like Aristotle, knewlittle math) and adopt a theory that:To be clear: even today not everyone participates in the quest forabsolute precision. For example, physics super-star Steven Weinbergwrites in a book on quantum field theoryspatial intuition is a given of human cognition, and gives rise togeometry,. . . there are parts of this book that will bring tears to theeyes of the mathematically inclined reader.intuition of time is similarly given, and leads to arithmetic.Even Hamilton (as in Hamiltonian systems and quaternions) tried toformulate such a model in 1853.In physics, this is probably a good thing that helps the field along. In CS,it would more likely be a disaster.34Infinitesimals35Euler considers an infinitesimal δ 0. This simplifies matters greatly:eδ 1 δProblem: Find a way to calculate e for real x.xWlog x 0. For x reasonably small we can writeex 1 x errorwith the error term being small. Alas, we have no idea what exactly theerror is (duh).33The problem with intuition-based reasoning is that it starts to fail whenthe subject of discourse becomes increasingly abstract and sophisticated(some would say: abstruse). Ordinary experience and every-day notionsstart to lose traction. The 19th century saw a lot of that.How does one construct solid proofs? What are the underlyingmathematical foundations? Up to the middle of the 19th century,basically no one cared.Leonhard Euler had the amazing ability to concoct arguments that wereeminently plausible, and led to correct results, but were exceedinglydifficult to justify in the modern sense. Here is an example:If Gauss says he has proved something, it seems very probable to me; if Cauchy says so, it is about as likely as not; ifDirichlet says so, it is certain.Jacobi was no slouch but one of the experts from the last slide; if hecriticizes a proof it is because there are real, serious and difficult-to-fixproblems, not just some superficial lack of understanding.32Euler, an Example31But things started to unravel a bit in the 19th century. Here is a mostrevealing quote in a letter to A. von Humboldt:Aka Ancient Mathematical History. For our purposes, let’s say that’severything up to 1800.FoundationsApproaching the AbyssIt is justified by Leibniz’s lex homogeneorum transcendentalis, thetranscendental law of homogeneity: proof of the law is by higherauthority (or nonstandard models of arithmetic 250 years later).Once we accept the last identity, we can calculate happily:

Finale Furioso36ex (eδ )x/δHeadache?37The result is perfectly correct. But the argument . . . oy vey. (1 δ)x/δ 1 x/δ 2x/δδ δ .21Incidentally, Euler also had an ingenious argument to show that1 2 3 . n . 1 x 1/2 x(x δ) . . .No, that’s not nuts. 1 x 1/2 x2 . . . X112Look up ζ function regularization and analytic continuations.xi /i!i 0Food for Thought38ExerciseFind all the places where Euler’s reasoning is dubious from a modern dayperspective.Exercise (Very Hard)Fix all the problems with Euler’s argument.ExerciseFigure out why it makes sense to claim that 1 2 3 . . . 1/12.Similarly 1 1 1 . . . 1/2.The Antidote40Apparently, the only reliable (and somewhat unpalatable) solution to thisproblem of rigor is to be exceedingly formal and precise in all arguments.At least four frameworks emerged that appear to be helpful in thisenterprise (perhaps in combination):Logic and Formalization (Boole, Frege, Peano)Axiomatization (Peano, Dedekind, Hilbert)Set theory (Dedekind, Cantor, Frege, Zermelo, Fraenkel)Type theory (Russell, Howard-Curry, Church, Per-Löf, Voevodsky)1Administrivia2Course Material3Computation and/versus Math4The FixQuoi?41The first two merged more or less into the notion of a formal system: asuitable logic, that makes it possible to formalize appropriate axioms andrules of inference (first-order logic is the standard).Under Bourbaki, set theory developed into the reference implementation,the de facto gold standard that everybody relies on (though mostpractitioners would have a hard time explaining ZF).Type theory was off to a great start under Russell and Whitehead, butgot clobbered by set theory. However, at present type theory is arguablymore important in CS, and as suggested by MKM and theorem proving,might at some point also become dominant in math.

Hilbert’s Program42Perfect for CS43Strictly finitary means that every single logical operation has to beentirely mechanical and, in a sense, trivial. In particular, they could easilybe carried out by a computer (some would say that’s the only thing acomputer can do). In particular it must be decidable whether a givenargument is a valid proof.In the 1920s, partially in response to paradoxes and intuitionistic lunacy,David Hilbert proposed a program to salvage all of mathematics. In anutshell:Formalize mathematics and concoct a finite set of axiomsthat are strong enough to prove all theorems of mathematics (completeness) and show that the system is free fromcontradictions (consistency); by strictly finitary means.The part about ideal objects means that reasoning about infinite objectsis fine as long as it can be justified in a finitary way.Initially good progress was madeAlso show that statements about “ideal objects” can beproven in the system, without using ideal objects.completeness of propositional logic (Ackermann 1928),completeness of predicate logic (Gödel 1930).Gödel44But then, in 1931, Kurt Gödel drops a bombshell: any formalmathematical system of the kind Hilbert had in mind is necessarilyincomplete or inconsistent. So in any consistent system some truestatements cannot be proven.Interestingly, Gödel’s argument is based on a version of the oldEpimenides paradox, exploiting self-reference:There is a clear connection between incompleteness and unsolvability, socomputability is a rather central notion in mathematics.Note that this type of paradox is quite different from the purely logicalparadox of Russell (see below) and far more opaque.D. Hilbert, W. AckermannGrundzüge der theoretischen Logik, 1928Thus the notion “computable” is in a certain sense “absolute,” while almost all metamathematical notions otherwiseknown (for example, provable, definable, and so on) quiteessentially depend upon the system adopted.K. Gödel, 1936This sentence is false.The Entscheidungsproblem is solved when one knows a procedure by which one can decide in a finite number of operations whether a given logical expression is generally validor is satisfiable. The solution of the Entscheidungsproblemis of fundamental importance for the theory of all fields, thetheorems of which are at all capable of logical developmentfrom finitely many axioms.45Though some parts of Hilbert’s program were irreparably damaged byGödel’s result, in many ways things just started to become reallyinteresting.In particular consistency itself (i.e. lack of internal contradictions) is mostelusive: e.g. one cannot prove consistency of arithmetic in ayersIn the interest of fairness, we point out again that the whole premissabout the importance of computation and computers in math (and evenin CS) is certainly not without its detractors.In fact, it drives some people right up the wall.Here is an excerpt from a paper written in 1991 by a propellerhead whoshall go unnamed and unmentioned.In modern terminology: find a decision algorithm for statements ofmathematics (or at least some part like arithmetic, group theory, . . . ).47

Computers Bad48Computers Very Bad49Lastly, and most dastardly, there is the much ballyhooedextension of the notion of mathematical proof, far beyondthe classical Greek paradigm of of axioms and rules of inference, to include so-called computer-proofs, whose nonsurveyability by human beings demands appeals to faith inimical to the enterprise of science, and yet allegedly yieldsresults which are otherwise of necessity far beyond the powers of mortal man to obtain.OK, one more quote from the same guy.A mediocre mathematician with a computer might be ableto simulate the creative powers of a top notch mathematician with pencil and paper.As my old high school philosophy teacher said, after some studentcomplained about not being satisfied with a lecture: That issue you willhave to take into your own hands.The Catch?Admitting the computer shenanigans of Appel and Haken tothe ranks of mathematics would only leave us intellectuallyunsatisfied.50So where is the catch? If it is true that the math–computationconnection is so utterly useful and compelling, why is it that in 2021 thestandard approach to math is not a trip to the computational universe?Why is there a lag of whole century?Infinite Wisdom51In theory there is no difference between theory and practice.In practice there is.Of course, old habits die hard, so one should expect some amount ofresistance. This is particularly relevant here where some of the new ideascome from a different, and often ridiculed field.Yogi BerraAnd then there is a famous problem pointed out by a well-knownAmerican philosopher of the 20th century.A Warning52The standard of correctness and completeness necessary toget a computer program to work at all is a couple of ordersof magnitude higher than the mathematical community’sstandard of valid proofs.Bill Thurston, Notices AMS, 1994Fields Medal 1982, used computers extensively in his seminal work onlow-dimensional topology. Supposedly taught himself to visualize 4-dimobjects.To be honest, Thurston had ulterior motives to make this statement, butthat does not detract from its fundamental correctness.But the Future is Golden53I expect that digital computing machines will eventuallystimulate a considerable interest in symbolic logic . . . Thelanguage in which one communicates with these machines. . . forms a sort of symbolic logic.Alan TuringThe Algorithm’s coming-of-age as the new language of science promises to be the most disruptive scientific development since quantum mechanics.Bernard ChazelleGenerally, computer science, that no-nonsense child of logic,will exert growing influence on our thinking about the languages by which we express our vision of mathematics.Yuri Manin

Battleplan54Reading55Brief introduction to computability and complexity.Selected topics in discrete math:Transition systemsGroups and finite fieldsAlas, discrete math is far too broad to fit into a single semester, so takethis as a proof of concept.Take a look at the notes on primitive recursive functions on the web.Don’t worry about technical details, just get a general idea.Ask questions on Thursday (or on Piazza if time-critical).

MIP RE 27 MIP refers to a multi-interactive-prover protocol (the computationally powerful provers try to convince the weak veri er). The star means the provers have entangled qubits. RE is the collection of all recursively enumerable sets{which includes the undecidable Halting Set. Alas, the provers require a rather large number of entangled .