fom
Posts:
1,969
Registered:
12/4/12


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


On 8/18/2013 8:04 AM, Jim Burns wrote: > On 8/18/2013 8:02 AM, Ben Bacarisse wrote: >> William Elliot <marsh@panix.com> writes: >> >>> On Sun, 18 Aug 2013, Peter Percival wrote: >>>>> >>>>>>>> Can addition be defined in terms of multiplication? I.e., >>>>>>>> is there a formula in the language of arithmetic >>>>>>>> x + y = z <> ... >>>>>>>> >>>>>>>> such that in '...' any of the symbols of arithmetic >>>>>>>> except + may occur? >>>>>>>> >>>>>>>> The symbols of arithmetic (for the purpose of this question) are >>>>>>>> either >>>>>>>> individual variables, (classical) logical constants >>>>>>>> including =, >>>>>>>> S, +, *, and punctuation marks; >>>>>>>> or the above with < as an additional binary predicate symbol. >>>>>>> >>>>>>> How about >>>>>>> x + y = z <> 2^x * 2^y = 2^z >>>>>>> >>>>>>> where 2^x is just an abbreviation for the function 2pwr: N > N, >>>>>>> defined by >>>>>>> 2pwr(0) = 1 >>>>>>> 2pwr( Sx ) = 2 * 2pwr( x ) >>>>>> That goes beyond what I defined as the language of arithmetic. >>>>> >>>>> It does not. It quite definable with Peano's axioms >>>>> which may be presumed to be what you intend because >>>>> of the inclusion of S in the symbols of arithematic. >>>> >>>> Then I think the onus is on you to produced definitions in one or >>>> both of >>>> these forms: >>>> x + y = ... >>>> x + y = z <> ... >>>> >>>> where the only nonlogical symbols (baring punctuation) in the ... >>>> are from >>>> this set: {*,S,0} or this set: {*,S,0,<}. I wouldn't be surprised >>>> if + can be >>>> defined (in the way requested) from {*,S,0} or {*,S,0,<} but I would >>>> like >>>> either to see it spelt out, or to be given a reference. >>> >>> As Jim Burns said >>> z = x + y iff 2^z = 2^x * 2^y >>> >>> where 2^n is defined by induction 2^0 = 1, 2^1 = 1 and 2^(n+1) = 2*2^n >>> all of which can be done with Peano's axioms. >> >> Stepping out of my comfort zone here, but I think the point is that >> allowing recursive definitions makes the theory secondorder, and raises >> the question of why one would not simply define + directly that way too. >> >> Broadly speaking, you can either have a secondorder theory in which + >> and * and so on are not in the signature of the language (but are >> defined recursively) or you can have a firstorder theory where + and * >> and so on are added to the signature, with axioms used to induce the >> usual meaning. >> >> I suspect Peter is talking about a firstorder theory where recursive >> definitions are not permitted. >> >> <snip> >> > > Does "first order theory" mean no recursive definitions or > no recursion at all? > > I have grown used to gliding past the logical implications of > definitions, assuming (possibly incorrectly) that there were > no *logical* implications, that they were solely a matter of > convenience for the writer and reader  although a very > important matter of enormous convenience in practice, > making the otherwise incomprehensible comprehensible. > How wrong am I? >
You can find a discussion of defined symbol eliminability in Kleene's "Introduction to Metamathematics". There are certain provability requirements which must be met.
I suppose the question of "logical" implications would depend on how you view "logic".
Obviously, definitions for the purpose of a particular problem domain are stipulative and convenient. The question of a logical foundation, however, will trace the hypothetical assertions of theorems backward to minimal sets of common premises. Similarly, the principal of noncircularity will permits tracing defined symbols backward to language primitives which cannot be eliminated through substitution.
Since the deductive calculus does not introduce symbols other than variables (x=x is an instance of the axioms of identity introducing a term into a proof  as in "Fix x" or "Let x be..."), the language of a theory are the symbols different from the logical constants (and punctuation) which appear in the sentences through which the theory is expressed.
If one begins with a given theory and the language determined by the alphabet of symbols in its given assertions, then introducing a symbol with a definition is a *new* language.
Here is an explanatory excerpt from Hodges' "Model Theory" concerning the extension of a language with constant symbols:
"The conventions for interpreting variables are one of the more irksome parts of model theory. We can avoid them, at a price. Instead of interpreting a variable as a name of the element b, we can add a new constant for b to the signature. The price we pay is that the language changes every time another element is named. When constants are added to a signature, the new constants and the elements they name are called parameters."
Kleene gives more general remarks because he includes the stipulated definitions of logical constants among the symbols which may be eliminated. Section 74 begins with:
"At various stages in the informal development of a mathematical theory additions may be to the stock of concepts and notations. If the development is formalized, at the corresponding stages the new formation rules and postulates are added to a given formal system S_1 to obtain another S_2. Thus the formulas (provable formulas) of S_1 become a subset of those of S_2. The new formation rules introduce new formal symbols or notations, and the new postulates provide for their use deductively. We shall write "(1)" ("(2)") for the deducibility relation in S_1 (in S_2).
"Under such circumstances, we say that the new notations or symbols (with their postulates) are eliminable (from S_2 in S_1), if there is an effective process by which, given any formula E of S_2, a formula E' of S_1 can be found, such that:
(I)
If E is a formula of S_1, then E' is E
(II)
(2) E <> E'
(III)
If Gamma (2) E, then Gamma' (1) E'
Here Gamma' is D_1', ..., D_k', if Gamma is D_1, ..., D_k. We call (1)  (3) the elimination relations."
This view of languages seems to come from mixed algebraic and logical principles. However, I believe that Whitehead published a book on universal algebra prior to "Principia Mathematica". When Tarski wrote his 1933 paper on truth in formalized languages, he specifically excluded languages built from definitions. Since "Principia Mathematica" had been the standard at that time, one may interpret the situation with respect to the algebraic notion.
As I wrote elsewhere it is significant that Chang and Keisler describe model theory as
(model theory) = (universal algebra) + (logic)
I wonder if some of the confusion over these matters would be alleviated if curriculum committees placed a course on universal algebra as a prerequisite for courses on mathematical logic. The latter introduce model theory without the algebraic analyses and thus conflate the role of definitions in mathematics and logic.
I hope these remarks provide some clarification for your question. Depending on one's view of logic, it might be more correct to say that definitions have no "mathematical" implications.

