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

\def\rr{{\mathbb R}}
\def\aa{{\mathbb A}}
\def\cc{{\mathbb C}}
\def\qq{{\mathbb Q}}
\def\zz{{\mathbb Z}}
\def\res{{\upharpoonright}}
\def\qed{{$\Box$}}

\def\moda{{\mathcal A}}
\def\modb{{\mathcal B}}
\def\modc{{\mathcal C}}
\def\modd{{\mathcal D}}



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


\def\lec#1{{\par\bigskip\noindent (#1)\par}}


\begin{document}
\begin{flushright}
  A. Miller \\
  M571\\
  Homework
\end{flushright}


\lec{1-23}

(A) Use Venn Diagrams to prove that
$$A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$$

(B) Let $A=\{1,2,\ldots,n\}$. How many binary relations $R$ on $A$,
(ie. $R\subseteq A^2$), are there such that

(1) (no conditions)

(2) $R$ is reflexive

(3) $(A,R)$ is a linear order

(4) $(A,R)$ is a graph, ie. $R$ is irreflexive and symmetric

(5) $(A,R)$ is an equivalence relation with exactly two equivalence classes.

\lec{1-25}

(A) Suppose $f:A\to B$ and $g:B\to C$ are functions.  Prove
\begin{enumerate}
\item if $f$ and $g$ are 1-1, then $g\circ f$ is 1-1.
\item if $f$ and $g$ are onto, then $g\circ f$ is onto.
\item Show by examples that neither of the above implications reverse.
\end{enumerate}

(B) Suppose $A$ is a nonempty set.  Prove the following are equivalent:
\begin{enumerate}
  \item there is a 1-1 $g:A\to\omega$
  \item there is an onto $f:\omega\to A$.
\end{enumerate}

\lec{1-28}

(A) Prove that for every set $X$ there is no map $f:X\to P(X)$ which
is onto.

(B) Let $\qq[x]$ be the polynomials with rational coefficients, i.e.,
$$\qq[x]=\{p\;\;: \mbox{ for some }n\in\omega,\; a_i\in\qq\;
\; p=a_0+a_1x+a_2x^2+\cdots+a_nx^n\}$$
Prove that $\qq[x]$ is countable.

(C) Let $\aa\subseteq\cc$ be the set of algebraic numbers. A complex number
is algebraic iff it is the root of a nontrivial polynomial $p\in \qq[x]$.
Prove that $\aa$ is countable.


\lec{1-30}
p.19 : 2,3,5

\lec{2-1}
p.27-29 : 5,9,10,14

\lec{2-4}


(A) Prove or disprove: For every WFF $\theta$ there exists
a WFF $\theta^*$ which is logically equivalent to
$\theta$ and does not contain the negation symbol, i.e.,
WFF which are strings of the symbols:
$$\{\disj,\conj,\implies,\iff,),(,A_1,A_2,A_3,\ldots\}$$


(B) For each of the 16 binary logical connectives $\circ$, let
WFF$_\circ$ be the set of well-formed formulas in the language
$L=\{\circ,(,),A_1,A_2,\ldots\}$.  The connective $\circ$ is
called adequate for propositional logic iff every WFF is logically
equivalent to one in WFF$_\circ$.  Determine (with proof) all
adequate binary logical connectives.

\lec{2-6}

p.53-9 : It is not clear what $(A\iff B\iff C)$ means.   Probably
Enderton means $((A\iff B)\iff C)$ or $(A\iff (B\iff C))$ which
are logically equivalent.  Every other mathematician
would mean $((A\iff B)\conj (B\iff C))$.

p.54-12

\lec{2-8}

proplog handout: 21,22,23

\lec{2-11}

(A).  Suppose $\Sigma\subseteq WFF$ is complete and finitely satisfiable.
Suppose $F\subseteq\Sigma$ is finite and $\theta$ is a WFF such that
$F\models\theta$.

Prove that $\theta\in\Sigma$.

\lec{2-13}

(A).  Suppose $\Lambda\subseteq WFF$ is complete and finitely satisfiable
and $\theta$ and $\psi$ are logically equivalent WFFs.
Prove that $\theta\in\Lambda$ iff $\psi\in\Lambda$.

\lec{2-15}
proplog handout: 24,25,26,27

\lec{2-18}
proplog handout: 30,32,34

\lec{2-20}
p.65-1,2,3

\lec{2-22}
$U$ and $V$ are unary predicates,
$x$ and $y$ distinct variables,
 and $\equiv$ means logically equivalent.

Prove or disprove

