\documentclass[11pt]{article}
\usepackage{hw}
\newcommand{\mdot}{\cdot}
\newcommand{\fa}{\forall}
\begin{document}

\dotitle{10}{Thursday, December 7}


\begin{enumerate}

\item  Let $L$ be a language with two unary predicates, $A$ and $B$. Consider
the equivalence
\[
\exists x (A(x) \land B(x)) \liff \exists x A(x) \land \exists x B(x).
\]
\begin{enumerate}

\item Show that one direction is valid, using only semantic notions.
In particular, your answer should make it clear that you know what ``valid'' means!

\item Show that the other direction is not valid.
\end{enumerate}


\item Find a prenex sentence (i.e.~one where all the quantifiers occur up
front) equivalent to the following:
\[
\lnot (\ex x A(x) \limplies \fa y B(y))
\]
Prove the equivalence algebraically.


\item Give natural deduction proofs of the following validities (using the 4 quantifier rules, and not defining $\exists\varphi$ as $\neg\fa\neg\varphi$\ !).
\begin{enumerate}

\item $\lnot \ex x \ph(x) \limplies \fa x \lnot \ph(x)$

\item  $\ex x \lnot \ph(x) \limplies \lnot \fa x \ph(x)$

\item $(\ex x \ph \limplies \psi) \limplies \fa x (\ph \limplies \psi)$, 
where $x$ is not free in $\psi$.

\end{enumerate}

\item Formalize the following argument in first-order logic, and determine whether it is valid (justify your answer).

% change 
\begin{quote}
Some Greeks are not philosophers.\\
No slaves are philosophers.\\
Therefore, some Greeks are not slaves.
\end{quote}

\item State and prove the Compactness Theorem.

\item \begin{enumerate}
\item State the Model Existence Lemma.
\item State the Completeness Theorem.
\item Assuming the Model Existence Lemma, prove the Completeness Theorem.
\end{enumerate}


\item The language of \emph{linear orders with endpoints} has two constant symbols $0, 1$ and a binary relation symbol, written $x\leq y$. The axioms for linear orders with endpoints are:

\begin{itemize}
\item[] reflexivity:\quad  $\forall x\ (x\leq x)$,
\item[] transitivity:\quad $\forall x,y,z\ ((x\leq y \wedge y\leq z) \to x\leq z)$,
\item[] antisymmetry: \quad $\forall x,y\ ((x\leq y \wedge y\leq x) \to x=y)$,
\item[] linearity:\quad  $\forall x,y\ (x\leq y)\vee (y\leq x)$,
\item[] endpoints: \quad $\forall x\ (0\leq x)\wedge(x\leq 1)$.  
\end{itemize}

Consider the following models of the theory of linear orders with endpoints:
\begin{align*}
\mathcal{I} &= ([0,1] \subseteq\mathbb{R}, 0, 1, \leq)\\
&\qquad \text{ (the usual ordering of unit interval in the reals)}\\
\mathcal{N} &= (\mathbb{N}\cup\{\infty\}, 0, \infty, \leq)\\
&\qquad \text{ (the usual ordering of the natural numbers,}\\
&\qquad\quad\text{ but with a new element $\infty$ added at infinity)}
\end{align*}

\begin{enumerate}

\item 
Show that these models are distinguishable in first-order logic by producing a sentence that is satisfied by one but not the other.

\item
Can there be a model that satisfies all the same first-order sentences as $\mathcal{N}$ and is uncountable?  Justify your answer!

\item\addstar (for Grad Students) 

Using compactness, show that there are models of this theory that are strictly larger than $\mathcal{I}$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{enumerate}
\end{enumerate}
\end{document}