MATH 3066 ALGEBRA AND LOGIC Second Assignment

1. A positive well-formed formula (positive wff) in the Propositional Calculus is a well-formed formula that avoids all use of the negation symbol ∼ .
(a) Use induction on the length of a wff to prove that if W = W (P1 , . . . , Pn ) is a positive wff in terms of propositional variables P1 , . . . , Pn , then V (P1 ) = . . . = V (Pn ) = T
implies V (W ) = T . (5 marks)

(b) Prove that if W = W (P1 , . . . , Pn ) is any wff in the Propositional Calculus such that V (P1 ) = . . . = V (Pn ) = T implies V (W ) = T , then W is logically equivalent to a positive wff. (optional, bonus marks)

2. Use the rules of deduction in the Predicate Calculus to find formal proofs for the following sequents (without invoking sequent or theorem introduction):

(a) (∃x)(∃y)(∀z) K(y, x, z) ⊢ (∀z)(∃y)(∃x) K(y, x, z)

(b) (∀x)(G(x) ⇒ F (x))

(c) (∀x)(∀y)(∃z) R(x, z) ∧ R(y, z)

(d) (∀x)(∀y)(∀z) R(x, y) ∧ R(y, z) ⇒ R(x, z) ,

(∃x) ∼ F (x) ⇒ (∃x) ∼ G(x) ⊢ (∀x)(∃y) R(x, y)

(∀x)(∀y)(∃z) R(x, z) ∧ R(z, y)
(∀x) R(x, x)
(21 marks)

3. Consider the following well-formed formulae in the Predicate Calculus:
W1
W2
W3

=

=

=

(∃x)(∃y) R(x, y)

(∀x)(∀y) R(x, y) ⇒ ∼ R(y, x)

(∀x)(∀y) R(x, y) ⇒ (∃z) R(z, x) ∧ R(y, z)

Prove that any model in which W1 , W2 and W3 are all true must have at least 3 elements. Find one such model with 3 elements. (6 marks)
4. Let R = Z[x] and
I = 2Z + xZ[x] ,
the subset of R consisting of polynomials with integer coefficients with even constant terms. Verify that I is an ideal of R. Show that I not a principal ideal. (8 marks)
5. Let R = Z3 [x]/(x2 − x − 1)Z3 [x], so we may write R = { 0 , 1 , 2 , x , x + 1 , x + 2 , 2x , 2x + 1 , 2x + 2 } ,
where we identify equivalence classes with remainders after division by the polynomial x2 − x − 1. Then R is a commutative ring with identity. Construct the multiplication table for R and use it to explain why R is a field. Now find a primitive element, that is, an element a ∈ R such that all nonzero elements of R are powers of a.
(8 marks)

6. In each case below, if it helps, you may identify the ring with remainders after division by x2 + x + 1, so that the elements become linear expressions of the form a + bx where a, b come from Z3 in part (a) or from R in part (b).
(a) Explain why R = Z3 [x]/(x2 + x + 1)Z3 [x] is not a field.

(b) Prove that F = R[x]/(x2 + x + 1)R[x] is isomorphic to C, the field of complex numbers.