\documentclass[11pt]{article}

\usepackage{homework,amssymb,eufrak}

\begin{document}

\soltitle{10}{Thursday, October 6}

\begin{list1} 
  
% \item[2.\hfill] We need to show that for every structure $\gmdl A$, we
%   have
% \[
% \gmdl A \models (\psi \limplies \ex x \ph(x)) \limplies \ex x (\psi
% \limplies \ph(x)).
% \]
% So let $\gmdl A$ be any structure. If $\gmdl A \not\models \psi
% \limplies \ex x \ph(x)$, we are done (because then the implication
% comes out true, in the semantics). So suppose $\gmdl A \models \psi
% \limplies \ex x \ph(x)$. Then either $\gmdl A \not\models \psi$, or
% $\gmdl A \models \ex x \ph(x)$. 

% In the first case, let $a$ be any element of $| \gmdl A|$. By the
% definition of the semantics for implication, $\gmdl A \models \psi
% \limplies \ph(\bar a)$, and so, $\gmdl A \models \ex x (\psi \limplies
% \ph(x))$.

% In the second case, for some $a$ in $|\gmdl A|$, $\gmdl A \models
% \ph(\bar a)$. But then, again by the definition of the semantics for
% implication, $\gmdl A \models \psi \limplies \ph(\bar a)$. And so in
% this case too we have $\gmdl A \models \ex x (\psi \limplies \ph(x))$.

% \item[3.\hfill] Consider the structure $\la \mathbb{N}, >^{\mathbb N}
%   \ra$. In this structure, $\fa x \ex y (y > x)$ is true, because for
%   every number there is one larger; but $\ex y \fa x (y > x)$ is
%   false, because there is no number that is bigger than every other
%   one.
  
%   You can also provide counterexamples by drawing pictures of graphs,
%   where $\fa x \ex y R(x,y)$ is interpreted as the assertion that
%   every vertex is connected to some other vertex, and $\ex y \fa x
%   R(x,y)$ is interpreted as the assertion that there is one vertex
%   that every other vertex is connected to. Or you can interpret
%   $R(x,y)$ as ``$x$ loves $y$,'' provided you present {\em specific}
%   structures involving sets of people and an account of who loves who.
  
