THE UNIVERSITY OF SYDNEY
MATH3066 ALGEBRA AND LOGIC
Semester 1 Second Assignment 2021
This assignment is worth 20% of the overall assessment. Full marks may be obtained
by achieving 100 marks. The assignment is due 23:59, May 28. 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:
- Your answers should be well written, neat, thoughtful, mathematically con-
cise, and a pleasure to read. Present your arguments clearly using words of
explanation and diagrams where relevant. 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) Derive the following sequents:
(i) (∀x)(F (x)⇒ G(x)), (∀x)F (x) ` (∃x)G(x)
(ii) (∀x)(G(x)⇒ H(x)), (∃x)(F (x) ∧G(x)) ` (∃x)(F (x) ∧H(x))
(iii) (∃x)F (x) ` ∼ (∀x) ∼ F (x)
(iv) ∼ (∀x) ∼ F (x) ` (∃x)F (x)
(b) Assuming the Soundness Theorem for First Order Logic, show that each
of the following sequents is not valid:
(i) (∃x)(∃y)F (x, y) ` (∀z)F (z, z)
(ii) ((∀x)F (x)⇒ (∀x)G(x)) ` (∀x)(F (x)⇒ G(x))
(24 marks)
2. (a) Define W1 = (∀x)(B(x)⇒ H(x)) and
W2 = (∀y)((∃z)(B(z) ∧H(y, z))⇒ (∃z)(A(z) ∧H(y, z))).
(i) Prove W1 `W2.
(ii) Prove W1 |= W2 directly (without using the Soundness Theorem).
(b) Consider the following wffs in First Order Logic:
W1 = (∃x)(∀y)R(x, y)
W2 = (∀x)(∀y)(R(x, y)⇒ R(y, x))
W3 = (∀x)(∀y)(∀z)((R(x, y) ∧R(y, z))⇒ R(x, z))
(i) Prove that in any model U , R ⊆ U × U in which W1,W2,W3 are all
true, it holds that R = U × U .
(ii) Use the rules of deduction of First Order Logic to prove that the
following sequent is valid:
W1,W2,W3 ` (∀x)(∀y)R(x, y).
(26 marks)
3. (a) Let F be a field and suppose that we have the following equation in F [x]:
a(x) = q(x)b(x) + r(x),
where deg r(x) < deg b(x).
(i) Prove that gcd(a(x), b(x)) = gcd(b(x), r(x).
(ii) Suppose gcd(a(x), b(x)) = 1. Prove that there exist polynomials
M(x), N(x) such that
M(x)a(x) +N(x)b(x) = 1.
(b) Prove that the following are irreducible:
(i) 5x4 + 2x3 + x+ 3 ∈ Z[x]
(ii) 1 + x+ x2 + x3 + x4 + x5 + x6 ∈ Z[x] (Hint: use Eisenstein’s Criterion
with a shift.)
(c) Let p(x) ∈ Q[x] be irreducible of degree n, and set I = p(x)Q[x]. Let
α ∈ C be a root of p(x), i.e. p(α) = 0. Consider the field F = Q[x]/I.
(i) Show that the map φ : F → C given by φ(f(x) + I) = f(α) is a
well-defined and injective ring homomorphism.
(ii) Show that
image(φ) = {
n−1∑
i=0
aiα
n−1 | ai ∈ Q, i = 0, ..., n− 1}.
(iii) Use part (b.ii) above to deduce that
{a0 + a1$ + a2$2 + a3$3 + a4$4 + a5$5 + a6$6 | ai ∈ Q}
is a subfield of C, where $ = e 2pii7 . Find the multiplicative inverse of $ in
this field, i.e. express the inverse in the form a0 + a1$ + · · ·+ a6$6 with
ai ∈ Q.
(38 marks)
4. Let R be a unital commutative ring. Let I ⊂ R be an ideal of R. Say that I
is “inclusive” if for any a, b ∈ R, if ab ∈ I then either a ∈ I or b ∈ I. Say that
I is “large” if for any ideal J ⊆ R such that I ⊆ J , either J = I or J = R.
(a) Show that R/I is an integral domain if and only if I is inclusive.
(b) Show that R/I is a field if and only if I is large.
(12 marks)

欢迎咨询51作业君