Gödel's Incompleteness Theorems
This is the first ever machine-assisted proof of the second incompleteness theorem, and coding is simpler, with no need to formalise the notion of multiplication (let alone that of a prime number) in the formalised calculus upon which the theorem is based.
Gödel’s incompleteness theorems
This thesis will explore two formal languages of logic and their associated mechanically recursive proof methods with the goal of proving Godel’s Incompleteness Theorems. Beautifying Gödel
The incompleteness theorems of Kurt Gödel [1931] are considered to be among the most important results of mathematics. They are regarded as “deep”, and they strongly influenced the course of modern… An Introduction to Gödel's Theorems
An unusual variety of proofs for the First Theorem are presented, how to prove the Second Theorem is shown, and a family of related results are explored, including some not easily available elsewhere. The development of mathematics toward greater precision has led, as is well known, to the formalization of large tracts of it, so that one can prove any theorem using nothing but a few mechanical rules. The most comprehensive formal systems that have been set up hitherto are the system of Principia mathematica (PM) 2 on the one hand and the Zermelo-Fraenkel axiom system of set theory (further developed by J. von Neumann) 3 on the other. These two systems are so comprehensive that in them all methods of proof today used in mathematics are formalized, that is, reduced to a few axioms and rules of inference. One might therefore conjecture that these axioms and rules of inference are sufficient to decide any mathematical question that can at all be formally expressed in these systems. It will be shown below that this is not the case, that on the contrary there are in the two systems mentioned relatively simple problems in the theory of integers 4 that cannot be decided on the basis of the axioms. This situation is not in any way due to the special nature of the systems that have been set up but holds for a wide class of formal systems; among these, in particular, are all systems that result from the two just mentioned through the addition of a finite number of axioms, 5 provided no false propositions of the kind specified in note 4 become provable owing to the added axioms.
Open Preview See a Problem?We’d love your help. Let us know what’s wrong with this preview of On Formally Undecidable Propositions of Principia Mathematica and Related Systems by Kurt Gödel. Thanks for telling us about the problem.
Friend ReviewsTo see what your friends thought of this book, please sign up. Reader Q&ABe the first to ask a question about On Formally Undecidable Propositions of Principia Mathematica and Related Systems Community Reviews· 370 ratings · 26 reviews Start your review of On Formally Undecidable Propositions of Principia Mathematica and Related Systems
Feb 05, 2015 Kunal Sen rated it it was amazing It was much harder than I thought, and it is best suited for professional mathematicians. For the rest of us Godel's Proof by Nagel is a better option. Still, had to try the original for one of the most audacious ideas humankind can be proud of. It was much harder than I thought, and it is best suited for professional mathematicians. For the rest of us Godel's Proof by Nagel is a better option. Still, had to try the original for one of the most audacious ideas humankind can be proud of. ...more
Nov 14, 2008 Nick Black rated it it was amazing The greatest achievement in human thought to date, IMHO. Every family ought have a copy on their coffee table. I read this the summer after high school, and have gone back a few times. In less than one hundred pages, that silent madman Gödel will shatter your mind, put it back together with turing tape, and leave you changed forever. Minimal mathematical background is required.
A few words of advice: 1. If you are NOT a mathematician, please, read (and re-read) thoroughly the introduction by R. B. Braithwaite until you feel comfortable with Gödel’s notation,
specially in those cases where it parts from everything you have read or been taught before. It will pay off heavily later on. 2. If you are a mathematician, you can go straight into Gödel’s paper starting on page 37. Pay attention to the definition of class-sign on page 43 —it will come back on page 57!—, and work 1. If you are NOT a mathematician, please, read (and re-read) thoroughly the introduction by R. B.
Braithwaite until you feel comfortable with Gödel’s notation, specially in those cases where it parts from everything you have read or been taught before. It will pay off heavily later on. 2. If you are a mathematician, you can go straight into Gödel’s paper starting on page 37. Pay attention to the definition of class-sign on page 43 —it will come back on page 57!—, and work on each of the 45 functions (and relations) on pages 49-55. It will save you a lot of time when you are reading
the proof to the famous undecidability theorem. 3. Formula (15) on page 59 is wrong (in my copy): the antecedent needs to be overlined to denote negation. The same correction needs to be made in this page, line 17. All these been said... Gödel wrote a fine piece of mathematics which deals with the limits to certain formal systems. He was not trying to demolish or tear down Hilbert’s formalistic standpoint (as some people suggest) and you will become aware of this fact towards the
very end of the paper (page 71). In coming up with two beautiful results (the undecidability theorem and the one stating that the consistency of a formal consistent system is unprovable within itself), he displayed an astonishing sharpness and unbelievable insight. You will find both in this book. Happy readings.
Snarky assholes should present these arguments to their seventh grade algebra teachers: but this is all impossible! why bother? formal axiomatics is undecidable!
Aug 24, 2012 David Joseph rated it it was amazing This review has been hidden because it contains spoilers. To view it,
click here. It does necessarily follow from the valid statement "2+2=4" that some other statement is equally valid, but not necessarily so. Weird. One can apply a
variety metalogical thinking strategies to deductive sytems and... blah blah blah. For sure, hard thinkin' leads straight to this proof, but thinking hard alone will not really make it clear. Also weird. This is the most difficult text I've ever read. I picked it up thinking I could develop an understanding of it through a careful reading. I didn' It does necessarily follow from the valid statement "2+2=4" that some other statement is equally valid, but not necessarily so.Weird. One can apply a variety metalogical thinking strategies to deductive sytems and... blah blah blah. For sure, hard thinkin' leads straight to this proof, but thinking hard alone will not really make it clear. Also weird. This is the most difficult text I've ever read. I picked it up thinking I could develop an understanding of it through a careful reading. I didn't realize that a careful reading was going to require the mastery of such a counter-intuitive language. In the end it required of me, a lot of humility and a bunch of sharp pencils and notebook paper. )Oh ,and flashcards. And Hofstadter! ...more
Aug 06, 2015 Alamir rated it it was amazing I read this book in 2011 and four years later I have come to realize it's probably one of the top ten most influential books I've ever read (not that I have a list). Judging by some of the other reviews on here, I'm afraid that readers may feel overwhelmed by his more in-depth equations and may give up on the book. If that's the case, my advice would be to try to first understand his greater argument and then you can always return to his equations to drill down further. I read this book in 2011 and four years later I have come to realize it's probably one of the top ten most influential books I've ever read (not that I have a list). Judging by some of the other reviews on here, I'm afraid that readers may feel overwhelmed by his more in-depth equations and may give up on the book. If that's the case, my advice would be to try to first understand his greater argument and then you can always return to his equations to drill down further. ...more
A challenging exercise of reading this in English and following the proof. Amazing how significant exposure to even mathematics in a native language makes the difference
I thought it was quite interesting, but I don't feel I have the necessary background in math to
completely appreciate this work. Gödel makes up his own notations, but follows some standards for mathematical logic. It helped that the book had references to what it was talking about in the book itself though, and it is also extensively footnoted. I though it was a very interesting paper, but like I said, I need a more thorough grounding in logic to fully appreciate it. I will be reading this again I will be reading this again when I can understand it better. Five
out of five for turning the establishment on it's head though. Before this paper, mathematicians assumed it was possible to go and explain everything in math. But you can't explain everything in math using math, so there are some things that are just unexplainable. I probably didn't really get that right, but it matters not.
Jun 03, 2011 Kory rated it really liked it Godel gives one of the most interesting proofs I have seen. The proof itself is hard to read and understand, to say the least. However, the consequences of his proof are incredible.
I first heard of Gödel's theorem from a recorded talk by Alan Watts given at IBM in the late 60's.
The theorem piqued my interest because, apart from the impact it has had on mathematics, I was impressed by the profound ontological implications (as Watts so eloquently expressed). The math in Gödel's paper was well beyond me and I found myself lost in a sea of strange symbols. I take it at the word of the mathemeticians that Gödel's set up works and does in fact prove the limitations of principal The math in Gödel's paper was well beyond me and I found myself lost in a sea of strange symbols. I take it at the word of the mathemeticians that Gödel's set up works and does in fact prove the limitations of principal mathematics. I frequently found
myself on Youtube looking for more digestable forms of the thereom to little avail. There was one video, however, that expressed the theorem (thankfully) in lingusitic terms; imagine you have a sheet of paper. On one side is written the phrase "The statement on the other side of this paper is false." If you flip the paper over, you would find written "The statement on the other side of this paper is true." The paradox is immediately evident and, as the matemetician in the video states,
Gödel expresses this same paradox in mathematical terms. The general application of this theorem, from my position of relative ignorance, seems to imply that you can never understand the entirety of a system without being able to step outside of the system. As Watts so concisely said "you can't see the back of your own head with your naked eye." I think this concept represents a massive obstacle in the path of artificial intelligence - never will we be able to recreate our conciousness
artificially without being able to step outside the axioms of our conciousness. So too, the implications this has when one considers the origin of language leads one to rather interesting ontological musings. In summary, this along with similarly categorized concepts I've learned from David Hilbert (Hilbert Space), Benoit Mandelbrot (Mandelbrot's set), and Newton (1st Law of Thermodynamics) are all, in my estimation, substantial proofs for an unbounded exisitence contained and governed by
a force much greater than ourselves. On a brief side note, this paper also introduced me to the concept of metamathematics. A mind-blowing concept and a subject I look forward to exploring further.
Kurt Gödel was a genius and his paper is proof of that fact. Even after reading it twice I cannot say with certainty I understood
everything from these 26 pages, but I believe I got the gist of it. The title, in English “On Formally Undecidable Propositions of Principia Mathematica and Related Systems”, sounds a little bulky, but the text (the words that surround the formulas) is quite accessible. As for the formulas: They look kind of nice on paper, and they carry a certain kind of nostalgic cha Even after
reading it twice I cannot say with certainty I understood everything from these 26 pages, but I believe I got the gist of it. The title, in English “On Formally Undecidable Propositions of Principia Mathematica and Related Systems”, sounds a little bulky, but the text (the words that surround the formulas) is quite accessible. As for the formulas: They look kind of nice on paper, and they carry a certain kind of nostalgic charm (coming from almost 90 years ago when mathematical formulas looked a
lot different than today), but, frankly, I skipped many of those. To explain what Gödel found, one has to first understand what a formal system is. A formal system is a closed system in which mathematical statements can be proven. Each formal system consists of: The axioms themselves are also statements of the system, but they cannot be proven. They are believed to be true, or better yet, the axioms are true by definition. [For instance in the formal system of arithmetic, there are only five of those axioms, the so-called Peano axioms) which basically describe the set of
natural numbers]. It’s important to note that every well-formed statement of the system (=every word of the system’s “language”) is either true or false – it cannot be both, nor can it be neither. This implies that each statement is either true or its negation is true. If you set up a formal system there are two desirable properties you want it to have: For a formal system that is complete and consistent, the terms truth and provability are one and the same. Although there are statements, for example in the system of arithmetic
(like the famous Goldbach conjecture), that are notoriously hard to prove, mathematicians believed this system to be complete as well as consistent. It would only be a matter of time before someone will come up with a valid prove of those hard statements, and there’s no such thing as ignorabimus in the field of mathematics, as David Hilbert put it in his program on mathematics: “a proof that all true mathematical statements can be proven in the formalism.” That was the state of
affairs when Godel entered the stage. In his paper, published in 1931, Gödel demonstrated that in a formal system of sufficient complexity (like the one on arithmetic), there will be necessarily statements which are true, but cannot be proven within the system. Such a system must therefore be incomplete! What Gödel did, was to assign numbers to statements (in general to each mathematical object of the system), and through this kind of “Gödelisation” (or Gödel-numbering as it is now known)
he was able to phrase statements about statements within the system itself. At the core of his proof Gödel constructed a statement (a Gödel-number) S that basically says about itself “I am not provable (within my system).” Since S is a valid statement it must necessarily be either true or false, like any other statement. If S were false: that would mean the opposite of S is true, or, in other words, S would be provable. So there’s a false statement
that is provable and this renders the formal system I know this all sounds pretty out of touch with the real world for most people, but Gödel’s incompleteness theorems (there are two of those, the second one stating that a formal system cannot prove its own consistency) had a huge impact in the field of mathematics and beyond, and I personally like the fact that someone was able to put
things into perspective and that there are indeed things which can never be known. PS: The above mentioned Goldbach conjecture is still not proved until today. It states that every even integer number N greater than two can be written as the sum of two prime numbers p and q (like 4=2+2, 6=3+3, 8=3+5, or 444=131+313 etc.), and it occurred to me that, if it would be possible to prove that this conjecture cannot be proven (within
its formal system), the conjecture must be true, because otherwise there would only be finitely many examples for the equation N=p+q, and those can surely be formulated within the system of arithmetic. Strange.
Aug 31, 2020 Mkawass rated it it was amazing This book is quite short, but it is also very deep. Kurt Gödel was a mathematician back in the 1930s that had an idea. He grew up during a time where it was thought that everything could be explained through mathematics and that mathematics itself would be "complete." However, Kurt Gödel comes up one fine day in 1931 or so and publishes this little paper explaining that there are ideas that can't be expressed in the language of mathematics. Using the language developed by Bertrand Russell and Al This book is quite short, but it is also very deep. Kurt Gödel was a mathematician back in the 1930s that had an idea. He grew up during a time where it was thought that everything could be explained through mathematics and that mathematics itself would be "complete." However, Kurt Gödel comes up one fine day in 1931 or so and publishes this little paper explaining that there are ideas that can't be expressed in the language of mathematics. Using the language developed by Bertrand Russell and Alfred North Whitehead, Kurt Gödel establishes basic math and then proceeds to tear it down. A tour de force of logic. ...more
I *read* this book. As to mean I followed the ideas and propositions presented here but to be frank could not distinguish the connection in parts of the proposition and not assess the accuracy of them. Regardless it remains an okay pamphlet and an elaborate explanation of the simple categorical impotency of rigid mathematical collections. True to the tradition of Philosophical Investigations of Wiggy the elusive signs are meant for those that are already enthralled by them. The myth of one geniu I *read* this book. As to mean I followed the ideas and propositions presented here but to be frank could not distinguish the connection in parts of the proposition and not assess the accuracy of them. Regardless it remains an okay pamphlet and an elaborate explanation of the simple categorical impotency of rigid mathematical collections. True to the tradition of Philosophical Investigations of Wiggy the elusive signs are meant for those that are already enthralled by them. The myth of one genius german mathematician eschewing and ruining any ground for mathematics to stand on is also too sweet for most to pass. ...more
Sep 16, 2017 Msalem rated it really liked it Straightforward and clear but otherwise hampered by a needless and often disorganized introduction in the first half.
Feb 11, 2018 Gary rated it it was amazing I understood little of it, but I wanted to find out what I needed to learn in order to understand. Godel’s theorems are stunning.
The most important result in logic's history. The introduction is a great explication of the thought process behind Godel's result. The most important result in logic's history. The introduction is a great explication of the thought process behind Godel's result. ...more
Jun 22, 2012 Vladimir rated it it was amazing This is the hardest text that I have ever read in my life. The result is revolutionary, and it is worth all the effort. Because of the conceptual density of the book, I needed to read it many times to get acquainted with the notation and to realize indeed how beautiful the proof is: all concepts introduced are so cleverly used that the proof is minimalistic and inevitable and its main result is compelling in its force and implications.
Dec 16, 2010 Guy M rated it it was amazing The symbols of Godel's formal logic are outdated and bizarre to the modern reader, but it's still an absolutely essential text. Other books describe the findings of what is one of the most remarkable discoveries of modern times in Godel's incompleteness proofs, but actually watching it unfold over the course of 40 or so pages is remarkable. The symbols of Godel's formal logic are outdated and bizarre to the modern reader, but it's still an absolutely essential text. Other books describe the findings of what is one of the most remarkable discoveries of modern times in Godel's incompleteness proofs, but actually watching it unfold over the course of 40 or so pages is remarkable. ...more
Mar 16, 2014 Mitch Allen rated it it was amazing The classic math destroying argument presented in the original proofs. The implication of this work is far more interesting to me than the proofs themselves, but it's a powerful work. The classic math destroying argument presented in the original proofs. The implication of this work is far more interesting to me than the proofs themselves, but it's a powerful work. ...more
Sep 24, 2015 Dr Matt rated it it was amazing A classic of logic and, when generalized, philosophy. Profound and brilliant.
I first tried to tackle Kurt Gödel's proof as an undergrad mathematics student. We didn't cover it as part of our coursework. I didn't understand all of it - had to use some helper texts. One of the greatest treatises in mathematical logic of all time. There are better explanations of it, but nevertheless, this is the real-deal. I first tried to tackle Kurt Gödel's proof as an undergrad mathematics student. We didn't cover it as part of our coursework. I didn't understand all of it - had to use some helper texts. One of the greatest treatises in mathematical logic of all time. There are better explanations of it, but nevertheless, this is the real-deal. ...more Kurt Gödel was an Austrian-American logician, mathematician and philosopher. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the 20th century, a time when many, such as Bertrand Russell, A. N. Whitehead and David Hilbert, were pioneering the use of logic and set theory to understand the foundations of mathematics. Gödel i Gödel is best known for his two incompleteness theorems,
published in 1931 when he was 25 years of age, one year after finishing his doctorate at the University of Vienna. The more famous incompleteness theorem states that for any self-consistent recursive axiomatic system powerful enough to describe the arithmetic of the natural numbers (Peano arithmetic), there are true propositions about the naturals that cannot be proved from the axioms. To prove this theorem, Gödel developed a technique now known as Gödel numbering, which codes formal expressions
as natural numbers. He also showed that the continuum hypothesis cannot be disproved from the accepted axioms of set theory, if those axioms are consistent. He made important contributions to proof theory by clarifying the connections between classical logic, intuitionistic logic, and modal logic. Related ArticlesNeed another excuse to treat yourself to a new book this week? We've got you covered with the buzziest new releases of the day. To create our... Welcome back. Just a moment while we sign you in to your Goodreads account. What is an undecidable proposition?In foundations of mathematics: Recursive definitions. … formal mathematical system will contain undecidable propositions—propositions which can be neither proved nor disproved.
Is Principia Mathematica outdated?Newton's Principia is hideously out of date, and it bears no relation to how physics is done by anyone today—or for the past couple hundred years. It's not even clear that it bears much relation to how Newton did physics. For a start, the book involves no calculus.
Why did the Principia Mathematica fail?Russell and Whitehead's P.M. was an attempt to formulate all of mathematics solely in terms of formal logic. This ambitious project failed when Kurt Gödel proved his incompleteness theorems , which demonstrated that P.M. could never achieve its goal.
What was Godels statement?In 1931, the Austrian logician Kurt Gödel published his incompleteness theorem, a result widely considered one of the greatest intellectual achievements of modern times. The theorem states that in any reasonable mathematical system there will always be true statements that cannot be proved.
|
On formally undecidable propositions of principia mathematica and related systems
direito autoral © 2024 cemle Inc.
