Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof of the existence Godel Statement (With no numbering)

  1. May 20, 2013 #1
    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 from a contradiction."
    7. P(x) universal instantiation (5)
    8. P(¬x) universal instantiation (5)
    9. x axiom 1 (7)
    10. ¬x axiom 1 (8)
    11. (x∧¬x) conjunctional introduction (9,10)
    12. ∀sP(s)→(x∧¬x) conditional proof (5,11)
    "If any statement is a provable, then one can prove a contradiction."
    13. ∀sP(s)↔(x∧¬x) biconditional introduction (6,12)
    14. ∃s¬P(s)↔(¬x∨x) contraposition (13)

    •13. "(All statements are provable) is false."

    •14. "(There exists a statement that is unprovable) is true."


    Does this also imply "There exists no unprovable statement that is false."?
     
    Last edited: May 20, 2013
  2. jcsd
  3. May 20, 2013 #2
    That proof can be done much simpler
    1) Axiom 1: P(x) -> x

    2) P(1=0) -> 1=0 specification (1)

    3) ~1=0 -> ~P(1=0) transposition (2)

    4) ~1=0 well known result

    5) ~P(1=0) modus ponens (3,4)

    So there exists an unprovable statement wich happens to be 1=0.

    It's also false, so the answer to your last question must be: No, there does exist an unprovable statement that is false.
     
  4. May 20, 2013 #3
    P(x) = "x is Provable"
    Is it ok to use an x which is inherently unprovable?

    And does this also mean that the number of provable true statements are smaller than the number of provable false statements?
     
  5. May 20, 2013 #4
    Of course the assumption that any provable statement is true implies that any false statement, like 0=1, is unprovable. That's not a Godel statement. A Godel statement is a TRUE statement that is unprovable, given the assumption that all provable statements are true.

    By the way, in your title you claim to be trying to prove the existence of a Godel statement with "no numbering". Well, a key property of a Godel statement is that it's a statement WITHIN the language of the formal system you're trying to prove is incomplete. Presumably the formal system does not talk about what is provable in that formal system itself, so you can't use "P" in a statement within the formal system. The whole point of Godel numbering is to encode statements ABOUT a formal system into statements WITHIN the formal system.

    What is required to make a Godel statement is a statement within a formal system which encodes a statement about the formal system, which in turn talks about the original statement within the formal system. Making such a statement requires Godel numbering plus some clever thinking. You can see the gory details here. Or to see a more intuitive (yet fully rigorous) presentation of it, you can read Godel Escher Bach by Douglas Hofstadter. Attached is an excerpt from it, although you may not fully understand it if you haven't read the the rest of the book.
     

    Attached Files:

  6. May 21, 2013 #5
    Couldn't the numbering approach be a different way of approaching the same conclusion?

    You could generalize the proof above and state that its true for all systems that use similar logic.
     
  7. May 21, 2013 #6
    As I said, the proof you gave proves something absolutely trivial, that there exists an unprovable false statement (assuming that all provable statements are true). But Godel's theorem is about the existence of an unprovable TRUE statement (again assuming all provable statements are true), and I don't see how you can prove that without Godel numbering.
     
  8. May 21, 2013 #7

    pwsnafu

    User Avatar
    Science Advisor

    japplepie, do you understand what Godel's theorems say?
     
  9. May 21, 2013 #8
    I guess the number 14 of my proof isn't clear to you. (Bad translation, I guess)

    "There exists an unprovable statement if and only if it is true."


    do you understand what im saying?
     
  10. May 22, 2013 #9

    pwsnafu

    User Avatar
    Science Advisor

    That's not what Godel says.

    That answers why question how?
     
  11. May 22, 2013 #10

    What I'm saying is (if you could understand my proof) I'm not proving the theorem, I'm proving one of it's supporting arguments namely the existence of statements that are both true and unprovable.

    (without the gory numbering)


    again..
    do you understand what im saying?
     
  12. May 22, 2013 #11

    pwsnafu

    User Avatar
    Science Advisor

    Let me phrase it this way: we have examples of axiomatic theories that are complete and consistent. How does your proof exclude those examples?
     
  13. May 22, 2013 #12
    But you're not proving that at all. 14 says "(There exists an unprovable statement s) if and only if (x is true or false)", which is equivalent to "(There exists an unprovable statement s) if and only if (A trivially true statement is true)", which is equivalent to "There exists an unprovable statement s." But you have not proved that s is true.

    And as pwsnafu says, you wouldn't possibly be able to prove the existence of an unprovable true statement with a proof like this. After all, there are formal systems, like Tarski's axiom system for Euclidean geometry, for which there are NO unprovable true statements (in the language of the formal system).
     
  14. May 22, 2013 #13

    That sounds absolutely right, thanks for clearing it up. I guess I need more work on translations.
     
  15. May 25, 2013 #14
    Let me correct a couple other translations you made. You translated axiom 1 as "Statement x can be proven true", but really it should be "If statement x can be proven, then it is true." You translated 6 as "Anything is provable if it follows from a contradiction.", but it's unclear what you mean by "it" here. 6 should be translated as "The statement that 'everything is provable' follows from a contradiction."
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof of the existence Godel Statement (With no numbering)
  1. Statement Proof. (Replies: 16)

  2. Godel Numbers (Replies: 3)

Loading...