%% Process me in latex2e.

% BEGIN PREAMBLE

\documentclass[12pt]{article}
\pagestyle{empty}   % no page numbers
\nofiles % no aux file


% fonts:
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{latexsym}  % latex2e symbol package


% if needed, to get the format right:
 \addtolength{\textwidth}{4mm}
 \addtolength{\oddsidemargin}{-2mm}
 \addtolength{\textheight}{20mm}
 \addtolength{\topmargin}{-10mm}


\newcommand\LL{\mathcal{L}}

\newcommand\RRR{{\mathbb R}} 

\newcommand\HF{\mathit{HF}}

% END PREAMBLE

\begin{document}



\begin{center}
MATH 770 HOMEWORK 5 \\
{\it Semester I, 2006-2007} \\
{\it Due November 16}
\end{center} 


\bigskip

\textbf{21.}
Prove the compactness theorem for propositional logic
directly from Tukey's Lemma.
Here, ``consistent'' (= ``satisfiable'') is defined just by truth tables.
\textit{Hint.} Call $\Sigma$
{\it finitely consistent\/} iff every
finite subset of $\Sigma$ is consistent.
If $\Sigma$ is finitely consistent and maximal, show that exactly
one of $\{\varphi, \neg\varphi\}$ is in $\Sigma$
for each $\varphi$.  Then, we can declare a proposition letter $p$
to be true iff $p \in \Sigma$.

\bigskip

\textbf{22.}
Use the compactness theorem for {\it propositional\/} logic to
prove that a graph is 4-colorable iff every finite subgraph is.
Here, a (undirected) graph is pair, $G = (V,E)$, such that $E$ is a symmetric
relation on $V$.  $G$ is {\it 4-colorable\/} iff
there is a map
$c: V \to 4$ such that $x E y \to c(x) \ne c(y)$.
``Finite subgraph'' means
$(F,E \cap F \times F)$, where $F$ is a finite subset of $V$.
{\it Hint.} Use propositional letters $p^i_x$
($i \in 4 ; x \in V$) which ``say'' ``$x$ gets colored $i$''.
\textit{Remark.} There are other proofs of this (e.g., using ultrafilters or
the Tychonov Theorem), but note that the
obvious direct ``Zorn's lemma'' argument fails, since a maximal
partial coloring need not be a total coloring.

\bigskip


\textbf{23.}
Assume that the ordered field $(F; +, \cdot, <)$ is a proper extension
of  $(\RRR; +, \cdot, <)$.  Call $\varepsilon \in F$
\textit{infinitesimal} iff $\varepsilon  \ne 0$ but
$|\varepsilon| < |r|$ for all non-zero $r \in \RRR$.
Say $x \sim y$ iff $x-y$ is infinitesimal or $0$.  Then prove that
${(x + \varepsilon)^3 - x^3 \over \varepsilon}\sim 3x^2$
for each $x \in \RRR$ and each infinitesimal $\varepsilon$.
\textit{Remark.} This is a warmup for non-standard analysis.
Here, $F$ can be constructed by algebra,
and the properties of $F$ that you need are obtained from
the properties of ordered fields.  The model theory comes in when
you try to take the derivative of a function like \textit{sin};
you would need to construct an elementary extension
of  $(\RRR; +, \cdot, <, \mathit{sin},\mathit{cos)}$.




\bigskip

\textbf{24.}
A formula $\varphi$ in $\LL = \{\in\}$ is $\Delta_0$ iff
all quantifiers (if any) in $\varphi$ are bounded -- that is, occur
in combinations like $\exists x \in y$ or
$\forall x \in y$.  Then, a subset of $\HF^n$
is called $\Delta_0$ iff it is defined by some $\Delta_0$
formula.
For example, ``$\{x\} \in y$'' is expressed as
$\exists u \in y \, [x \in u \wedge \forall v \in u \, [v = x]]$.
Write $\Delta_0$ formulas to express $x = \bigcup y$ and
$x = \langle y, z \rangle$.
\textit{Remark.} Each
$\Delta_0$ property is decidable in polynomial time
if your input sets are written with $\},\{, \emptyset$.
It is $\Delta_1$, not $\Delta_0$, which yields the standard
recursion theory notion of ``decidable''.
``$x \in \omega$'' is also $\Delta_0$
(see any set theory text), but ``$x,y \in \omega \,\wedge\, y = x + x$'' isn't
(by elementary model theory; see the next HW set).




\end{document}