Mathematics 243, section 2 – Mathematical Structures Information on Exam 1 September 22, 2017

General Information

As announced in the course syllabus and the schedule on the course homepage, the first exam this semester will be given Friday, September 29 (or possibly Thursday evening, September 28). The exam will cover the material we have discussed since the start of the semester, through the material on mathematical induction proofs from class on September 20 and 22. The topics to review are:

1) Logic: truth tables for “not,” “and,” “or,” “implies,” “iff,” and their use in finding truth tables for compound statements, establishing tautologies, etc.

2) Sets, set operations: union, intersection, complement, set difference, and their properties; proving or disproving set containment, equality, etc. (This might include some material about partitions of sets as well)

3) The natural numbers, know the Peano axioms, be able to do proofs by mathematical induction

Practice Problems

The exam will consist of 4 or 5 problems (each possibly having several parts). Some questions will ask you to find sets by using set operations or compute a truth table, some will ask for definitions and/or (short) proofs.

Suggestions on How To Prepare

Read over your notes from class (several times, if necessary!). Make sure you can follow all the steps in proofs and examples. Review the problems from the problem sets, and pay particular attention to any problems you missed the first time. Then try the following review questions:

Note: This list is longer than the actual exam will be to show the range of different kinds of questions that might appear.

I. Construct the truth tables for the following statements. A) (P and (P implies Q)) implies Q. B) ((not Q) and (P implies Q)) implies (not P). C) (P or (Q and R)) if and only if ((P or Q) and (P or R)). D) Which of A,B,C are tautologies?

II. Let

U = Z
A = {x ∈ Z : x is even and − 3 ≤ x ≤ 10}
B = {1, 2, 3, 4, 5}
C = {x ∈ Z : x < −4 or x > 7}

A) What is the set A ∩ B. B) What is the set A^{c} ∩ (B ∪ C)? C) What is the set C^{c}?

III. Let A, B be any two subsets of a universal set U. Prove that (A ∩ B)^{c} = A^{c} ∪ B^{c} (where X^{c} is the complement of X in U).

IV. Consider the following statement, where A, B are nonempty sets of real numbers. “If A ∩ [0, 1] = ∅, and B ∩ [0, 1] = B, then A ∩ B = ∅. A) Give the contrapositive form of this statement. B) Give the converse of the statement. Is the contrapositive statement true or false?

Explain.

V. Prove or disprove: A) 12Z ⊆ 6Z B) 24Z ∩ 30Z = 120Z C) For any three sets A, B, C, A ∩ (B ∪ C) = (A ∩ B) ∩ (A ∩ C). D) If n^{2} is an odd integer, then n is an odd integer.

VI. A) Prove: If m, n are integers with no common factors, then \frac{m}{n} ≠ \sqrt{3}. (Prove by contra-

diction. You may use without justification the following plausible statement that we will prove later: If k is an integer and k^{2} is a multiple of 3 then k is a multiple of 3.)

B) Investigate this question: For which integers m is it true that if k is an integer and k^{2} ∈ mZ, then k ∈ mZ? Is it true for m = 4, 5, 6, 7, 8, 9, etc. ? (Note: this is too open-ended to be an exam question, but it is interesting to look at!)

VII. Prove by mathematical induction: A) For all n ≥ 1 in N,

1 · 2 + 2 · 2^{2} + 3 · 2^{3} + ⋯ + n · 2^{n} = (n − 1)2^{n+1} + 2

B) For all n ≥ 1 in N,

1^{2} + 3^{2} + 5^{2} + ⋯ + (2n − 1)^{2} = \frac{n(2n − 1)(2n + 1)}{3}

C) For all n ≥ 6, n^{3} < n!