(A) $(\exists x U(x)) \conj (\exists x V(x)) \equiv
\exists x (U(x) \conj  V(x))$

(B) $(\forall x U(x)) \disj (\forall x V(x)) \equiv
\forall x \forall y (U(x) \disj V(y))$

\lec{2-25}
p. 79 - 1,2,5

\lec{2-27}
p. 100-104 : 9,16,18,27

\lec{3-13}
p. 146 - 6,8,9

\lec{3-20}
p. 145 - 3,7

\lec{4-3}
p.100- 11,12,15

\lec{4-8}
p.180- 1,4,5

\bigskip
Hint (1)
$$(\rr,\qq,<,..)\models \forall x\forall y \; (x<y\implies \exists q\;
\qq(q)\conj x<q<y)$$

Hint (4) If $A$ is finite,then say $A=\{a_1,a_2,\ldots,a_n\}$.
$$(\rr,A,..)\models \forall x\; (A(x)\iff (x=a_1\disj x=a_2\disj\cdots
\disj x=a_n)$$
If $A$ is infinite, then $A$ is either unbounded or contains a limit point.
Or you can use that $A$ contains an infinite sequence.

\bigskip

\lec{4-12}
(A) In the language with one binary relation symbol and one unary relation
(say ${\mathcal L}=\{\leq,U\}$) prove that the following two structures are
elementarily equivalent
 $$(\rr,\leq,\qq)\equiv(\qq,\leq,D_2)$$
where $D_2$ is the set of diyadic rational numbers:
 $$D_2=\{{m\over 2^n}\;:\; m\in\zz,\; n=1,2,3,\ldots\}$$
Prove that
 $$(\rr,\leq,\qq)\not\equiv(\rr,\leq,\zz)$$

\bigskip
(B) In the language of one binary relation let

$\moda=(\rr^*,\approx)$ where $x\approx y$ iff $x$ and $y$ are
infinitesimally close.

$\modb=(\rr,\approx_{\qq})$ where $x\approx_{\qq} y$ iff
$\exists q\in\qq\;\;\; x=y+q$

$\modc=(\qq,\approx_{\zz})$ where $q\approx_{\zz}r$ iff $q-r\in\zz$

\noindent Prove that $\moda\equiv\modb\equiv\modc$

\bigskip

(C) In the same language let $\modd_k=(\zz,\equiv_k)$
for $k=2,3,\ldots$ where $m\equiv_kn$ iff $m-n$ is divisible
by $k$ (i.e. $m=n$ mod $k$).

\noindent Prove that for every $k$, $\modd_k\not\equiv\modc$.

\noindent Prove that for every sentence $\theta$ if
$\modc\models\theta$ then there exists $N$ such that for all $k\geq N$
$\modd_k\models\theta$.

\bigskip
Hint (A). Suppose the language of these structures is $\{\leq, U\}$ where
$U$ is a unary predicate symbol.
Let DLO$^*$ be the theory of dense linear orders without end points plus
$$\forall x\forall y (x<y)\implies \exists u\exists v (U(u)\conj \neg U(v)\conj
x<u<y\conj x<v<y)$$
Use the {\L}os-Vaught Test to prove that DLO$^*$ is a complete theory.

(B). Write down axioms $\Sigma$ which say that the binary relation is
an equivalence relation, with infinitely many equivalence classes, and
all equivalence classes are infinite.  Prove the $\Sigma$ is complete
by using the {\L}os-Vaught Test.


\bigskip

\lec{4-22}
Prove that the definable subsets of $(\omega,S,0)$ are the
finite and cofinite subsets of $\omega$.
\par Hint: $(\omega,S,0)\equiv (\omega,S,0)+(\zz,S)$ or you can use
elimination of quantifiers as in book.


\lec{4-24}
Prove that Th$(\omega,+,|)$ is undecidable where $|$ is the
binary predicate
 \par $n|m$ iff $n$ divides $m$.
 \par\noindent Hints: Show multiplication is definable in this
structure. $n^2+1$ is the least common multiple of $n$ and $n+1$,
$(a+b)^2=a^2+2ab+b^2$

\lec{5-1}

(A) An integer $x$ is square-free iff $x\geq 2$ and no integer
$y\geq 2$ exists such that $y^2$ divides $x$.  Let $S(n)$
be the sum of the first $n$ square-free integers.  Prove
that $S:\omega\to\omega$ is primitive recursive.

(B) Prove there exists an integer $n$ such that
5 divides n,
7 divides n+1,
9 divides n+2,
11 divides n+3, and
13 divides n+4.


\end{document}