Metamathematics Fall 2001 Problem Set 1:

The first problem will be discussed on Wednesday Aug. 22. The other problems will be reviewed in class on Monday Aug. 27. Tentatively, 1-4 are due September 3.

A. How many different answers are there to the question 720÷120÷20÷6? What are they? More generally suppose a structure has a single binary operation #? How many different values could the expression a_{1}#a_{2}# … #a_{n}? take?

1. A truth function is a map from the set of truth values {T, F } to itself. The truth function H is definable from H_{1}, … H_{n} if H(a_{1}, … a_{n}) = … where the r.h.s is built up from H_{1}, … H_{n}, a_{1}, … a_{n}, commas and parentheses in the natural way.

a) Let H_{D,n} be the truth function defined by H_{D,n}(a_{1}, … a_{n}) = T iff some a_{i} = T and let H_{C,n}(a_{1}, … a_{n}) = T iff every a_{i} = T. Let H_{¬}(a_{1}) = T if a_{1} = F and vice versa. Show that every truth function is definable in terms of H_{¬} and certain of the H_{C,n}, H_{D,n}.

More precisely,

b) Show every truth function is definable from H_{¬} and H_{∧} = H_{C,2}.

c) What are H_{→} and H_{↔}?

d) Show not every truth function is defined from H_{∧}, H_{∨}, H_{↔}.

e) The Scheffer stroke is the truth function H_{S} defined by H_{S}(a, b) = T iff a = b = T. Show every truth function is definable from the Scheffer stroke.

2. a) Suppose ϕ_{1}, …, ϕ_{n} are L-formulas and ψ is a Boolean combination of ϕ_{1}, …, ϕ_{n}. Then there is S ⊆ P({1, …, n}) such that

⊧ ψ ⇔ ⋁_{X∈S}(⋀_{i∈X} ϕ_{i} ∧ ⋀_{i∉X} ¬ϕ_{i}).

b) Show that every formula is equivalent to one of the form Q_{1}v_{1} … Q_{m}v_{m} ψ where ψ is quantifier free and each Q_{i} is either ∀ or ∃.

3. a) Let L = {·, e} be the language of groups. Show that there is a sentence ϕ such that M ⊧ ϕ if and only if M ≅ ℤ/2ℤ × ℤ/2ℤ.

b) Let L be any finite language and let M be a finite L-structure. Show that there is an L-sentence ϕ such that N ⊧ ϕ if and only if N ≅ M.