Exam 1

Show all work in a neat and organized fashion. Clearly indicate your answers.

100 points possible.

1. (10 pts.) (a) The statement below is true. Write the beginning and end of a proof, but not the middle. Include the starting point and what is to be shown.

Every compact Hausdorff space is normal.

(b) Is the following proof valid or not? If not, find the mistake.

Theorem. For all integers k, if k > 0 then k²+2k+1 is composite.

Proof. Suppose k is an integer such that k > 0. If k²+2k+1 is composite, then there exists an integer b such that 1 < b < k²+2k+1 and b | k²+2k+1. If 1 < b < k²+2k+1, then b is positive, b ¹ 1, and b ¹ k²+2k+1. Since k²+2k+1 is divisible by b, then k²+2k+1 has a positive divisor other than 1 and itself. Thus, k²+2k+1 is not a prime. Hence k²+2k+1 is composite.

2. (10 pts.) Prove that the sum of two odd integers is even.

3. (10 pts.) (a) Define ``t is divisible by w.'' (Use the textbook definition.)

(b) Disprove: If x and y are integers with x | y, then x £ y.

4. (10 pts.) Prove that if x, y, and z are integers for which x | (y+z) and x | y, then x | z.

5. (10 pts.) Use a truth table to show that x« y is logically equivalent to (x®y)Ù((not x)®(not y)).

6. (10 pts.) (a) A bit string is a list of 0s and/or 1s. How many length-j bit strings can be made?

(b) Define a ternary string to be a list of 0s, 1s, and/or 2s. How many length-j ternary strings can be made?

7. (10 pts.) Order the following integers from least to greatest: 2^1000000, 1000000², 1000000^1000000, 1000000!, 1000¹⁰⁰⁰. (Your work must justify your answer.)

8. (10 pts.) Find the cardinality of the following sets.

(a) {x Î Z : 1 £ x² £ 2}

(b) {{1,2},{3,4,5},{6,7,8,9,10}}

(c) {x Î Z: emptyset Í {x}}

(d) 2^2{0,1,2,3}

(e) {x Î Z: x Î emptyset}

9. (10 pts.) True or False. Please label each of the following sentences about integers as either true or false. (You do not need to prove your answer.)

(a) $x, $y, x+y=0

(b) "x, $y, x+y=0

(c) $y, "x, x+y=0

(d) "x, $y, xy=0

(e) $y, "x, xy=0

10. (10 pts.) Let R, S, and T denote sets. Prove that

(R - S)×T=(R×T) - (S×T).