MATH1061 / 7861 Assignment 4 Semester 2/2020
Due Friday 30 October at 1pm on blackboard.
Marks will be deducted for sloppy working. Clearly state your assumptions and conclusions, and
justify all steps in your work.
The marked question 5 is required for MATH7861 students only. However, MATH1061 students are encouraged to try this also!
Q1 Q2
Q3
(a) Prove that |R| = |R × Z2|.
(b) Prove that |R| = |R × Z|. (10 marks)
For any real number r, let φ(r) denote the fractional part of r: φ(r) = r−⌊r⌋. For example, φ(5.21) = 0.21, and φ(−6.1) = 0.9.
LetI denotetheinterval[0,1),includingtheendpoint0butexcluding1. Let⊕: I×I→I be defined by x ⊕ y = φ(x + y), and let ⊙: I × I → I be defined by x ⊙ y = φ(x · y).
(a) Is (I,⊕) a group? If so, prove it; otherwise, explain why not.
(b) Is (I,⊙) a group? If so, prove it; otherwise, explain why not. (10 marks)
In this question we work with the complex numbers C: these are all numbers of the form x + yi, where x and y can be any real numbers, and where i is a special symbol with the property i · i = −1. Examples of complex numbers include 3, −i, 2 + 7i, and 4 − 3i.
The complex numbers C form a field under addition and multiplication (and you do not need to prove this!). An example of addition is (2 + 7i) + (4 − 3i) = (6 + 4i) , and an example of multiplication is
(2+7i)·(4−3i) = 2·4−2·3i+7i·4−7i·3i = 8−6i+28i−21i2 = 8+22i+21 = 29+22i, where we use the fact that −21i2 = −21 · (−1) = +21.
(a) The four complex numbers 1, −1, i, −i form a group under multiplication (you do not need to prove this either!). Draw the 4 × 4 Cayley table for this group.
(b) Prove that this group ({1, −1, i, −i}, ×) is isomorphic to (Z4, +).
(c) Prove that (C − {0}, ×) is not isomorphic to (R − {0}, ×) . (10 marks)
Q4 (a)
Q5
When voting for a mayor in Queensland local elections, you number candidates using consecutive integers 1, 2, 3, . . ., and you may number as many or as few candidates as you like (in particular, you may number all of the candidates if you wish, and you may number none of the candidates if you wish). For example, if there are five candidates on the ballot, you might choose to number your three favourite candidates 1,2,3.
In how many possible ways can you vote if there are five candidates on the ballot? Give your answer as a single integer, and show your working.
⋆ For the state election on Oct 31, you must number every box for your vote to count!
(b) The International Olympiad in Informatics uses approval voting. Like before, you can vote for as many or as few candidates as you like (including all or none), but this time you do not use numbers: instead you just place an X against each candidate that you like. For example, if there are six candidates on the ballot, you might choose to place an X against your four favourite candidates.
In how many possible ways can you vote if there are six candidates on the ballot? Give your answer as a single integer, and show your working. (10 marks)
[MATH7861 only]
(a) Is (Z×Z,+) isomorphicto (Z,+)? Herewedefine (a,b)+(x,y)=(a+x,b+y). (b) Is (Q×Q,+) isomorphicto (Q,+)? Againwedefine (a,b)+(x,y)=(a+x,b+y).
You should prove both of your answers correct.
(10 marks)