Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: zz-x2580
MATH3066 ALGEBRA AND LOGIC
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 20
May 2022. 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)
((
G(x) ∨H(x)) ⇒ K(x)) , (∃x) ∼ K(x) ` (∃x) ∼ H(x)
(8 marks)
2. (a) Find the error in the following argument. Explain briefly.
1 (1) (∃x)(G(x)⇒ H(x)) A
2 (2) G(a)⇒ H(a) A
3 (3) (∃x)G(x) A
4 (4) G(a) A
2, 4 (5) H(a) 2, 4 MP
2, 4 (6) (∃y)H(y) 5 ∃ I
2, 3 (7) (∃y)H(y) 3, 4, 6 ∃ E
1, 3 (8) (∃y)H(y) 1, 2, 7 ∃ E
1 (9)
(
(∃x)G(x))⇒ ((∃y)H(y)) 3, 8 CP
(b) Find a model to demonstrate that the following sequent cannot be proved
using the Predicate Calculus:
(∃x)(G(x)⇒ H(x)) ` ((∃x)G(x))⇒ ((∃y)H(y))
(c) Prove the following sequent using rules of deduction from the Predicate
Calculus: (
(∃x)G(x))⇒ ((∃y)H(y)) ` (∃x)(G(x)⇒ H(x))
Sequent and Theorem Introduction (with appropriate substitutions) are
permitted with respect to sequents from the Propositional Calculus that
have been proved in lectures or tutorials.
(16 marks)
3. Consider the following well-formed formulae:
W1 = (∃x)H(x) , W2 = (∀x)E(x, x) , W3 = (∀x)
(
G(x)⇒ ∼ H(x))
W4 = (∃x)(∃y)
(
G(x) ∧G(y)∧ ∼ E(x, y)
)
(a) Explain why, in any model U for which W3 is true, the predicates G and
H, regarded as subsets of U , must be disjoint.
(b) Prove that any model in which W1, W2, W3 and W4 are all true must have
at least 3 elements. Find one such model with 3 elements.
(9 marks)
4. Recall the division ring of quaternions
H = {a+ bi+ cj + dk | a, b, c, d,∈ R}
where i2 = j2 = k2 = ijk = −1, so that ij = −ji = k, jk = −kj = i and
ki = −ik = j. Furthermore, every real number commutes with every element
of H under multiplication.
(a) If α = a+ bi+ cj + dk ∈ H then put α = a− bi− cj − dk. Verify that
αα = a2 + b2 + c2 + d2 .
(a) Put β = 1 + i+ j + k. Find γ, δ ∈ H such that
βγ = δβ = 4i .
(7 marks)
5. Let R = {0, 1, x, x + 1, x2, x2 + 1, x2 + x, x2 + x + 1} be the subset of Z2[x]
consisting of all polynomials of degree at most 2, with usual addition and
multiplication of polynomials followed by taking the remainder after dividing
by x3 + x + 1. Then R is a commutative ring with identity (and you do not
need to verify this).
(a) Construct the multiplication table for nonzero elements of R, and explain
briefly why R is a field. (To get full credit for this part, it is not necessary
to show any calculations.)
(b) List the elements of the set {α2 + α |α ∈ R}. (To get full credit for this
part, it is not necessary to show any calculations.)
(c) Solve the following equation over R for α where
α3 + (x2 + x)α+ x2 + x+ 1 = 0 .
[Hint: α = 1 is a solution.] (10 marks)
6. Define the mapping ϕ : R[x]→ R⊕ R by the rule
ϕ : p(x) 7→ (p(1), p(−1))
for p(x) ∈ R[x] Then ϕ is a ring homomorphism (and you do not need to verify
this). Prove that ϕ is surjective and kerϕ = (x2 − 1)R[x]. Deduce that
R[x]/(x2 − 1)R[x] ∼= R⊕ R .
