math - How can I show that a function is always not commutative -

i have following vexing problem. have implemented following function:

function bool less(nat x, nat y) {     if (y<>0)        if (x<>0)            return less(x-1,y-1);        else            return true;        end;     else        return false;     end; end; 

how can show x,y following less(x,y) , less(y,x) not possible @ same time?

bye

(c) 2010, jan burse, 8004 zürich

well, first of ask consider case of less(-1, -2), have define function on bounds of n ≥ 0. when first input equal second return true both orderings, have assume x ≠ y.

i use proof contradiction.

assume x , y x , y both ≥ 0 , x≠y, less(x,y) , less(y,x) both true.

this imply while x , y both nonzero, subtract 1 them n times until 1 of them zero, checking x first. function returns true when first operand reaches zero, false when second operand reaches 0 while first nonzero.

there 2 cases this:

1. x reaches 0 first. in case n = x, because 0 = x - n(1).
2. y reaches 0 first. in case n = y, because 0 = y - n(1).

by our assumption, less(x,y) returned true, meaning function iterated x times, after x - x(1) = 0 , y - x(1) > 0 (because y ≠ x, , function didn't return false before hand).

similarly, less(y,x) returned true, meaning function iterated y times, after y- y(1) = 0 , x - y(1) > 0 (same reasons before).

this gives 2 useful relations: y - x > 0 , x - y > 0. rearranged: y > x , x > y (the semantic meaning of function, have achieved definition of how function works , have reduced pure mathematics can work axioms for).

from y > x , x > y, can rearrange x > x , y > y (if x greater y, greater things y greater than. y greater x, therefore x greater x).

this logical contradiction, , therefore our assumption (that both true) incorrect.

therefore, proof contradiction, when x ≠ y, , x,y ≥ 0, function less cannot return true both less(x,y) , less(y,x).

(it's been while since had proof (though i'm going have coming practice) might bit rusty. if 1 sees error, please point out , try fix it)