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


David Libert wrote: > Can addition be defined in terms of multiplication? > ...................................................
Thank you. I rather fancied that my question had an affirmative answer.
> 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. >
 Sorrow in all lands, and grievous omens. Great anger in the dragon of the hills, And silent now the earth's green oracles That will not speak again of innocence. David Sutton  Geomancies

