Description
Problem 1 (10+1 points)
Using the WOP, prove that for any positive integer n, 3
n+2 + 24n+2 is divisible by 13.
Problem 2 (35+4 points)
Consider the following sets:
A =
1
2
−
1
2
k
: k is a positive integer
B =
1
2
+
1
2
k
: k is a positive integer
.
(a) (10+1 points) Prove or disprove that A is well-ordered.
(b) (10+1 points) Prove or disprove that B is well-ordered.
(c) (10+1 points) Prove that A satisfies the following property: for any real number x such
that 0 < x < 1 2 and any positive integer n, there exist n distinct elements of A that are all greater than x. In other words, A contains decreasing sequences that are arbitrarily long. (d) (5+1 points) Does A contain an infinite decreasing sequence? Justify your answer. Problem 3 (14+1 points) Consider the operator ⊕ defined so that P ⊕ Q is TRUE if P and Q have different truth values, and FALSE otherwise. Prove or disprove each of the following. (a) (3 points) ⊕ is associative. (b) (3 points) ⊕ is commutative. (c) (3 points) ⊕ is idempotent. (d) (5 points) P ⊕ Q ↔ ¬(Q → P) ∨ (P ∧ ¬Q). Problem 4 (15+1 points) Consider the operator # defined so that P #Q is TRUE if and only if P is FALSE and Q is TRUE. For each of the following expressions, give an equivalent expression which uses only the # and ¬ operators. That is, your expression should have only P, Q, ¬, #, and parentheses (where each can be used any number of times). (a) (5 points) P ∧ Q. (b) (5 points) P ∨ Q. (c) (5 points) P → Q.