
Re: Can addition be defined in terms of multiplication?
Posted:
Aug 22, 2013 12:49 PM


Can addition be defined in terms of multiplication? ...................................................
Author: David Libert Date: 20130822 12:18:08 EDT
Table of Contents ................. 1 this article is dual posted to Usenet and Wikispaces 2 this is a reply to Peter Percival's Aug 20 article 3 Two stackexchange references from Alan Smaill and Peter 4 Summary of results from second stackexchange reference 5 Discussion of quoted results 5.1 Herbert Enderton A Mathematical Introduction to Logic 5.2 Successor cannot define addition or multiplication 5.3 Multiplication is not definable from successor and + 5.4 Addition IS definable from successor and multiplication 5.5 Decidability or not of arithmetic (sub)theories 5.5.1 Followup about theory of multiplication only 5.5.1.1 Further Handbook reference
1 this article is dual posted to Usenet and Wikispaces ........................................................ Dual posting in accordance with policy http://davesscribbles.wikispaces.com/policyusenetincrwikispaces
http://davesscribbles.wikispaces.com/plusundeffrommult
2 this is a reply to Peter Percival's Aug 20 article ...................................................... [1] Peter Percival sci.logic sci.math Can addition be defined in terms of multiplication? Tue Aug 20, 2013 https://groups.google.com/d/msg/sci.logic/Oh0di6uEMSM/I0gwV8M8HhcJ
3 Two stackexchange references from Alan Smaill and Peter ........................................................... > > Versions of this use just FOL; > > > overview here: > > > > > > http://math.stackexchange.com/questions/312891/howisexponentiationdefinedinpeanoarithmetic > > > > Which led me to > > http://math.stackexchange.com/questions/449146/whyareadditionandmultiplicationincludedinthesignatureoffirstorderpea?rq=1 Above, Alan and Peter gave two stackexchange references: [2] http://math.stackexchange.com/questions/312891/howisexponentiationdefinedinpeanoarithmetic [3] http://math.stackexchange.com/questions/449146/whyareadditionandmultiplicationincludedinthesignatureoffirstorderpea?rq=1
4 Summary of results from second stackexchange reference .......................................................... Peter quotes results stated in [3]: > Actually, more is known. Neither addition nor multiplication is > > definable from successor alone; multiplication is not definable from > > successor and addition; and addition is not definable from successor and > > multiplication. The theory of the natural numbers with multiplication > > and addition is undecidable, but the restriction to just addition is > > decidable, and the restriction with just multiplication is decidable.
5 Discussion of quoted results ................................
5.1 Herbert Enderton A Mathematical Introduction to Logic ........................................................... [4] Herbert Enderton A Mathematical Introduction to Logic Academic Press copyright 1972
5.2 Successor cannot define addition or multiplication ........................................................ In [4], section 3.1 pp 178184, Enderton defines the theory of successor only on the natural numbers and proves it admits elimination of quantifiers.
In that section 3.1, exercise 4 on page 184 uses the elimination of quantifiers above to conclude the sets definable in this theory are each finite or compliment of finite (cofinite).
From + we can define the set of even numbers, which is neither finite nor cofinite. From * we can define the set if squares, which is neither finite nor cofinite.
So neither + nor * are definable.
5.3 Multiplication is not definable from successor and + .......................................................... This is from Presberger's elimination of quantifiers argument on successor and + from 1929. [4] states the decidability of this theory on page 188 and gives the elimination of quantifiers proof in the following pages. On page 192 [4] states the consequence of this elimination of quantifiers above that the definable sets are exactly the eventually periodic ones.
From * we can define the set if squares, which is not eventually periodic, so * is undefinable from this theory.
5.4 Addition IS definable from successor and multiplication ............................................................. The quote from [3] above says multiplication is NOT definable from successor and multiplication, but this seems to be in error.
Herbert Enderton posted about this, noting a method from Julia Robinson:
[5] Herbert Enderton Tue Dec 10, 2002 sci.logic "Re: The language of whatever (Was: Definable real numbers)" https://groups.google.com/d/msg/sci.logic/A6l0yl6QzbA/76ELiiVDNBMJ https://groups.google.com/forum/#!original/sci.logic/A6l0yl6QzbA/76ELiiVDNBMJ
5.5 Decidability or not of arithmetic (sub)theories ..................................................... [3] noted +,* together are undecidable, but + and * are each individually decidable.
For +,* code Turing machines into +,* and the undecidability of the halting problem. Such coding can be done with Godel's methods to code sequences as from [2].
[6] http://en.wikipedia.org/wiki/Decidability_(logic)
attributes this:
> The firstorder theory of the natural numbers with > addition, multiplication, and equality, established > by Tarski and Andrzej Mostowski in 1949.
(Above I edited to break a long line.)
The + decidability is Presberger's Theorem as above.
In this thread
[7] Robin Chapman sci.logic sci.math Fri Aug 16, 2013 "Re: Can addition be defined in terms of multiplication?" https://groups.google.com/d/msg/sci.logic/Oh0di6uEMSM/remJFZUASlcJ
noted the Presberger result about + above, and then noted this should also apply to *.
This sounds right to me though I don't yet see it in detail. The standard model of * is a finite support product of omega copies of the standard + model, ie each coordinate copy corresponding to powers of a distinct prime. Composite numbers appear as finite support Cartesian products of those copies.
Either repeat Presberger's proof on this more complicated setup directly. Or maybe some abstract nonsense does a reduction.
If that is correct about * being a decidable theory, that answers the original question of this thread:
[8] Peter Percival sci.logic sci.math Can addition be defined in terms of multiplication? Fri Aug 16, 2013 https://groups.google.com/d/msg/sci.logic/Oh0di6uEMSM/ll6XE2ItRvAJ
namely answer that addition cannot be defined from multiplication. Robin already pointed this out in [7].
5.5.1 Followup about theory of multiplication only ................................................... Above is as far as I got on my own.
Since writing that I Googled and found some more. Not proofs I know but literature references. So I am adding this as a separate section about that and preserving my original comments above. Those comments were from a less informed background so are still easier to understand.
I Googled "theory of multiplication only decidable" and that led me to the references I will give and discuss below.
[9] On Direct Products of Theories Andrzej Mostowski Source: J. Symbolic Logic Volume 17, Issue 1 (1952), 131. http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.jsl/1183731313
[10] Research web page of Alexis BÃ¨s University of Paris http://lacl.fr/bes/recherche.html
[11] A.BÃ¨s Definability and decidability results related to the elementary theory of ordinal multiplication Fund.Math.171, 197211 (2002). http://lacl.fr/bes/publi/ordimult.ps http://lacl.fr/bes/publi/errataordimult.ps
[11] page 1 notes that the decidability of theory of multiplication only on omega was announced by Skolem in 1930 and proved by Mostowski in [9]. [11] notes that proof in [9] was a direct consequence of Mostowski's results on direct products of structures and Presberger's result on decidability of the theory of + on omega. So it seems this was along the lines I was noting in the section
[10] links to [11].
[11] notes as above about Skolem and [9]. [11] also references two other papers proving that decidability of the theory of multiplication on omega.
[11] also states and proves its main new theorem: the elementary theory of usual ordinal multiplication on an ordinal alpha (ie von Neumann's definition: considering ordinal alpha to be the set of all smaller ordinals, and hence the universe of a structure) is decidable <> a < omega^omega.
[11] includes further technical results about definability from multiplication on an ordinal.
Those are the basic references I found. So this is further support for the stackexchange [3] about theory of multiplication being decidable. As Robin noted in [7] and I noted in the section above, this is enough to answer the original [8] question: multiplication can't define addition.
There is the Feferman Vaught theorem, along the lines of decidability of theory of a product structure of factors having decidable theories. Possibly related to the Mostowski [9].
Googling "feferman vaught" I found a reference on this sort of thing, though scanning I didn't notice the names Feferman Vaught:
[12] http://theory.stanford.edu/~tingz/talks/quals.pdf
[12] page 34 is specifically about decidability of multiplication on natural numbers.
5.5.1.1 Further Handbook reference ................................... Since writing the above I found an additional reference:
[13] Handbook of Mathematical Logic Edited by Jon Barwise NorthHolland Publishing Company 4th printing 1985
[14] Decidable Theories Michael O. Rabin [13] pp 595629
[15] in [14] section 2.5 Further results pp 611612 page 612
[15] notes properties of product structures was initiated by Mostowski and developed by Feferman and Vaught. Rabin notes this applies to show the theory of multiplication on omega is decidable, applying these product results to the decidability of the theory of + on omega. Namely by this general theory getting the decidability of the direct sum of omega many copies of + on omega. This as I wrote earlier about finite support.
Rabin mentions this decidability of * as due to Skolem and Mostowski.

