THE UNIVERSITY OF SYDNEY MATH3066 ALGEBRA AND LOGIC Semester 1 Second Assignment 2025 This assignment comprises 60 marks and is worth 15% of the overall assessment. It should be completed and uploaded into Canvas by 11:59 pm on Thursday 22 May 2025. Acknowledge explicitly any sources or assistance, including the use of AI. This must be your own work and written in your own words. Printouts or direct results of searching with AI without any processing of the information are not acceptable. Breaches of academic integrity, including copying solutions, sharing answers and attempts at contract cheating, attract severe penalties. 1. Use the rules of deduction in the Predicate Calculus (but avoiding derived rules) to find formal proofs for the following sequents: (a) (8x) ⇣ G(x) _H(x)) ⇠ K(x)⌘ , (9x) K(x) ` (9x) ⇠ G(x) (b) (8x)(8y)L(x, y)) ⇠ L(y, x) ` (8x) ⇠ L(x, x) (9 marks) 2. (a) Find the fault in the following argument, giving a brief explanation: 1 (1) (9x)G(x)) (9y)H(y) A 2 (2) ⇠ H(a) A 3 (3) G(a) A 3 (4) (9x)G(x) 3 9 I 1, 3 (5) (9y)H(y) 1, 4 MP 6 (6) H(a) A 2, 6 (7) H(a)^ ⇠ H(a) 2, 6 ^ I 2, 6 (8) H(b)^ ⇠ H(b) 7 SI(S) (P^ ⇠ P ` Q) 1, 2, 3 (9) H(b)^ ⇠ H(b) 5, 6, 8 9 E 1, 2 (10) ⇠ G(a) 3, 9 RAA 1 (11) ⇠ H(a)) ⇠ G(a) 2, 10 CP 1 (12) (8x)(⇠ H(x)) ⇠ G(x)) 11 8 I (b) Find a model to demonstrate that the following sequent is not valid: (9x)G(x)) (9y)H(y) ` (8x)(⇠ H(x)) ⇠ G(x)) Briefly justify your answer. (6 marks)

3. In this exercise, we use w↵s to capture the idea of the game scissors-paper-rock, with a cycle of domination, where scissors dominates paper, paper dominates rock, and rock dominates scissors. Consider the following w↵s in the Predicate Calculus: W1 := (9x)(9y) H(x, y) , W2 := (8x)(8y) H(x, y)) ⇠ H(y, x) , (a) Explain why any model in which W1 and W2 are true must have at least two elements. Consider, in addition, the following w↵s: W3 := (8x)(8y) H(x, y), ⇠ K(x, y) , W4 := (8x)(8y) ⇣ K(x, y) _ (9z)H(y, z) ^H(z, x)⌘ . Suppose, in what follows, that U is a model in which W1, W2, W3 and W4 are all true. (b) Explain why U ⇥ U = H [K, and why this union is disjoint. (c) Explain why the diagonal relation {(a, a) | a 2 U} is contained in K. (d) Show that U has at least three distinct elements. (e) Find a model with exactly three elements in which W1, W2, W3 and W4 are true. Full credit is obtained by correctly finding such a model, and it is not necessary to add verifications that these w↵s hold. (15 marks) 4. Recall the division ring of quaternions H = {a+ bi+ cj + dk | a, b, c, d,2 R} where i2 = j2 = k2 = ijk = 1, so that ij = ji = k, jk = kj = i and ki = ik = j. Furthermore, every real number commutes with every element of H under multiplication. (a) If ↵ = a+ bi+ cj + dk 2 H then put ↵ = a bi cj dk. Verify that ↵↵ = a2 + b2 + c2 + d2 . (b) Put = 1 + i+ j. Find , 2 H such that = = j + k . (6 marks) 5. Define the mapping ' : R[x]! R R by the rule ' : p(x) 7! p(0), p(1) for p(x) 2 R[x]. Then ' is a ring homomorphism (and you do not need to verify this). (a) Prove that ' is surjective. (b) Prove that ker' = (x2 + x)R[x]. Hence, by the Fundamental Homomorphism Theorem, R[x]/(x2 + x)R[x] = R[x]/ker' ⇠= im' = R R . (6 marks) 6. In this exercise, you may quote any relevant results or theorems from lectures. Consider the following nontrivial commutative rings with identity, each of which contains exactly 9 elements: S1 = Z3[x]/(x2 + x)Z3[x] , S2 = Z3[x]/(x2 + x+ 1)Z3[x] , S3 = Z3[x]/(x2 + x 1)Z3[x] , S4 = Z3[x]/(x2 x 1)Z3[x] . (a) Use a general result from lectures to explain why S3 and S4 are fields, but S1 and S2 are not fields. (b) Put I = (x2 + x 1)Z3[x]. Find the inverse of I + x+ 1 in S3. Justify your answer briefly. (c) Put J = (x2 x 1)Z3[x]. Find the inverse of J + x+ 1 in S4. Justify your answer briefly. (d) Prove that S3 and S4 are isomorphic. Hint: find an appropriate evaluation map from Z3[x] onto S4, with kernel (x2 + x 1)Z3[x] and apply the Fundamental Homomorphism Theorem. (e) Prove that S1 and S2 are not isomorphic. (18 marks) 51作业君版权所有