Discrete Math: CS70, prepositions

Question

For each of the following cases, is $$∀k \in \mathbb{N} \;\big(P(k) {\implies} P(2k)\big)$$ true, false or dependent on the value of $P(k)\,?$

a) $∀n \in \mathbb{N} \;P(n),$

b) $P(0) ∧ P(1),$

c) $∀n \in \mathbb{N} \;P(2n).$

My answers are:

a)true (because for any natural number $n,$ $P(n)$ is true so $P(2n)$ will also be true,

b)true,

c)true.

But I don't know if they are right or wrong. I don't really understand the question.

Answer 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.

$$∀k{∈}N \;\big(P(k) {\implies} P(2k)\big)\tag#$$

a) $∀n{∈}N \;P(n)$

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(k) {\implies} P(2k);$ thus, $(\#)$ is true.

b) $P(0) ∧ P(1)$

b)true

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) $∀n{∈}N \;P(2n)$

c)true

Yes, the given statement (c) tells us that $P(k) {\implies} P(2k)$ is true regardless of quantification; thus, $(\#)$ is true.