What is Godel: Definition and 42 Discussions

Kurt Friedrich Gödel (; German: [ˈkʊɐ̯t ˈɡøːdl̩] (listen); April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher. Considered along with Aristotle and Gottlob Frege to be one of the most significant logicians in history, Gödel had an immense effect upon scientific and philosophical thinking in the 20th century, a time when others such as Bertrand Russell, Alfred North Whitehead, and David Hilbert were using logic and set theory to investigate the foundations of mathematics, building on earlier work by the likes of Richard Dedekind, Georg Cantor and Gottlob Frege.
Gödel published his first incompleteness theorem in 1931 when he was 25 years old, one year after finishing his doctorate at the University of Vienna. The first incompleteness theorem states that for any ω-consistent recursive axiomatic system powerful enough to describe the arithmetic of the natural numbers (for example Peano arithmetic), there are true propositions about the natural numbers that can be neither proved nor disproved from the axioms. To prove this, Gödel developed a technique now known as Gödel numbering, which codes formal expressions as natural numbers. The second incompleteness theorem, which follows from the first, states that the system cannot prove its own consistency.Gödel also showed that neither the axiom of choice nor the continuum hypothesis can be disproved from the accepted Zermelo-Fraenkel set theory, assuming that its axioms are consistent. The former result opened the door for mathematicians to assume the axiom of choice in their proofs. He also made important contributions to proof theory by clarifying the connections between classical logic, intuitionistic logic, and modal logic.

View More On Wikipedia.org
  1. edmund cavendish

    A P vs NP & Godel | A Comprehensive Guide

    I think the essence is captured above.
  2. Giulio Prisco

    A Can Gödel's Theorem Inform Our Understanding of Physical Reality?

    What does Gödel’s theorem say about physical reality? Does Gödel’s theorem imply that no finite mathematical model can capture physical reality? Does the nondeterminism found in quantum and chaos physics - it’s impossible to predict (prove) the future from the present and the laws of physics -...
  3. PeterDonis

    I Does rotation in Gödel spacetime depend on the frame of reference?

    [Moderator's note: Thread spun off to allow discussion of this topic to continue since the previous thread was closed.] I have had something nagging at me about this for a while, and it finally hit me while looking through this paper about the Godel Universe...
  4. M

    MHB Is this a Gödel number of a Turing machine?

    Hey! :o We have the number \begin{align*}70&6737922567786324304462189150536772513339293263220644 \\ &=2^2\cdot 3\cdot 59^5\cdot 103\cdot 149^2\cdot 353\cdot 607\cdot 823^4\cdot 1409\cdot 1873^2\cdot 4201^3\end{align*} I want to check if this is a Gödel number of a Turing machine. From...
  5. S

    I Godel metric in a cylindrical chart

    Can someone express the Godel metric line element in cylindrical coordinates? I keep looking for this line element, but no source clearly gives it to me. Can you please express it using the (- + + +) signature and while retaining all c terms? Thanks. Here is the line element in Cartesian...
  6. Look

    MHB Gödel Number Usefulness to Determine an Infinite Set's Completeness

    Gödel numbers are used to encode wffs of formal systems that are strong enough in order to deal with Arithmetic. In my question, Gödel numbers are used to encode wffs as follows: Syntactically (by formalism without semantics) there is set A (the set which is postulated to be infinite), such...
  7. Posty McPostface

    I Loophole in Godel's Incompleteness Theorem?

    Gödel's incompleteness theorem only applies to logical languages with countable alphabets. So it does not rule out the possibility that one might be able to prove 'everything' in a language with an uncountable infinite alphabet. Is that a loophole in Godel's Incompleteness Theorem? Doesn't...
  8. G

    Why is the Gödel Universe Rotating

    Homework Statement Consider the Godel Metric in spherical coordinates as on page 6 here; ds^2=4a^2\left[-dt^2+dr^2+dz^2-(\sinh^{4}(r)-\sinh^{2}(r))d\phi^2+2\sqrt{2}\sinh^{2}(r)dt d\phi)\right] This is a solution to Einstein's Equations if we have ##a=\frac{1}{2\sqrt{2\pi\rho}}## and ##\Lambda...
  9. PetSounds

    GEB: Exploring Douglas R. Hofstadter's Strange Loops

    Lately, I've been hooked on Douglas R. Hofstadter's book Gödel, Escher, Bach. In it, he discusses the idea of "strange loops"—often apparent logical paradoxes—and argues that they are the key to understanding consciousness. He includes witty dialogues, as well as examples of "strange loops" in...
  10. Demystifier

    I Exploring the Philosophical Implications of Godel's Incompleteness Theorems

    Consider the following sentence: "Prof. Godel cannot prove this sentence." Is this sentence true? If it is true, can Prof. Godel prove it? If he can't, does it tell us anything about Prof. Godel? More generally, does it tell as anything about creative human mathematicians (who are supposed to be...
  11. N

    Help me Prove that such a set does NOT exist

    Let Q denote the theory of Robinson Arithmetic. A theory T is nice iff T is consistent, is p.r. adequate and extends Q. The fixed-point lemma states that for all nice theories T, for any formula φ, there is a sentence σ such that T ⊢σ↔φ("σ")...
  12. arupel

    A How Does Gödel's Diagonalization Relate to Proofs in Peano Arithmetic?

    I can readily accept that the Godel sentence The theorem is that "This theorem is not provable" can be expressed in the language of Peanno Arithmetic. 2. Godel on the other side of a correspondence with the above, first translates the Godel sentence using the Godel numbering system 3. Having...
  13. S

    I Noticing CTC's / time travel in a Godel space-time

    I have been working with the Godel solution to the Einstein field equations which is known to contain closed time-like curves. The metric I am using is the following: ds2 = dt2/(2ω2) + (exdzdt)/ω2 + (e2xdz2)/(4ω2) - dx2/(2ω2) - dy2/(2ω2) This is sign convention (+ - - -) Now from what I've...
  14. Math Amateur

    MHB Gödel Numbering - Exercise 3.2.5 - Chiswell and Hodges

    I am reading the book Mathematical Logic by Ian Chiswell and Wilfred Hodges ... and am currently focused on Chapter 3: Propositional Logic ... I need help with Exercise 3.2.5 which reads as follows:Can someone please help me with reconstructing the formula of the Gödel number that is given...
  15. S

    Weyl tensor for the Godel metric interpretation

    I have recently derived both the purely covariant Riemann tensor as well as the purely covariant Weyl tensor for the Gödel solution to Einstein's field equations. Here is a wiki for the Gödel metric if you need it: http://en.wikipedia.org/wiki/Gödel_metric There you can see the line element I...
  16. I

    Godel's Theorem, What's it really saying?

    Hi, So I was just going through my copy of The Emperor's New Mind, and I'm having a little difficulty accepting Godel's theorem , at least the way Penrose has presented it. If I'm not wrong, the theorem asserts that there exist certain mathematical statements within a formal axiomatic system...
  17. S

    Godel Metric Cosmological Constant

    What is the cosmological constant for the Godel metric?
  18. S

    Type Godel Metric Line Element - Get Help Here!

    Can someone please type out the line element for the Godel metric (including any and all c terms and any other terms that one might omit if they were using natural units to set terms like c = 1)? I ask this because different sources on line have it written out in different ways which look...
  19. T

    Which Godel statements are seen to be true by humans?

    My questions arose when reading an article about artificial intelligence, and the argument of Penrose that says that humans can see the truthfulness of statements that machines cannot. But it doesn't say what those "Godel sentences" are...
  20. nomadreid

    Decoding Gödel Numbers for Sequences: A Constructive Approach

    First, this is not the same question as https://www.physicsforums.com/threads/goedel-numbering-decoding.484898/ It concerns a different encoding procedure, hence a different decoding one. My question concerns the argument in http://en.wikipedia.org/wiki/G%C3%B6del_numbering_for_sequences for...
  21. Demystifier

    A confusion about Godel theorem and real numbers

    I am confused, since some claims about the first Godel incompleteness theorem and real numbers seem mutually contradictory. In essence, from one point of view it seems that the Godel theorem applies to real numbers, while from another point of view it seems that the Godel theorem does not apply...
  22. F

    About Gödel incompleteness theorem

    I'm a starting amateur mathematician. I'm studying Gödel's incompleteness theorem and have a couple of rookie questions that I can't seem to sort out. 1) In the text I'm reading it talks repeatedly about systems containing "addition and multiplication". Since multiplication can be derived from...
  23. nomadreid

    Is Gödel numbering a first or second order function?

    Gödel-numbering (in its broadest meaning, not necessarily the one Gödel used): On one side, it would seem that an assignment of a symbol to a number is just a first order function, and the recursion set up to translate a formula into numbers would be first-order, but on the other hand the...
  24. ferst

    Gödel Metric Theses & Dissertations: 3 in Eng/Port, 1 in Portuguese

    Hi, I'm doing the master in science and one of things that I have to study is the Gödel metric. His paper have a high level for me and I'm seeking theses and dissertations about the Gödel universe. At moment I got three theses about the subject in english and portuguese-BR and one dissertation...
  25. J

    Proof of the existence Godel Statement (With no numbering)

    P(x) = "x is Provable" axiom 1 : P(x)→x "Statement x can be proven true." 1. (x∧¬x) consider a contradiction 2. x simplification(1) 3. ¬x simplification (1) 4. x∨∀sP(s) addition (2) 5. ∀sP(s) disjunctive syllogism (3,4) 6. (x∧¬x)→∀sP(s) conditional proof (1,5) "Anything is provable if it follows...
  26. J

    Assigning Godel Numbers to Turing Programs

    I am working through a computability theory textbook and right now the author is discussing assigning Godel numbers to each Turing Program. To do this, he suggests assigning each internal state, each of the elements of {1,B} and each of the elements of {L,R} a number. Then using these numbers...
  27. jfy4

    Geodesic Motion for the Gödel Space-time

    (Hopefully, Part 1 of 2) This is one of my favorite metrics, and I decided that while tedious, and old-fashioned, I would practice for my GR studies by finding the Christoffell symbols and write out the equations for geodesics using the Gödel metric, then attempting to solve them. First...
  28. A

    How to Decode a Natural Number Back into a Sequence Using Gödel Numbering?

    I'm ok with encoding, but I m confused about decoding a natural number back into a sequence of natural numbers. For example, to decode a natural number N back to the sequence <x1,x2,...xn>
  29. P

    Gödel vs Goldbach: Truth but Not Provability?

    I was once told that Goldbach's conjecture could perhaps fall into Gödel's first incompleteness theorem, and be true but not provable. Is that really the case? I mean, if Goldbach's conjecture were false it would be easily provable, as it would mean that an even number exists that is not the...
  30. B

    Godel and The Philosophy of Special Relativity

    Burton Feldman, in his book "112 Mercer Street" (Einstein's address during his tenure at Princeton) tells of a comment that Einstein made to a friend: "...when he felt old and his own work no longer meant much, he came to the Institute mostly for the privilege of walking home with Godel." Godel...
  31. E

    Does Godel's Incompleteness Theorem Apply to Fuzzy Sets?

    Hello all Does Godel's incompleteness theorem still hold true for fuzzy sets? My feeling is that it doesn't since the http://en.wikipedia.org/wiki/Law_of_excluded_middle" no longer applies. Is this reasoning correct?
  32. George Jones

    Wolfgang Rindler: Godel's Remarkable Excursion into Cosmology

    Wolfgang Rindler has an interesting article, Godel, Einstein, Mach, Gamow, and Lanczos: Godel's remarkable excursion into cosmology, in this month's American Journal of Physics. Rindler writes about the history, context, philosophy, and physics of Godel's work. Unfortunately, this paper is...
  33. DaveC426913

    Godel Escher Bach: Interesting number sequence

    I've been re-reading https://www.amazon.com/dp/0465026567/?tag=pfamazon01-20 and came across an interesting algorithm. Start with any whole number. If it is even, halve it. If it is odd, triple it and add 1. Repeat until the number reaches 1. Count # of steps it took. Number/Count...
  34. Demystifier

    Explaining Godel's Theorem: Intuitive Explanation w/o Math

    The essence of the 1. Godel theorem can be reduced to the fact that one can always find a self-referring sentence. It is intuitively clear that such sentences lead to problems, which, indeed, is the source of the Godel theorem. Can someone explain to me why it is not possible to construct a...
  35. T

    Godel incompletness related to physics?

    can anybody shed light on this paper? http://arxiv.org/abs/0705.0147
  36. T

    How Do Gödel's and Tarski's Theories Impact Our Understanding of Knowledge?

    Hi, I'm sorry for being lazy again and asking for help here instead of looking stuff for myself, but I'm being lazy merely because I've tons of other stuff to read. What I want to understand is: 1) Under what conditions does Gödel's incompleteness theorem 1 hold? (That for theories...
  37. P

    Medical Does the Godel theorm disallow computers with minds?

    Penrose seems to argue that computers will never have minds or understanding as humans do due to Godel's Incompleteness theorem. I think he is right about this one as computers just are formal systems. But why then are there still so many critics that claim that AI is possible?
  38. M

    Truth and Justification in light of Godel

    I was thinking about Godel's Incompleteness Theorem and was wondering if this is a fair conclusion: Godel seems to have demonstrated that within axiomatizations of arithmetic, that is of a sufficiently rich axiomatized system which could generate arithmetic, there are statements which can not...
  39. H

    Mathematica Godel and the Nature of Mathematical Truth

    Godel and the Nature of Mathematical Truth A Talk with Rebecca Goldstein http://edge.org/3rd_culture/goldstein05/goldstein05_index.html A fascinating read! Highly recommended. In addition to discussing Godel's Incompleteness Theorem in the context of his metaphysical views, it also...
  40. A

    Godel - Completeness of axiomatic systems

    I am aware of Godel's proof of the incompleteness of formal systems that allow for defining the natural numbers. I noted recently in the Wikipedia entry for Godel's Incompleteness Theorem "that both the real numbers and complex numbers have complete axiomizations". Is this true? Can...
  41. I

    Retrieving a Gödel Proposition: Exploring Gödel's Theorem

    I was just reading about Godel's Theorem. I was unable to grasp the exact meaning of this sentence: from the paragraph: I don't understand what is meant by "..retruning a Godel proposition.."
  42. U

    Is Godel's system of axioms inconsistent?

    As we cannot prove that Godel's system of axioms (ZFC?) is consistent, is it possible that it is inconsistent, that the Godel sentence is false, and that we yet prove it to be 'true'?