1.       Let S S L(P) be a set of propositions. Suppose that every finite subset of S has a model. Prove that S itself has a model.

2.       Let t1 , t2 , . . .  be a sequence of propositions with the following property:  for every valuation v , there is some n such that v(tn ) = 1.

Deduce the following stronger statement: there exists N > 1 such that, for every valuation v , there is some n s N such that v(tn ) = 1.

3.       Suppose we color the integer lattice points Z2  red and blue: that is, we give a function c : Z2  → {r, b}.

Assume the following result: for any such coloring c, there is an axis-aligned square (x, y), (x + a, y), (x, y + a), (x + a, y + a) (where x, y e Z and a e Z / {0}) with all points the same color.

(a)  Let P\  = {px,y : x, y e Z}. If px,y  denotes the statement “c(x, y) is red”, show that there exists a

set S S L(P\ ) of propositions which encode the statement “there is no axis-aligned square with all points the same color” .

(b)  Prove the following statement: there exists N > 1 such that any red-blue coloring of {-N, . . . , N}2

contains an axis-aligned square with all points the same color.

[Hint: use the compactness theorem.]

4.       Let S1 , S2   S L(P) be subsets with the following property:  for every valuation v, either v is a model of S1  or v is a model of S2 , but not both.

Prove that there exist finite subsets  T1   S  S1   and T2   S  S2   such that T1   is tautologically equvialent to S1  and T2  is tautalogically equivalent to S2 .