Bristol lectures in logic 2010 from emergence of reasoning to modern Unprovability Theory by Andrey Bovykin

Thu: 2:00	Thu: 4:00	Fri: 1:10	Fri: 4:00
		Feb 5	Feb 5
Feb 11		Feb 12	Feb 12
Feb 18		Feb 19	Feb 19
Feb 25		Feb 26	Feb 26
Mar 4		Mar 5	Mar 5
Mar 11		Mar 12	Mar 12
Mar 18		Mar 19	Mar 19

EASTER BREAK

Apr 22	Apr 22	Apr 23	Apr 23
Apr 29	Apr 29	Apr 30	Apr 30
May 6	May 6	May 7	May 7 ++

May 13:     2:00 - 5:20 Foundations of Mathematics Debate

May 14:   revision session

All materials for this course are posted on THIS WEBPAGE.

Last year's pages WHICH ARE HERE will be very useful. This year I am planning to produce and enhanced/optimised version of last year's course. There are no formal pre-requestives to this course, but a certain level of mathematical maturity is expected from each participant, say the level of a clever third-year undergraduate mathematics student. :) Philosophy students and computer science students are also welcome to participate in this course (helped by two years of logic training in their departments).

 
Here's the plan:

• Part 1: About reasoning

  An assortment of things that must be said. Emergence of reasoning. Evolutionary studies on reasoning. Nervous system, brain structure. Brief sketch of the work of the nervous system. Great Apes. Artificial intelligence. Reasoning in sciences and humanities: reasoning in History, reasoning in Law, reasoning in Medicine. Science: modelling versus classification. Emergence of proofs.

• Part 2: Geometries: Hyperbolic, Euclidean, Elliptic

  Euclid's "Elements", the first postulates, Euclid's fifth postulate and attempts to prove it, Gauss, Lobachevski, Bolyai, Hyperbolic geometry, Klein's model, Poincare's model, elliptic geometry. About Unprovability: the First Scenario of Impossibility in Mathematics ("alternative worlds").

• Part 3: Ruler and Compass Constructions: possibility and impossibility results.

  Ruler and compass constructions, examples of what can be done by ruler and compass, classical Impossibility results (trisecting an angle, squaring a circle, doubling a cube), regular polygons: Gauss's theorem, Steiner's theorems, impossibility of finding the centre of a circle by ruler alone, other instruments, linkages, the story of Watt's parallelogram, Watt's problem and Paucelier's solution. The Second Scenario of Impossibility in mathematics ("insufficient instruments").

• Part 4: Four Scenarios of Impossibility in Mathematics

  The Third Scenario of Impossibility ("no uniform solution exists") and examples: Galois theory, and glimpses into the future chapters: halting problem, hydras, etc.

  The Fourth Scenario of Impossibility ("the right objects don't yet exist"), examples: irrational numbers, complex numbers, algebraic extensions, etc. Discussion of the Four Scenarios of Impossibility.

• Part 5: Formalisation of mathematics: theories and models

  basic definitions of predicate calculs: language, formulas, axioms, proofs, structures, models

   

• FIRST SET OF EXERCISES: languages, formulas, structures, models.

   

• Part 6: First examples of theories and models

  empty theory, there are at least n elements, there are exactly n elements, linear orders, partial orders, trees, dense linear orders without end-points, discrete linear orders, graphs, directed graphs, groups, fields, linearly ordered fields, algebraically closed fields, real-closed fields.

• Part 7: Foundational theories

  PA Peano Arithmetic), Z_2 (Second-Order Arithmetic), CST ("Cantor's Set Theory"), NF, ZFC.

  Definition of a foundational theory, understanding models of foundational theories.

• Part 8: Main Theorem of Model Theory

  Compactness, every theory is contained in a complete theory, The Main Theorem of Model Theory (every consistent theory has a model), practical drills and applications of the Main Theorem of Model Theory, Lowenheim-Skolem theorems, DLO is countably categorical, DLO is complete. Drills and example of applications of the main theorem of model theory.

   

• SECOND SET OF EXERCISES: theories, models, compactness, applications of the Main Theorem of Model Theory

   

• Part 9: Foundational Crisis

  A modern account of the Foundational Crisis: the zoo of antinomies and what to think about them, ideal objects versus concrete mathematical objects, the "Choice Principle" debate, Weyl and predicativity, actual infinity versus potential infinity, intuitionist (constructive) mathematics, Hilbert's Programme, why Hilbert believed it would work.

