Thread: Definition of Sum

I have been trying to find an acceptable definition of the "sum" of two natural numbers. Wikipedia has come close to what I am looking for. They begin by saying:

Let n' be the successor of n, that is the number following n in the natural numbers, so 0'=1, 1'=2. Define a+0=a.

I get all the above. They then continue by saying:

Define the general sum recursively by a + (b') = (a+b )'. Hence 1+1=1+0' = (1+ 0)'=1'=2.

I see the truth in everything that they are saying in the immediately preceding. However, I fail to see how that gives us a general definition for the sum of two natural numbers. I was really expecting something more along the lines of, "c is the sum of the natural numbers a and b if and only if blah blah blah." Anyway, can someone please tell me how I interpret the above as the definition of two natural numbers?

Thanks for any input.

... doug

Well first consider how the natural numbers were constructed:

1 =
2 =
3 =

So each element of the new number is the set of one of the numbers that came before it. We also include the empty set as an element of each new number as well. (It's also how we get ordering, as seen 2 is a subset of 3)

So C is the sum of A,B if and only if the cardinality of C is equal to the trivial cardinality (equivalent elements are treated separately) of .

Just so you know I just came up with this... so if its flawed or just dumb... don't hate too hard

The recursive definition of Wikipedia and the set-theoretic definitions are two different approaches, One is not needed for the other.

Recursive functions have definitions like

f(0) = m
f(n') = G(f(n))

for some already known function G. Since you know f(0), you can calculate G(f(0)) and so f(0'), i.e., f(1). Then you can calculate G(f(1)), which is f(1'), or f(2), and so on. This is calculating bottom up. In practice, you need to compute, e.g., f(0'''), which you reduce to G(f(0'')), G(G(f(0')) and so on (this computation is called top-down).

Addition is a function of two arguments defined by recursion on the second argument (it could as well be defined by recursion on the first one). We have

a + 0 = a
a + b' = (a + b)'

E.g., 2 + 3 = 2 + 0''' = (2 + 0'')' = (2 + 0')'' = (2 + 0)''' = 2''' = 5.

Does it bother anyone else that we are here talking about a successor element within the context of set? My understanding was that the order of elements within a set is irrelevant, e.g., { 3, 2, 1 } = { 1, 2, 3 }.

... doug

Originally Posted by ddjolley

Does it bother anyone else that we are here talking about a successor element within the context of set? My understanding was that the order of elements within a set is irrelevant, e.g., { 3, 2, 1 } = { 1, 2, 3 }.

... doug

The successor function is a map from a set to itself and is not concerned by the order in which you list the elements of the set in the notation you use above.

CB