Recall the definition of linked lists from class. Consider this (incomplete) definition: Definition The function \(\textit{increment} : \underline{\hspace{6em}}\) that adds 1 to the data in each node of a linked list is defined by: \[\begin{array}{llll} & & \textit{increment} : \underline{\hspace{3em}} & \to \underline{\hspace{3em}} \\ \textrm{Basis Step:} & & \textit{increment}([]) & = [] \\ \textrm{Recursive Step:} & \textrm{If } l \in L, n \in \mathbb{N} & \textit{increment}((n, l)) & = (1 + n, \textit{increment}(l)) \end{array}\] Consider this (incomplete) definition: Definition The function \(\textit{sum} : L \to \mathbb{N}\) that adds together all the data in nodes of the list is defined by: \[\begin{array}{llll} & & \textit{sum} : L & \to \mathbb{N} \\ \textrm{Basis Step:} & & \textit{sum}([]) & = 0 \\ \textrm{Recursive Step:} & \textrm{If } l \in L, n \in \mathbb{N} & \textit{sum}((n, l)) & = \underline{\hspace{8em}} \end{array}\] You will compute a sample function application and then fill in the blanks for the domain and codomain of each of these functions.

1. Based on the definition, what is the result of \(\textit{increment}((4, (2, (7, []))))\)? Write your answer directly with no spaces.

2. Which of the following describes the domain and codomain of increment?

   2

   1. The domain is \(L\) and the codomain is \(\mathbb{N}\)

   2. The domain is \(L\) and the codomain is \(\mathbb{N} \times L\)

   3. The domain is \(L \times \mathbb{N}\) and the codomain is \(L\)

   4. The domain is \(L \times \mathbb{N}\) and the codomain is \(\mathbb{N}\)

   5. The domain is \(L\) and the codomain is \(L\)

   6. None of the above

3. Assuming we would like \(sum((5, (6, [])))\) to evaluate to \(11\) and \(sum((3, (1, (8, []))))\) to evaluate to \(12\), which of the following could be used to fill in the definition of the recursive case of sum?

   2

   1. \(\begin{cases} 1 + \textit{sum}(l) & \textrm{when } n \neq 0 \\ \textit{sum}(l) & \textrm{when } n = 0 \\ \end{cases}\)

   2. \(1 + \textit{sum}(l)\)

   3. \(n + \textit{increment}(l)\)

   4. \(n + \textit{sum}(l)\)

   5. None of the above

4. Choose only and all of the following statements that are well-defined; that is, they correctly reflect the domains and codomains of the functions and quantifiers, and respect the notational conventions we use in this class. Note that a well-defined statement may be true or false.

   2

   1. \(\forall l \in L \, (\textit{sum}(l))\)

   2. \(\exists l \in L \, (\textit{sum}(l) \land \textit{length}(l))\)

   3. \(\forall l \in L \, (\textit{sum}(\textit{increment}(l)) = 10)\)

   4. \(\exists l \in L \, (\textit{sum}(\textit{increment}(l)) = 10)\)

   5. \(\forall l \in L \, \forall n \in \mathbb{N} \, ((n \times l) \subseteq L)\)

   6. \(\forall l_1 \in L \, \exists l_2 \in L \, (\textit{increment}(\textit{sum}(l_1)) = l_2)\)

   7. \(\forall l \in L \, (\textit{length}(\textit{increment}(l)) = \textit{length}(l))\)

5. Choose only and all of the statements in the previous part that are both well-defined and true.