Assignment 2: Due Sept. 10. page 24: 4.7 and 4.8 and the following: In proving unique readability of formulas I changed the formation rules to make (x=y) and (Rx_1 ... x_n) well formed (and e.g. x=y is not well formed. Returning to the definition in book show that no proper initial segment of a formula is a formula.
page 32: Turn in one part of 2.1.
The Scheffer stroke is the connective p|q which is true unless both p and q are true. Show that {|} is a truth functionally complete set of connectives. That is, every propositional formula is equivalent to one using only |.
page 33: Turn in exercise 3.3 and 3.4.
page 47: 6.7, 6.9, 6.10. Do 6.8 or if you find it boring try to classify the complete theories which extend the theory of equivalence relations. If you do this second part, concentrate your effort on a careful succinct presentation of the alternatives, not an exhaustive description of how to formalize various statements.
page 90: 2.5
page 93: turn in 3.7, 3.8, 3.9, 3.10. Make sure you can do 3.11.
Let L contain a single binary relation symbol: $<$. Let $T$ be a complete $L$ theory such that the models of $T$ are linearly ordered. $T$ admits well orders if there is a model of $T$ which is well-ordered by $<$. Show using the Lowenheim Skolem theorem that there are at most $\aleph_1$ complete theories which admit well orders. (Challenge: Show there are only countably many such theories.)
Assignment 7: Due Oct. 15 Recall that for any $L$-structure $A$ the (quantifier free diagram) of $A$ is the collection of all $L(A)$ -sentences $\phi(\vec a)$ such that $\phi(A)$ is true in $A$. Assume the following: If $k$ is a field and $f \in k[x]$ is a nonconstant polynomial then $f$ has a root in some extension field of $k$. 1. Show every field $k$ has an extension field $k_1$ in which every nonconstant polynomial $f \in k[x]$ has a root. (Hint. Expand the axioms for fields and the diagram of $k$ by adding for each $f \in k[x]$ the axiom that it has a root. Prove the consistency of this theory by compactness. 2. Show that every field is a subfield of an algebraically closed field. (Iterate 1.) 3. A celebrated theorem of Urbana shows all maps of finitely many countries can be colored with 4 colors (and no two adjacient countries are the same color). Use the compactness theorem to show this holds even if there are infinitely many countries.
Assignment 8: Due Oct. 24. page 156: 1.11, page 162: 2.10, 2.11, 2.13, 2.14, page 170: 4.3 If you know the definition of Turing machine, think about proving that Turing machines and register machines compute the same functions.
Assignment due Dec. 5 (last day of classes) 1. Recall that Gamma is a right total interpretation (in the sense of Hodges) of U into T if for each model B of U there is a model A of T such that Gamma A is isomorphic to B. Show that if there is a right total interpretation and U is both finitely axiomatizable and undecidable then T is undecidable. 2. Let B be the direct sum of A with itself. Show B is interpretable in A. 3. Which of the following theories are decidable; which undecidable? a) the real field, R, b) rings of polynomials over the reals R[x], c) the real quaternions d) the field of functions Q(x). 4. Is it possible that the theory of fields is essentially undecidable? undecidable? 5. Show that the range of a nonrecursive total recursive function is a recursive set. 6. Enderton's book asked whether the function f(n) which is identically 0 if Fermat's theorem is true and indentically 1 otherwise is recursive. Why could this problem be answered in 1985? 7. Show that a subset of (N,S) is definable if and only if it finite or cofinite. Show that the standard order relation on N is not definable in (N,S).