1
$\begingroup$

We prove a lot of statements by contradiction.

  1. We got a statement.
  2. Then suppose its negation.
  3. Derive a contradiction

But what if instead of deriving contradiction I just show a case where the negation fails to be true. Will it mean that the statement is true? Because it seems to me like a cheating. For motivational example suppose our statement is "Square of an even number is also even".

We could prove it by contradiction, showing the square of $2m$ is divisible by $2$ that is why it is a contradiction.

But what about showing a simple case to disprove the negation?

Suppose it is false, i.e. the square number is odd. Let $a=2$. Then square is $2^2 = 4$. But 4 is not odd, since it is divisible by 2. Then the statement is true.

It is like thinking of the negation as a new statement. And we can disprove any statement by showing a case where it fails to be true. Is it acceptable? As I said, I think of this more as a cheating, because showing a contradiction is more general unlike showing a case.

$\endgroup$
  • 1
    $\begingroup$ "But what if instead of deriving contradiction I just show a case where the negation fails to be true. Will it mean that the statement is true?" No. You proved the negation is not always true. That doesn't mean the negation is always false. And the means the statement is sometimes true. It doesn't mean it is always true. $\endgroup$ – fleablood Jan 3 '18 at 3:45
  • $\begingroup$ "Suppose it is false, i.e. the square number is odd. " No. The negation is that it can be odd. Not that it is always odd. "But 4 is not odd... Then the statement is true". No. It is only true for $a = 2$. It might be false for some different even number. To prove it by contradiction: the negation is "some even a, has an odd square". Let $a$ be that even number so $a$ is even and $a^2$ is odd. So $a = 2k$ for some $k$ and $a^2 = 2j + 1$ for some $j$ and so $(2k)^2 = 2j + 1$. You must prove that is a contradiction. .... $\endgroup$ – fleablood Jan 3 '18 at 3:51
  • $\begingroup$ ... $(2k)^2=4k^2 = 2j + 1$ so $4k^2 -1 = 2j$ so $2k^2 - \frac 12 = j$ but $2k^2$ is an integr and $\frac 12 $ is not so $j = 2k^2 - \frac 12$ is not an integer. THAT is the contradiction. That proves that an even number having an odd square can't ever happen. But that's a really hard way of doing it. $\endgroup$ – fleablood Jan 3 '18 at 3:54
2
$\begingroup$

No, your "logic" doesn't work at all. Starting with the square number is odd: whose square? In fact, the issues start even earlier: you said that you plan to disprove the negation, but you didn't state that negation, so I'm afraid you don't actually know what you're trying to disprove.

First of all, you need to understand the original statement: "Square of an even number is also even". Is it talking about a particular even number or about an arbitrary even number? Once you realize that this is a statement about an arbitrary number, you should realize that this is actually a "for all" kind of statement. A more precise formulation of this statement is:

$$\forall n\in\mathbb{Z}: n \text{ is even} \implies n^2 \text{ is even.}$$

Then how do we construct negations of "for all" statements? The negation of $\color{blue}{\forall x\,(P(x))}$ is $\color{red}{\exists x\,(\neg P(x))}$. This is where your "logic" fails. By finding an example that holds true you demonstrate that $\color{magenta}{\exists x\,(P(x))}$, which does NOT disprove $\color{red}{\exists x\,(\neg P(x))}$: both $\color{magenta}{\exists x\,(P(x))}$ and $\color{red}{\exists x\,(\neg P(x))}$ can be true simultaneously.

I'll help you out with your example: its negation that you would use for a proof by contradiction would be

$$\exists n\in\mathbb{Z}: n \text{ is even} \wedge n^2 \text{ is odd.}$$

That's what you are presumably trying to disprove. Disproving a "there exists" statement is equivalent to proving that for all $n$ the new statement is false, so we're back to proving the original one. Thar's why this wasn't a good example: it's easy enough to prove "Square of an even number is also even" directly rather than by contradiction.


Informally, in plain words: by finding a case where the negation fails to be true, you find a case where the original statement is true. But your goal is to show that the original statement is true for all cases. Does presenting a single case achieve that goal?

$\endgroup$
2
$\begingroup$

