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.

Addition Recursive Definition

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

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?

Addition Alternative Definition

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.

  • 2
    $\begingroup$ 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. $\endgroup$
    – saulspatz
    May 10 at 16:11
  • $\begingroup$ 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 .... $\endgroup$ May 10 at 16:20
  • 3
    $\begingroup$ 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. $\endgroup$
    – saulspatz
    May 10 at 16:28
  • 1
    $\begingroup$ 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". $\endgroup$
    – TomKern
    May 10 at 17:44
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mark S.
    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$.

Yes, the "y - 1" term is problematic. If you're still defining addition, you haven't got subtraction.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.