2

I am currently trying to prove a statement that has the following form: $(Q(X)$ or $R(X)) \implies P(X)$. I usually start by taking $Q(X)$ or $R(X)$ as hypothesis; this means that $Q(X)$ is the case, or that $R(X)$ is the case, or that both are the case.

So I proceed as follows:

  • If $Q(X)$ is the case then ...
  • If $R(X)$ is the case then ...

Now, my proof is by induction over $X$, and in one case my induction hypothesis implies that $R(X)$ is the case. However, without assuming $Q(X)$ I can't prove what I'm after.

Can I also assume $Q(X)$? The thing is, since $R(X)$ is implied, my hypothesis $(Q(X)$ or $R(X))$ is already satisfied.

Alistair -L.
  • 163
  • 4
  • 1
    As a side remark: in cases like these, it often is easier to prove the transpose statement: $A\Rightarrow B$ is logically equivalent to $\neg B\Rightarrow\neg A$. In this case, that would mean: $\neg P(X)\Rightarrow \neg (Q(X)\text{ or }R(X))$, which in turn is the same as $\neg P(X) \Rightarrow \neg Q(X)\text{ and }\neg R(X)$. – HSN Sep 18 '13 at 16:00

1 Answers1

0

I assume you mean that you need the induction hypothesis for both statements, and in that case you can assume that without problems, that Q and R individually imply P on all smaller cases. If Q(X) can be reduced to either an application of the hypothesis on either Q(X') or R(X') for a smaller case X' then there is no problem. Just make sure you have the base case for both proved too.

To clarify: let $X=n$ be a positive integer for simplicity here, the statement being proved is that $Q(n) $ or $ R(n) \implies P(n)$

The induction hypothesis should be that for any $k<n$, $Q(k)$ or $R(k) \implies P(k)$.

Now assume just $Q(n)$. You are allowed to use the fact that $Q(k)$ implies $P(k)$ and $R(k)$ implies $P(k)$ in your quest to show $P(n)$. That is all I am saying. Then once you have done that, you do the same but just assuming $Q(n)$ and trying to deduce $P(n)$.

If you assume both $Q(n)$ and $R(n)$ simultaneously then you are not proving the same statement anymore.

Evan
  • 3,861
  • Are you sure you can assume that $Q$ and $R$ imply $P$ in the induction? It seems to me like you can only know that when you get to the part that the hypothesis should be able to handle, you can only assume that one of $Q(X')$ or $R(X')$ holds, but cannot know which one. – Eric Stucky Sep 18 '13 at 15:03
  • To be clear, I'm not able to show $P(X)$ with just $R(X)$ in that particular inductive case. $R(X)$ comes for free by the induction hypothesis, but $R(X)$ is not good enough for me. However, If I add the $Q(X)$ hypothesis all is good. – Alistair -L. Sep 18 '13 at 15:10
  • @Alistair see clarification but it seems if I understand you correctly the answer is no. But HSN's comment may be helpful. Could you also just for concreteness tell us what it is you are trying to prove? (and request no full solutions be given if you don't want anything spoiled) – Evan Sep 18 '13 at 16:05
  • @EricStucky maybe it is clearer now, I realize there may have been some ambiguous wording – Evan Sep 18 '13 at 16:06