\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{1}

% title command
\newcommand{\mytitle}[1]{\begin{center} {\Large Intro to Cognitive Science -- 
9.62J Problem Set \psnum \\ Juliet Bourne -- #1} \\ \vspace{-.1in}
\rule{6in}{.5mm} \end{center}}
% problem command
\newcommand{\prob}[1]{\vspace{.15in}\noindent{\fbox{\large\bf Problem #1}}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}
% newpage setup command 
\newcommand{\mynewpage}{\newpage\noindent
\begin{center}
{\Large 9.62J Problem Set \psnum -- Juliet Bourne -- {\bf Page \thepg}}
\rule{6in}{.5mm}
\end{center}
\addtocounter{pg}{1}}

\begin{document}

\mytitle{9/20/90}

\prob{1}

Since {\em A} and {\em B} can be generated by programs (by the
definition of r.e.), the union of {\em A} and {\em B} can also be
generated by a program and is therefore also r.e. For example, let's
say that {\em A} is generated by $P_A$ and {\em B} by $P_B$. A program
$P_{A\cup B}$ can then be made which calls $P_A$ to generate {\em A}
and then $P_B$ to generate {\em B}. $P_{A\cup B}$ therefore generates
the union of {\em A} and {\em B}.

\prob{2}

Given two set {\em A} and {\em B} which are r.e., there is no
guarantee that the intersection of these two sets will also be r.e.
For example, suppose that {\em A} is the infinite set all of the odd
numbers and that {\em B} in the infinite set of all the even numbers.
Both of these are r.e. The intersection of {\em A} and {\em B} is the
empty set. However, if we created a program to generate $A \cap B$, it
would sit there forever, never returning anything. This behavior would
be indistinguishable from the program being in a loop.

\prob{3}

From the definition of recursive sets, {\em A} and {\em B} are r.e. as
well $\bar{A}$ and $\bar{B}$. Therefore, $A \cup B$ is r.e. and
$\bar{A} \cup \bar{B}$ is r.e. So, by the definition of recursive
sets, $A \cup B$ is also recursive.

\prob{4}

Using the assertion that the intersection of two r.e. sets is not
necessarily r.e., we can show that the intersection of two recursive
sets is not necessarily recursive. Since $A \cap B$ and $\bar{A} \cap
\bar{B}$ are not necessarily r.e., then, by the definition of
recursive sets, $A \cap B$ is not necessarily recursive.

\prob{5}

If a set, say {\em A}, is r.e., its complement $\bar{A}$ is not
necessarily r.e. Using the example given in class:

Given that $K = \{i \mid i \in W_i\} = \{i \mid P_i(i) \downarrow \}$, we
can see that $K$ is r.e. since there a program $P_i$ which halts for
every member of $K$. Its complement $\bar{K}$, however, is not. If we
assume that it is r.e., then $\bar{K} = W_j$. Therefore, $j \in
\bar{K} \; iff \; j \in W_j \; iff \; j \in K$, which is a
contradiction. So, $K$ is r.e. but its complement $\bar{K}$ is not.

\prob{6}

A subset of {\em A} (which is r.e. by definition of recursive sets)
will also be r.e. since the program $P_A$ halts for every member of
{\em A}, including the subset of {\em A}. A similar argument can be
made for a subset of $\bar{A}$ which is also r.e. since {\em A} is
recursive. Therefore, a subset of {\em A} will be recursive.

\prob{7}

A superset of the recursive set {\em A} is not necessarily also
recursive. There is no guarantee that $P_A$ will halt for the
additional members of the superset. Nor is there a guarantee that a
program can be found to generate this superset.

\end{document}