% \item[12.\hfill] By Lemma 2.4.5, showing that $\lnot \ex y \fa x
%   (S(y,x) \liff \lnot S(x,x)$ is true in every structure amounts to
%  showing that $\ex y \fa x (S(y,x) \liff \lnot S(x,x)$ is false in
%  every structure.
%
% For the sake of a contradiction, suppose it were true in some structure
% $\A$. Using Lemma 2.4.5 again, this amounts to saying that there is an
% $a$ in the universe of $\A$ such that for every $b$ in the universe of
% $\A$, $S(\bar a, \bar b)$ and
% $\lnot S(\bar b, \bar b)$ have the same truth value. In particular,
% when $b=a$, we have that $S(\bar a, \bar a)$ and $\lnot S(\bar a, \bar
% a)$ have the same truth value. But this is impossible (again by Lemma
% 2.4.5). 

% Note that in this problem and in 2a, what you are really doing is
% using the semantic definitions to translate a statement of the form
% $\A \models \psi$ into a statement about $\A$ ``in the real world''---
% namely, what $\psi$ ``says'' about $\A$. Then you prove this statement
% informally, in the same manner that you might carry out an informal
% proof in any mathematics classroom.

% Once we have defined a proof system and shown that it is sound, the
% other alternative will be to give a formal proof, that is, to show
% $\vdash \psi$.

\item[6.\hfill] Each line below combines a number of steps. In the
  first step I rename all variables that are ``different,'' and use
  the fact that for arbitrary formulas $\eta$ and $\theta$, $\lnot
  (\eta \limplies \theta)$ is equivalent to $\eta \land \lnot \theta$.
  In the last step, there is flexibility in the order in which you
  bring quantifiers to the front.
% \[
% ((\fa x \ph(x) \limplies \ex y \psi(x,y)) \limplies \psi(x,x))
% \limplies \ex x \fa y \sigma(x,y)
% \]
% \begin{eqnarray*}
% & \equiv & \lnot ((\fa z \ph(z) \limplies \ex y \psi(x,y)) \limplies
% \psi(x,x)) \lor \ex u \fa v \sigma(u,v) \\
% & \equiv & ((\fa z \ph(z) \limplies \ex y \psi(x,y)) \land \lnot
% \psi(x,x)) \lor \ex u \fa v \sigma(u,v) \\
% & \equiv & ((\ex z \lnot \ph(z) \lor \ex y \psi(x,y)) \land \lnot
% \psi(x,x)) \lor \ex u \fa v \sigma(u,v) \\
% & \equiv & \ex {z,y,u} \fa v ((( \lnot \ph(z) \lor \psi(x,y)) \land \lnot
% \psi(x,x)) \lor \sigma(u,v))
% \end{eqnarray*}
\[
\lnot (\ex x \ph(x,y) \land (\fa y \psi(y) \limplies \ph(x,x))
\limplies \ex x \fa y \sigma(x,y))
\]
\begin{eqnarray*}
& \equiv & \ex z \ph(z,y) \land (\fa w \psi(w) \limplies \ph(x,x))
\land \lnot \ex u \fa v  \sigma(u,v) \\
& \equiv & \ex z \ph(z,y) \land (\ex w \lnot \psi(w) \lor \ph(x,x))
\land \fa u \ex v \lnot \sigma(u,v) \\
& \equiv & \ex z \ph(z,y) \land \ex w (\lnot \psi(w) \lor \ph(x,x))
\land \fa u \ex v \lnot \sigma(u,v) \\
& \equiv & \ex {z,w} \fa u \ex v (\ph(z,y) \land (\lnot \psi(w) \lor
\ph(x,x)) \land \lnot \sigma(u,v)).
\end{eqnarray*}

\item[7.\hfill] Let $\mdl M$ be any structure. I need to show that 
\[
\mdl M \models \ex x (\ph(x) \limplies \fa y \ph(y)).
\]
Applying Lemma 2.4.5, this amounts to showing that there is an element
$a$ in the universe of $\mdl M$ such that either $\mdl M \models \lnot
\ph(\bar a)$ or $\mdl M \models \fa y \ph(y)$.

If $\mdl M \models \fa y \ph(y)$, then we are done; any element $a$ of
the universe of $\mdl M$ will do. (Remember, we are assuming that our
structures have nonempty universes.) Otherwise, $\mdl M \not\models
\fa y \ph(y)$, which is to say, it is not the case that for every $b$
in $| \mdl M |$, $\mdl M \models \ph(\bar b)$. In other words, for
some $b$ in $|\mdl M|$, $M \models \lnot \ph(\bar b)$. In that case,
we can take $a = b$, and again we're done.

Alternatively, you can use the transformations in Section 2.5 to show
that the following are all equivalent:
\begin{eqnarray*}
& & \ex x (\ph(x) \limplies \fa y \ph(y)) \\
& & \ex x (\lnot \ph(x) \lor \fa y \ph(y)) \\
& & \ex x \lnot \ph(x) \lor \fa y \ph(y) \\
& & \lnot \fa x \ph(x) \lor \fa y \ph(y) \\
& & \lnot \fa x \ph(x) \lor \fa x \ph(x)
\end{eqnarray*}
Clearly the last formula is valid.

% \item[9.\hfill]
% \begin{list2}
% \item $\fa z (z \in x \limplies z \in y)$
% \item $\fa {x,y} ( x= y \liff \fa z (z \in x \liff z \in y))$
% \item $\fa z \ex w \fa u (u \in w \liff u \subseteq z)$
% \end{list2}

% \item[10.\hfill]
% \begin{list2}
% \item $\fa {x,y,z} (x < y \land y < z \limplies x < z)$
% \item $\fa {x,y} (x < y \limplies \ex z (x < z \land z < y))$
% \item $\ex x \fa y (x < y \lor x = y)$
% \item $\lnot \ex x \fa y (y < x \lor y = x)$
% \end{list2}
% Variations of these are also o.k.

\item[11.\hfill]
\begin{list2}
\item $\fa x (\fn{Cow}(x) \limplies \fn{EatsGrass}(x))$
\item $\ex x (\fn{Car}(x) \land \fn{Blue}(x) \land \fn{Old}(x))$
\item $\lnot \ex x (\fn{Car}(x) \land \lnot \fn{Pink}(x))$
\item $\fa x (\fn{Car}(x) \land \fn{Old}(x) \limplies
  \fn{MustBeInspectedAnnually}(x))$
\end{list2}

% \item[12.\hfill] 
% \begin{list2}
% \item The simplest example has just two elements, $a$ and $b$, neither
% of which is less than or equal to the other. In this case, both
% elements are minimal, but neither one is minimum.
% \vspace*{0.4in}
% \item Recall that a linear ordering satisfies $\fa x \fa y (x \leq y
% \lor y \leq x)$ in addition to the axioms for a partial ordering.

% Now suppose that $a$ is an element in a linear ordering that is
% minimum. Then if $b$ is any other element, we have $a \leq b$. By the
% axioms for partial orderings, if also $b \leq a$ then $b=a$. So there
% is no element $b$ satisfying $b < a$. This shows that $a$ is minimal.
% (This argument in fact holds for any partial ordering, not just linear
% orderings.)

% Suppose, on the other hand, that $a$ is minimal. If $b$ is any other
% element, we know that $a \leq b$ or $b \leq a$. Since $a$ is minimal,
% we know that $\lnot (b < a)$, so either $a \leq b$ or $a = b$; in
% other words, $a \leq b$. This shows that $a$ is minimum.

% \item Just take the integers, $\la \mathbb{Z}, \leq \ra$.

% \end{list2}

% \item[13.\hfill] $\gmdl A_2$ has an element that is bigger than every
%   other element, while $\gmdl A_4$ doesn't; so we can take $\sigma$ to
%   be
% \[
% \ex x \fa y ( y \leq x).
% \]
% Alternatively, only $\gmdl A_4$ has an element that is not comparable with
% anything but itself, so we can take $\sigma$ to be
% \[
% \lnot \ex x \fa y (x \leq y \lor y \leq x \limplies x = y).
% \]
% Other answers are possible.

\item[14.\hfill] To separate $\gmdl A_1$ and $\gmdl A_2$, let $\sigma$
  say that there is a smallest element:
\[
\ex x \fa y (x \leq y).
\]
To separate $\gmdl A_2$ and $\gmdl B$, let $\sigma$ say that between
any two elements, there is another element:
\[
\fa {x,y} (x < y \limplies \ex z (x < z \land z < y))
\]
where $x < y$ abbreviates $x \leq y \land \lnot (x = y)$.

\item[15.\hfill] $\sigma$ ``says'' that there is something that is
  comparable with every element. Let $\gmdl A$ and $\gmdl B$ be the
  posets below:

\vspace{1in}

In other words, $\gmdl B$ is the poset with two incomparable elements,
and $\gmdl A$ is the poset with two elements, one of which is less
than the other. Then $\gmdl A \models \sigma$ and $\gmdl B \models
\lnot \sigma$. (For $\gmdl A$, the 1-element poset would also work.)

% \item[16.\hfill] Here $\sigma$ ``says'' every two elements can be
%   bouded from above or bounded from below. The examples above work; in
%   other words, here, too, $\gmdl A \models \sigma$ and $\gmdl B \models
% \lnot \sigma$.

% \item[18.\hfill] First, define 
% \[
% Prime(x) \equiv x \neq 0 \land x \neq S(0) \land \fa {y,z} (x =
%   y \times z \limplies y = x \lor z = x)
% \]
% and
% \[
% x | y \equiv \ex z (x \times z = y).
% \]
% Also, define $1$ to be $S(0)$, $2$ to be $S(S(0))$, $x \leq y$ to be
% $x < y \lor x = y$, and $x > y$ to be
% $y < x$.
% \begin{list2}
% \item $x$ and $y$ are relatively prime:
% \[
% \fa z (z | x \land z | y \limplies z = 1).
% \]
% \item $x$ is the smallest prime greater than $y$:
% \[
% x > y \land Prime(x) \land \fa z (z > y \land Prime(z) \limplies x
% \leq y).
% \]
% \item $x$ is the greatest number with $2x < y$:
% \[
% 2 \times x < y \land \fa z(2 \times z < y \limplies z \leq x).
% \]
% \end{list2}

\item[19.\hfill] 
\begin{list2}
\item $Prime(x) \equiv x \neq 0 \land x \neq S(0) \land \fa {y,z} (x =
  y \times z \limplies y = x \lor z = x)$
\item $OddSquare(x) \equiv \ex y (x = y \times y) \land \ex z (x = (z
  + z) + 1)$
\item $ThreePrimeFactors(x) \equiv \ex {u,v,y,z} (x = u \times v
  \times y \times z \land Prime(u) \land Prime(v) \land Prime(y) \land
  u \neq v \land u \neq y \land v \neq y)$
\end{list2}
Once again, there are many reasonable variations of these.

% \item[21.\hfill] In the first structure, every element other than the
% least element has a unique predecessor. In the second structure,
% there are infinitely many elements that precede 1. So use the
% following sentence:
% \[
% \fa x (\ex y (y < x) \limplies \ex y (y < x \land \fa z (z < x
% \limplies z < y \lor z = y))).
% \]
% In words, if there is anything less than $x$, then there is a
% greatest element less than $x$. Equivalently, only the second
% structure satisfies
% \[
% \ex x \fa y (y < x \limplies \ex z (y < z \land z < x)),
% \]
% ``there is an $x$ such that for every $y$ less than $x$, there is
% something between $x$ and $y$.''

\end{list1}

\end{document}