Hacker News Reader

Comment by thisrod | Hacker News Reader

> All statements are true, false, arbitrary, or nonsensical.

In which category do you place the arithmetical statement that Godel showed how to construct?

Godel constructed statements S that are neither true nor false (more precisely, you could add an axiom saying "S is true", or you could add an axiom saying "S is false", and you'd get a consistent logical system either way).

It turns out that if you can prove something is both true and false, then EVERYTHING is both true and false. For example, let's say you want to prove X. Note that Y is true. But then you obtain a contradiction (since Y is false)! Hence X is true.

"Godel constructed statements S that are neither true nor false"

No, that's not what he did.

He constructed a statement that is true, but that can't be proved in a certain logical system. The statement was basically "This statement is unprovable with these axioms", which can either be proved - meaning you've proved something false, or can't be proved, meaning the statement is true, but is unprovable.

Note that this uses two notions of "true" - provable (can be derived from axioms), and actually true.

> Note that this uses two notions of "true" - provable (can be derived from axioms), and actually true.

Even the second notion of truth actually just semantic consequence of the second-order theory of the naturals, which is a mathematical formal concept, not quite the same as actual (ontological) truth.

You assume that proof by contradiction always works, but is that necessarily the case?

It was a true statement. (It's not provable, but we should not expect to be able to prove all true statements)

I've been meaning to ask, what does it mean to say that a mathematical theorem is true but not provable?

I thought Goedel Sentences are true in the sense of being provable within a "larger" system of axioms.

For e.g. the continuum hypothesis, there are models which obey the ZFC axioms in which it is true and models which obey the axioms in which it is false. The Gödel sentences are less interesting; any model in which those sentences were false would be a model in which PA was inconsistent. Which sure, can exist (e.g. the "self-hating theory", PA plus the axiom that PA is inconsistent, is a somewhat legitimate set theory with some interesting properties). So saying the Gödel sentences are true was not entirely accurate; rather, it depends which model we're working with. But a model which declares PA is inconsistent doesn't seem like the sort of model that we'd want to do physics with.

You're right that there are "larger" theories that can prove the consistency of PA, e.g. PA + existence of a large cardinal proves the consistency of PA. But, per Gödel, no consistent axiom system large enough to contain PA can prove its own consistency. This is probably a lot less bad than it sounds though; after all, if we have some unknown axiom system T, and we have a proof in T that T is consistent, does that really tell us anything? Because if T isn't consistent, then it can prove anything, including that T is consistent.

Ok, now here's a question: are there any textbooks introducing model theory and talking about these sorts of topics that don't rely on preexisting knowledge of abstract algebra? Not that I don't want to learn abstract algebra, but I don't even know a good textbook to start that from.

Reply on news.ycombinator.com