Need of hypothesis and counter-example

Question

I have a theorem in the form : if A is verified and B is verified and C is verified then D is verified. I'd like to show that we can't do without hypothesis C. How can I do this? Do I need to find an example where I have A, B and non(C) which are verified such that D is unverified? If I do this, what will I have shown?

Answer 1

Let's say that

$$ A ∧ B ∧ C → D $$

That "you can't do without hypothesis $C$" is to say also that $\neg(A\land B\land \neg C → D)$.

So if you prove both these two things you'd have what you want but, what is that counterexample thing?

If you suppose your formulas $A$, $B$, $C$ and $D$ depend on some variable and your formula is actually of the form

$$∀x.\ A(x) ∧ B(x) ∧ C(x) → D(x)$$

then that "you can't do without hypothesis $C$" actually becomes $\neg\big(∀x.\ A(x)∧B(x)∧\neg C(x)→ D(x)\big)$ which by de Morgan's law ends up as

$$\exists x.\ \big(A(x) ∨ B(x) ∨ \neg C(x)\big) ∧ \neg D(x)$$

This is to say that you only need to find one candidate for the negation of the original formula, a counterexample.

---

It can also be said that "you can't do without hypothesis $C$" should be interpreted as $\neg(A\land B → D)$ instead, and the end result with quantifiers would be

$$∃x.\ \big(A(x)∨B(x)\big)\land\neg D(x)$$

So here what you are doing is not assuming $C$ instead of assuming its negation.

Notice that this implies the first one, and is more natural in my opinion, so if you can actually prove this instead, it would be better.

---

Let me know in a comment if this doesn't quite answer your question.

Cheers!