5
$\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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Oct 25, 2020 at 6:48

3 Answers 3

Reset to default
1
$\begingroup$

I have created the tag synonym -> .

$\endgroup$
4
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$
11
  • $\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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Oct 14, 2020 at 9:00
  • $\begingroup$ @YCor All right, thank you. I tweaked the tag exceerpt a bit. $\endgroup$
    – Emil Jeřábek
    Commented 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
    Commented Oct 15, 2020 at 4:38
  • $\begingroup$ @EmilJeřábek and Noah Schweber: your reaction to Joel David Hamkins's late answer would be useful. $\endgroup$
    – YCor
    Commented Dec 22, 2023 at 2:50
  • $\begingroup$ Since you were involved in the previous discussion, I will point out this follow-up question: Should the tags (peano-arithmetic) and (theories-of-arithmetic) be merged? (But probably you noticed it even without my comment.) $\endgroup$
    – Martin Sleziak
    Commented Aug 8 at 5:24
2
$\begingroup$

I realize that I am coming late to this discussion, but I am not happy with the tag situation regarding models of PA.

Currently I feel there is no suitable tag for questions about models of PA. This is a big research area, known by the name "Models of PA", with hundreds or perhaps thousands of published articles. There are several books with the phrase "Models of Peano arithmetic" in the title, there is the MOPA seminar in New York (MOPA = Models of PA), and many researchers describe their subject as "Models of PA".

There are many dozens of questions on MO, perhaps hundreds, about models of PA. We used to have the tag models-of-pa, which I often used and which was just perfect for this research area.

We have the tag theories-of-arithmetic, to be sure, which is a fine subject, but for many questions, focused on the model theory of PA, that tag is unnatural, since these questions are about the models, not the theories. The tag models-of-pa was folded into theories-of-arithmetic, but in many cases this seems off to me. I think many questions currently tagged with theories-of-arithmetic, perhaps even most of them, would be better tagged with models-of-pa.

To be sure, questions in models of PA often turn into questions about weaker theories, as one optimizes the results, and these further questions would usually be thought of under the description "weak arithmetic". For example, there is the big conference series Weak Arithmetic Days, between Paris and NYC, which is all about models of PA and weaker arithmetic theories. I would support a weak-arithmetic tag for posts in this area, although probably theories-of-arithmetic is already suitable.

I recognize that "pa" is perhaps not descriptive enough in a tag, but in this case I would recommend that models-of-pa be a tag synonym for models-of-peano-arithmetic, so that when users type models-of-pa it turns into models-of-peano-arithmetic on the site.

As a compromise, since I recognize that MO has many logic users who are focused on weaker arithmetics such as IDelta_0 etc., we could have models-of-arithmetic. But in truth, I think those users are more focused on the theories than the models, and so perhaps they would prefer theories-of-arithmetic anyway.

I would be less happy with a tag peano-arithmetic, since the name of the subject is "Models of PA", but having that tag would be better than having to use theories-of-arithmetic.

I think we need two tags:

  • models-of-pa, synonym for models-of-peano-arithmetic, for questions in the research area known as models of PA. This is the model theory of models of PA and models of arithmetic generally.

  • theories-of-arithmetic, for questions about theories of arithmetic, including weak arithmetic.

