Meta-Mathematics and the Foundations of Mathematics. EATCS Bulletin, June 2002, vol. 77, pp. 167-179 G. J. Chaitin This article discusses what can be proved about the foundations of mathematics using the notions of algorithm and information. In this article I'm going to concentrate on what we can prove about the foundations of mathematics using mathematical methods, in other words, on metamathematics.
Then, as is pointed out in Turing's original paper (1936), and as was emphasized by Post in his American Mathematical Society Bulletin paper (1944), the set X of all theorems, consequences of the axioms, can be systematically generated by running through all possible proofs in size order and mechanically checking which ones are valid. The size in bits H(X) of the program that generates the set X of theorems---that's the program-size complexity of X---will play a crucial role below.
But first let's retrace history, starting with a beautiful antique, Gödel's incompleteness theorem, the very first incompleteness theorem. What is an Algorithm? Cantor and Cohen: Infinite investigators part I. June 2008 This is one half of a two-part article telling a story of two mathematical problems and two men: Georg Cantor, who discovered the strange world that these problems inhabit, and Paul Cohen (who died last year), who eventually solved them. The first of these problems — the axiom of choice — is the subject of this article, while the other article explores what is known as the continuum hypothesis.
Each article is self-contained, so you don't have to read both to get the picture. Cantor: The infinite match-maker Georg Cantor was a German logician who, in the late 19th century, achieved a feat which scientists, philosophers, and theologians had previously only dreamed about: a detailed analysis of infinity. For Cantor personally, the consequences of this triumph were not happy. Unable to solve one of the questions his work opened up, known as the continuum hypothesis, he became obsessive and miserable with his failure. Georg Cantor Suppose you have two collections of objects. . Theorem of the Day. The Whole Jolly Lot (now enriched with The list is presented here in reverse chronological order, so that new additions will appear at the top.
This is not the order in which the theorem of the day is picked which is more designed to mix up the different areas of mathematics and the level of abstractness or technicality involved. The way that the list of theorems is indexed is described here. Every theorem number is linked to its entry in the delightful 'Prime Curios! ' compendium at The Prime Pages. For good measure I have highlighted primes in red. Click on any number and be beguiled (don't forget to look at the theorem too!)
All files are pdf , mostly between 100 and 300 Kbytes in size. A QED following a theorem indicates that the description includes a proof of the theorem. 211 Willans' Formula QED 210 The Basel Problem QED 209 The Erdős Discrepancy Conjecture QED ( a Theorem under construction!) 208 Toricelli's Trumpet QED 207 The Eratosthenes-Legendre Sieve QED 206 Euler's Formula QED. Gödel's incompleteness theorems. Gödel's incompleteness theorems are two theorems of mathematical logic that establish inherent limitations of all but the most trivial axiomatic systems capable of doing arithmetic.
The theorems, proven by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of mathematics. The two results are widely, but not universally, interpreted as showing that Hilbert's program to find a complete and consistent set of axioms for all mathematics is impossible, giving a negative answer to Hilbert's second problem. The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an "effective procedure" (i.e., any sort of algorithm) is capable of proving all truths about the relations of the natural numbers (arithmetic). For any such system, there will always be statements about the natural numbers that are true, but that are unprovable within the system.
Background[edit] First incompleteness theorem[edit] Diagonalization[edit] B. A Visual Tutorial in Formal Logic - The 16 Combinations of Meaning. Hammack Home. This book is an introduction to the standard methods of proving mathematical theorems. It has been approved by the American Institute of Mathematics' Open Textbook Initiative. Also see the Mathematical Association of America Math DL review (of the 1st edition), and the Amazon reviews. The second edition is identical to the first edition, except some mistakes have been corrected, new exercises have been added, and Chapter 13 has been extended.
(The Cantor-Bernstein-Schröeder theorem has been added.) The two editions can be used interchangeably, except for the last few pages of Chapter 13. (But you can download them here.) Order a copy from Amazon or Barnes & Noble for $13.75 or download a pdf for free here. Part I: Fundamentals Part II: How to Prove Conditional Statements Part III: More on Proof Part IV: Relations, Functions and Cardinality Thanks to readers around the world who wrote to report mistakes and typos!