MATH 160A FALL 2022 Homework – week 3
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH 160A
FALL 2022
Homework – week 3
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 .
5. Which of the following functions N → N n {l} are (partial) computable? You may give the answers “definitely yes”, “definitely no” or “not known to be computable given the current state of mathematical knowledge” .
(a) f (n) =
(b) f (S, t) = r(t)wise.
(c) f (n) =
,
2022-10-20