1
$\begingroup$

This may be super random, but I will use a question from calculus, but this is pure logic question.

I am trying to understand what is wrong with this way of thinking about proofs using assuming the opposite and then getting a contradiction.

Given this task: Prove that

$$ \limsup (a_n + b_n) \leq \limsup a_n + \limsup b_n \tag{1}$$

Why can't I say:
Assuming that $$\limsup (a_n + b_n) > \limsup a_n + \limsup b_n \tag{2}$$

And then giving a counter-example - thus proving (1).

This probably does not tell me right away that $\text{(1)}$ is correct, but logically I don't find it any different than other "assuming that P(x) is wrong then we get to a contradiction thus P(x) must be right because of the law of excluded middle (tertium non datur) "

Where do I get things wrong here?

$\endgroup$
5
  • 2
    $\begingroup$ Before (1) you should say "For all sequences $a_n,b_n$ such that...". Before (2) this becomes "There exist sequences $a_n,b_n$ such that ...". This is because "For all" and "There exist" switch when you take negation. Now what exactly do you mean by a counterexample to something existing? You could give an example of a sequence where (2) fails, but that does not mean one could not exist where it holds. $\endgroup$
    – tkf
    Commented Nov 10, 2020 at 0:11
  • 2
    $\begingroup$ @tkf oh, so you are saying (2) is not that "for all" but "exists" and to counter example "exists" we need to iterate over each possibility... (analogy to disprove "forall" by finding only one counter example) $\endgroup$
    – CSch of x
    Commented Nov 10, 2020 at 0:13
  • 1
    $\begingroup$ Exactly. That is right. $\endgroup$
    – tkf
    Commented Nov 10, 2020 at 0:14
  • 1
    $\begingroup$ @tkf You should turn your comments into an answer. (I posted mine before I saw your comments.) $\endgroup$ Commented Nov 10, 2020 at 0:18
  • 1
    $\begingroup$ @NoahSchweber It's fine - you explained the point (+1). $\endgroup$
    – tkf
    Commented Nov 10, 2020 at 0:28

1 Answer 1

4
$\begingroup$

The issue is quantifiers.

The original statement has an implicit universal quantifier: it would be better phrased as "Every pair of sequences $(a_i),(b_i)$ has property [stuff]." The negation of this involves an existential quantifier: "There is a pair of sequences $(a_i),(b_i)$ without property [stuff]." When we negate, universals turn into existentials (and vice versa).

So in the OP, you've successfully proved that your statement $(2)$ (which also carries an implicit universal quantifier) is false. But your statement $(2)$ is not the negation of statement $(1)$ - it's a much stronger statement, so disproving it doesn't finish your problem.

This is something natural language unfortunately makes rather annoying: in my experience, the biggest confusion students have with proving complicated expressions is keeping track of quantifier structure. The OP gives an example of how the type of quantifier (universal or existential) can be obscured by the natural language phrasing, but there are other subtleties to keep an eye out for, especially order of quantifiers (to see that order matters, consider "For all $x$ there is some $y$ such that $x<y$" versus "There is some $y$ such that for all $x$ we have $x<y$").

$\endgroup$
1
  • $\begingroup$ Reminder for myself: we need to pay attention to the quantifiers hiding in the meta-language, thank you sir! $\endgroup$
    – CSch of x
    Commented Nov 10, 2020 at 0:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .