MATHEMATICAL LOGIC

Idea $2\mathrm{.}23[$Inductive function definition$]$

Let S be defined inductively from basis B and some construction rule. to difine a function f on elements of S do the following:

Basis : : Specify the value f$($x$)$ for each x in B

Ind : : For each way an x in S can be obtained from some y$1,...$ yn in S$,$ specify how to obtain f$($x$)$ from the values f$($y$1)...$ f$($yn$).$

Clsr : : The closure of S ensures that f is defined for all x in S$.$

$\_\_\_\_\_\_\_\_\_\_$

Exercise $3$

Let $$ be an alphabet. We call its elements characters.

$($a$)$ We can implement finite sets of strings ${}^{*}$ as lists of strings.

Define an inductive function $f$ which checks if a given string win${}^{*}$ is in a list lin List ${}^{*}.$

$($b$)$ We can implement finite sets of strings $$ as tries of characters.

Define an inductive function $g$ which checks if a given string win${}^{*}$ is in a trie tin Trie $.$

$($c$)$ Do these inductive functions follow Idea $2\mathrm{.}23,$ one of the extensions earlier in this exercise set, or

do you need to create yet another idea to make the above work?

Provide details for your answer.