The statement “An integer is even if and only if its square is even”

(5 points) True/False Let S = {a, b, c}
(a) T F a ∈ P(S)
(b) T F {a} ∈ P(S)
(c) T F {a, b} ⊆ P(S)
(d) T F {a, {a, b}} ⊆ P(S)
(e) T F {{a}, {a, b}} ⊆ P(S)
(10 points) Consider the statement “An integer is even if and only if its square is even”
(a) Translate the statement into quantified logic. Be sure to specify a universe, and define
any open statements you use.
(b) Prove the statement.
(10 points) For any sets A and B: A ∩ B = A ∪ B
(a) Sketch two Venn Diagrams to convince yourself (and me) of this property.
(b) Now prove this property using Laws of Logic.
(5 points) Recall the Fibonacci Sequence:
F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2
Prove by induction:
Xn
i=0
F2i = F2n+1 − 1
(5 points) Use the division algorithm to express the number 500 in base 7.
(10 points) Let a = 232 and b = 144.
(a) Use The Euclidean Algorithm to find gcd(a, b).
(b) Find integers x and y so that: gcd(a, b) = ax + by
(10 points) Construct counter-examples to the following implications:
(a) If A ∪ C = B ∪ C then A = B
(b) If A ∩ C = B ∩ C then A = B
(5 points) Prove: For all a, b, c ∈ Z, [(a|b) ∧ (b|c))] ⇒ a|c.
(5 points) Prove: For all a, b ∈ Z, [(a|b) ∧ (b|a))] ⇒ a = ±b.