Second-order arithmetic

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

Discussion Overview

The discussion revolves around the properties and implications of second-order arithmetic, particularly in relation to first-order logic. Participants explore the uniqueness of models defined by second-order logic, the completeness of logical systems, and the validity of certain theorems within these frameworks. The conversation touches on theoretical aspects, including Gödel's completeness theorem and Löwenheim-Skolem theorem, as well as philosophical implications regarding the nature of mathematical axioms.

Discussion Character

  • Exploratory
  • Debate/contested
  • Conceptual clarification
  • Technical explanation

Main Points Raised

  • Some participants note that first-order logic is not categorical, which leads to multiple infinite models, while second-order logic aims to address this issue but lacks semantic completeness.
  • There is a discussion about whether Trachtenbrot's theorem or Löwenheim-Skolem theorem apply to second-order logic, with some arguing that they do not due to their relevance only to first-order theories.
  • Participants express confusion regarding the apparent contradiction between Löwenheim-Skolem being invalid in second-order logic and the invalidity of completeness in second-order logic.
  • Some suggest that the original Peano axioms could clarify the discussion when applied specifically to natural numbers.
  • Concerns are raised about the implications of properties that are valid in every model but cannot be proved from axioms, questioning the nature of such properties and their relation to axioms.
  • One participant emphasizes the philosophical significance of the limitations of mathematical models and the nature of axioms as beliefs rather than proven truths.
  • There is a debate about the definition of "valid" in the context of logical systems and whether unprovable properties could be treated as axioms.

Areas of Agreement / Disagreement

Participants express differing views on the applicability of certain theorems to second-order logic and the implications of completeness and validity. The discussion remains unresolved, with multiple competing perspectives on the nature of second-order arithmetic and its properties.

Contextual Notes

Some participants highlight the complexity of the subject matter, indicating that certain mathematical statements may not be easily provable or applicable within the frameworks discussed. There are also references to the philosophical implications of mathematical axioms and their limitations.

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
3K
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 64 ·
3
Replies
64
Views
2K
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