6
$\begingroup$

It seems to me that a tag for "arithmetic logic" is missing while it concerns a significant number ($\sim 500?$) of questions, which currently have no common tag other than the very broad —3700 questions— (while the main specific tag in this direction, —206 questions— is much too restrictive). What should be a good name, good tag excerpt for such a tag? What should be the scope of such a tag?

Initial suggestion: "arithmetic-logic" (discarded as too broad after feedback).

Edit: Now created taking feedback into account .

As was suggested, current instances of should be replaced with : as this can only be performed by moderators, I added the metatag.

Concretely, the request to either

An advantage (noticed by Martin Sleziak in this Editor Lounge discussion) of (a) is that users typing "peano" when typing tags, will be proposed . In option (b), I understand that after merging, the tag can be recreated.

Here I just list (maybe not comprehensively) of possibly concerned questions that have a very high number of upvotes, just to have an idea of the scope of the tag, and I list the tags they currently have.

(1) Is (Z,+,0,1,P2,P3) decidable?

(2) Gödel's Incompleteness Theorem and the complexity of arithmetic

(3) What can be proven in Peano arithmetic but not Heyting arithmetic?

(4) Which recursively-defined predicates can be expressed in Presburger Arithmetic?

(5) Does Taranovsky's system of ordinal notations make sense?

(6) Proof as a Σ₁ approximation to truth: what about higher degrees?

maybe also [edit: and not these ones although they ring the "logic" and "arithmetic" bells]:

(7) Is being rational decidable?

(8) Independence of being an integer

(9) Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?

