% -----------------------acknowledge for overleaf and designer of this template-----------------------
\documentclass[12pt]{exam}
\usepackage{amsthm}
\usepackage{libertine}
\usepackage[utf8]{inputenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{ascmac}
\usepackage{multicol}
\usepackage[shortlabels]{enumitem}
\usepackage{siunitx}
\usepackage{cancel}
\usepackage{graphicx}
\usepackage{pgfplots}
\usepackage{listings}
\usepackage[all]{xy}

% automata
%\usepackage{tikz}
%\usetikzlibrary{automata, positioning, arrows}


\pgfplotsset{width=10cm,compat=1.9}
\usepgfplotslibrary{external}
\tikzexternalize

\newcommand{\class}{\Large Logic and Foundations I, Autumn 2023 } % This is the name of the course
\newcommand{\examnum}{Homework No.12} % This is the index of the homework https://www.overleaf.com/project/650b9566039710695765623c
\newcommand{\examdate}{Due:  }% This is the due date
\newcommand{\examname}{Name:    }
% Your name here





\begin{document}
\pagestyle{plain}
\thispagestyle{empty}

\noindent
\begin{tabular*}{\textwidth}{l @{\extracolsep{\fill}} r @{\extracolsep{8pt}} l}
\textbf{\class} & & \textit{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}\\
&&\\
\textbf{\examnum} & &\textit{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}\\
\textbf{\examdate} &&\\
\textbf{\examname} &&\\
\end{tabular*}\\
\rule[2ex]{\textwidth}{2pt}
% ---

\noindent \textbf{Problem 1}\\
(1) $T$ is called $\omega$-consistent if for any formula $\varphi(x)$, if $T \vdash \varphi(\bar{n})$ for all $n \in \mathbb{N}$ then $T \not\vdash \exists x \neg \varphi(x)$.

\medskip
Show that a $\Sigma_1$-complete theory $T$ is 1-consistent iff it is
$\omega$-consistent with respect to the $\Sigma_0$ formulas $\varphi(x)$.

\bigskip
\noindent(2) $T$ is called $\Sigma_n$-consistent if any $\Sigma_n$ theorem of $T$ is true. Similarly for
$\Pi_n$-consistency.

\medskip
Show that if a $\Sigma_1$-complete theory $T$ is $\omega$-consistent, then it is $\Pi_3$-consistent,
but not necessarily $\Sigma_3$-consistent.


\vspace{1em}

\noindent\underline{\textsf{Solution:}}


\end{document}




