Could someone please answer part a and c (or d)

Code Example 6.9. We give a Java class that corresponds to this definition. public class Nat { public Nat next; public Nat (Nat n) {next=n;} } This is a very odd class that one wouldn't want to use in practice, but the example here is to show you that this can be done. Note that this class does not have a built-in upper bound for the numbers so defined (unlike the Java class List). In practice the size of the numbers you can use in this way is limited by the machine's memory. Note also the way the class is constructed the number you get from using the argument encoding n is the number encoding n +1. You can picture an object of this class as shown below. Assume that we have a Nat object n4 with n.next=n3 and a Nat object n3 with n3.next=n2 and a Nat object n2 with n2.next=nl and a Nat object nl with nl.next=null. 308 You may picture these objects as follows: n4 n3 n2 nl dos Just as we need to count the number of symbols S to know which number is given by SSSSSSSSSSSSSSSSSSSSSSSSSSSO, so we have to check how many references we have to follow until we reach the null reference to know which number is given by some object of class Nat. Tip The standard structure for an inductive proof over the natural numbers is the following. Assume we have a statement given in terms of the variable n denoting an element of N. Base case. We show the statement for some number b. The base case is the case of the smallest number b for which the given statement holds, and it is obtained by replacing every occurrence of n by that smallest number. Ind hyp We assume that the statement holds for n (in which case it coin- cides with the given statement), or possibly all numbers that are less than or equal to n, and greater than or equal to the number b from the base case. Step case. We show the statement for Sn by proving the statement where every occurrence of n has been replaced by Sn. Below we do not give the induction hypothesis explicitly if it coincides with the statement we are proving. Example 6.34. As another example we show that m + Sn = Sm + n. (*) Often in a statement with two variables where induction is required it is sufficient to carry out the induction over one of the variables. Usually the better choice is to follow the pattern given by the recursive definition, here the definition of +, and so we carry out an induction over the variable n. Note that for more complicated statements it may be necessary to carry out a double induction proof, that is, a proof where induction has to be carried out over both arguments. We begin the proof of statement (*) with the base case, n = 0. Base case N. We have m+ S0 = S(m+0) step case + 311 = Sm base case + = Sm +0 base case +. Next one has to establish the step case, where Sn appears in the place of n, and where one may use the induction hypothesis, that is the claim Sm+n = m+Sn. Step case N. We have m+ SSn = S(m + Sn) = S(Sm+n) = Sm + Sn step case + induction hypothesis step case +. CExercise 136. Carry out the following tasks, justifying each step in your proofs. (a) Define a function d from N to N that doubles its argument, without refer- ring to the operations + or - (b) Give code that implements this operation for the class nat from Code Example 6.9. (c) Show that for all n e N we have dn = SSo.n. Hint: You may find property (*) useful, and you will definitely require addition in this proof. (d) Consider the function mod2 defined as follows: Base case mod2 : 0. Base case mod2 : SO. Step case mod2. mod 20 = 0. mod2S0 = SO. mod2(SSN) = mod2n. 313 How would you describe the action of this function? Why do we need two base cases to define this function? Show that for all n E N we have mod 2dn = 0. Code Example 6.9. We give a Java class that corresponds to this definition. public class Nat { public Nat next; public Nat (Nat n) {next=n;} } This is a very odd class that one wouldn't want to use in practice, but the example here is to show you that this can be done. Note that this class does not have a built-in upper bound for the numbers so defined (unlike the Java class List). In practice the size of the numbers you can use in this way is limited by the machine's memory. Note also the way the class is constructed the number you get from using the argument encoding n is the number encoding n +1. You can picture an object of this class as shown below. Assume that we have a Nat object n4 with n.next=n3 and a Nat object n3 with n3.next=n2 and a Nat object n2 with n2.next=nl and a Nat object nl with nl.next=null. 308 You may picture these objects as follows: n4 n3 n2 nl dos Just as we need to count the number of symbols S to know which number is given by SSSSSSSSSSSSSSSSSSSSSSSSSSSO, so we have to check how many references we have to follow until we reach the null reference to know which number is given by some object of class Nat. Tip The standard structure for an inductive proof over the natural numbers is the following. Assume we have a statement given in terms of the variable n denoting an element of N. Base case. We show the statement for some number b. The base case is the case of the smallest number b for which the given statement holds, and it is obtained by replacing every occurrence of n by that smallest number. Ind hyp We assume that the statement holds for n (in which case it coin- cides with the given statement), or possibly all numbers that are less than or equal to n, and greater than or equal to the number b from the base case. Step case. We show the statement for Sn by proving the statement where every occurrence of n has been replaced by Sn. Below we do not give the induction hypothesis explicitly if it coincides with the statement we are proving. Example 6.34. As another example we show that m + Sn = Sm + n. (*) Often in a statement with two variables where induction is required it is sufficient to carry out the induction over one of the variables. Usually the better choice is to follow the pattern given by the recursive definition, here the definition of +, and so we carry out an induction over the variable n. Note that for more complicated statements it may be necessary to carry out a double induction proof, that is, a proof where induction has to be carried out over both arguments. We begin the proof of statement (*) with the base case, n = 0. Base case N. We have m+ S0 = S(m+0) step case + 311 = Sm base case + = Sm +0 base case +. Next one has to establish the step case, where Sn appears in the place of n, and where one may use the induction hypothesis, that is the claim Sm+n = m+Sn. Step case N. We have m+ SSn = S(m + Sn) = S(Sm+n) = Sm + Sn step case + induction hypothesis step case +. CExercise 136. Carry out the following tasks, justifying each step in your proofs. (a) Define a function d from N to N that doubles its argument, without refer- ring to the operations + or - (b) Give code that implements this operation for the class nat from Code Example 6.9. (c) Show that for all n e N we have dn = SSo.n. Hint: You may find property (*) useful, and you will definitely require addition in this proof. (d) Consider the function mod2 defined as follows: Base case mod2 : 0. Base case mod2 : SO. Step case mod2. mod 20 = 0. mod2S0 = SO. mod2(SSN) = mod2n. 313 How would you describe the action of this function? Why do we need two base cases to define this function? Show that for all n E N we have mod 2dn = 0