xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

数学代写-MATH3066-Assignment 20

时间：2021-04-12

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)

学霸联盟

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)

学霸联盟