THE UNIVERSITY OF SYDNEY
MATH3066 ALGEBRA AND LOGIC
Semester 1 First Assignment 2020
This assignment is worth 20% of the overall assessment. Full marks may be obtained
by achieving 100 marks. The assignment is due April 24. You need to submit it
on Canvas via Turnitin. There will be information on the Canvas webpage on how
to do this. Keep in mind the following:
- Please write neatly and clearly, showing all explanations. Illegible work
will not be marked.
- You may freely use theorems from class. However when you do apply a
result from class, please state what that result is.
- Discussing the assignment questions with your peers is fine, and indeed
general discussions are encouraged and are usually beneficial. However:
Your final written solutions must be your own work - copying solutions
is of course plagiarism, and will be given zero marks.
You shouldn’t need to make use of material from outside of the course -
however if you do then you absolutely must clearly reference anything that
assisted you with the preparation of your solutions. Failing to do so is a
form of plagiarism.
1. (a) Use the formal rules of deduction to carefully prove the following are valid
sequents. Feel free to use earlier sequents in proofs of later ones by applying
Sequent Introduction.
(i) P ⇒ Q, Q⇒ R ` P ⇒ R
(ii) P, P ⇐⇒ Q ` Q
(iii) P, ∼ (P ∧Q) ` ∼ Q
(iv) P ∧ (Q ∨R) ` (P ∧Q) ∨ (P ∧R)
(b) Give truth tables for each of the following:
(i) (∼ P )⇒ (P ⇒ Q)
(ii) (P ∧Q) ∨ (P ∧ (∼ R))
(c) Use truth values by working backwards to verify that the following are semantic
theorems:
(i) ∼ Q⇒ (P ⇒ (Q⇒ R))
(ii) (P ⇒ R)⇒ ((Q⇒ R)⇒ ((P ∨Q)⇒ R))
(28 marks)
2. (a) Prove that the following sequents cannot be valid:
(i) (P ⇒ Q)⇒ ∼ P, P ⇒ Q ` P
(ii) ` (P ⇒ Q)⇒ (Q⇒ P )
(b) Recall that the proof of the Soundness Theorem breaks up into ten cases cor-
responding to the ten different rules of derivations. Complete the case of the
proof corresponding to DN.
(c) The proof of the Completeness Theorem relies on the Key Lemma, and the
proof of the Key Lemma is by strong induction on the length `(W ) of a wff W .
We will complete to cases of the inductive step of the proof of the Key Lemma
that we skipped in lecture.
Let N ≥ 1 and suppose the Key Lemma holds for any wff W such that `(W ) ≤
N . Now let W be a wff of length N + 1 and let X,Y be wffs. Show that the
Key Lemma holds for W in the cases where:
(i) W = X ∨ Y
(ii) W = X ⇒ Y
(22 marks)
3. (a) If today is Monday, what day will it be in 2525 days?
(b) Let x = dkdk−1 . . . d2d1 be the base 10 representation of an integer x where
d1, . . . , dk are digits between 0, . . . , 9. Show that
(i) x ≡ d1 + d2 + . . . + dk (mod 9)
x ≡ d1 + d2 + . . . + dk (mod 3)
x ≡ d1 − d2 + d3 − d4 + . . . + (−1)k−1dk (mod 11)
(ii) Explain how to use this to check easily whether numbers are divisible by
3, 9 and 11. Use this to check whether 911, 219, 186, 429 is divisible by 3, 9
and 11.
(14 marks)
4. (a) Consider the two ideals in the ring Z2[x] given by I = (x2 + 1)Z2[x] and
J = (x2 + x)Z2[x]. Let R = Z2[x]/I and S = Z2[x]/J . Note that these are
both rings of order 4. Write down the addition and multiplication tables for
both R and S.
(b) Are R and S isomorphic? If they are, construct the isomorphism, and if they
are not, explain why.
(12 marks)
5. (a) Let f : X → Y be a function between sets X,Y . For x, x′ ∈ X define x ∼ x′ if
f(x) = f(x′). Show that ∼ is an equivalence relation, and construct a bijection
between X/ ∼ and im(f).
(b) Let Z[i] = {a + bi | a, b ∈ Z}. This is a subring of C (you don’t have to prove
this). Consider the ideal I = (x2 + 1)Z[x] / Z[x]. Construct an isomorphism
Z[x]/I ∼= Z[i]. You may use the following fact without proof: if p(x) ∈ Z[x]
satisfies p(i) = 0 then x2 + 1 divides p(x).
(12 marks)
6. (a) Let R be a commutative unital ring, and let I / R be an ideal. Fix an element
a ∈ R. Show that
J = {x + ay | x ∈ I, y ∈ R}
is an ideal of R, and that I ⊆ J .
(b) Let R be as in part (a). Call an ideal I / R “large” if I 6= R, and any ideal
J / R such that I ⊆ J satisfies J = I or J = R. Now let I / R be a large ideal.
Show that R/I is a field. (Hint: use part (a).)
(12 marks)



















































































学霸联盟