Gödel, Escher, Bach: an in-depth explainer

Post by butokai » Tue, Sep 20, 2022, 2:40 PM UTC

adastra22 wrote: post #134

mreid wrote: post #93

Earlier quoted context omitted.

It might be easiest to give a sense of what "unprovable but true" means by way of an imagined example. Goldbach's conjecture is that "every even number bigger than 2 is the sum of exactly two prime numbers", so 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, etc. For this statement to be *true* it just means that every even number there must exist two primes that add to that number. This is a statement about infinitely many integer…

I’ve only ever seen examples like the one you give here, which seem like trite, trivial, and uninteresting middle-school level logical gotchas. Are there actually interesting properties which are true but can’t be proven? Or is it just a statement about self-referential recursive logic being unprovable?

Harvey Friedman, one of the most renowned contemporary logicians, has a research program devoted to finding such examples as those you seem to be looking for. This article presents his views: https://nautil.us/this-man-is-about-to-blow-up-mathematics-2...

Post by black_knight » Wed, Sep 21, 2022, 7:31 PM UTC

trashtester wrote: post #237

black_knight wrote: post #213

Earlier quoted context omitted.

Not sure what you are thinking of here. In first order logic if something is true in all models it is also provable. This is called completeness. And is one of the sanity requirements of a semantics.

I was thinking that something could be true and undecidable (as for the halting problem). I'm somewhat on thin ice on the mathetematical formulation, but I suppose something could be undecidable but true with respect to all standard models of a theory, while not true for some non-standard model. For instance, there may be statements acting on infinite sets (such as N) that may not be compressed into a recoursive form…

> I'm somewhat on thin ice on the mathetematical formulation, but I suppose something could be undecidable but true with respect to all standard models of a theory, while not true for some non-standard model.

The term "standard model" is interesting, because it pushes the problem a bit. So, let us take the natural numbers. Sure, we can prove in set theory that some of the undecided statements of Peano arithmetic are true for the standard model. But seen from the outside this means that we have changed our axiomatic system from Peano arithmetic to set theory. But there are still undecided statements – even arithmetic ones – in this new system! These will hold in some models of set theory, while being false in some other.

So, saying “Oh, I mean the standard ℕ, not any of those other ones” does not get us off the hook, because it raises the question: “The standard ℕ... in which model of ZF?”

Re: Gödel, Escher, Bach: an in-depth explainer

Re: Gödel, Escher, Bach: an in-depth explainer