\documentclass{article}
\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{amssymb}
\newcounter{probcnt}
\newenvironment{problem}{\stepcounter{probcnt}{\bf Problem \arabic{probcnt}}.}{}
\newcounter{pracprobcnt}
\newenvironment{pracproblem}{\stepcounter{pracprobcnt}{\bf Practice Problem \arabic{pracprobcnt}}.}{}
\setlength{\parskip}{.4cm}
\setlength{\baselineskip}{15pt}
\setlength{\parindent}{0cm}
\newcommand{\compl}[1] {\overline{#1}}
\newcommand{\meanl} {[\![}
\newcommand{\meanr} {]\!]}
\newcommand{\means}[1] {\meanl #1 \meanr}
\newcommand{\propsem}[2] {#1\means{#2}}
\newcommand{\logprf} {\vdash}
\newcommand{\logcnsq} {\models}
\newcommand{\polyred}[2] {#1\: \leq_{\mathrm{P}}\: #2}
\newcommand{\mred}[2] {#1\: \leq_m\: #2}
\newcommand{\rec} {\mbox{REC}}
\newcommand{\re} {\mbox{RE}}
\newcommand{\core} {\mbox{co-RE}}
\newcommand{\dtime}[1] {\mbox{DTIME}(#1)}
\newcommand{\ntime}[1] {\mbox{NTIME}(#1)}
\newcommand{\dspace}[1] {\mbox{DSPACE}(#1)}
\newcommand{\nspace}[1] {\mbox{NSPACE}(#1)}
\newcommand{\polytime} {\mbox{P}}
\newcommand{\nptime} {\mbox{NP}}
\newcommand{\conp} {\mbox{co-NP}}
\newcommand{\lgspc} {\mbox{L}}
\newcommand{\expt} {\mbox{EXP}}
\newcommand{\nlgspc} {\mbox{NL}}
\newcommand{\nexpt} {\mbox{NEXP}}
\newcommand{\pspc} {\mbox{PSPACE}}
\newcommand{\co}[1] {\mbox{co-}#1}
\author{}
\date{}
\begin{document}
\hrule
\begin{center}
{\LARGE \sc $\underline{\mbox{Homework 3}}$} \\
{\Large \sc CS 498 MV: Logic in Computer Science}\\
\ \\
\begin{tabular}{ll}
Assigned: October 8, 2018 & Due on: October 16, 2018
\end{tabular}
\end{center}
\hrule
{\bf Instructions:} Please do not turn in solutions to the practice
problems. Solutions to the homework problems should be turned in as a
PDF file on Gradescope. See instructions on Piazza.
{\bf Recommended Reading:} Lectures 3, 8, and 9: Compactness theorem
and first order logic.
$\underline{\mbox{\bf Practice Problems}}$
\begin{pracproblem}
Express the following statements using predicates, quantifiers,
logical connectives, and mathematical operators.
\begin{enumerate}
\item The product of two negative numbers is positive.
\item The difference of a real number and itself is zero.
\item Every positive real number has exactly two square roots.
\end{enumerate}
\end{pracproblem}
\begin{pracproblem}
Show that the following sentences are not valid by constructing a
structure in which they do not hold.
\begin{enumerate}
\item $(\forall x \exists y P(x,y)) \rightarrow (\exists y \forall x
P(x,y))$
\item $\neg ((\forall x \exists y P(x,y)) \rightarrow (\exists y
\forall x P(x,y)))$
\item $(\forall x \exists y P(x,y)) \rightarrow (\exists y P(y,y))$
\end{enumerate}
\end{pracproblem}
\begin{pracproblem}
Show that the names of bound variables are unimportant. In other
words, show that $\forall x \varphi$ is logically equivalent to
$\forall y \varphi^x_y$, where $y$ is a fresh variable not appearing
in $\varphi$.
\end{pracproblem}
\newpage
$\underline{\mbox{\bf Homework Problems}}$
\begin{problem}
Recall that a set of sentences $\Gamma$ is satisfiable, if there is a
structure ${\cal A}$ such that for every $\varphi \in \Gamma$, ${\cal
A} \models \varphi$. Further $\Gamma$ is finitely satisfiable if
every finite subset of $\Gamma$ is satisfiable. Show that if a set of
sentences $\Gamma$ is finitely satisfiable then $\Gamma$ is
satisfiable. Assume that the signature $\tau$ being considered is
finite. {\em Hint:} Follow the idea behind the proof using Henkin
models of the compactness theorem for propositional logic (Section 3.2
of lecture 3 notes). That is, starting from $\Gamma$, construct a
sequence $\Delta_0, \Delta_1, \ldots$ in the following manner. Let
$c_1, c_2, \ldots$ be an infinite sequence of constant symbols not in
$\tau$, and let $\varphi_1, \varphi_2, \ldots$ be an enumeration of
sentences over signature $\tau \cup \{c_1,c_2,\ldots\}$
\begin{itemize}
\item {\bf Case 1:} If $\Delta_i \cup \{\varphi_{i+1}\}$ is finitely
satisfiable then $\Delta_{i+1} = \Delta_i \cup \{\varphi_{i+1}\}$
\item {\bf Case 2:} If $\Delta_i \cup \{\varphi_{i+1}\}$ is not
finitely satisfiable and $\varphi_{i+1}$ is not of the form $\forall
x \psi$ then $\Delta_{i+1} = \Delta_i \cup \{\neg \varphi_{i+1}\}$
\item {\bf Case 3:} If $\Delta_i \cup \{\varphi_{i+1}\}$ is not
finitely satisfiable and $\varphi_{i+1}$ is of the form $\forall x
\psi$ then $\Delta_{i+1} = \Delta_i \cup \{\neg \varphi_{i+1}, \neg
\psi^x_c\}$, where $c$ is the first symbol in the list $c_1, c_2,
\ldots$ not appearing in $\Delta_i$
\end{itemize}
Show that $\Delta_i$ is finitely satisfiable for all $i$, and so is
$\Delta = \bigcup_i \Delta_i$. Then conclude that the sentences in
$\Delta$ can be used to construct a structure satisfying $\Delta$ and
hence $\Gamma$.
\end{problem}
\begin{problem}
The compactness theorem is evidence that first order logic is weak,
from an expressive standpoint. Consider the signature of graphs
$\tau_G = \{E\}$, where $E$ is a binary relation. Prove that there is
no sentence $\psi$ over $\tau_G$ such that a structure ${\cal A}
\models \psi$ if and only if ${\cal A}$ is finite. That is, you cannot
express in first order logic that a structure has a finite universe.
\end{problem}
\begin{problem}
Consider a signature $\tau$ that does not have any constant
symbols. That is, $\tau$ only has relation symbols. Consider a
$\tau$-structure ${\cal A} = (A, \{R^{\cal A}\}_{R \in \tau})$. A
structure ${\cal B} = (B, \{R^{\cal B}\}_{R \in \tau})$ is said to be
a \emph{submodel} of ${\cal A}$ if $B \subseteq A$ and for every $R
\in \tau$, $R^{\cal B} = R^{\cal A} \cap B^k$, where $k$ is the arity
of $R$. In other words, the universe of ${\cal B}$ is a subset of
${\cal A}$ and every relation symbol has the same interpretation as
${\cal A}$ except that it is restricted to be over the tuples of $B$.
\begin{enumerate}
\item A sentence $\varphi$ is said to be \emph{universal} if it is of
the form $\forall x_1\forall x_2\cdots \forall x_n \psi$, where
$\psi$ has no quantifiers. Prove that for any universal sentence
$\varphi$, and two structures ${\cal A}$ and ${\cal B}$ such that
${\cal B}$ is a substructure of ${\cal A}$, if ${\cal A} \models
\varphi$ then ${\cal B} \models \varphi$.
\item Let $P$ be a unary relation symbol in $\tau$. Using the previous
part, prove that the sentence $\exists x Px$ is not equivalent to
any universal formula.
\end{enumerate}
\end{problem}
\end{document}