Problem#1.

(a) Provide a derivation (via natural deduction in propositional logic) of the following: {(-ϕ)} 上 (ϕ - ψ).

(b) Provide a derivation (via natural deduction in propositional logic) of the following: 上 ((ϕ v ψ) 4 ((ϕ - ψ) - ψ))

(c) Suppose that Γ C PROP is a set of propositions, and ϕ, ψ e PROP are propositions. Show that if Γ is consistent and Γ 上 (ϕ v ψ), then at least one of the sets Γ u {ϕ} and Γ u {ψ} is also consistent.

Problem#2.

(a) Write down the similarity types of the following structures.

(i) (Q, <, 0〉.

(ii) (p(N), C, u, n, 0〉.

(iii) (Z/5Z, +, · , _, − 1 , 0, 1, 2, 3, 4〉.

(b) Consider the language of rings.

(i) Give a sentence ϕ in the language of rings so that a ring a is an integral domain if and only if a >= ϕ .

(ii) Give a sentence σ with free variable x so that for any ring a and any a e >a>, we have a >= σ(a) if and only if the principal ideal (a) is prime.

(c) Justify the following statements.

(i) If a is a structure and σ is a sentence in L(a), then either a  >= σ or a  >= -σ . (Hint: This does not take long to justify.)

(ii) The statement above isn’t true for formulas in general. To show this, give a struc- ture a and a formula ϕ so that both a > ϕ and a > -ϕ . Briefly explain the issue in one or two lines of plain english.

Problem#3.

(a) Show the following:

(i) For any formula ϕ , >= (Ax(ϕ - ψ)) - ((Axϕ) - (Axψ)) is true.

(ii) The converse is false:  > ((Axϕ) - (Axψ)) - (Ax(ϕ - ψ)). (Prove via example.)

(b) For any formula ϕ, show >= 3x ┌ ϕ(x) - (Ay ϕ(y))] is true.

(c) If S is a binary predicate, then >= -3yAx ┌ S(x, y) 4 -S(x, x)] is true.

. One may wish to think of the predicate S(x, y) as representing “y shaves x” . This viewpoint relates the sentence above to Russell’s barber paradox, which is a fun thing to google and learn about, although it isn’t strictly necessary for the problem or the module.