(A new question of the week)
Last week we looked at a recent question about an attempt to write a proof using the contrapositive, which was foiled by difficulty in negating a statement. Two weeks later, we had another question about the same sort of issue, but with a different problem in the negation. In both cases the proof by contradiction was easier!
A question and two answers
Here is the question, from June:
I have to prove an important lemma in the proof of uniqueness of the limit of a sequence:
If for all e > 0, |x| < e, then x = 0.
There are two methods, contradiction and contrapositive.
I know the method of contradiction.
Let x ≠ 0, then |x| > 0. Then consider |x|/2 = e (we can because we want any e > 0).
But then it means |x| < e = |x|/2.
This contradiction occurred due to assumption x ≠ 0, which must be false.
Therefore it must be true that x = 0.
Can anybody tell how to prove the same using contrapositive?
The idea of contrapositive is that to prove a ⇒ b, we can prove not b ⇒ not a.
By the symbol “⇒” I mean implies.
But I am unable to use the idea.
The statement Rahul wants to prove is, in effect, that if the absolute value of x is less than any positive number, then it must be zero. (This seems obvious, but still has to be proved! That’s what makes it a “lemma”, a small theorem used in a larger proof.)
His proof by contradiction assumes the premise to be true but the conclusion false, and finds a contradiction. He does this by choosing a particular positive number e that is less than x, which exists if the premise (about any e) is true.
Now he wants to prove it using the contrapositive, just as we saw last week.
The contrapositive is like the contradiction
Doctor Fenton replied:
Hi Rahul,
I think this is primarily a matter of interpretation. The logical steps in the proof are essentially the same for the argument by contradiction and the contrapositive. If you are using contradiction to prove p → q, you assume p ^ ~q, i.e. that p is true and q is false and derive a contradiction. To use a contrapositive argument, you assume ~q and logically derive ~p, i.e. you show (~q) → (~p).
In this case, p is “for every e > 0, |x| < e” and q is “x = 0″, so ~q is ” x ≠ 0″. The properties of the absolute value function show that |x| = 0 if and only if x = 0, and that |x| ≠ 0 if and only if |x| > 0. Then ~q ↔ (|x| > 0). Also, if a is any positive real number, then a/2 < a, so that if x ≠ 0, then there exists a positive real number e (e.g. e = |x|/2) such that |x| < e is false. This shows that ~q → (there is an e >0 such that |x| < e is false), and the statement (there is an e > 0 such that |x| < e is false) is the negation of (for every e > 0, |x| < e). Then ~p is a logical consequence of ~q, i.e. ~q → ~p. That itself is a contrapositive argument. But then p ^ ~q → p ^ ~p which is a contradiction. That is, I would argue that you use a contrapositive argument to obtain the contradiction.
As you see in the first paragraph, in both methods you assume ~q to be true, but in contradiction you also assume p and show that this can’t be true, while in contraposition you just derive ~p from it. So you can often obtain a contrapositive argument by just twisting a contradiction argument a little. That’s what he’s doing in the second paragraph.
More on indirect proofs
I saw two things to add to this:
Hi again, Rahul.
I’ll just add a couple things to what Doctor Fenton has said, which I agree with.
First, I checked for any help on these ideas in Ask Dr. Math and found this example comparing the two methods:
There may be nothing there you don’t already know.
That page tries three methods to prove “If \(x^2 = 2\), then x is not a rational number”, trying a direct proof and a contrapositive proof (which he leaves unfinished), and then completing the proof by contradiction. It gives a nice explanation of the thinking behind it all – and concludes that the contradiction is easier.
Finding the negation
The main thing I’d observed was that the negation, as in last week’s example, is commonly the hardest part of a contrapositive to work out, so a focus on that might be useful:
Second, you didn’t say where you got stuck trying to use the contrapositive, but probably the hardest part here is to recognize the negations. So I would personally start there, writing out what “~p” is, in order to know what to be looking for in a proof (and to recognize it when I get there).
Here, p is “for all e > 0, |x| < e”; as Doctor Fenton pointed out, ~p is “there exists e > 0, |x| ≥ e”. That is, the negation of “|x| < e is always true” is “|x| < e is sometimes false“. So I’d be trying to find such an e.
We don’t have a lot on negating quantifiers, but here is a page that touches on it (at the end of the first answer):
A False Statement Implies Any Statement
There’s more in this blog post:
Negating Logic Statements: How to Say “Not”
Be sure to let us know if there is a piece of this we need to explain more.
Where I said, “I’d be trying to find such an e”, you may recognize that this was the key to the contradiction proof, too! So Rahul had done this part of the work already, but likely was having trouble seeing where it would come into play.
Quantifiers and negation
The first link is worth quoting here; this is “the end of the first answer”, which was just about what quantifiers are:
As for the "Quantifiers" part of your question, notice the similarity to the word "Quantity," which means "how many." Logic is not usually interested in specific quantities like "113" or "several dozen". The important quantities to concentrate on are ALL and SOME :
1. ALL, which usually involves sentences starting out like "For all" or "For every," or which could be written that way. Consider the sentence "Every police officer wears a badge." You could also say, "For every police officer, that officer wears a badge." In symbols, that could come out "For every police officer P, B(P)" where I am using B(P) to stand for P wears a badge. By the way, the sentence we are talking about is probably false, because of undercover detectives and the like.
It's sort of a predictable thing that whenever a mathematician or logician is turned loose without much supervision, very soon some symbolism is introduced (grin). Like, how many times have you heard a math teacher start working on a word problem by saying "Let X be the unknown"!
2. SOME, which usually involves sentences starting out like "For some" or "There exists a," or which could be written that way. Consider the sentence "Some police officer enjoys listening to Mozart." You could also say, "There exists a police officer, such that that officer enjoys Mozart." In symbols again, "There exists a police officer P such that M(P)" where I am using M(P) to stand for P enjoys Mozart.
The ALL-type phrases are called Universal Quantifiers because they are claiming something is true for all things in a certain collection (or universe) of things, as all the police in Brooklyn, or all flute players studying at the Eastman School of Music.
The SOME-type phrases are called Existential Quantifiers because they are claiming that something exists within a group, such as a course in Japanese among the offerings at your local High School.
One more thing. When you negate (say "It is false that ...) any Universally quantified sentence, you get an Existentially quantified sentence, and vice versa. An example. Saying that "All police wear badges" is False, is the same as saying "Some police do NOT wear badges" is True.
The last paragraph is what I was specifically referring to. Our p is like “All police wear badges”.
The part of the blog post on “Negating quantifiers” includes explicit rules for these negations.
A first attempt at the contrapositive
Rahul replied to my comments; my guess was right:
Thanks for the help.
I went through all the links you suggested and understood the content.
Let me write what I have understood about the contrapositive in the original question.
As pointed out both (P ⇒ Q) and (not Q ⇒ not P) are logically equivalent.
So P is “for all e > 0, |x| < e”, and Q is “x = 0”.
So not Q is “x ≠ 0”, and not P is “there exists an e > 0 such that |x| ≥ e” (why not e < 0 is another question).
As you correctly pointed out, “probably the hardest part here is to recognize the negations”.
He’s got the correct negation of p; I’ll be answering the side question I bolded there. He continued,
Going forward,
We assume (not Q) that x ≠ 0. So we know that |x| > 0.
So if e > 0 then |x| ≥ e.
Why? because |x| and e both are > 0, so either |x| > e > 0 or |x| = e > 0.
Am I right? Because in the statement above (“So if e > 0 then |x| ≥ e”), I assumed e > 0 from nowhere in the not Q statement.
Clarifying the negative
He rightly questions his work. I first dealt with the question about e < 0, and then the attempted proof:
I have a couple comments.
First, you said,
So not Q is “x ≠ 0”, and not P is “there exists an e > 0 such that |x| ≥ e” (why not e < 0 is another question).
We are negating the statement, “for all e > 0, |x| < e“. This is a statement about what is true when e > 0; it says nothing about the case that e < 0. So its negation likewise will not say anything about what is true or false when e < 0. (If I say that all Americans have red hair, then if you want to call me wrong, you won’t say something about the French, whom I said nothing about, but rather about an American you know with black hair.)
Again, the positive statement says, “|x| is less than any positive number“; its negation says, no, there is some positive number that |x| is not less than.
An alternative way to think about this “for all” statement is as a conditional statement: if e > 0, then |x| < e. The negation of this statement is not “if e < 0 …”. We want a statement that says, “it is not true that if e > 0, then |x| < e”. The negation of a conditional statement p → q (which is equivalent to ¬p ∨ q) is p ∧ ¬q, so our negation is “e > 0 and |x| ≥ e”. That is, “e is positive but |x| is not less than e”. Again, this says nothing about the case where e < 0. The negation of a conditional statement is a counterexample: it is possible for p to be true but q is not.
Many of the things I said here echo things that Doctor Fenton said in his initial answer; they just needed to be said slowly and repeatedly in order to make sense. There is a lot here for a student to be learning! To repeat yet again, the negation of “for all x, p” is “for some x, not p“; and the negation of “if p then q” is “p but not q“.
Fixing the logic
Second, you said,
So if e > 0 then |x| ≥ e.
Why? because |x| and e both are > 0, so either |x| > e > 0 or |x| = e > 0.
Am I right? Because in the statement above (So if e > 0 then |x| ≥ e), I assumed e > 0 from nowhere in the not Q statement.
No, I don’t think that works. Remember that what we want to conclude is that “there exists some e > 0, such that |x| ≥ e”. So we are not making a statement about every e; we just need to find a counterexample. So we can choose e = |x|/2, or |x|/3, or 99|x|/100, or whatever we like that we know is less than |x|! But the existence of this choice is the key to the proof.
Does that help at all?
He was still talking about all positive e, and got tangled up, because there were too many possibilities. All he needs is one value of e. The negation of a universal quantifier is an existential quantifier.
Closure
Rahul was satisfied:
Yes sir it clearly helped.
“If I say that all Americans have red hair, then if you want to call me wrong, you won’t say something about the French, whom I said nothing about, but rather about an American you know with black hair.”
The above explanation made clear why negation works like it does.
So understood it very well that we want to conclude is that “there exists some e > 0″ and find counter example.
Thank you very much to all.
Regards,
Rahul.
The two proofs on display
To finish this off, we need an adequate proof. I’ll just take what Doctor Fenton said, remove some of the commentary and spread it out a bit to make it easier to see, while expressing it as an actual proof:
To prove: If for all e > 0, |x| < e, then x = 0.
We will prove the contrapositive, namely,
If x ≠ 0, then there exists e > 0 such that |x| ≥ e.
The properties of the absolute value function show that |x| = 0 if and only if x = 0, and that |x| ≠ 0 if and only if |x| > 0.
Also, if a is any positive real number, then a/2 < a, so that if x ≠ 0, then there exists a positive real number e (e.g. e = |x|/2) such that |x| < e is false, that is, |x| ≥ e.
This confirms the contrapositive, which is equivalent to the statement to be proved.
Do you see how similar this is to Rahul’s own proof by contradiction? Here is it, put into a similar form:
To prove: If for all e > 0, |x| < e, then x = 0.
Suppose that for all e > 0, |x| < e.
For the sake of contradiction, suppose that x ≠ 0. Then |x| > 0.
Now consider e = |x|/2; then e > 0, satisfying the condition.
But then |x| < e = |x|/2, which is not true.
This contradiction occurred due to the assumption that x ≠ 0, which must be false.
Therefore it must be true that x = 0.
They are almost the same proof. The hard part of the proof by contrapositive was seeing what the contrapositive is!