Problem Set 4

due Thursday, Feb 20, 2003

Reading

Please read Smullyan, Chapter XI, p. 101-108 for Tuesday, February 18

Problems

  1. Let $S$ be a set of formulas. Assume for every valuation $v$\(_{_i}\!\) there is an $X$\(_{_i}\!\) \(\,\scriptstyle\in\,\)$S$ with val($X$\(_{_i}\!\),$v$\(_{_i}\!\)) = f. Show that for some $n$ the conjunction $X$\(_{_1}\!\) \(\,\scriptstyle\wedge\,\)... \(\,\scriptstyle\wedge\,\)$X$\(_{_n}\!\) is unsatisfiable.

  2. Call a set $S$ complete if every formula or its negation is in $S$.

    Show that a set is consistent and complete if and only if it is maximally consistent.

  3. ``The simplest proof of the compactness theorem''

    Let $S$ be a consistent set and {$p$\(_{_1}\!\), $p$\(_{_2}\!\), ...} be the set of all propositional variables. Construct an infinite sequence of sets $B$\(_{_i}\!\) as follows:

    $B$\(_{_0}\!\) := {} $B_{n{+}1}$ := $\left\{\begin{array}{ll} B_n {\mbox{\(\cup\)}} \{p_{n{+}1}\} & \mbox{if $S {... ...up\)}} \{{\mbox{\(\sim\)}}p_{n{+}1}\} & \mbox{otherwise} \end{array}\right.$

    Define $B^*$ := \(\displaystyle\bigcup\)$B$\(_{_i}\!\). Show that there is exactly one interpretation v\(_{_0}\!\) that satisfies $B^*$ and that $S$ is uniformly satisfied by v\(_{_0}\!\).


Juanita Heyerman 2003-02-12