Let's use your example to figure out what is going on. When proving a statement $P$ via contradiction, what you are showing is that it is necessarily true that $\lnot P$ is false, therefore $P$ is necessarily true. What that would correspond to here is showing it is necessarily false that the square of an even number is odd.

When you are merely showing a counterexample to the negation, what you are showing is that it is not necessarily true that $\lnot P$ is true. But this is not the same thing as what a proof by contradiction usually attempts to show. The fact that the square of 2 is even does not show that the square of any even number is necessarily even, merely that the square of any even number is not necessarily odd. That's why this is not sufficient.

To put it another way, the negation of "the square of an even number is even" is not "the square of an even number is odd," simply that "it is not always the case that the square of an even number is even." Your counterexample only has bearing on the former, not the latter.

$\endgroup$
1
$\begingroup$

To prove a statement is ALWAYS true, and to prove it by contradiction you must assume the negation. The negation is the statement is SOMETIMES false. Then you get a contradiction. So you must prove the statement is NEVER false.

You can't prove something is NEVER false but showing only one example where it happens to be false.

Example:

Statement 1: An even $a$ will ALWAYS have an even $a^2$.

Statement 2: A person who is a girl, will ALWAYS love chocolate

Negation 1: An even $a$ will SOMETIMES have an odd $a^2$.

Negation 2: A person who is a girl, will SOMETIMES dislike chocolate.

Attempt a contradiction:

Method 1: Take an example.

Let $a = 2$... as an example. Pick that girl, Charlene... as an example.

$a^2 = 4$. That's interesting. "Hey, Charlene! Do you like chocolate?" "Yes, I love chocolate".

$4$ isn't odd so I guess it is always true that $a^2$ will be even for all $a$. And Charlene doesn't dislike chocolate. So I guess it is true that all girls like chocolate.

I hope you can see what is wrong with that reasoning.

To show that a negation is SOMETIMES false leads to a contradiction, I must show that if ever an even $a$, and I don't know which even $a$ it is, has an odd $a^2$ that that leads to a contradiction.

So I say if $a^2$ is odd then $2$ does not divide $a^2$. And if $2$ does not divide $a^2$ then $4$ does not divide $a^2$. If $2$ divides $a$ then $4$ divides $a^2$. But I just showed it didn't. So $2$ does not divide $a$. So $a$ is not even. That's a contradiction.

To do that with the girls and chocolate statement I must say, suppose there is a girl $c$ (I don't know which one) who likes chocolate. I must prove that the leads to a contradiction. (Which I don't think is possible. Nothing about liking chocolate can force a person into not being a girl.)

$\endgroup$
1
$\begingroup$

Negation

I think, it is valuable to look at the definition of negation before considering the particular question of implications of falsification of it. According to wikipedia:

Classical negation is an operation on one logical value, typically the value of a proposition, that produces a value of true when its operand is false and a value of false when its operand is true. So, if statement A is true, then ¬A (pronounced "not A") would therefore be false; and conversely, if ¬A is false, then A would be true.

This gives us a viable criteria to determine when a statement $A$ is negation of statement $B$.

Consider checking if the statement (I think it will help pin down the statment precisely) you are considering the negation of statement "Square of even number is even" satisfies the definition. Also note that, definition justifies that if $\neg S$ is negation of $S$, then

$$\neg S \ is \ True \Rightarrow S \ is \ false$$ and $$\neg S \ is \ False \Rightarrow S \ is \ True.$$

Your case

Consider a statement defined over some set $A$ which is about some property $p$ $$S=\forall x \in A \ p(x) \ is \ True.$$ Negation of $S$ is following expression(Note that: $$\neg S=\exists x, p(x) \ is \ False. $$

Note that in order to show that negation is false, one needs to show that, $$\forall x \in A, p(x) \ is \ True.$$

Hence, giving an example of $x$ does not help, as it may well be the case that, there exists such an $x$ for which $\neg S$ is $True$.

Another Case

Note that if any statement is of the form $$S=\exists x, p(x) \ is \ True$$, then negation $$\neg S=\forall x \in A, p(x) \ is \ False.$$ Here, your argument will be correct. You do not even need the negation to prove $S$ if you know such $x$ which is an counter-example for $\neg S$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.