MTH 207 Final Sample, Fall 2012

1. Let A, B and C be sets. Who that (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C) , using any method. (Remember A ⊕ B = {x s.t. x ∈ A or x ∈ B but not in both} 2. Let f : Z × Z → Z be defined by f(m, n) = 2m3n. (a) Is f 1-1? (b) Is f onto? 3. Same question if f : R × R → R × R 4. Let ∼ be a relation on Z given by m ∼ n if and only if m3 = n3 Show that ∼ is an equivalence relation and find the equivalence classes 5. Fill in the blanks with the appropriate symbols (∈, /∈,or ⊂, �) in the following cases: (a) 1.....{1, 2, {1}, {1, 2}} (b) {2}....{1, 2, {1}, {1, 2}} (c) {{1}}...{1, 2, {1}, {1, 2}} (d) {1, {2}}...{1, 2, {1}, {1, 2}} 6. Write the negation of the following statements (a) All students are given a second chance (b) If we relax, we will perform (c) If the weather permits and if we are lucky then we will meet in the park 7. Sketch a graph whose adjacency matrix is     0 0 1 0 1 0 0 0 1 2 0 0 3 0 0 1     You can label the vertices with any letter you choose, ex v1, v2, .. 8. Write your own relation on the set {1, 2, 3, 4, 5} that is (Reflexive) and (Anti Symmet- ric) and (Transitive).Draw its digraph. 9. Write an explicit formula;a for an = 3an−1 − 2an−2; n ≥ 3, where a1 = 5, and a2 = 3. 10. If bn = 4 + bn−1, for all n ≥ 1, if b0 = 5,show that bn = 5 + 4n 11. Consider the matrices: A =   4 5 −3 2 1 4 3 1 0   and B =   2 −1 1 0 2 2 1 0 3   . Evaluate the following: (a) A + B 1 (b) 2A − 3B (c) A.B (d) B.A (e) At 12. Prove by induction that n(n2 + 5) is divisible by 6. 13. A license plate for a car consists of 3 letters followed by 4 digits. (a) How many possible licence plates are there? (b) How many are there with no repeated letters and non repeating digits? 14. Partial Order Define the relation R on the plane by (x, y) R (w, u) if x2 + y2 < w2 + u2 or (x, y) = (w, u) • Show that this relation is a partial order • Is it a total order? 15. Given any four integers, explain why two of them must be congruent mod 3. 16. Let A and B be two finite sets with |A| < |B|. True or false. • There is a function mapping A onto B • There is a function mapping B onto A. • There is a one to one function from a A to B • There is a one to one function from B to A 17. True or false • The set of positive rationals is countable • The set of all positive real numbers is countable • The intersection of two countably infinite sets is countably infinite 18. Show that m � k=0 aknk = amnm + O(nm−1), if am ̸= 0 19. Fact1: If R is a relation on a set S, then R is transitive if and only if R2 ⊆ R. Fact 2: If MR is the boolean matrix corresponding to R, then the matrix given by the boolean product MR ⊙ MR corresponds to the composition of the relation with itself i.e. R ◦ R. 2 For two boolean matrices of the same size m × n, M and N, we say that M ≤ N if mij ≤ nij for all i = 1, · · · m and j = 1, · · · n. Fact 3: R1 ⊆ R2 if and only if MR1 ≤ MR2 Use the 3 facts above to show that the relation R on the set S = {1, 2, 3} whose matrix is MR =   1 0 0 1 0 0 1 1 0   is transitive (compute a suitable boolean product) 3