Lets define a function $f$ such that $\Bbb N \times\Bbb N \to\Bbb N$.
It takes two natural numbers as inputs and also outputs a natural number. Let $f$ have the following properties
- $f(a,b) = f(b,a)$ for all $a$ and $b$ in natural numbers
- $f(a,0) = a$ for all $a$ in natural numbers
- $f(a,b) = f(a-b,b)$ for all $a$ and $b$, when $a \ge b$ and $b \gt 0$
Now, I need to prove two things about $f$
Q1. Why is $f$ no longer well defined if we replace property 3 with $f(a,b) = f(a-b,a)$ for $a\ge b$ and $b > 0$?
Q2. Prove by induction that there exist integers $x$ and $y$ in natural numbers such that $xa + yb = f(a,b)$.
For Q1, i figured that if $a\ne b$, and both $a$ and $b \ne 0$ and $a>b$ then $f(a,b) = f(a-b,a)$
now we know $a-b < a$, but from property 1, $f(a-b,a) = f(a,a-b)$ and since $a> a-b$, $f(a, a-b) = f(a-a+b,a)$ which simplifies to $f(b,a)$ from property 3. then $f(b,a) = f(a,b)$
Now we can see the chain here as $f(a,b) = f(a-b,a) = f(a,a-b) = f(b,a)$
Can I argue that this function will never resolve for some $a$ and $b$ values, therefore its not well defined?
Im really not sure how to handle Q2. Which variables do I induct on?