John Landry

2022-07-15

For each of the following cases, is
$\forall k\in \mathbb{N}\phantom{\rule{thickmathspace}{0ex}}\left(P\left(k\right)\phantom{\rule{thickmathspace}{0ex}}⟹\phantom{\rule{thickmathspace}{0ex}}P\left(2k\right)\right)$
true, false or dependent on the value of P(k)?
a) $\forall n\in \mathbb{N}\phantom{\rule{thickmathspace}{0ex}}P\left(n\right),$
b) $P\left(0\right)\wedge P\left(1\right),$
c) $\forall n\in \mathbb{N}\phantom{\rule{thickmathspace}{0ex}}P\left(2n\right).$

Raul Garrett

Expert

Step 1
First, notice that the sentence
$A\to B$
is true whenever B is true. We use this fact in parts (a) and (c) below.
$\begin{array}{}\text{(#)}& \forall k\in N\phantom{\rule{thickmathspace}{0ex}}\left(P\left(k\right)\phantom{\rule{thickmathspace}{0ex}}⟹\phantom{\rule{thickmathspace}{0ex}}P\left(2k\right)\right)\end{array}$
a) $\forall n\in N\phantom{\rule{thickmathspace}{0ex}}P\left(n\right)$
a) true (because for any natural number n, P(n) is true so P(2n) will also be true
Yes, the given statement (a) tells us that P(2k) is true regardless of quantification; thus, so is $P\left(k\right)\phantom{\rule{thickmathspace}{0ex}}⟹\phantom{\rule{thickmathspace}{0ex}}P\left(2k\right);$; thus, (#) is true.
b) $P\left(0\right)\wedge P\left(1\right)$
b) true
Step 2
No. Here are two possibilities that are consistent with the given statement (b):
- statement (a) is true, in which case (#) is true,
- P(2) is false, in which case (#) is false.
Thus, we have insufficient information to conclude whether (#) is true or false.
c) $\forall n\in N\phantom{\rule{thickmathspace}{0ex}}P\left(2n\right)$
c) true
Yes, the given statement (c) tells us that $P\left(k\right)\phantom{\rule{thickmathspace}{0ex}}⟹\phantom{\rule{thickmathspace}{0ex}}P\left(2k\right)$ is true regardless of quantification; thus, (#) is true.

Do you have a similar question?