\documentclass{article}

\usepackage{amsmath}
\usepackage{amssymb}

\usepackage{bussproofs}

\newcommand{\con}{{\bigwedge \hspace{-2.5mm} \bigwedge}}
\newcommand{\dis}{\bigvee \hspace{-2.5mm} \bigvee}

\newcommand{\unsat}{unsatisfiable}
\newcommand{\sat}{satisfiable}


\title{History of Logic\\
Midterm Exam (Take Home)} 
\author{Joost J.\  Joosten}
\begin{document}
\maketitle

This Exam is a good indication as to the level of the final exam. Of course, we have only covered half of the material so far. Please submit your answers by email to me before May 23, say, 18:00. Of course, this week, you will not need to invent a question and answer two others, or do any of the discussion posts. 

%Zeer bruikbaar: Logica voor Filosofen 2005
 
\begin{enumerate}
\item
Enumerable and decidable sets.
\begin{enumerate}
\item
Show that if $A$ is computably enumerable and $B$ is decidable, then $A \setminus B$ is computably enumerable.

\item
Show that the intersection of two computably enumerable sets is again computably enumerable

\item
It is not the case that $A$ is computably enumerable and $B$ is decidable, then $A \setminus B$ is decidable. Give a counterexample.

\item
It is not the case that $A$ is computably enumerable and $B$ is computably enumerable, then $A \setminus B$ is computably enumerable. Give a counterexample.

\end{enumerate}

\item
With ${\sf RFN}_T(\Pi_1 )$, we denote so-called $\Pi_1$-reflection. This says that any $\Pi_1$ statement (Goldbach-like) that is provable in $T$ is actually true. In symbols: 
\[
\Box_T \pi \ \ \Rightarrow \ \ \pi \ \ \ \ \mbox{for $\pi \in \Pi_1$}.
\]
Prove that ${\sf Con}(T)$ and ${\sf RFN}_T(\Pi_1 )$ are equivalent.

\item
Give an example of a consistent theory that proves its own inconsistency.

\item
Show that G\"odel's fixed point G is actually Goldbach-like.

\item
Consider the Rosser Sentence from the book. Let us call it $R_T$ for the moment. 
\begin{enumerate}
\item
Show that $R_T$ is a $\Pi_1$ sentence.
\item
Show that a theory $T$ is consistent, then its Rosser sentence $R_T$ will be undecidable in $T$.
\end{enumerate}

\item
Let us consider one half of the first incompleteness theorem where $G$ stands for G\"odel's fixed point.
\[
\begin{array}{ll}
(1) \ \ \ \vdash G \ \Rightarrow \ \vdash {\sf Bew}(\ulcorner G \urcorner) &
\mbox{ because of \ldots}\\

(2) \ \ \ \vdash G \ \Rightarrow \ \vdash \neg {\sf Bew}(\ulcorner G \urcorner) &
\mbox{ because of \ldots}\\

(3) \ \ \ \vdash G \ \Rightarrow \ \vdash \bot &
\mbox{ because of \ldots}\\

(4) \ \ \ {\sf Con}(T) \ \Rightarrow \ \not \vdash G &
\mbox{ because of \ldots}\\


\end{array}
\]
\begin{enumerate}
\item
Fill out the dots in the above reasoning giving a concise justification for the particular step.

\item
Show that G\"odel's second incompleteness theorem implies the first.

\item
Show how a close inspection of the above reasoning, together with some extra observations and the fact that $G$ is undecidable in $T$ gives a proof of the second incompleteness theorem. 


\end{enumerate}

\end{enumerate}
\end{document}