max(), sum(), next()

[Ken Starks]

castironpi wrote:
> On Sep 5, 9:20 pm, "Manu Hack" <manuh... at gmail.com> wrote:
>> On Fri, Sep 5, 2008 at 1:04 PM, castironpi <castiro... at gmail.com> wrote:
>>> On Sep 5, 3:28 am, "Manu Hack" <manuh... at gmail.com> wrote:
>>>> On Thu, Sep 4, 2008 at 4:25 PM, castironpi <castiro... at gmail.com> wrote:
>>>>> On Sep 4, 2:42 pm, bearophileH... at lycos.com wrote:
>>>>>> David C. Ullrich:
>>>>>>> At least in mathematics, the sum of the elements of
>>>>>>> the empty set _is_ 0, while the maximum element of the
>>>>>>> empty set is undefined.
>>>>>> What do you think about my idea of adding that 'default' argument to
>>>>>> the max()/min() functions?
>>>>>> Bye,
>>>>>> bearophile
>>>>> For max and min, why can't you just add your argument to the set
>>>>> itself?
>>>>> The reason max([]) is undefined is that max( S ) is in S.
>>>> It makes sense.
>>>>> The reason sum([]) is 0 is that sum( [ x ] ) - x = 0.
>>>> It doesn't make sense to me.  What do you set x to?
>>> For all x.
>> But then how can you conclude sum([]) = 0 from there?  It's way far
>> from obvious.
> 
> You can define sum([a1,a2,...,aN]) recursively as
> sum([a1,a2,...a(N-1)])+aN.  Call the sum sum([a1,a2,...,aN]) "X", then
> subtract aN.
> 
> sum([a1,a2,...a(N-1)])+aN=X
> sum([a1,a2,...a(N-1)])+aN-aN=X-aN
> 
> For N=2, we have:
> 
> sum([a1,a2])=X
> sum([a1,a2])-a2=X-a2
> sum([a1,a2])-a2-a1=X-a2-a1
> 
> Since X= a1+ a2, replace X.
> 
> sum([a1,a2])-a2-a1=(a1+a2)-a2-a1
> 
> Or,
> 
> sum([a1,a2])-a2-a1=0
> 
> Apply the recursive definition:
> 
> sum([a1])+a2-a2-a1=0
> 
> And again:
> 
> sum([])+a1+a2-a2-a1=0
> 
> And we have:
> 
> sum([])=0.
> 

This is not necessarily so.

The flaw is that you provide a recursive definition with no start value,
which is to say it is not a recursive definition at all.

A recursive definition should be (for lists where elements
can be added, and ignoring pythonic negative indexing):

Define 'sum(L)' by
a.  sum(L[0:1]) = L[0]
b.  sum(L[0:i]) = sum(L[0:i-1]) + L[i]  ... if i > 1

 From this you can prove the reverse recursion
     sum{L[0:k]) = sum(L[0:k+1]) - L[k+1]
    __only__ if k >= 0

It says nothing about the empty list.

You could add, as part of the definition, that sum{[]) = 0, or any other
value.

A rather different approach, not quite simple recursion, would be to
start with

A. a slicing axiom, something like:

   for all non-negative integers, a,b,c with a <=b <= c:

   sum(L[a:c]) = sum(L[a:b]) + sum(L[b:c])

B. a singleton axiom:

   for all integers a where L[a] exists:
  sum(L[a:a]) = L[a]




2a.  sum{