3 ms·

Not sure where this HN title comes from since it's not the original but I have a gripe with the way it represents Peano's Axioms as THE building blocks of arith

by culi 2y ago

Not sure where this HN title comes from since it's not the original but I have a gripe with the way it represents Peano's Axioms as THE building blocks of arithmetic. Instead of just one of the many attempts at coming up with a set of axioms that can serve as the building blocks of Arithmetic

bediger4000 2y ago
What would some others be? I usually only see Peano's axioms.
- gylterud 2y ago
  There are many axiom systems for natural numbers. My favorites are 1. Heyting Arithmetic, and 2. In category theory, one can characterise the natural numbers and the initial algebra of the X |–> X+1. functor.
  - Koshkin 2y ago
    Sure, one can, but does it help with anything? Just curious.
    - ketralnis 2y ago
      It's up to you if you think it's "better" but it's answering the question of whether Peano axioms are the only fundamental structure
      - Koshkin 2y ago
        Category Theory itself assumes the existence of natural numbers. My point was about whether their futher "axiomatization" via a functor makes it easier to prove theorems or make discoveries.
- lisper 2y ago
  https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_t...
- aithrowawaycomm 2y ago
  Maybe a roundabout answer to your question, but Peano's axioms are equiconsistent with many finite set theories (even ZFC without axiom of infinity), and I do think philosophically it makes more sense to say weak axiomatic set theory + predicate calculus forms building blocks of arithmetic[1]. The idea of "number" as conceived by Frege is an equivalence class on finite sets: A ~ B <-> there is a bijection, which is in fact a good way of explaining "counting with fingers" as an especially primitive building block of arithmetic: {index, middle, ring} ~ {apple, other apple, other other apple} ~ {1, 2, 3} as representatives of the class "3" etc etc, predicates would be "don't include overripe apples when you count" etc. Then additions are unions and so on, and the Peano axioms are a consequence. [1] In my view Peano axioms are the Platonic ideal of arithmetic, after the cruft of bijections and whatnot are tossed away. I agree this is splitting hairs.
- xjm 2y ago
  Another one is Presburger Arithmetic, which is Peano Arithmetic minus the multiplication. What makes it interesting (and useful) is that this removal makes the theory decidable. https://en.wikipedia.org/wiki/Presburger_arithmetic https://en.wikipedia.org/wiki/Presburger_arithmetic
  - ogogmad 2y ago
    Skolem arithmetic is decidable too: https://en.wikipedia.org/wiki/Skolem_arithmetic https://en.wikipedia.org/wiki/Skolem_arithmetic I'm wondering whether there are decidable first-order theories about the natural numbers that are stronger than either Skolem or Presburger arithmetic, that presumably use more powerful number theory. Ask "Deep Research"? [edit] Found something without AI help: The theory of real-closed fields is decidable, PLUS the theory of p-adically closed fields is also decidable - then combined with Hasse's Principle, this might take you beyond Skolem. [edit] Speculating about something else: Is there a decidable first-order theory of some aspects of analytic number theory, like Dirichlet series? That might also take you beyond Skolem. https://en.wikipedia.org/wiki/Analytic_number_theory#Methods_of_analytic_number_theory https://en.wikipedia.org/wiki/Analytic_number_theory#Methods...
    - gwern 2y ago
      I recently learned about https://en.wikipedia.org/wiki/Self-verifying_theories https://en.wikipedia.org/wiki/Self-verifying_theories which gives you most of multiplication while still being decidable, which is pretty crazy.
      - ogogmad 2y ago
        That's cool, but where does it say it's decidable?
        eru 2y ago
        Not on that Wikipedia page, but you might want to have a look at the papers?
- alan-crowe 2y ago
  Conway's Surreal Numbers https://en.wikipedia.org/wiki/Surreal_number#Arithmetic https://en.wikipedia.org/wiki/Surreal_number#Arithmetic
