% -----------------------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}
\newcommand{\code}[1]{\ulcorner #1 \urcorner}

% 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.14} % 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}\\
Let $\mathfrak{A}$ be a non-standard model of $\mathsf{PA}$, and $a \in A$ be an arbitrary non-standard element. Then, in $\mathfrak{A}$, let $\mathrm{K}(\mathfrak{A}\,; a) $ denote the set of all element $b \in A$ that can be defined by the formula $\varphi(x, a)$ (does not include parameters other than $a$). That is, $\mathrm{K}(\mathfrak{A}\,; a) $ denote the set of $b$'s such that $\mathfrak{A }_{\{a, b\}} \models \forall x (x = b \leftrightarrow \varphi(x, a))$. Then prove the following.

(1) By restricting functions and relations of $\mathfrak{A}$ to that of $\mathrm{K}(\mathfrak{A}\,; a)$,  $\mathrm{K}(\mathfrak{A}\,; a)$ can be seen as a substructure of $\mathfrak{A}$. $\mathrm{K}(\mathfrak{A}\,; a)$ is an elementary substructure of $\mathfrak{A}$.

(2) Prove that the following set is recursive and finitely satisfiable, but it cannot be realized by $\mathrm{K}(\mathfrak{A}\,; a)$.
\begin{align*}
\Phi(x, a) =  \{ \exists v \varphi(v, a) \to \exists v \!< \! x \ \varphi(v, a): \varphi(v, u) &\mbox { contains no free variables} \\
&\mbox {  or parameters other than } u, v  \}
\end{align*}
\vspace{1em}

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

\newpage
\noindent \textbf{Problem 2}\\
Let $\mathfrak{A} = (A, +, \boldsymbol{\cdot}, 0, 1, <)$ be a non-standard model of $\mathrm{I} \Sigma_1$. Show that $\mathfrak{A'} = (A,  +, 0, 1, <)$ is recursively saturated.

\vspace{1em}

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


\end{document}




