0

Let's say I have a predicate, $\forall x\in h(x) : f(x) \leftrightarrow h(x) \lor g(x)$

I understand that when Q $\implies$ P that we do cases and assume both h(x) and g(x) in each case, however when it is P $\implies$ Q I'm not sure if I should break it into cases, as we cannot assume h(x) or g(x).

user322058
  • 1

1 Answers1

0

Prove: $\forall x\in h(x) : f(x) \leftrightarrow h(x) \lor g(x)$

$\Leftarrow:$   Yes, proof by cases is used here.

  • Case 1: By assuming $h(x)$ holds for any $x$, we must show $f(x)$ must hold too.
  • Case 2: By assuming $g(x)$ holds for any $x$, we must show $f(x)$ must hold too.

$\Rightarrow:$   Here, by assuming $f(x)$ holds for some arbitrary $x$, we must show that at least one of either $g(x)$ or $h(x)$ holds (that it is impossible for both to not hold when the assumption does).   Proof by cases thus requires extra assumptions.

  • Case 1: By assuming $f(x)$ holds but not $g(x)$, show that $h(x)$ must hold.

  • Case 2: By assuming $f(x)$ holds but not $h(x)$, show that $g(x)$ must hold.

    Alternatively, you can demonstrate that whenever $h(x)$ and $g(x)$ both do not hold, then $f(x)$ cannot either.   (That is: proof by contradiction).

Graham Kemp
  • 129,094
  • 1
    The 2nd case breakdown can be done a bit more cleanly like this: Assume $f(x)$ holds. If $g(x)$ holds, we are done. If not, then additionally assume that $g(x)$ does not hold and show that $h(x)$ must hold. – Justin Benfield Mar 12 '16 at 08:33
  • @JustinBenfield Yes, that works too. A demonstration of $f(x)~\to~\Big(~g(x)~\vee~\big(\neg g(x)\wedge h(x)\big)~\Big)$ is enough. – Graham Kemp Mar 12 '16 at 10:49