\documentclass{amsart}

\title{21-300 F15 HW 1}

\begin{document}

\maketitle

Please read the instructions on the course webpage regarding preparation and submission of
  homework sets!

\begin{enumerate}

\item  Recall that we defined an inductive structure to generate the wff's of propositional logic as follows:
 The wffs are finite strings of symbols from the alphabet
\[
    \{ A_n : n \in {\mathbb N} \} \cup \{ (, ) \} \cup \{ \vee, \wedge, \neg, \rightarrow \}
\]
     $B$ is the set of all strings
   of length $1$ of form $A_n$, and $K = \{ F_\vee, F_\neg, F_\wedge, F_\rightarrow \}$
   is  a family of functions for generating strings: $F_\vee(s, t) = (s \vee t)$,
   $F_\wedge(s, t) = (s \wedge t)$, $F_\rightarrow(s, t) = (s \rightarrow t)$, $F_\neg(s) = (\neg s)$.
  We showed in class that this has unique readability. The set $C$ of wffs is the closure of $B$ under $K$.

\begin{enumerate}

\item  Define a function $G: C \rightarrow {\mathbb N}$ by the following recursion:
   $G(A_n) = 1$ for all $n$, $G( (s \vee t) ) = G(s) + G(t)$,
   $G( (s \wedge t) ) = G(s) + G(t)$, $G( (s \rightarrow t) ) = G(s) + G(t)$,
   $G( (\neg s) ) = G(s)$.

   What is $G$? For full credit your answer should include an inductive proof that
   your description of $G$ is correct.

\item Give a recursive definition for each of the following functions on $C$. For full credit each answer should
   include an inductive proof that the definition is correct.

\begin{enumerate} 

\item  The function which returns the length of the string $s$ for each $s \in C$.

\item  The function which returns the set of propositional letters appearing in $s$ for each
   $s \in C$.

\end{enumerate} 

\item  Is it possible to give a recursive definition for the function from $C$ to $\mathbb N$ which returns 
   the number of distinct propositional letters appearing in $s$? 


\end{enumerate}

\item (This exercise is intended to motivate our restriction to finitary functions) Let 
   $X$ be the set of all subsets of $\mathbb N$, let $X^{\mathbb N}$ be the set of
   all infinite sequences $(x_n : n \in {\mathbb N})$ from $X$, and let
   $F: X^{\mathbb N} \rightarrow X$ be the function that returns $\{ n : n \notin x_n \}$ 
   on the argument $(x_n : n \in {\mathbb N})$. 

   Given $Y \subseteq X$ we will say that $Y$ is {\em closed under $F$} if 
   $F( (y_n : n \in {\mathbb N} ) ) \in Y$ for all sequences such that $y_n \in Y$ for all $n$.

\begin{enumerate}

\item  Prove that $F( (x_n : n \in {\mathbb N}) ) \neq x_n$.  

\item  Prove that no countable set $Y \subseteq X$ is closed under $F$.

\item  Let $B = \{ \emptyset \}$ and let $Y$ be such that $B \subseteq Y \subseteq X$ and
    $Y$ is closed under $F$. Prove that $Y = X$.

\end{enumerate}
  
\item   An absent-minded professor messes up the definition of the wff's of propositional logic by 
   leaving out all the right parentheses, that is by writing
     ``$B$ is the set of all strings
   of length $1$ of form $A_n$, and $K = \{ F_\vee, F_\neg, F_\wedge, F_\rightarrow \}$
   is  a family of functions for generating strings: $F_\vee(s, t) = (s \vee t$,
   $F_\wedge(s, t) = (s \wedge t$, $F_\rightarrow(s, t) = (s \rightarrow t$, $F_\neg(s) = (\neg s$.''

   Is the resulting inductive structure uniquely readable?




\end{enumerate}

\end{document} 



