# Is this a valid definition for addition on Natural Numbers constructed from sets?

I had some issues understanding how addition is defined recursively in Von Neumann construction of Natural Numbers.

As a computer scientist student who is approaching the topic of Set-Theory, it helps me to formulate my problems and ideas with some small portions of code, I hope this can be forgiven.

    int add(int x, int y) {                              |Von Neumann Constuction:
if(y==0)                                           |  0=∅
return x;                                      |  1={∅}
else                                               |  2={∅,{∅}}
}                                                 |  :

where x, y, 0 and 1 are sets as in Von Neumann construction


My struggle with this definition is that I can't stop considering the $$y-1$$ term problematic, since what I think we usually define is the successor term $$y+1$$ as $$( y+1=y\cup \{y \})$$. Defining the "antecedent" seems more painful to me, the reasons are surely linked to my ignorance on the topic and I feel I wouldn't even be able to express them properly so I guess I will keep studying and then come back.

Meanwhile I came up with an "alternative" deifnition of addition that feels less painful for my untrained mind and I wanted to share it with you to get some feedback.

Can this be considered a valid alternative?

Set add (set x, set y) {
set h=∅
set z=∅
while (x!=z)
z= z U {z};
while (y!=h) {
z= z U {z};
h= h U {h};
}
return z;
}

where x, y, h, and z are sets as in Von Neumann construction


I wrote this code with set operations to strip any abstraction away, hoping it would make my ideas easier to be understood. If this is not the case, please share any suggestion.

• I don't think you are starting with the correct definition of addition. As I recall, if $S$ is the successor function, then the definition is $x+S(y)=S(x+y)$ There's no predecessor involved. May 10 at 16:11
• I think your memories are correct. But I feel that in order to unravel that recursion you must take for granted what is the antecedent of an element.... $4+3=4+S(2)=S(4+2)=S(4+S(1))$.....you're always assuming 2 to be the antecedent of 3 and 1 the antecedent of 2 and so on .... May 10 at 16:20
• It's a recursive definition, not an algorithm. One of the axioms is that every natural number is either $0$ or the successor of another natural, so that it's enough to define addition in the cases $0+0,\ S(x)+0,\ x+S(y)$ . You seem to be wondering how to show that it's effectively computable, which is important, but not quite the same thing. I think your algorithm is the best that could be done on an unlimited register machine, say. May 10 at 16:28
• If you're concerned about the use of $y-1$ in your first definition, some programming languages offer pattern matching. You could say "if you're trying to add x and S(y), return S(x+y) and otherwise (i.e the second argument isn't of the form S(y)), return x". May 10 at 17:44
• The sort of pattern matching @TomKern is describing is used in this Haskell example add Zero b = b (if you add $0$ to $b$, output $b$) and add (Succ a) b = Succ (add a b) (if you add $S(a)$ to $b$, output $S(a+b)$). Zero and the successor of a Peano natural are the only Peano naturals, so this covers all the cases. May 10 at 18:02

The alternative definition looks fine. It might be better though to remove the first "while" loop, and just initialize z to x. That better expresses the requirement $$x + 0 = x$$.
On the other hand, the "antecedent" notion is not so bad. Since the successor function is one-to-one, it has a well defined inverse, the predecessor function, and the domain of the predecessor function is the range of the successor function, the set of all non-zero natural numbers. There's even an easy way to calculate it; the predecessor of the natural number $$x$$ is just the union of the collection $$x$$ of sets of natural numbers.