Question

1. The equality operation on naturals is correctly computed by the following pseudo-Java method:

boolean equals (natural x, natural y) {

if (zero(x)) return zero(y);

return equals(pred(x), pred(y));

}

2. Suppose we define a function f from naturals to naturals as follows. We define f(0) to be 0, and for any natural x we define f(Sx) to be 1. Then this function satisfies the equation f(x · y) = f(x) · f(y), for any naturals x and y.

3.

Suppose I want to prove "for all x: S0 + x = Sx". The following is valid:

Ordinary induction on all naturals x.

Base case: x = 0, the desired formula becomes "S0 + 0 = S0". This is true by the base case of the definition of addition.

Inductive hypothesis: S0 + x = Sx

Inductive goal: S0 + Sx = S(Sx)

Proof of inductive step: By the inductive case of the definition of addition, S(S0 + x) = S0 + Sx. By the inductive hypothesis, applied inside the parentheses, the left-hand side of this equation is equal to S(Sx)). So the inductive goal is true.

Please help with True or False Questions

Answer 1

The solutions for the above questions is given below and if you feel any problem then feel free to ask.

1. True, because the function is of type boolean and returning bool, also the function is taking two arguments as natural x and y. And in the first case zero function returns a boolean value if x is zero then the function will return the boolean value for y whether it is zero or not and after if the function is return the boolean for whether x and y are equal or not.

2. True, as the f(0) =0 and for any x f(Sx)=1. Then taking f(x.y) we can write it as f(x).f(y) as the value for f(x) =1 and f(y) =1 and x.y is also a natural number or zero if x or y is zero then the value of f(x.y) becomes equal to 0 or 1. And, similarly the value of f(x).f(y) is either 0 or 1 (0 if any number is zero).

3. False, as the base condition is S0 + 0 =S0 which is true according to condition. And now taking the inductive hypothesis we get S0+n =Sn for n=x

and for the inductive step, for n=x+1

S0+(n+1) = S0 +n+1 = Sn+1 = S(n+1)

Here in the above question the goal for inductive step is not correct as the inductive step is used to prove the truthiness of our inductive hypothesis by proving it true for the next step i.e., n+1. But in the given case it is just putting the value of hypothesis in the equation instead of the next step.