3

Is this a settled (as much as it can be) philosophical area? I feel like I understand that there will always be incompleteness for a finite set of axioms trying to capture all of arithmetic. But I want to know if incompleteness about arithmetic goes as far to say, any representation, which is all we humans have of the world (even the thinking of a mathematical proposition), of arithmetic will have these problems, and then if arithmetic without representation (as far as we can grasp) is fully clear of incompleteness.

^By arithmetic I mean all and only the truths of that infinitely extended line of natural numbers with their normal arithmetic operations we all know of.

^^of course by "problem" I just mean where is incompleteness located

J Kusin
  • 2,668
  • 1
  • 7
  • 15
  • 1
    There is an accessible discussion of this by Armstrong on Less Wrong. Second order arithmetic has a single full model, so it "captures" all of arithmetic in a sense, but it has no algorithmic proof procedure, so you still cannot prove every truth of arithmetic in it. If you embed arithmetic into ZFC, while many unprovable true statements become provable, some of them remain unprovable. We can "capture" it only in unprovable ways. – Conifold Jan 08 '24 at 05:52
  • Thanks everybody – J Kusin Jan 08 '24 at 18:29

3 Answers3

3

Arithmetic itself — the natural numbers, the addition and multiplication operations — is not incomplete; (in)completeness is a property of theories, not models, and the natural numbers are a model. However, by Gödel's reasoning, every theory of the natural numbers is either too weak to describe addition and multiplication, inconsistent, or incomplete.

This has mathematical consequences. Most notably, some questions about mathematical structures are fully arithmetizable, like the famous question about P and NP; see Aaronson's evergreen article on the topic for details and discussion.

Corbin
  • 803
  • 5
  • 16
  • 2
    I like to word it as: either too weak to describe addition and multiplication, or so strong that it can describe more things than it can prove; or even stronger than that, in which case it can prove everything and its opposite. – Stef Jan 07 '24 at 09:05
  • Does it make sense to ask about theories of natural numbers which can or can't Godel encode? – J Kusin Jan 08 '24 at 02:11
  • 1
    @JKusin: Those are covered under "too weak". For gory details, see e.g. Chapter 7 (p49-52) of Smith 2007, or any other explainer. – Corbin Jan 08 '24 at 17:57
1

The incompleteness theorems are about "first order" theories and automatic theorem provers in general. The natural setting for arithmetic is a second order theory, the formulation of the induction axiom in the first order settings is an axiom scheme that in unable to express the full power of the second order induction principle. On the other hand the second order theory doesn't provide a recursive deductive system.

Marco Disce
  • 522
  • 3
  • 8
0

Arithmetic is just fine. Most of mathematics is just fine.

“Incompleteness” means there are statements that at true / false but cannot be proven to be true / false. There are many statements that have not been proven true or false. Some are just boring and nobody bothered. Some are hard enough to prove but not quite important enough to spend too much time. Some are very hard to prove, but mathematicians believe that eventually someone might find a proof. And some are so chaotic that mathematicians believe they might be true but not be provable. And Gödel added just one tiny group: Statements that are true but not provable.

gnasher729
  • 5,515
  • 11
  • 17
  • can we go as far to say any representation of arithmetic, not just the ones math trusts, will have incompleteness? – J Kusin Jan 06 '24 at 19:38
  • 2
    "Statements that are true but not provable" is not accurate, the correct thing to say is "For any given formal theory there are Statements that are true but not provable in that formal theory" – Marco Disce Jan 07 '24 at 14:45