dang 2y ago
I'm guessing that the submitter was also the author of the post* and decided to use a different title for HN. I've reverted it now. * since they've posted most of https://news.ycombinator.com/from?site=principlesofcryptography.com https://news.ycombinator.com/from?site=principlesofcryptogra...

by culi 2y ago

bediger4000 2y ago

What would some others be? I usually only see Peano's axioms.

gylterud 2y ago
There are many axiom systems for natural numbers. My favorites are 1. Heyting Arithmetic, and 2. In category theory, one can characterise the natural numbers and the initial algebra of the X |–> X+1. functor.
- Koshkin 2y ago
  Sure, one can, but does it help with anything? Just curious.
  - ketralnis 2y ago
    It's up to you if you think it's "better" but it's answering the question of whether Peano axioms are the only fundamental structure
    - Koshkin 2y ago
      Category Theory itself assumes the existence of natural numbers. My point was about whether their futher "axiomatization" via a functor makes it easier to prove theorems or make discoveries.
lisper 2y ago
https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_t...
aithrowawaycomm 2y ago
Maybe a roundabout answer to your question, but Peano's axioms are equiconsistent with many finite set theories (even ZFC without axiom of infinity), and I do think philosophically it makes more sense to say weak axiomatic set theory + predicate calculus forms building blocks of arithmetic[1]. The idea of "number" as conceived by Frege is an equivalence class on finite sets: A ~ B <-> there is a bijection, which is in fact a good way of explaining "counting with fingers" as an especially primitive building block of arithmetic: {index, middle, ring} ~ {apple, other apple, other other apple} ~ {1, 2, 3} as representatives of the class "3" etc etc, predicates would be "don't include overripe apples when you count" etc. Then additions are unions and so on, and the Peano axioms are a consequence. [1] In my view Peano axioms are the Platonic ideal of arithmetic, after the cruft of bijections and whatnot are tossed away. I agree this is splitting hairs.
xjm 2y ago
Another one is Presburger Arithmetic, which is Peano Arithmetic minus the multiplication. What makes it interesting (and useful) is that this removal makes the theory decidable. https://en.wikipedia.org/wiki/Presburger_arithmetic https://en.wikipedia.org/wiki/Presburger_arithmetic
- ogogmad 2y ago
  Skolem arithmetic is decidable too: https://en.wikipedia.org/wiki/Skolem_arithmetic https://en.wikipedia.org/wiki/Skolem_arithmetic I'm wondering whether there are decidable first-order theories about the natural numbers that are stronger than either Skolem or Presburger arithmetic, that presumably use more powerful number theory. Ask "Deep Research"? [edit] Found something without AI help: The theory of real-closed fields is decidable, PLUS the theory of p-adically closed fields is also decidable - then combined with Hasse's Principle, this might take you beyond Skolem. [edit] Speculating about something else: Is there a decidable first-order theory of some aspects of analytic number theory, like Dirichlet series? That might also take you beyond Skolem. https://en.wikipedia.org/wiki/Analytic_number_theory#Methods_of_analytic_number_theory https://en.wikipedia.org/wiki/Analytic_number_theory#Methods...
  - gwern 2y ago
    I recently learned about https://en.wikipedia.org/wiki/Self-verifying_theories https://en.wikipedia.org/wiki/Self-verifying_theories which gives you most of multiplication while still being decidable, which is pretty crazy.
    - ogogmad 2y ago
      That's cool, but where does it say it's decidable?
      - eru 2y ago
        Not on that Wikipedia page, but you might want to have a look at the papers?
alan-crowe 2y ago
Conway's Surreal Numbers https://en.wikipedia.org/wiki/Surreal_number#Arithmetic https://en.wikipedia.org/wiki/Surreal_number#Arithmetic

dang 2y ago

I'm guessing that the submitter was also the author of the post* and decided to use a different title for HN. I've reverted it now. * since they've posted most of https://news.ycombinator.com/from?site=principlesofcryptography.com https://news.ycombinator.com/from?site=principlesofcryptogra...