Wikipedia:Reference desk/Archives/Mathematics/2019 May 2

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 2

Does anybody here know, what Skolem arithmetic (i.e. the first order theory of multiplication of natural numbers) looks like?

185.46.78.56 (talk) 08:04, 2 May 2019 (UTC)

The same user [[User:185.46.78.56]|185.46.78.56]]] ([[User talk:185.46.78.56]|talk]] · [[Special:Contribs/185.46.78.56]|contribs]]) asked the same question on my page. I must admit that I do not understand the question. I mostly know what is written in the wikipedia page. I also know how to decide whether a sentence holds or not/whether a formula is satisfiable, but it does not seems to answer the question. Thus I'd like to have more precision about what «looks like» mean. Arthur MILCHIOR (talk) 12:59, 2 May 2019 (UTC)

I meant, what are the axioms of Skolem arithmetic? Are they, all Peano's axioms, excluding those that contain the "+" symbol? Additionally, is the axiomatic system of Skolem arithmetic - finite? Is it complete? Unfortunately, the page about this arithmetic contains no hint on that... 185.46.78.56 (talk) 13:03, 2 May 2019 (UTC)

I suggest that you also post this question in the talk page of the article, instead of writing it in my talk page. Since you asked the question to me precisely, I'll answer. I've never seen Skolem arithmetic used in proof theory. I've only seen it used in model theory. Which means that I don't know whether anyone have given a set of axiom for this logic. Each time I've seen «Skolem arithmetic», it was always assumed that we all know what the natural numbers are, and that we wanted to study what can or can not be done with multiplication alone. Note that I used to be a model theorist, which means that I was strongly biased in the article I did read. However, a quick google search let me think that there are indeed no axiomatization of this logic. I should emphasize that Peano's axiom for multiplication uses the addition symbol. Thus you can't just omit the axioms of addition and have a consistent theory. What I would do, if I were to give an axiomatization, is to consider that a number $n$ is an infinite sequence $(a_{i})$ with finite support, such that $n=\prod _{i}p_{i}^{a_{i}}$, with $p_{i}$ the primes. Then I'll introduce a symbol $P_{p_{i}}$ for each prime number, and repeat the axiom of addition for each prime number. That is: $P_{p_{i}}(n)=P_{p_{i}}(m)\implies n=m$, $P_{p_{i}}(n)\neq 1$, $n\cdot 1=n$, $P_{p_{i}}(n\cdot m)=n\cdot P_{p_{i}}(m)$. But it leads to an infinite number of axiom and does not even allow to have anything similar to induction (because, in order to do induction correctly, your hypothesis would need to consider every single $P_{p_{i}}$, instead of considering only the successor symbol. Note that, I've got no citation for what I've just wrote. So it can't be used in an article. I hope at least it'll help your research. Arthur MILCHIOR (talk) 03:48, 3 May 2019 (UTC)

Thank you so much. I've adopted your suggestion and posted my new questions on the article talk page as well.

I wonder if Skolem himself wrote down any axiomatization for his arithmetic, unless he only discussed it from a model theorist's viewpoint - like you; In my view, the latter possibility does not seem to be reasonable, because he was a well known theorist of axiomatizations as well (who also contributed his "foundation axiom" to set theory, for example). I also wonder whether Skolem arithmetic can be axiomatized by a complete system, just as Presburger arithmetic (having its induction axiom scheme) can. Anyway, I'm very grateful for your important comments on this issue. 185.46.78.67 (talk) 07:08, 3 May 2019 (UTC)

I'm not an expert on model theory, but from a purely algebraic point of view we're talking about a free commutative monoid with countably infinite generators. Pretty sure the fundamental theorem of arithmetic would be one of the axioms. --RDBury (talk) 15:54, 3 May 2019 (UTC)

It says in the article that Skolem arithmetic is decidable, probably by quantifier arithmetic like Presburger arithmetic. It looks like it is just the multiplicative fragment of Peano arithmetic, while Presburger arithmetic is the additive fragment. It apparently shows up in complexity theory, which I hadn't seen before arXiv:1504.04181). 67.164.113.165 (talk) 09:15, 6 May 2019 (UTC)

But the multiplicative fragment of Peano arithmetic contains one axiom only: 0X=0. Could Skolem call it "arithmetic"? 185.46.78.26 (talk) 10:12, 6 May 2019 (UTC)

Peano arithmetic means the whole theory (i.e. including all the theorems, not just the axioms), and similarly for its fragments. The multiplicative fragment is basically all the sentences in the theory that don't use addition. Even the axioms (PA has some infinite axiom schemas) have a subset that don't use addition. But you should probably try a web search for something with a formal definition of Skolem arithmetic, if that is what you are looking for. I don't remember if you're the OP who asked last week about splitting PA into two decidable fragments that when combined give an undecidable theory, but this would seem to be an example. The person around here who really understood this stuff was CBM, but he seems to have given up on us :(. 67.164.113.165 (talk) 21:54, 6 May 2019 (UTC)

All axioms in the scheme you've mentioned, do use addition. As far as I know, PA has no axioms that don't use addition, except the axiom 0X=0, so I wonder how Skolem could build his multiplicative arithmetic using the multiplicative fragment of Peano arithmetic only. Unless he was only interested in the multiplicative theorems of Peano, and allowed to use additive axioms, but then I wonder if the name "multiplicative arithmetic" is justifiable (Yes I am the OP who asked last week about splitting PA into two complete fragments that when combined give an incomplete theory, but I didn't understand how this can be helpful). 185.46.78.64 (talk) 20:15, 7 May 2019 (UTC)

You should probably ask this question on math.stackexchange.com. The logic gurus from here either aren't around any more or are keeping quiet. The Bes paper linked from the Skolem arithmetic article isn't much help, and the web searches I've done so far haven't found anything really better. But, "forall a,b. a×b = b×a" is a multiplicative theorem that doesn't use any addition. 67.164.113.165 (talk) 03:52, 8 May 2019 (UTC)

I have never claimed PA has no theorems that use no addition, I have only claimed PA has no axioms that use no addition, besides the axiom 0X=X.

Thank you for your suggestion of stackexchange, I've just signed up, but I couldn't find the right place on the site for my question to be typed and sent, where is it? 185.46.78.36 (talk) 06:23, 8 May 2019 (UTC)

Yeah I think I'd look into the actual proof of decidability for Skolem arithmetic. Something is missing from the picture: how on earth does one prove multiplication is commutative, without induction on the successor function? Maybe you are allowed to use all the axioms of PA, and the fragment consisting of theorems that can be stated without addition/successor are still decidable. For Math.SE look for the "post question" or "ask question" button. 67.164.113.165 (talk) 19:24, 8 May 2019 (UTC)

If Skolem did axiomatize his multiplicative arithmetic - by multiplicative axioms only (as opposed to your assumption), then he must have used the multiplicative commutative law - as an independent axiom, just as this axiom is needed for defining the concept of field. Anyway, I've just posted my question on the site you've suggested. 185.46.78.2 (talk) 19:40, 8 May 2019 (UTC)