$\endgroup$
24
  • $\begingroup$ It seems to me that a single tag encompassing both would be a much simpler matter (certainly "models-of-pa" is worse than "models-of-peano-arithmetic"). If most "models of PA" questions are currently tagged "th of ar", creating "models of PA" will add confusion and entropy, unless a substantial effort is done to single out which of the currently 100 questions should be retagged. $\endgroup$
    – YCor
    Commented Dec 21, 2023 at 15:24
  • $\begingroup$ Well, indeed it was a mistake to have folded models-of-pa into theories-of-arithmetic in the first place. I would be willing to gradually retag questions with models-of-pa. The problem is that right now, there is no good tag for models of PA questions. If we renamed theories-of-arithmetic to peano-arithmetic, that would be easier and greatly improve the situation. But then the weak arithmetic posts would be wrongly tagged, but I think there are fewer of them. $\endgroup$
    – Joel David Hamkins
    Commented Dec 21, 2023 at 15:28
  • $\begingroup$ Temporarily (or not) I'm adding "models of Peano arithmetic" in the tag info of [tag:theories of arithmetic], since it was created to encompass it. $\endgroup$
    – YCor
    Commented Dec 21, 2023 at 15:31
  • $\begingroup$ We need a models-of-pa tag. I don't understand the argument against it. $\endgroup$
    – Joel David Hamkins
    Commented Dec 21, 2023 at 15:37
  • $\begingroup$ In this context, it is worth pointing out that the tag (models-of-pa) contained only nine questions at the time when it was removed (in 2020): chat.stackexchange.com/transcript/10243/2020/10/22 chat.stackexchange.com/rooms/10243/conversation/… $\endgroup$
    – Martin Sleziak
    Commented Dec 21, 2023 at 15:41
  • $\begingroup$ The argument is not against it but against creating it immediately without discussion. There was a discussion in this thread which lasted several days and involved several users, which led to the creation of theories-of-arithmetic. It is unfortunate you didn't participate. You claim that theories-of-arithmetic can't encompass models of PA and this should be discussed since it seems to me to contradict the purpose of theories-of-arithmetic. If you want more visibility: maybe create a new discussion, and better ping the main participants of the previous discussion. $\endgroup$
    – YCor
    Commented Dec 21, 2023 at 15:41
  • $\begingroup$ The objection to theories-of-arithmetic is that the subject is not about theories of arithmetic, but about the models of PA. If theories-of-arithmetic were renamed as peano-arithmetic, then this would be an acceptable compromise. But as Emil observed, there are other problems with that. $\endgroup$
    – Joel David Hamkins
    Commented Dec 21, 2023 at 15:44
  • $\begingroup$ There are 1300 posts on MO with the phrase " PA ", but only 299 (or 102?) using the tag theories-of-arithmetic. $\endgroup$
    – Joel David Hamkins
    Commented Dec 21, 2023 at 15:53
  • $\begingroup$ 135 results for "model of PA" and 48 additional for "models of PA" without "model of PA". $\endgroup$
    – Joel David Hamkins
    Commented Dec 21, 2023 at 16:05
  • 1
    $\begingroup$ @YCor I think I agree with Joel here, although I don't have strong feelings either way. The dispositive point for me at least is the fact that there is a large research community which uses the term "Models of PA" for itself, as noted at the start of Joel's answer. I guess I think tags should serve two roles: search/general info optimization and reflection of research communities. It's a bit hard for me to articulate the latter, but "models of PA" meets it and "theories of arithmetic" doesn't really. (Awkwardly, rereading this thread I might be responsible for the current tag name. :P) $\endgroup$
    – Noah Schweber
    Commented Dec 22, 2023 at 3:18
  • 1
    $\begingroup$ “models-of-pa” is unnecessarily narrow (and a bit cryptic for a nonspecialist, who will have no idea what “pa” is). I understand the desire for a tag for model theory of arithmetical theories separate from the more general “theories-of-arithmetic” tag, but then I’d support the tag name to be just “models-of-arithmetic”. $\endgroup$
    – Emil Jeřábek
    Commented Dec 22, 2023 at 8:07
  • 1
    $\begingroup$ I'd suggest having models-of-pa as a synonym for models-of-arithmetic, so when experts tag their questions and type models-of-pa, it will show up for them as expected, but will show on the site as models-of-arithmetic. $\endgroup$
    – Joel David Hamkins
    Commented Dec 22, 2023 at 14:26
  • 1
    $\begingroup$ FWIW my personal ideal would be "models of arithmetics," but I don't think anyone uses that for anything. $\endgroup$
    – Noah Schweber
    Commented Dec 29, 2023 at 20:42
  • 1
    $\begingroup$ To me, creating a tag (models-of-arithmetic) - with synonyms (models-of-pa) and (models-of-peano-arithmetic) - seems like a reasonable compromise. So +1 from me. (Naturally, if that tag is created, it has to be maintained in a reasonable way.) Of course, there is no doubt that opinion of people more familiar with this topic is most important. (I guess it's a bit unfortunate that this was posted as an answer rather than as a new question - IMO in this way it's less likely that some users might notice this discussion and provide their input.) $\endgroup$
    – Martin Sleziak
    Commented Jan 12 at 9:18
  • 1
    $\begingroup$ @MartinSleziak I can post a new question with the proposal you mention, which seems like a reasonable compromise also to me. I am willing to do some work to implement the tag, writing a tag description, and tagging suitable questions with it (gradually). $\endgroup$
    – Joel David Hamkins
    Commented Jan 12 at 11:47

You must log in to answer this question.

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