3 ms·

> In the final analysis, we may appeal to the Gödel Incompleteness Theorems and conclude that in every logic there are statements which are true, but not provab

> In the final analysis, we may appeal to the Gödel Incompleteness Theorems and conclude that in every logic there are statements which are true, but not provable, or provable, but not true. Is this wrong? "true but not provable" is easy. What is an example of a statement that is "provable but not true"?

jeapostrophe 13y ago
It's true. The theorems are a statement about the logics. Most of the time when you design a logic, you get to "choose" which case you'll get. Most people choose "true but not provable" because that's a little useful. It would be very bad to choose "provable but not true", because then you could never trust any conclusions of the proof system. - the author
freyrs3 13y ago
Poorly worded, and a bit disingenuous to bring Gödel's theorem in this context. Taken to it's logical conclusion, by his argument we shouldn't bother analyzing the properties of programs at all.
cmhamill 13y ago
"Provable but not true" statements only arise in logical systems which are inconsistent, so it's fairly normal to not be able to come up with one. So you need to assume two contradictory things are true, somewhere deep down in your logical system. As a trivial example, assume that both the following are true: 1. I am a robot. 2. I am not a robot. And our false statement which we are going to prove is: Pizza is made of fear. We know that the following proposition is true: I am a robot OR pizza is made of fear Because we know that I am not a robot, the first term in the above must be false, and so the second term must be true. Therefore, pizza is made of fear. That's really more an example of the principle of explosion, but the above is a tiny logical system which contains statements that are provable, but not true. In practice, we tend to use logical systems which can't prove all true statements, but don't let you prove false ones. Much more useful, really.

jeapostrophe 13y ago

It's true. The theorems are a statement about the logics. Most of the time when you design a logic, you get to "choose" which case you'll get. Most people choose "true but not provable" because that's a little useful. It would be very bad to choose "provable but not true", because then you could never trust any conclusions of the proof system. - the author

freyrs3 13y ago

Poorly worded, and a bit disingenuous to bring Gödel's theorem in this context. Taken to it's logical conclusion, by his argument we shouldn't bother analyzing the properties of programs at all.

cmhamill 13y ago

"Provable but not true" statements only arise in logical systems which are inconsistent, so it's fairly normal to not be able to come up with one. So you need to assume two contradictory things are true, somewhere deep down in your logical system. As a trivial example, assume that both the following are true: 1. I am a robot. 2. I am not a robot. And our false statement which we are going to prove is: Pizza is made of fear. We know that the following proposition is true: I am a robot OR pizza is made of fear Because we know that I am not a robot, the first term in the above must be false, and so the second term must be true. Therefore, pizza is made of fear. That's really more an example of the principle of explosion, but the above is a tiny logical system which contains statements that are provable, but not true. In practice, we tend to use logical systems which can't prove all true statements, but don't let you prove false ones. Much more useful, really.