Second-order arithmetic

  • Context: Graduate 
  • Thread starter Thread starter Demystifier
  • Start date Start date
Click For Summary
SUMMARY

The discussion centers on the complexities of second-order arithmetic and its relationship with first-order logic, specifically addressing the Löwenheim-Skolem theorem and Gödel's completeness theorem. Participants highlight that Löwenheim-Skolem is invalid in second-order logic, while completeness is also not applicable, leading to confusion about the implications of these facts. The conversation emphasizes that second-order logic can define unique models, yet certain properties may remain unprovable by axioms, raising philosophical questions about the nature of mathematical truths.

PREREQUISITES
  • Understanding of first-order and second-order logic
  • Familiarity with Gödel's completeness theorem
  • Knowledge of the Löwenheim-Skolem theorem
  • Basic concepts of Peano axioms and their implications
NEXT STEPS
  • Research the implications of Gödel's incompleteness theorems on second-order logic
  • Study the differences between first-order and second-order Peano arithmetic
  • Examine the philosophical implications of unprovable properties in mathematical models
  • Explore the applications of second-order logic in formal systems and model theory
USEFUL FOR

Logicians, mathematicians, philosophy of mathematics scholars, and anyone interested in the foundations of mathematical logic and its complexities.

Physics news on Phys.org
  • #32
Demystifier said:
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.
 
  • #33
Demystifier said:
...
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.
 
  • #34
Bosko said:
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.
 
Reply
  • Like
Likes   Reactions: Bosko
  • #35
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##).
 

Similar threads

Graduate Second order logic and completeness
  • · Replies 11 ·
Replies
11
Views
3K
Undergrad Syntactic vs semantic logical consequence (entailment)
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad What is truth in the completeness theorem?
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad A confusion about axioms and models
  • · Replies 75 ·
3
Replies
75
Views
9K
Undergrad Direct limit of multiverse models of ZFC
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad What Are the Axioms of Fuzzy Logic and How Do They Extend Boolean Algebra?
  • · Replies 7 ·
Replies
7
Views
2K
Is mathematics invented or discovered?
  • · Replies 2 ·
Replies
2
Views
648
Graduate First order logic and set theory: who comes first?
  • · Replies 2 ·
Replies
2
Views
3K
Graduate (Im)possibility to prove the Goodstein's theorem
  • · Replies 4 ·
Replies
4
Views
3K
MHB Is induction a circular way to define natural numbers?
  • · Replies 1 ·
Replies
1
Views
2K