1

I'm trying to prove something by negation, and was wondering.

For all statements, if their negation can be shown to be false (under one or more circumstances) then is the original statement guaranteed to be true? Or does the negation have to be a contradiction?

Howard P
  • 409
  • 4
  • 16
  • Take a look at the Law of the Excluded Middle https://en.wikipedia.org/wiki/Law_of_excluded_middle. It states that a statement or its negation must be true. – The Turtle Mar 01 '17 at 21:57
  • I'm aware of this law, but the negation I'm working with is true in some cases, and false in other. – Howard P Mar 01 '17 at 22:00
  • 1
    To disprove a universal statement $\forall x P(x)$ (meant to apply to every x), then if you have found even a single counterexample for which there exists an x in the domain for which $\lnot P(x)$, then the universal statement is false. – amWhy Mar 01 '17 at 22:08
  • Thank you for the distinction between a statement and a universal statement, that helps very much! – Howard P Mar 01 '17 at 22:36
  • Howard, Note also that $$\exists x(\lnot P(x))\equiv \lnot \forall x(P(x))$$ – amWhy Mar 01 '17 at 22:45

2 Answers2

1

Suppose you want to prove $p\rightarrow q$. Then, If you assume NOT q, and can derive NOT p, then you will have proven $$\lnot q\rightarrow \lnot p \equiv p\to q$$ That's basically proving a statement by proving its contrapostive.

Now, suppose you want to prove $p\to q$. Now, the only way an implication is false is if $p$ is true and $q$ is false. So, if you assume $p$ is true, and also assume $q$ is false $(\lnot q)$, and you are able arrive at any contradiction whatsoever, you will have proven that then we must have conclude the assumption $\lnot q$ was false, and hence, we have $p\to q$.

amWhy
  • 209,954
1

Consider the statement, "everybody in that room likes ice cream." Suppose it is false. Its negation is "somebody in that room doesn't like ice cream." This is going to be true, but you cannot draw the conclusion that "nobody in that room likes ice cream" without further evidence.

What I'm getting at is that if "the negation is true in some cases, and false in others" you are probably looking at a sentence of the form

$$ \forall x \,.\, P(x) \enspace, $$

whose negation is

$$ \neg \forall x\,.\, P(x), ~~\text{ equivalent to }~~\exists x \,.\, \neg P(x) \enspace, $$

which in turn is quite different from

$$ \forall x \,.\, \neg P(x) \enspace, $$

though in some cases they may be both true (or both false).

Fabio Somenzi
  • 7,676