Description

CS 70 Discrete Mathematics and Probability Theory

1 Proof Practice
(a) Prove that ∀n ∈ N, if n is odd, then n2 +1 is even. (Recall that n is odd if n = 2k+1 for some natural number k.)
(b) Prove that ∀x,y ∈ R, min(x,y)=(x+y−|x−y|)/2. (Recall, that the definition of absolute value for a real number z, is

(c) Suppose A ⊆ B. Prove P(A) ⊆ P(B). (Recall that A0 ∈ P(A) if and only if A0 ⊆ A.)
2 Preserving Set Operations
For a function f, define the image of a set X to be the set f(X)= {y | y = f(x) for some x ∈ X}. Define the inverse image or preimage of a set Y to be the set f −1(Y)= {x | f(x) ∈ Y}. Prove the following statements, in which A and B are sets. By doing so, you will show that inverse images preserve set operations, but images typically do not.
Recall: For sets X andY, X =Y if and only if X ⊆Y and Y ⊆ X. To prove that X ⊆Y, it is sufficient to show that (∀x)((x ∈ X) =⇒ (x ∈Y)).
(a) f −1(A∪B)= f −1(A)∪ f −1(B).
(b) f(A∪B)= f(A)∪ f(B).
3 Fermat’s Contradiction
Prove that 21/n is not rational for any integer n ≥ 3. (Hint: Use Fermat’s Last Theorem. It states that there exists no positive integers a,b,c s.t. an+bn = cn for n ≥ 3.)
4 Pebbles
Suppose you have a rectangular array of pebbles, where each pebble is either red or blue. Suppose that for every way of choosing one pebble from each column, there exists a red pebble among the chosen ones. Prove that there must exist an all-red column.