% 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}