Second-order arithmetic

[Demystifier]

Very nice article on this stuff:
https://www.lesswrong.com/posts/MLq...ss-incompleteness-and-what-it-all-means-first

 

[fresh_42]

Very nice article on this stuff:
https://www.lesswrong.com/posts/MLq...ss-incompleteness-and-what-it-all-means-first

Nice. I only wished he would have mentioned AC when he wrote

"Every (non-empty) set of numbers has a least element."

as his basic phrase to describe second-order language or that he would have called it

"Every (non-empty) set of natural numbers has a least element."

especially as he mentioned the reals. I liked his emphasis on semantics very much.

 

[Bosko]

...
All these statements are considered true, but cannot be formally proved within the system to which they refer. ...

I'm just wondering if something as simple as the Goldbach's conjecture falls under these unprovable truths.
"every even natural number greater than 2 is the sum of two prime numbers"
https://en.wikipedia.org/wiki/Goldbach's_conjecture

Can it be proven that it is undecidable? That there is no proof whether it is true or not.

 

[fresh_42]

I'm just wondering if something as simple as the Goldbach's conjecture falls under these unprovable truths.
"every even natural number greater than 2 is the sum of two prime numbers"
https://en.wikipedia.org/wiki/Goldbach's_conjecture

Can it be proven that it is undecidable? That there is no proof whether it is true or not.

No. I think it is only a matter of time before we can prove (or disprove) it. If it were provably undecidable, people wouldn't still work on attempts to prove it, and we have already achieved partial results. Fermat took over 350 years, Goldbach is currently at 283.

 

[SSequence]

I don't know anything about second-order, so I can't comment much on points related to that.

However, it is worth mentioning that "second-order-arithmetic" can also often refer to a first order theory (often written as $\mathrm{Z}_2$).