dea $2\mathrm{.}15$ An inductive definition of a set $S$ consists of

BASIS :: a list of some $($at least one$)$ elements BsubeS,

IND. :: one or more rules to construct new elements of $S$ from already

existing elements,

CLSR$.$ :: the statement that $S$ contains only the elements obtained from

the basis by the induction steps.

Saying that something is defined by induction, the closure condition be

comes implicitly assumed and is not stated.

$-----------$

Exercise $2$

$($a$)$ Define APIs as $I=($:$T,F$:$),T$ is some set of type names and every $(f$:$t_{1}dots{t}_{k}t)inF$ being a

function declaration with arguments $t_1,$dots,$t_k$inT and result tinT. A function with $0$ arguments

is called a constant. Let $V$ be a set of variable names typed by a function type : $VT.$

Define the set $E_{\text{I}\text{,}V,t}$ of type correct expressions of type $t$ for interface I and variables $V.$ The base

case are the variables of type $t$ and all constants of type $t.$ The constructors are the non$-$constant

functions of type $t.$ Note that the inductive case will need to depend on the set of expressions for

each of the argument types of the constructors.

To make this work, you need to modify Idea $2\mathrm{.}15($inductive definition of a set$).$

$($b$)$ Consider the inductive constructors ${?}^1$ for a linked list over a set $S$ :

Define an API for this data type. We can treat the set $S$ as a set of variables and define the

inductive set of list expressions on $S.$

$($c$)$ Consider the inductive constructors for a binary tree:

$\backslash$langle$\backslash$rangle : Tree $S$

Branch$(L,s,R)$: Tree $SS$ Tree $S$ Tree $S$

Define an API for this data type. We can treat the set $S$ as a set of variables and define the

inductive set of list expressions on $S.$

$($d$)$ Show that for ninN and the set B$,$ the indexed sets

$)n$

are equivalent to the APIs and inductive definitions of lists and trees.