[FOM] arithmetic without product

[morgorod at gmx.net]

> 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