$\endgroup$
7
  • 1
    $\begingroup$ PS Relevant 2020 MSC numbers seem to be: 03C62 Models of arithmetic and set theory; 03F30 First-order arithmetic and fragments; 03F35 Second- and higher-order arithmetic and fragments 03H15 Nonstandard models of arithmetic $\endgroup$
    – YCor
    Oct 10, 2020 at 12:49
  • 1
    $\begingroup$ +1 from me - mainly to get the question to score $\ge3$ so that it appears in the community bulletin. (That could help more users to notice this question and improve the chances that some users will joint the discussion.) $\endgroup$
    – Martin Sleziak
    Oct 11, 2020 at 3:33
  • $\begingroup$ This is kind of addressed in Noah Schweber's answer, but would a question about Hilbert's 10th problem (en.wikipedia.org/wiki/Hilbert%27s_tenth_problem) fit under this tag? $\endgroup$
    – Sam Hopkins
    Oct 11, 2020 at 4:45
  • $\begingroup$ @SamHopkins I put computability questions after "maybe also" as I was quite skeptical they should be included. $\endgroup$
    – YCor
    Oct 11, 2020 at 7:10
  • $\begingroup$ (Just for the record: at the time of edit, with amended request, the question has a balance of +5=8−3 votes and Noah Schweber's answer has a balance of +6=6−0 votes.) $\endgroup$
    – YCor
    Oct 14, 2020 at 14:30
  • $\begingroup$ To be consistent, following up on a suggestion of Martin Sleziak's, chat.stackexchange.com/transcript/message/55819928#55819928, we should have the tag [models-of-pa] to be a synonym for [models-of-arithmetic]. $\endgroup$
    – jeq
    Oct 24, 2020 at 23:10
  • $\begingroup$ @jeq there are only 5 questions now (initially 9) with models-of-pa, it's easy to do it manually. $\endgroup$
    – YCor
    Oct 25, 2020 at 6:48

2 Answers 2

Reset to default
2
$\begingroup$

I have created the tag synonym -> .

$\endgroup$
2
  • $\begingroup$ How long should it take for this change to propagate? For example, after four days, on my machine, mathoverflow.net/users/2000/… shows 17 posts with the [peano-arithmetic] tag (and one with [theories-of-arithmetic]), but clicking it gives mathoverflow.net/search?q=user:2000+[peano-arithmetic], which shows only one post, missing the other 17. $\endgroup$
    – jeq
    Oct 24, 2020 at 21:47
  • $\begingroup$ ...And the single post found had had the new tag manually added ten days ago. $\endgroup$
    – jeq
    Oct 24, 2020 at 22:13
7
$\begingroup$

I think having a tag for something like this would be quite reasonable. However, I have a couple reservations with your proposal.

First, in my opinion "arithmetic logic" is not an ideal tag name: it sounds like it refers to the study of general logics from an "arithmetic" perspective, rather than the study of theories of arithmetic in (usually) classical first-order logic. This is especially true given the term "algebraic logic," which does refer to the study of general logics from an algebraic perspective.

I think a better tag name would be "theories of arithmetic." This doesn't give a false impression, is a phrase used frequently within logic, and as far as I know has no other usage within mathematics. It would also cover models of (theories of) arithmetic, since that amounts to the semantic aspect of the study of theories of arithmetic.

("Arithmetic model theory" would also be a plausible candidate, but I like it less: it suffers from the same false impression drawback, given $(i)$ the interactions between model theory and number theory, as opposed to theories of arithmetic, and $(ii)$ terms like "geometric stability theory" for which the corresponding impression is accurate.)

Second, I don't really think that the examples "Is being rational ..." and "Are surjectivity ..." should be included: they're not about theories of arithmetic, but rather computability-theoretic aspects of arithmetic. I would use as a criterion that in order to get this tag, a question should somehow be about sets of sentences, in some appropriate logic, which describe the natural numbers. While questions about computability-theoretic aspects can of course be rephrased in such a form, that's not how they're naturally posed, so I don't think they should count.

$\endgroup$
9
  • $\begingroup$ It shouldn’t include Independence of being ... either as it is a question on independence in ZFC rather than any arithmetic, Does Taranovsky’s system... as it is a question on definitions of compuatble ordinals that does not per se involve any arithmetic, and I don’t think it should include Proof as $\Sigma_1$ approximation... as the fact that it uses PA as an example is mostly irrelevant to the question. Moreover, Is (Z,+,0,1,P2,P3) decidable? is borderline; as I read it, it is a question about decidability of a certain structure, not a question about a theory of arithmetic. $\endgroup$
    – Emil Jeřábek
    Oct 11, 2020 at 7:30
  • 1
    $\begingroup$ Really, it seems to me that if the tag is to make a coherent sense rather than being a hodge-podge of various tangentially related things from logic, it should essentially be just a renaming of the existing “peano-arithmetic” tag (which has always been interpreted much more broadly than the name suggest, including subsystems and extensions of PA, that is, essentially, any “theories of arithmetic”). I agree that the name of the “peano-arithmetic” tag is suboptimal for the purpose, but I don’t see the need for any genuinely new tag here. $\endgroup$
    – Emil Jeřábek
    Oct 11, 2020 at 7:35
  • $\begingroup$ @EmilJeřábek I have the impression that much less than half of the concerned questions currently have the peano-arithmetic tag, and that's precisely the problem. (For instance out of the first six questions in my post, which I believe fit the "theories-of-arithmetic" topic, only one has the peano tag, and I'm afraid this reflects the general picture.) $\endgroup$
    – YCor
    Oct 11, 2020 at 8:42
  • 1
    $\begingroup$ @YCor This problem is not solved by creating a new tag, but by making sure to include the existing tag on questions where it is appropriate (and by renaming it so its scope is more clear). And to repeat, only 3–4 questions on your list fit the topic; the remaining ones are on tangential topics such as computability, descriptive complexity, and set theory. $\endgroup$
    – Emil Jeřábek
    Oct 11, 2020 at 9:27
  • $\begingroup$ @EmilJeřábek which questions among (1)-(6) don't fit a (broad) interpretation of "theories-of-arithmetic"? in any case I clearly see a problem in systematically retagging "peano-arithmetic" questions that are not about Peano arithmetic. $\endgroup$
    – YCor
    Oct 11, 2020 at 9:40
  • 1
    $\begingroup$ Right, so as I already wrote twice, rename the “peano-arithmetic” tag as “theories-of-arithmetic”. $\endgroup$
    – Emil Jeřábek
    Oct 11, 2020 at 9:59
  • $\begingroup$ @EmilJeřábek, Noam: I have created the tag theories-of-arithmetic. (This is for the moment easily reversible as the number of questions is very small.) I included a short tag excerpt, please improve it if necessary. I'll request to moderators to rename all instances of peano-arithmetic as theories-of-arithmetic. Note that this can be done in (at least) 2 ways: making a synonym, or merging, see Martin Sleziak's explanation at editor's lounge. $\endgroup$
    – YCor
    Oct 14, 2020 at 9:00
  • $\begingroup$ @YCor All right, thank you. I tweaked the tag exceerpt a bit. $\endgroup$
    – Emil Jeřábek
    Oct 14, 2020 at 10:03
  • $\begingroup$ @EmilJeřábek and YCor: Just to be on the safe side, I will repeat that merging is a tool which has to be used carefully, since it cannot be reversed. (If a synonym is created without merging, then it can be cancelled and the posts will have the original tags - with the exception of questions which were edited while it existed. If the tags are merged, then tags are actually changed and cancelling the synonym does not restore the original state, to get back to it one would retag manually.) $\endgroup$
    – Martin Sleziak
    Oct 15, 2020 at 4:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .