% LaTex2e
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}

\def\moda{{\frak A}}
\def\rr{{\mathbb R}}
\def\aa{{\mathbb A}}
\def\cc{{\mathbb C}}
\def\qq{{\mathbb Q}}
\def\nn{{\mathbb N}}
\def\zz{{\mathbb Z}}
\def\famf{{\mathcal F}}

%\def\res{{\upharpoonright}}
%\def\qed{{$\Box$}}

\def\disj{\vee}
\def\conj{\wedge}
\def\implies{\to}
\def\iff{\leftrightarrow}

\newcount\probno
\probno=0
\def\prob{\advance\probno by 1  \par\bigskip
    \noindent\the\probno . }


\begin{document}

\begin{flushright}
  A.Miller\\
M571\\
Spring 2002\\
Midterm Exam\\

\end{flushright}

Do not hand in this exam, so do not write your answers on it.

You can take as long as you want on this exam.

You will need your own paper.

\bigskip

\prob Let $H$ be the set of all integers which are either
divisible by $3$ or negative.  Prove that $H$ is countable by
constructing a map from $\nn=\{1,2,3,\ldots\}$ onto $H$.

(Be sure and prove that the map you construct is onto.)

\prob Which of the following sets are countable?


(a) $\rr$

(b) $\qq$

(c) $\{0,3,5\}$

(d) $\{\rr,\cc,\sqrt{2}\}$

(e) the empty set

(f) $\{x\in\rr: x^2=-1\}$

(g) the set of points in the plane $\rr^2$.

(h) the set of all subsets of $\nn$.

(i) the set of all finite subsets of $\nn$.

(j) $\{(x,y)\in\rr^2\;:\; x^2+y^2=1\}$

\bigskip\noindent(For this problem just answer
countable or uncountable (ctble, unctble), you need not justify your answer.)


\prob Give the truth table for the propositional sentence
$$((A\implies B)\disj C)$$

\prob Let $\Sigma=\{A, (A\implies B)\}$.  For each of
these prove or disprove:

(a) $\Sigma\models B$

(b) $\Sigma\models ((\neg A)\disj (\neg B))$


\prob Find a sentence in disjunctive normal form which is
logically equivalent to $$\neg (A \iff B)$$

\newpage

\prob Prove or disprove:
\par Every well-formed formula of propositional logic is logically equivalent
to one in which the only symbols are $\implies$, $\neg$, parentheses, and
propositional letters.

\prob Suppose that $\Sigma$ is a set of formulas of propositional logic
which is finitely satisfiable.  Show that for any formula $\theta$
of propositional logic
that either $\Sigma\cup\{\theta\}$ is finitely satisfiable or
$\Sigma\cup\{\neg\theta\}$ is finitely satisfiable.

(Do not use the compactness theorem or any lemma used to prove
compactness in your proof.)


\prob A square in a graph $(V,E)$ is a set $\square=\{a,b,c,d\} \subseteq V$
of four distinct vertices
such that $aEb$, $bEc$, $cEd$, $dEa$,
$\neg aEc$, and $\neg bEd$. Let $n$ be a fixed positive integer.

Suppose that every finite subgraph of $V$ is the union of $n$ sets none of
which contain a square. Show that $V$ is the union $n$ sets none of which
contain a square.

(You may use the compactness theorem without proof.)

\prob
$R$ is a binary predicate symbol.
Prove or disprove:

$(\forall y\exists x\; R(x,y)) \implies
(\exists x \forall y\; R(x,y))$ is a logical validity.

\prob Let ${\mathcal L}_R$ be the language containing the binary
relation symbol $R$.  Write down a first order ${\mathcal L}_R$-sentence
$\theta$ such that for any ${\mathcal L}_R$-structure ${\moda}$

${\moda}\models \theta$ iff ${\moda}$ is a linear
order with no greatest element.

\newpage

\begin{center}
  Answers
\end{center}

\bigskip
1. Define $g(n)=3n$ then $g$ maps $\nn$ onto the positive
multiples of $3$. Define $h(n)=-n+1$ then $h$ maps $\nn$
onto the integers $\{0,-1,-2,\ldots\}$.  Combine them
into one map $f:\nn\to H$ by the rule
$f(2n)=g(n)$ and $f(2n-1)=h(n)$.

\bigskip
2. ucccccuucu

\bigskip
3. There is only one false line in the truth table.  It
is ABC - TFF.

\bigskip
4. a is true and b is false.

\bigskip
5. $(\neg A \conj B)\disj( A \conj \neg B)$

\bigskip
6. This is true. Note that $(\theta\disj \psi)$ is logically equivalent to
$(\neg\theta)\implies \psi$.  Use induction to prove that
every WFF equivalent to one using only $\implies,\;\neg$.

\bigskip
7. (Do not use that $\Sigma$ is satisfiable in your proof.  We only know
this by the compactness theorem.)

Suppose for contradiction that
neither
$\Sigma\cup\{\theta\}$ is finitely satisfiable nor
$\Sigma\cup\{\neg\theta\}$ is finitely satisfiable.
Then there must exists finite sets $\Sigma_0,\Sigma_1\subseteq \Sigma$
such that
$\Sigma_0\cup\{\theta\}$ is not satisfiable and
$\Sigma_1\cup\{\neg\theta\}$ is not satisfiable.

But $\Sigma_0\cup\Sigma_1\subseteq \Sigma$ is finite. So by assumption
it is satisfiable.  Let $\nu$ be a truth evaluation which makes
every $\psi$ in $\Sigma_0\cup\Sigma_1$ true.

If $\nu(\theta)=T$, then $\Sigma_0\cup\{\theta\}$ is satisfiable
by $\nu$,
which is a contradiction.

If $\nu(\theta)=F$, then $\nu(\neg\theta)=T$ and therefore
$\Sigma_1\cup\{\neg\theta\}$ is satisfiable by $\nu$,
which is a contradiction.

Since either way leads to a contradiction the result is proved.

\bigskip
8. Let the set of propositional letters be the set of all $P_v^k$
for $v\in V$ and
$k=1,2,\ldots,n$.

Define

$\Sigma_1=\{(P_v^1\disj P_v^2 \disj \cdots \disj P_v^n)
\;\;:\;\; v\in V\}$

$\Sigma_2=\{\neg(P_a^k\conj P_b^k \conj P_c^k\conj  P_d^k)
\;:\;\{a,b,c,d\} \mbox{ is a square in } V, 1\leq k\leq n \}$

$\Sigma=\Sigma_1\cup\Sigma_2$.


\newpage
Claim. $\Sigma$ is finitely satisfiable.

proof: Given a finite $\Sigma_0\subseteq\Sigma$. Let $V'\subseteq V$
be the set of all vertices mentioned in $\Sigma_0$.
Since it is finite by assumption $V'$ is the union of
$n$ square free sets, so let
$V'=A_1\cup A_2\cup\ldots\cup A_n$ where each $A_i$ contains
no square.  Define a truth evaluation by

$\nu(P_v^k)=T$ iff $v\in A_k$.

\noindent But then it is easy to check that $\nu(\psi)=T$
for each $\psi\in \Sigma_0$.

\bigskip
By the compactness theorem $\Sigma$ is satisfiable.  So let
$\nu$ be a truth evaluation such that $\nu(\Sigma)=T$.  For
each $k$ define the set $A_k$ by

$$A_k=\{v\;:\; \nu(P^k_v)=T\}$$

By the axioms in $\Sigma_1$ we see that for every $v\in V$
there exists a $k$ such that $v\in A_k$.
By the axioms in $\Sigma_2$ we
see that no $A_k$ contains a square.  Hence $V$ is the union
of $n$ sets, none of which contain a square.

\bigskip
9. This is not a logical validity.  To show this exhibit a single
specific structure in which it is false - don't natter on and on about
this or that.

\bigskip
Counterexample: Let $A=\{0,1\}$  and $R_A=\{(0,0),(1,1)\}$.
Then
$$\moda\models (\forall y\exists x\; R(x,y))$$
since given $y$ taking $x=y$ always works.
But
$$\moda\models\neg(\exists x \forall y\; R(x,y))$$
since neither $x=0$ nor $x=1$ works for all $y$.

\bigskip
10. Remember a sentence of first-order logic has no free variables.

\bigskip

$\forall x\;\; R(x,x)$

$\forall x\forall y\;\; (R(x,y)\conj R(y,x))\implies x=y$

$\forall x\forall y\forall z \;\;(R(x,y)\conj R(y,z))\implies R(x,z)$

$\forall x\forall y\;\; R(x,y)\disj R(y,x)$

\bigskip
These are the axioms of a linear order.  To say that there is no
greatest element: $\neg \exists x \forall y\;\; R(y,x)$
or $\forall x\exists y \;\; (R(x,y)\conj x\not=y)$




\end{document}



