[FOM] arithmetic without product

[Dan Brumleve]

We could extend Presburger arithmetic with a binary predicate Square(x,y)
meaning y=x*x, and some axioms, something like

Square(x,y) & Square(x,z) -> z = y,
Square(x+1,z) <-> Square(x,y) & z = y + x + x + 1.

That is enough to express the property of being a sum of consecutive
positive integers in a particular range (using sum(i = 1 to n) = n(n+1)/2),
and for each of the instances to be provable in the extended theory.  But I
don't think it's enough to define full multiplication or a beta function.

However we have a similar problem again when we want to count the number of
such representations, I don't see how to handle that.

Dan

On Mon, Jul 23, 2018 at 8:00 AM, morgorod at gmx.net <morgorod at gmx.net> wrote:

>
>
> > On 21. Jul 2018, at 10:20, José Manuel Rodriguez Caballero <
> josephcmac at gmail.com> wrote:
> >
> > Consider the following theorem:
> >
> > For any positive integer k, there is a positive integer n having at
> least k representations as sum of consecutive positive integers.
> >
> > For example, for k = 3 we have n = 9 = 4+5 = 2+3+4.
> >
> > For the statement of this theorem we need the addition.
>
>
> It is not so clear that you only need addition for stating the theorem.
>
> You have to state that there are k-many numbers x_1, … x_k such that
> adding some succesors to these numbers will sum up to n.
>
> - One possibilty would be to speak about the set of such numbers and
> demanding that the cardinality of such a set is greater than k. It is not
> possible to formulate this in first order language of PA.
> - Another option would be to demand the existence of the Goedel number of
> the sequence x_0, … x_n in the theorem; the Goeddell number encodes all the
> necessary informations. But we need the beta-function to encode sequences
> of arbitrary lengths. And this function is defined in terms of
> multiplication.
> - Finally, we could formulate a separate version of this theorem for all n
> in N; this way we can demand a fixed number of natural numbers x_k, and
> multiplication can be avoided. But the resulting statements are weaker than
> the original theorem, and it seem not to be the desired approach to the
> question.
>
> There could be other formal representations of the theorem; but I do not
> see a version not using multiplication at all.
>
> Best, Rene G.
>
> > If we also have the multiplication, then our theorem can be proved using
> a well-known argument due to J. J. Sylvester. On the other hand, if we have
> not multiplication and we restrict ourselves to first order logic, the
> existence of a proof of this result is not so clear. Is there an
> "arithmetic with just addition" where this theorem can be stated but it
> cannot be proved?
> >
> > Kind Regards,
> > Jose M.
> > _______________________________________________
> > FOM mailing list
> > FOM at cs.nyu.edu
> > https://cs.nyu.edu/mailman/listinfo/fom
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> https://cs.nyu.edu/mailman/listinfo/fom
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20180725/ae894418/attachment.html>