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作业君