4

So, in his analysis book in appendix for logic he gives a proof that

if $n$ is a an integer, then $n(n+1)$ is an even integer.($Theorem A.2.4.$)

Since $n$ is an integer, $n$ is even or odd. If $n$ is even, then... . If $n$ is odd, then... . Thus in either case $n(n+1)$ is even, and we are done.

Note that this proof relies on two implications: "If $n$ is even, then $n(n+1)$ is even" and "If $n$ is odd, then $n(n+1)$ is even". Since $n$ cannot be both odd and even, at least one of these implications has a false hypothesis and is therefore vacuous.

After that he shows a corollary of this theorem with some big $N$.

Let $n = (253+142)*123 - (423+198)^{342} + 538 - 213$. Then $n(n+1)$ is an even integer.

In this particular case, one can work out exactly which parity $n$ is - even or odd - and then use only one of the two implications in the above Theorem, discarding the vacuous one.

What does he mean by "discarding the vacuous one"?(And why would i want to do this?)

After that he says:

This may seem like it is more efficient, but it is a false economy, because one then has to determine what parity $n$ is,...

but why, because of that "discard", do i have to determine parity then?

Community
  • 1
famesyasd
  • 475
  • See Vacuous truth: a conditional with a False antecedent is True. We say that it is "vacuously true". – Mauro ALLEGRANZA May 03 '17 at 07:56
  • The first proof relies on Proof by cases: if $n$ is even, then $P$; if $n$ is odd, then $P$; but either $n$ is odd or $n$ is even. Therefore $P$. – Mauro ALLEGRANZA May 03 '17 at 07:59
  • 2
    I think Tao's point is that you don't have to determine parity – 5xum May 03 '17 at 08:00
  • 1
    In the corollary, we know (I assume) the parity of $n$, and thus we apply the "relevant" part of the proof, e.g. if $n$ is odd, then $P$, without considering the other case (we discrad it). – Mauro ALLEGRANZA May 03 '17 at 08:02
  • well yes, i think that i more or less understand what vacuously true means and how i can use it in proofs, (for example to show that there is only one empty set) i just don't get it how Tao wants to show its usefulness with this theorem. – famesyasd May 03 '17 at 08:03
  • @5xum ?, yes i think that's the point too, just what it has to do with those vacuously true implications? why if we "discard" those vacuous cases we then will have to check parity of numbers – famesyasd May 03 '17 at 08:09
  • Tao is saying: we have a "general" result asserting that, for every $n, n(n+1)$ is even. We can apply to $n=2, n=1001$ or to $n=\ldots$ the very very big number in the Corollary, without need of knowing if $n$ is either even or odd. – Mauro ALLEGRANZA May 03 '17 at 08:13
  • He is making a "pedagogical example"... seemengly not very clear. – Mauro ALLEGRANZA May 03 '17 at 08:14
  • Ch A.2 discusses Implication (the conditional: "if..., then,,,"): "the least intuitive of the commonly used logical connectives". Tao makes some examples: true conditional with false antecedent and consequent and true conditional with false antecedent: "the falsity of the hypothesis does not destroy the truth of an implication, in fact it is just the opposite! (When a hypothesis is false, the implication is automatically true.)" Specifically, it seems that the case under discussion is aimed at showing: "how a vacuous implication can be used to derive a useful truth." – Mauro ALLEGRANZA May 03 '17 at 08:20
  • So, in conclusion: what is your concern ? About the use of the "truth functional" conditional in mathematics, or about the lacking of "clarity" in the provided examples ? – Mauro ALLEGRANZA May 03 '17 at 08:28
  • alright, i will summarize in another way: we have proved two implications "if n is even, then...". "if n is odd,then ". For an arbitrary n one of them becomes vacuosly true. When we go to the corollary we have an integer, like in theorem, but it's determined, so we can check its parity if we want to. Now it's like that: if we have implications like above we don't have to worry about n's parity, otherwise(if we discard something) we then have to worry and check it. I will now look upon what it is what we could have discarded: – famesyasd May 03 '17 at 08:35
  • @MauroALLEGRANZA in your post it works like this: we have checked parity, thus we discard one of the parts of theorem, but for me it's upsidedown: it's because we have discarded something considering vacuosity in the theorem about implications now we have to check parity. Maybe it's just that what i didn't understand correctly because i don't see any point, motive in checking number's parity just to take the relevant part of the proof. – famesyasd May 03 '17 at 08:50
  • 1
    I'm reading the corollary this way: apply the general theorem to $n=\ldots$ and we immediatley conclude that $n(n+1)$ is even. Otherwise, check parity of $n$: let us assume that it is odd, and apply directly the argument: "If $n$ is odd, then $n + 1$ is even; since any multiple of an even number is even, we have that $n(n + 1)$ is even." – Mauro ALLEGRANZA May 03 '17 at 08:53

2 Answers2

4

At the end of that section, Tao goes on to summarize the point of this particular exercise:

So, somewhat paradoxically, the inclusion of vacuous, false, or otherwise “useless” statements in an argument can actually save you effort in the long run! [...] All I’m saying here is that you need not be unduly concerned that some hypotheses in your argument might not be correct, as long as your argument is still structured to give the correct conclusion regardless of whether those hypotheses were true or false.

There are two implications:

  1. If $n$ is even, then $n(n+1)$ is even
  2. If $n$ is odd, then $n(n+1)$ is even

We could look at $n = (253+142)*123 - (423+198)^{342} + 538 - 213$ and say that $n(n+1)$ is an even integer because $n$ is odd (after expending some effort determining the parity directly), and know this thanks to implication 2.

We "discarded" (i.e. cast aside, didn't mention, ignored, etc) the first implication because it didn't apply. We found that $n$ was odd, so why bother bringing up details about unrelated scenarios involving even $n$?

In actuality, it would have saved us some effort if we had included both implications, despite the fact that one of them would be vacuous and not apply directly to this particular value of $n$. Since both implications cover both parity cases and yield the same outcome, we didn't need to actually check the parity directly to know that $n(n+1)$ is even.

Marcus Andrews
  • 4,941
  • alright, i will summarize in another way: – famesyasd May 03 '17 at 08:24
  • Alright, it seems i got it. Let's take n=10. We know that it's even(we either remember it, so it can take 0 time to check it or can check it it takes less than second). After that we may substitute n=10 in our general theorem and notice that for ex. second branch of proof is unnecessary, so why bother including it into our cureent proof? That economy of space in our proof may seem efficient, but in reality it is not, because to apply this effectivity we have sacrificed time to check parity of our number(Well, in case of number 10 it's equal to time of general theorem) which takes more time gen – famesyasd May 03 '17 at 09:12
  • so, yeah, in a way those vacuous implications save or time checking parity of number – famesyasd May 03 '17 at 09:14
  • Yep, you got it now – Marcus Andrews May 03 '17 at 09:14
  • how do i do it? nvm, i found it. Does checkmark mean that question is closed and if not do i need to close it? @Marcus Stuhr – famesyasd May 03 '17 at 18:33
2

Imagine you are travelling along a road. You come to a junction with two choices.

On the left is a sign saying:

Choose me if $n$ is even

On the right, a sign says:

Choose me if $n$ is odd

Whichever route you choose, the other route becomes vacuous.

JMP
  • 21,771