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)

学霸联盟