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

\newcount\probno
\def\prob{\par\medskip\noindent
 {\kern -.5in \parbox{.45in}{\the\probno.}}\advance\probno by 1}
\advance\probno by 1

\def\rr{{\mathbb R}}
\def\cc{{\mathfrak c}}
\def\res{{\upharpoonright}}
\def\qed{{$\Box$}}
\def\com#1{}
\def\nor{\circ}
\def\famc{{\mathcal C}}
\def\fama{{\mathcal A}}
\def\famf{{\mathcal F}}

\def\ss{{\mathcal S}}
\def\pp{{\mathcal P}}
\def\dex{}
\def\sdex#1{}
\def\disj{\vee}
\def\conj{\wedge}
\def\implies{\to}
\def\iff{\leftrightarrow}

\begin{document}

\begin{flushright}
  A.Miller\\
  M571\\
  Spring 2002
\end{flushright}

\begin{center}
Propositional Logic and the Compactness Theorem
\end{center}


The \dex{syntax} (grammar) of propositional logic is the following.
The \dex{logical symbols} are $ \conj ,\disj , \neg , \implies ,$ and $ \iff$.
The \dex{nonlogical symbols} consist of an arbitrary nonempty set
$\pp$ that we assume
is disjoint from the set of logical symbols to avoid confusion.  The
set ${\pp}$ is referred to as the set of \dex{atomic sentences} or
as the set of \dex{propositional letters}.
For example, $\{P,Q,R\}$, $\{P_0,P_1,P_2,\ldots\}$, or $\{S_r:r\in\rr\}$.
The set of
\dex{propositional sentences} ${\ss}$ is the smallest set of finite strings
of symbols such that
$\pp\subseteq \ss$, and if $\theta \in \ss$ and $\psi \in \ss$, then
$ (\neg \theta) \in \ss, (\theta \conj \psi) \in \ss,(\theta \disj \psi) \in \ss,
(\theta \implies \psi) \in \ss,$ and $(\theta \iff \psi) \in \ss$.

The \dex{semantics} (meaning) of propositional logic consists of truth
 evaluations.
A \dex{truth evaluation} is a function $e:{\ss}\to\{ T,F \}$,
that is consistent
with the following truth tables:
$$
\begin{array}{ccccccc}
\theta & \psi &\neg\theta &(\theta\conj\psi) &(\theta\disj\psi)
&(\theta\implies\psi) &(\theta\iff\psi) \\
T&T&F&T&T&T&T\\
T&F&F&F&T&F&F\\
F&T&T&F&T&T&F\\
F&F&T&F&F&T&T
\end{array}
$$
For example if $e(\theta)=T$ and $e(\psi)=F$, then
$e(\theta \implies \psi)=F$. Also $e(\neg\theta)=T$ iff $e(\theta)=F$.
For example, if $\pp=\{P_x:x\in\rr\}$ and we define
$e(P_x)=T$ if $x$ is a rational and  $e(P_x)=T$ if $x$ is a irrational,
then $e((P_2\conj \neg P_{\sqrt{2}}))=T$.  However if we
define $e^\prime(P_x)=T$ iff $x$ is an algebraic number, then
$e^{\prime}((P_2\conj \neg P_{\sqrt{2}}))=F$.

A sentence
$\theta$ is called a \dex{validity} iff for every truth evaluation $e$,
$e(\theta)=T$.

We say that two sentences $\theta$ and $\psi$ are \dex{logically equivalent}
iff for every truth evaluation $e$, $e(\theta)=e(\psi)$.
A set of logical symbols is \dex{adequate} for propositional logic iff
every propositional sentence is logically equivalent to one whose only logical
symbols are from the given set.

\bigskip

