Important! These are all exam-level problems. Do not attempt these problems without a solid foundation in the subject and use them for exam practice.
1. Suppose P(k) ---> P(k+2)
Answer A for always true, N for never true, or C for can be true.
a. P(0) =⇒ ∀n P(n+2)
b. P(n) =⇒ [∃m > n s.t P(m)]
c. (∀n ≤ 10, P(n))∧(∀n > 10 , ¬P(n))
d. ∃n∃m > n s.t [P(2n)∧ ¬P(2m)]
e. P(0) =⇒ ∀n P(n+1)
a. C
b. A
c. N
d. N
e. C 2. True or False: (∀n ∈ N)(P(n) =⇒ Q(n)) =⇒ (¬∃n ∈ N)(Q(n) =⇒ ¬P(n)) for all P,Q? Explain.
False, suppose P(n) and Q(n) are both false for all n. 3. True or False: ∀x (P(x)∧Q(x)) is equivalent to (∀x,P(x))∧(∀x,Q(x)). Explain.
True. Recall that to prove A ⇔ B, we have to prove both A ⇒ B and B ⇒ A.
Suppose the first statement ∀x (P(x)∧ Q(x)) is true. This means for all x, P(x)∧ Q(x) is true, so P(x)
and Q(x) are both true. Thus, the statement (∀x, P(x)) is true, and similarly the statement (∀x, Q(x)) is
true, so the conjunction (∀x,P(x))∧(∀x,Q(x)) is true.
Conversely, suppose the second statement (∀x,P(x))∧(∀x,Q(x)) is true. This means for all x, both P(x)
is true and Q(x) is true, which implies P(x)∧ Q(x) is true. Thus, the first statement ∀x (P(x)∧ Q(x)) is
true. This completes the proof of the equivalence