• Part 10: Computability

  Algorithm, Turing machines, computable function, Turing machines don't have to halt, decidable and undecidable sets, Godel number of a Turing machine, examples of algorithms, running time of algorithms, P=NP question, busy beaver, Operating System (universal algorithm), the halting problem, decision problems, undecidability of the halting problem, Diophantine equations, Matiyasevich-Robinson-Davis-Putnam theory, Hilbert's 10th Problem is undecidable, a list of classical undecidable problems, enumerable sets, enumerable but not decidable sets.

• Part 11: Decidable and Undecidable theories

  recursively axiomatised theories, decidable theories, complete recursively axiomatised theories are decidable, examples of decidable and undecidable theories. RCF, Presburger, about the question of decidability of the field of reals with exponentiation.

• Part 12: Arithmetisation of classical mathematics

  carefully arithmetising calculus and beyond in two languages: first-order arithmetic and second-order arithmetic.

• Part 13: Constructive Mathematics

  Brouwer-Heyting, Turing-Goodstein, Markov-Shanin, how to understand logical symbols constructively, Markov's Principle, constructive real number, constructive limit of a sequence, Specker's sequence (a strictly increasing bounded sequence of real numbers that has no limit), Turing's theorem on unenumerability of the continuum.

   

• THIRD SET OF EXERCISES: computability, foundational crisis, constructive mathematics, decidable and undecidable theories.

   

• Part 14: Arithmetisation of syntax

  representation theorem, provability predicate, formulating consistency statements, etc

• Part 15: Loss of Innocence: Godel's Incompletenss theorems

  Old-fashioned diaganalisation lemma, proof of Godel's First Incompleteness Theorem, Discussion, Father Christmas, Lob's Theorem, Godel's Second Incompleteness Theorem, Discussion, progressions of theories, notion of consistency strength, theories of incomparable consistency strengths, Gentzen's theorem (without proof), landscape of proof theory and ordinal analysis.

• Part 16: Unprovability in Mathematics

  I am planning an enlightened and accessible discussion of CH, AD, the Paris-Harrington Principle, hydras and other unprovable statements, Kruskal's theorem, Higman's lemma, the Graph Minor Theorem, Hilbert's 1st, 2nd and 10th Problems, all necessary explanations about [the mathematics of!] reverse mathematics, Weiermann's Programme of phase transitions between provability and unprovability, Boolean Relation Theory, Friedman's Programme, modern picture of classical important theories, famous classical theorem in mathematics posessing strength (e.g. the Ramsey theorem implying all theorems of Peano Arithmetic), discussion of the infinite-dimensional Ramsey theorem, perhaps discussions of some other big Issues (crucial to understanding modern logic).

  Connecting Unprovability with our Four Scenarios of Impossibility in Mathematics.

• Part 17: Understanding more about unprovabilty

  I am planning to discuss Unprovability further: the notion of arithmetical strength of an arbitrary foundational theory, the possibility of arithmetical splitting (good foundational theories that are arithmetically incomparable, i.e. contradict each other on some first-order arithmetical statements), two camps of thought about consistency strength (the Truly Incomparable Theories Camp versus the One Way Up Camp), some mathematical arguments for canonicity of former well-studied theories like ZFC and some arguments for ad hoc arbitrariness of former well-studied theories (like ZFC), future possibilities for threshold results. A discussion of possible relevance to old problems: can the Riemann Hypothesis, Navier-Stocks conjecture, P=NP-problem, Twin Prime conjecture, Hypothesis H, etc turn out to be unprovable? - understanding the logical differences between them. Discussion of Friedman-style templates: BRT, greed, dags, etc, discussion of flexible templates (hitting every theory) versus restricted templates (hitting only few theories). Discussion of the possibility of density results saying "almost all mathematical statements are unprovable" and variations. More on Pi-1 Splitting and Sigma-1 maximality (Solovay-Shavrukov theorems).

• Part 18: What to believe now?

  I am planning to type a somewhat caricature entertaining discussion about the three characters: a Platonist, a Pluralist and a Constructivist.

  However, I am not planning to teach it in the course but instead organise a show, a Public Debate, where a real-life Platonist, a real-life Pluralist and a real-life Constructivist will publicly argue and tell us what to believe (and why not to believe the other two guys). The video of last year's Debate is available.