MATH7861 ASSIGNMENT 4
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH7861 ASSIGNMENT 4
DUE DATE: FRIDAY OF WEEK 13 (OCTOBER 27), 4:00 PM
Problems.
(1) (15 marks) Throughout this question, × represents the operation of multiplication modulo 9.
That is, x × y = xy mod 9.
(a) Recall that Z9 = {0, 1, 2, . . . , 8}. Prove that (Z9 − {0} , ×) is not a group.
(b) Write out the Cayley table of (Z9 − {0, 3, 6} , ×) and use the table to prove that (Z9 − {0, 3, 6} , ×) is a group. (You may assume associativity, as we know that multiplication modulo any integer is associative.)
(c) Determine the cyclic subgroup ⟨4⟩ in (Z9 − {0, 3, 6} , ×).
(d) State an isomorphism from (Z9 −{0, 3, 6} , ×) to (Z6 , +) by listing the image of each element for your isomorphism. (ie. f(1) = ..., f(2) = ..., etc.)
(2) (15 marks) Let n be a positive integer. Recall that Sn is the group consisting of all bijections from {1, 2,..., n} to {1, 2,..., n} together with the binary operation ◦ denoting composition of functions. Let Fn be the set of all functions from {1, 2,..., n} to {1, 2,..., n} .
(a) Determine |Fn | stating your answer as a formula in the variable n.
(b) If a random function is chosen from F5 , what is the probability that it is a bijection? (c) For n ≥ 2, determine the number of elements f of Sn for which f(1) 
1 and f(2) 
2.
(3) (15 marks) Determine the probability that a randomly chosen 5-element subset of {1, 2, 3, . . . , 20} contains at least one prime number and at least one single-digit number.
(4) (15 marks) The AFL (Australian Football League) has 18 teams. Each team plays one game per week. Assume a team never plays a given other team more than once. Prove that after 8 weeks, there exists at least 3 teams none of which have played each other.
(5) (20 marks) Recall that in Assignment 1 you started reading an extract on G¨odel’s Undecidability Theorem; we now return to that text. Read pages 58–64 (Mathematical Systems, Consistency of Mathematical Systems, Resolving Logical Paradoxes and the start of the section on G¨odel’s Undecidability Theorem) of this extract. You do not need to read the explanation of the proof of G¨odel’s Theorem but you are welcome to read to the end of the document if you want. Note that completing the (optional) exercises 3–9 provided at the end of the document might assist your understanding of these sections. Solutions to those exercises have been provided.
(a) As in the reading, let point and line be undefined terms, and remember that a line does
not necessarily have to be straight or contain an infinite number of points. Prove that the following axioms are inconsistent.
(i) There are exactly seven points in the system.
(ii) Each line contains exactly four points.
(iii) Each pair of points lies on exactly one line.
(b) In your own words, describe Russell’s Paradox in a short paragraph of 100–200 words.
In addition to pages 63–64 of the extract on G¨odel’s Undecidability Theorem (Resolving Logical Paradoxes), you should also read the section on Russell’s Paradox in the course textbook Discrete Mathematics with Applications (pages 378–380 of the 4th edition or pages 419–421 of the 5th edition).
2023-10-24