\prob Define ${\ss}_0={\pp}$ the atomic sentences and define
$${\ss}_{n+1}={\ss}_n\cup\{\neg\theta:\theta\in {\ss}_n\}\cup
\{(\theta\#\psi):\theta,\psi\in {\ss}_n,\#\in
\{\conj,\disj,\implies,\iff\}\}$$
Prove that ${\ss}={\ss}_0\cup {\ss}_1\cup {\ss}_2\cup\cdots$.

\prob Prove that for any function $f:{\pp}\to \{T,F\}$ there exists a
unique truth evaluation $e:\ss\to \{T,F\}$ such that  $f=e\res {\pp}$.
The symbol $e\res {\pp}$
stands for the restriction of the function $e$ to $\pp$.
\sdex{$e?res {?pp}$}

\prob Let $\theta$ and $\psi$ be two propositional sentences.  Show
that $\theta$ and $\psi$ are logically equivalent iff $(\theta\iff\psi)$
is a validity.

\prob Suppose $\theta$ is a propositional validity, $P$ and $Q$ are
two of the propositional letters occurring in $\theta$, and $\psi$
is the sentence obtained by replacing each occurrence of $P$ in
$\theta$ by $Q$.   Prove that $\psi$ is a validity.

\prob Can you define $ \disj$  using only $\implies$?  Can you define $\conj$
 using only $\implies$?

\com{ $(p\implies q)\implies p$ is equivalent to $p\disj q$. $conj$ cannot
be defined (if there are at least two atomic sentences- it is definable if
there is only one), one proof is that every sentence using only implies is
made true by at least 50\% of the truth evaluations.}

\prob Show that  $\{ \disj, \neg \}$ is an adequate set for propositional
logic.

\prob The definition of the logical connective \dex{nor} ( $\nor$ )
is given by
the following truth table:
$$
\begin{array}{ccc}
 \theta & \psi & (\theta \nor \psi) \\
           T&T&F  \\
           T&F&F  \\
           F&T&F  \\
           F&F&T
\end{array}
$$
Show that $\{ \nor \}$ is an adequate set for propositional logic.

\prob (Sheffer) Find another binary connective that is adequate all
by itself.

\prob Show that   $\{\neg\}$   is not adequate.

\prob Show that $\{ \disj \}$ is not adequate.

\prob How many binary logical connectives are there?  We assume two
connectives are the same if they have the same truth table.

\prob Show that there are exactly two binary logical connectives that are
 adequate
all by themselves. Two logical connectives are the same iff they have the same
truth table.

\prob Suppose $\pp=\{P_1,P_2,\ldots,P_n\}$. How many propositional
sentences (up to logical equivalence) are there in this language?

\prob Show that every propositional sentence is equivalent to a sentence in
\dex{disjunctive normal form}, i.e. a disjunction of conjunctions
of atomic or the negation of atomic sentences:
$$\disj_{i=1}^m \bigl(\conj_{j=1}^{k_i}\theta_{ij}\bigr)$$
where each $\theta{ij}$ is atomic or $\neg$atomic.
The expression $\disj_{i=1}^n \psi_i$  abbreviates
$(\psi_1\disj(\psi_2\disj(\cdots\disj (\psi_{n-1}\disj\psi_{n})))\cdots)$.

\bigskip
In the following definitions and problems $\Sigma$ is a set of propositional
sentences in some fixed language and all sentences are assumed to be in this
same fixed language.
$\Sigma$ is \dex{realizable} iff there exists a truth evaluation $e$ such that
for all $\theta \in \Sigma$,  $e(\theta)=T.$
$\Sigma$ is \dex{finitely realizable}
iff every finite subset of $\Sigma$ is realizable.
$\Sigma$ is \dex{complete} iff for every sentence $\theta$ in the language of
$\Sigma$ either  $\theta$ is in $\Sigma$ or $\neg\theta$ is in $\Sigma$.

\medskip

\prob Show that if $\Sigma$ is finitely realizable and $\theta$ is
any sentence
 then either
$\Sigma \cup \{ \theta \}$ is finitely
realizable or $\Sigma \cup \{ \neg\theta \}$
 is finitely realizable.

\prob Show that if $\Sigma$ is finitely realizable and  $(\theta \disj \psi)$
 is in $\Sigma$, then either
$\Sigma \cup \{ \theta\}$ is finitely realizable or
$\Sigma \cup \{ \psi \}$ is finitely realizable.

\prob Show that if $\Sigma$ is finitely realizable
and complete and if $\theta$ and
$(\theta \implies \psi)$
are both in $\Sigma$, then $\psi$ is in $\Sigma$.

\prob Show that if $\Sigma$ is finitely realizable
and complete, then $\Sigma$ is
realizable.

\prob Suppose that the set of all sentences in our language is countable,
e.g.,
$S =\{ \theta_n : n = 0,1,2,\ldots \}$. Show that if $\Sigma$ is finitely
 realizable, then there
exists a complete finitely
realizable $\Sigma^\prime $ with $\Sigma\subseteq \Sigma^\prime$.

\prob ({\bf Compactness theorem for propositional logic})
Show that every finitely realizable $\Sigma$ is realizable.  You may assume
there are only countably many sentences in the language.

\bigskip
 A family of sets $\famc$ is a \dex{chain} iff for any $X,Y$ in $\famc$
 either
 $X \subseteq Y$ or $Y \subseteq X$.
The union of the family $\fama$ is
$$\bigcup \fama = \{ b : \exists c \in \fama ,b \in c \}.$$
$M$ is a \dex{maximal} member of a family $\fama$ iff $M \in \fama$ and
 for every $B$ if
$B \in \fama$ and $M \subseteq B$, then $M=B$.
A family of sets $\fama$ is closed under the unions of chains iff
for every subfamily, $\famc$,
of $\fama$ which is a chain the union of the chain, $\bigcup\famc$,
is also a member of $\fama$.

\par\medskip
 {\bf Maximality Principle:}  Every family of sets closed
 under the unions of
chains has a maximal member.
\par\medskip

\prob Show that the family of finitely realizable $\Sigma$ is closed under
unions of chains.

\prob Show how to prove the compactness theorem without the assumption
 that there are only countably many sentences. (You may use the Maximality
 Principle.)

\prob Suppose $\Sigma$ is a set of sentences and $\theta$ is some sentence
such that for every
truth evaluation $e$  if $e$ makes all sentences in $\Sigma$ true, then
$e$ makes
$\theta$ true.
Show that for some
 finite $\{ \psi_1, \psi_2, \psi_3,\ldots \psi_n \}\subseteq \Sigma$
the sentence
$$ ( \psi_1 \conj \psi_2 \conj \psi_3 \conj\cdots \conj \psi_n )
\implies \theta$$
is a validity.

\par\bigskip
\noindent A \dex{binary relation} $R$ on a set $A$ is a subset of $A \times A$.
Often
we write $xRy$ instead of $\langle x,y\rangle\in R$.
 A binary relation $\leq$ on a set $A$ is a \dex{partial order} iff
\par   a. (reflexive) $\forall a \in A \;  a\leq a$;
\par   b. (transitive) $ \forall a,b,c \in A \;[ ( a \leq b  \conj  b \leq c)
\implies  a \leq c]$; and
\par   c. (antisymmetric) $\forall a,b\in A\;[ (a \leq b  \conj  b \leq a)
\implies  a=b]$.


\noindent Given a partial order $\leq$ we define the \dex{strict order}
 $<$ by
$$x < y \iff (x \leq y \conj  x \not= y)$$

\noindent A binary relation $\leq$ on a set A is a \dex{linear order}
 iff $\leq$
is a partial order and
\par   d. (total) $\forall a,b \in A (a \leq b \disj b \leq a)$.

  A binary relation $R$ on a set $A$ extends a binary relation
$S$ on $A$ iff $S \subseteq R$.

\medskip

\prob Show that for every finite set $A$ and partial order $\leq$ on $A$
 there exists a
linear order $\leq ^*$ on $A$ extending $\leq$.


\prob Let $A$ be any set and let our set of atomic sentences $\pp$ be:
        $$\pp= \{ P_{ab} : a,b \in A \}$$
For any truth evaluation $e$ define  $\leq_e$ to be the binary relation
on $A$ defined by
       $$ a \leq_e b   \mbox{ iff }  e(P_{ab})=T. $$
Construct a set of sentences $\Sigma$ such that for every truth
evaluation $e$,

\centerline{$e$ makes $\Sigma$ true iff $\leq_e$ is a linear order on $A$.}

\prob  Without assuming the set $A$ is finite prove
 for every partial order $\leq$ on $A$
 there exists a linear order $\leq ^*$ on $A$ extending $\leq$.
\com{This one can be proved directly from the maximality principal, the
others I don't know about.}

\medskip
 In the next problems $n$ is an arbitrary positive integer.
\par\medskip


\prob If $X \subseteq  A$ and $R$ is a binary relation on $A$ then the
restriction of $R$ to $X$ is the binary relation
$S= R\cap (X \times X)$.
For a partial order $\leq$ on $A$, a set $B \subseteq A$ is an $\leq$-chain
iff the
restriction of $\leq$ to $B$ is a linear order.
 Show that given a  partial order $\leq$ on $A$:

the set $A$  is the union of less than $n$  $\leq$-chains
  iff
every finite subset of $A$ is the union of less than $n$  $\leq$-chains.


\prob A partial order $\leq$ on a set $A$ has \dex{dimension}
 less than $n+1$ iff
 there exists $n$ linear
orders $\{ \leq_1, \leq_2, \leq_3,\ldots,\leq_{n} \}$ on $A$ (not
necessarily distinct) such that:
       $$ \forall x,y \in A\;  [  x\leq y   \mbox{ iff }
          ( x\leq_i y \mbox{ for } i=1,2,\ldots,n) ].$$
Show that a partial order $\leq$ on a set $A$ has dimension less than $n+1$
iff for every
finite $X$ included in $A$ the restriction of $\leq$ to
 $X$ has dimension less than $n+1$.

\prob
A binary relation $E$ (called the edges) on a set $V$ (called the vertices)
is a \dex{graph} iff
\par    a. (irreflexive) $\forall x \in V    \neg xEx $; and
\par    b. (symmetric) $\forall x,y \in V \,  (xEy \implies yEx)$.
\par\noindent  We say $x$ and $y$ are adjacent iff $xEy$.
$(V^\prime ,E^\prime )$ is a subgraph of $(V,E)$ iff
$V^\prime\subseteq V$ and $E^\prime$ is the restriction of $E$ to $V^\prime$.
For a graph $(V,E)$ an $n$ coloring is a map
$c : V \to \{ 1,2,\ldots,n \}$ satisfying
$\forall x,y \in V  (xEy \implies c(x) \not= c(y))$,
 i.e. adjacent vertices have different colors.
A graph $(V,E)$ has \dex{chromatic number} $\leq n$ iff there is a $n$
coloring on its vertices.
 Show that a graph has chromatic number $\leq n$ iff
  every finite subgraph of it has
chromatic number $\leq n$.

\prob A triangle in a graph $(V,E)$ is a set $\Delta=\{a,b,c\} \subseteq V$
such that $aEb$, $bEc$, and $cEa$.  Suppose that every finite subset of
$V$ can be partitioned into $n$ or fewer sets none of which contain a
triangle.
Show that $V$ is the union of $n$ sets none of
which contain a triangle.

\prob (Henkin) A \dex{transversal} for a family of sets $\famf$ is a
one-to-one choice function.
That is a one-to-one function $f$ with domain $\famf$ and for every
$x\in \famf \,\, f(x)\in x.$ Suppose that $\famf$ is a family of
finite sets such that for
every finite $\famf^\prime  \subseteq \famf, \famf^\prime $ has a
transversal.
Show that $\famf$ has a
transversal.  Is this result true if $\famf$ contains infinite sets?

\prob Let $\famf$ be a family of subsets of a set $X$.  We say
that $\famc\subseteq \famf$
is an \dex{exact cover}
 of $Y \subseteq X$ iff every element of $Y$ is in a unique
element of $\famc$.  Suppose that every element of $X$ is in at most
finitely many
elements of $\famf$.  Show that there exists an exact cover
$\famc\subseteq \famf$ of $X$
iff for every finite $Y\subseteq X$ there exists
$\famc\subseteq \famf$ an exact
cover
of $Y$. Is it necessary that every element of $X$ is in at most finitely many
elements of $\famf$?

\com{Use $P_a$ to say ``$a\in \famc$'', so $\Sigma$ contains
$\disj_{x\in a} P_a$ for each $x\in X$ and $\neg(P_a\conj P_b)$ if
$a$ and $b$ are not disjoint. To verify finite sat- given Y finite get
$Z\supseteq Y$ finite which can witness the nondisjointedness of the
elements of $\famf$ which hit $Y$, then for exact cover $Z$ the
elements which
hit $Y$ are a disjoint exact cover of $Y$.}

\prob  If $\famf$ is a family of subsets of $X$ and $Y\subseteq X$
then we say $Y$
\dex{splits} $\famf$ iff for any $Z\in \famf,$
$ Z \cap Y $ and $Z \setminus Y$
 are both nonempty. Prove that if $\famf$ is a family of finite
subsets of $X$
then
$\famf$ is split by some $Y\subseteq X$ iff every finite
$\famf^\prime \subseteq \famf$
is split by some $Y\subseteq X$.  What if $\famf$ is allowed to
have infinite sets
in it?

\prob Given a set of students and set of classes, suppose each student
wants one of a finite set of classes, and each class has a finite
enrollment limit.  Show that if each finite set of students can
be accommodated, they all can be accommodated.

\prob Show that the compactness theorem of propositional logic is
equivalent to the statement that for any set $I$, the space $2^I$, with
the usual Tychonov product topology is compact, where $2=\{0,1\}$ has
the discrete topology. (You should skip this problem if you do not know what
a topology is.)



\end{document}