THE UNIVERSITY OF SYDNEY
MATH3066 ALGEBRA AND LOGIC
Semester 1 Second Assignment 2024
This assignment comprises 60 marks and is worth 20% of the overall assessment.
It should be completed and uploaded into Canvas before midnight on Friday 17
May 2024. Acknowledge any sources or assistance. This must be your own work.
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 to find a formal proof for
the following sequent (without invoking sequent or theorem introduction):
(∀x)
((
H(x) ∨K(x)) ⇒ G(x)) , (∃y)K(y) ` (∃z)G(z)
(4 marks)
2. (a) Find the fault in the following spurious argument. Explain briefly.
1 (1)
(
(∃x)G(x))⇒ ((∃y)H(y)) A
(2) G(a) ∨ ∼ G(a) TI(S) (P ∨ ∼ P )
3 (3) G(a) A
3 (4) (∃x)G(x) 3 ∃ I
1, 3 (5) (∃y)H(y) 1, 4 MP
6 (6) H(a) A
6 (7) G(a)⇒ H(a) 6 SI(S) (Q ` P ⇒ Q)
1, 3 (8) G(a)⇒ H(a) 5, 6, 7 ∃ E
9 (9) ∼ G(a) A
9 (10) G(a)⇒ H(a) 9 SI(S) (∼ P ` P ⇒ Q)
1 (11) G(a)⇒ H(a) 2, 3, 8, 9, 10 ∨ E
1 (12) (∀x)(G(x)⇒ H(x)) 11 ∀ I
(b) Use a model and Soundness to demonstrate that the following sequent
cannot be proved using the Predicate Calculus:(
(∃x)G(x))⇒ ((∃y)H(y)) ` (∀x)(G(x)⇒ H(x))
(c) Prove the following sequent using rules of deduction from the Predicate
Calculus (without invoking sequent or theorem introduction):(
(∃x)G(x))⇒ ((∀y)H(y)) ` (∀x)(G(x)⇒ H(x))
(12 marks)
3. Recall the division ring of quaternions
H = {a+ bi+ cj + dk | a, b, c, d,∈ R} .
(a) Put β = 1 + 2i+ 3j. Find γ, δ ∈ H such that
βγ = δβ = 4i+ 5j + 6k .
Verify any claims. You may quote the fact that if α = a+ bi+ cj+dk ∈ H
and α = a− bi− cj − dk. then αα = a2 + b2 + c2 + d2 .
(b) Find the two square roots of 2i− 3j− 6k in H and prove that there are no
others.
(c) Find infinitely many distinct square roots of −1 in H. Verify any claims.
(11 marks)
4. Consider the following subring S of Z210, consisting of all multiples of 7:
S = 7Z210 = {7k | k ∈ Z210} .
(a) Explain briefly why 91 is the multiplicative identity element of S.
(b) Verify that if α = 7k is an element of S, then α = α2 is idempotent if and
only if, as integers, each of 2, 3 and 5 divides either k or 7k − 1.
(c) List all the idempotents of S. (If you do this correctly, you gain full credit,
without any justification.)
(d) Prove that S is isomorphic to the ring Z2 ⊕ Z3 ⊕ Z5. You may quote the
Chinese Remainder Theorem and the fact that for any positive integer n,
the quotient ring Z/nZ is isomorphic to Zn.
(15 marks)
5. Consider the following set of 3× 3 matrices:
S =
{ a b c0 a b
0 0 a
 ∣∣∣∣∣ a, b, c ∈ R
}
.
Then S is a subring of the ring Mat3(R) of all 3 × 3 matrices over R. This is
straightforward and you may use this fact without proof.
(a) Verify that S is a commutative ring with identity, but S is not an integral
domain.
(b) Use an evaluation map from R[x] to S and the Fundamental Homomor-
phism Theorem, or otherwise, to show that
S ∼= R[x]/x3R[x] .
(c) Describe an ideal J of S such that
S/J ∼= R[x]/x2R[x] .
Verify any claims.
(18 marks)