Primitive recursive function, constructing a proof

144 Views Asked by At

I've came upon an example in the book that is not that clear to me.

The disparity function is proved to be primitive recursive in the following way:

$$disparity(x_0,x_1)=(x_0-x_1)-(x_1-x_0) = add(subtract(x_0,x_1),subtract(x_1,x_0) \\ = add(subtract(x_0,x_1), subtract(pr^1_2(x_0,x_1),pr^0_2 (x_0,x_1)))$$

where $subtract$ is defined as a subtraction for $subtract(x,y)=x-y$ where $y<x$ and it returns $0$ otherwise.

The question is why do we need to use the projection in the last subtraction operation?

1

There are 1 best solutions below

0
On BEST ANSWER

Are you sure you typed that in right? I would think the final equivalence would be:

$$add((subtract(pr^0_2(x_0,x_1),pr^1_2 (x_0,x_1)),(subtract(pr^1_2(x_0,x_1),pr^0_2 (x_0,x_1)))$$

When we break down our primitive recursive function completely, the reason we write "$subtract(pr^1_2(x_0,x_1), pr^0_2(x_0,x_1))$" instead of just writing "$subtract(x_1, x_0)$" becomes more evident when we think of the $subtract$ function as its own function $f$. (I will assume we have the 2-ary $subtract$ function defined and will not break it down).

If we were to write it without projection functions, the proper but incorrect way would be:$$f(x_0,x_1)=subtract((x_0,x_1), (x_0,x_1))$$

Which is nonsensical. Writing it the correct way gets a little tricky because the subtraction function is itself a 2-ary function, yet our input has not been broken down from its 2-ary form into two separate 1-ary inputs. We cannot go from the 2-ary input $(x_0,x_1)$ of $f$ to two separate 1-ary inputs for the 2-ary $subtract$ without explanation. Thus the projection function takes our 2-ary input, rewrites it as two separate 1-ary inputs to but put back into our 2-ary subtraction function, as follows:

$$f(x_0,x_1) =subtract(pr^0_2(x_0,x_1),pr^1_2 (x_0,x_1)) $$

I hope that helped!