Let S be the set of all binary strings of length 6. Define a relation ? on S as follows: ?a, b ? S, (a, b) ? ? if and only if the number of ones in the first half of a is equal to the number of ones in the second half of b. For each of the following statements, say whether the statement is true or false and give either a proof or a counterexample. (a) The relation ? is reflexive. (b) The relation ? is symmetric. (c) The relation ? is antisymmetric. (d) The relation ? is transitive. 2. (4 marks) Let T = P(Z +) - {Ø}. Define a relation t on T as follows: ?A, B ? T, AtB if and only if the least element in A is equal to the least element in B. (a) Prove that t is an equivalence relation. (b) Describe the equivalence classes of t . 3. (12 marks) Recall that Sn is the group consisting of the set of all bijections from {1, 2, . . . , n} to {1, 2, . . . , n} together with the binary operation ? denoting composition of functions. (a) Find a cyclic subgroup of S4 that has two elements. (b) Find a cyclic subgroup of S4 that has three elements. (c) Find a cyclic subgroup of S4 that has four elements.
MATH1061 Assignment 4 Due 2pm Thursday 27 May 2021 This Assignment is compulsory, and contributes 5% towards your final grade. It should be submitted by 2pm on Thursday 27 May, 2021. In the absence of a medical certificate or other valid documented excuse, assignments submitted after the due date will not be marked. Prepare your assignment as a pdf file, either by typing it, writing on a tablet or by scanning/photographing your handwritten work. Ensure that your name, student number and tutorial group number appear on the first page of your submission. Check that your pdf file is legible and that the file size is not excessive. Files that are poorly scanned and/or illegible may not be marked. Upload your submission using the assignment submission link in Blackboard. Please note that our online systems struggle with filenames that contain foreign characters (e.g. Chinese, Japanese, Arabic) so please ensure that your filename does not contain such characters. 1. (8 marks) Let S be the set of all binary strings of length 6. Define a relation ρ on S as follows: ∀a, b ∈ S, (a, b) ∈ ρ if and only if the number of ones in the first half of a is equal to the number of ones in the second half of b. For each of the following statements, say whether the statement is true or false and give either a proof or a counterexample. (a) The relation ρ is reflexive. (b) The relation ρ is symmetric. (c) The relation ρ is antisymmetric. (d) The relation ρ is transitive. 2. (4 marks) Let T = P(Z+)− {∅}. Define a relation τ on T as follows: ∀A,B ∈ T , AτB if and only if the least element in A is equal to the least element in B. (a) Prove that τ is an equivalence relation. (b) Describe the equivalence classes of τ . 3. (12 marks) Recall that Sn is the group consisting of the set of all bijections from {1, 2, . . . , n} to {1, 2, . . . , n} together with the binary operation ◦ denoting composition of functions. (a) Find a cyclic subgroup of S4 that has two elements. (b) Find a cyclic subgroup of S4 that has three elements. (c) Find a cyclic subgroup of S4 that has four elements. (d) Find a subgroup of S4 that is isomorphic to (Z2 × Z2,+), and prove that the two groups are isomorphic. 4. (8 marks) In Canada, postal codes consist of six characters with a space separating the third and fourth characters. The first, third and fifth characters are upper-case letters and the second, fourth and sixth characters are digits, for example, M7L 4R8. Canada Post has various restric- tions on the postal codes that are allowed to be used, but please answer this question assuming that the letters can be any of the 26 letters A,B, . . . , Z and the digits can be any of the 10 digits 0, 1, . . . , 9. (a) How many Canadian postal codes are there? (b) How many Canadian postal codes have distinct characters? (c) How many Canadian postal codes contain 7L as consecutive characters (in that order)? (d) If you choose a Canadian postal code at random, what is the probability that it contains the digit 5 or the letter N?