Proof of the existence Godel Statement (With no numbering)

[japplepie]

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."?

 

[willem2]

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 which 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.

 

[japplepie]

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?

 

[lugita15]

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.

 

[japplepie]

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.

 

[lugita15]

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.

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.

 

[pwsnafu]

japplepie, do you understand what Godel's theorems say?

 

[japplepie]

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.

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."

japplepie, do you understand what Godel's theorems say?

do you understand what I am saying?

 

[pwsnafu]

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."

That's not what Godel says.

do you understand what I am saying?

That answers why question how?

 

[japplepie]

japplepie, do you understand what Godel's theorems say?

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 I am saying?

 

[pwsnafu]

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 I am saying?

Let me phrase it this way: we have examples of axiomatic theories that are complete and consistent. How does your proof exclude those examples?

 

[lugita15]

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.

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).

 

[japplepie]

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).

That sounds absolutely right, thanks for clearing it up. I guess I need more work on translations.

 

[lugita15]

That sounds absolutely right, thanks for clearing it up. I guess I need more work on translations.

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."