The Opposite of Even is Odd … or Not?

(A new question of the week)

A recent question raised some interesting issues related to the contrapositive of a logical statement, and how to negate a statement, similar to some past discussions. What universe you are in makes a big difference!

Proof by contrapositive

The question came from Kalyan, in June:

My question is this:

Prove: If n is even, then 8n is even.

Solving it with a direct proof is quite easy, and “true” is the answer.  But, when I prove it with a contrapositive technique, I get puzzled. By contrapositive:

Assume – 8n is odd: 8n = 2k +1 (True)

Then, n = (2k+1)/8 which is quite baffling as n is not an integer in this case. (False)

Contrapositive becomes False.

So, contrapositive has failed to be logically equivalent to the original implication statement.

Recall that the contrapositive of a conditional statement \(p\rightarrow q\) is \(\neg q\rightarrow\neg p\). That is, we negate both statements and reverse the direction of the arrow. The contrapositive of any statement is equivalent to the original. But Kalyan seems to have found a case where this is not true, since if 8n is odd, n is not odd.

(The direct proof, by the way, is indeed easy: Since we can write \(8n\) as \(2(4n)\), and \(4n\) is an integer, 8n is even.)

“Not even” may not mean “odd”

I replied, commending Kalyan for turning a very simple exercise into a chance to learn something deeper, by trying out different techniques:

Hi, Kalyan.

I like this question — it shows that you are trying things you don’t need to try, just to understand them better, which is the way to learn math well. And subtleties like this are well worth thinking about.

The contrapositive of “If n is even, then 8n is even” is not exactly what you are thinking, “If 8n is odd, then n is odd“. Properly speaking, it is “If 8n is not even, then n is not even“. Do you see the difference? There are numbers that are neither even nor odd!

Your difficulty was that you concluded that n is not an integer, so that you couldn’t say “n is odd”. But in fact, if n is not an integer, then n is not even! So you do come to the expected conclusion, that the contrapositive is true.

If we take the simplest possible negation, by merely putting a “not” before the word “even”, everything works fine. If, for example, \(8n\) is 5, then \(n = \frac{5}{8}\), which in fact is not an even number – it is not an integer at all. The difficulty came in rewriting “not even” as “odd”. And that problem, in turn, arises from leaving the world of integers, as we’ll see later.

Another way to express this would be to state the theorem as, “If n is an even integer, then 8n is an even integer“. The contrapositive would be, “If 8n is not an integer, or is not even, then n is not an integer, or is not even”. This is more awkward to deal with!

Here I applied De Morgan’s law, that the negation of “p and q” is “not p, or not q“. That is, if it is not true that both p and q are true, then at least one of them must be false. So if it is not true that n is both even and an integer, then it must be either not an integer, or [an integer but] not even. In other words, there are two ways not to be even: to be odd, or not to be an integer at all.

Proof by contradiction

We could also express your thinking as a proof by contradiction, which is almost the same as proving the contrapositive. We would start by assuming that n is an even integer, and then suppose that 8n is not even. Since we know 8n is an integer, this implies that 8n is odd, that is, 8n = 2k + 1 for some integer k. But then n = (2k + 1)/8, which is not an integer, resulting in a contradiction.

I’m reminded of this post from our blog, which has some similar features:

Complicating the Converse

That page doesn’t deal with negation at all, but with finding a converse in a complicated situation where part of the condition is taken as a context, somewhat like the issue here with the context dealing with integers.

We’ll be looking at proof by contradiction and contrapositives next week. The benefit of using a proof by contradiction here is that we could explicitly assume that n is an integer, and within that assumption, suppose that 8n is odd.

Needing a lemma

But we have to think about another detail. You concluded that n = (2k + 1)/8 is not an integer. How did you prove that? It’s obvious, but in part because we know that an odd number can’t be a multiple of 8, which itself needs proof. And proving a negative directly can be difficult; I would typically prove this by proving its contrapositive — which would take us back to the original theorem.

We can easily fall into this little trap when proving familiar facts; we forget what we are allowing ourselves to “know” without proof, and what has to be proved (or may even be a consequence of the very fact we are trying to prove).

So I tried to prove this claim, on which Kalyan was depending:

But try this: Since 8n = 2k + 1 (for some integer k), we can conclude that k = (8n – 1)/2 = 4n – 1/2, which is not an integer. So here we have a clear contradiction. My proof by contradiction would end here; your proof by contrapositive would need another twist or two.

Here I haven’t replaced Kalyan’s work with a proof by contradiction, but just used contradiction to prove a lemma (a small theorem needed to prove a main theorem).

Ultimately, I would just say that some things are so much more easily proved by one approach than another, that it is best not to use the other. But we all need to try some of those other paths, in order to develop a sense of what will or will not be worth pursuing in the future. And occasionally, the path that looks useless turns out to be the best way, so it’s good to retain some willingness to try “the path not taken” (if nothing else works).

An open mind to alternative methods, as Kalyan is demonstrating, is not only good as a way to learn, but is useful even in subsequent work, where something that “obviously” won’t work may turn out to work very well when other ways fail.

Negation within a different universe

Kalyan responded:

Hello Doctor, I am happy that you have responded to my question in detail.

But, the answer hasn’t been satisfying. If I consider the negation of “8n is even” to be “8n is not even”, then why do books not write this, rather it is written as 8n is odd. As the opposite of even is odd.

Now, if I take 8n is not even, then the contrapositive is true. If I take to be odd, there is no logical equivalence between the original implied statement and the contrapositive one.

We have to dig more deeply into the nature of negation: Why do people say that “the opposite of even is odd”, if we can’t always replace “not even” with “odd”? How do you know when you can do that? The answer is that we must pay attention to the universe (the set of all entities under consideration).

I replied,

When we say that the negation of “x is even” is “x is odd”, that is a negation within the universal set of integers. If it is not understood that x is necessarily an integer, then we need to expand that. For example, the number 1.2 is neither even nor odd; so in saying that it is not even, I am not saying that it is odd.

The reason we have to bring non-integers into your proof is that in dividing, you are allowing a number to be a non-integer.

So when you find that n = (2k+1)/8 is not an integer, you can’t conclude that it is false to say it is odd; rather, you must conclude that it is true to say that it is not even. This is because the original statement is not about oddness, but about evenness.

In general, negation requires attention to the universal set, because it means, “everything [in the universe] except this”, so it depends on what we mean by “everything”.

To give a more mundane example, suppose I say, “Henrietta is not a girl”. Does that mean the same thing as, “Henrietta is a boy”? It would if we already knew that Henrietta is a child. But if we only know that Henrietta is a human, then she might be a woman! If we only know she is a mammal, she might be a pussycat. (That’s a Mister Rogers reference …) But in fact, Henrietta is a town in which I used to work! Each of those is a different universe.

In the same way, “x is not even” means “x is odd” only if we are assuming that x is an integer. If we don’t know that, then x might be 1.5, or pi, or 1 + i, or a cat, or a town in New York!

Making the contrapositive work

Let’s focus not on your proof, but on the notion of contrapositive, which is your main concern. You have the statement, “If n is even, then 8n is even”. I’ll generalize that to “If A is even, then B is even.”

If A=6 and B=4, then the statement is true, and so is your version of the contrapositive, “If B is odd, then A is odd”, because the condition is false.

If A=6 and B=3, then the statement is false, and so is your version of the contrapositive, “If B is odd, then A is odd”, because the condition is true but the conclusion is false.

So far, they are equivalent.

But if A=1/2 and B=3, then the statement is true, because the condition is false (A is not even); but your version of the contrapositive, “If B is odd, then A is odd“, is false, because the condition is true but the conclusion is false (A is not odd). However, my version of the contrapositive, “If B is not even, then A is not even“, is true, because the condition is true and the conclusion is true.

So your contrapositive can’t be right! Again, the reason it failed is that we have here moved from integers as the universal set, to real numbers, and in this set the negation of “A is even” is not “A is odd”, but “A is not even”.

The fact that your “contrapositive” is not equivalent to the original statement proves that it is not the real contrapositive!

We’ve seen why Kalyan’s version of the contrapositive is wrong (he negated on the assumption that n is an integer, but then allowed it not to be), and how we can know that it is wrong (that it would contradict a theorem about contrapositives).

The reason books commonly say that the negation of even is odd is that they are working within integers as the universe. When the context is different, they can only say that the negation is “not even” (which is what negation means!), because that is no longer equivalent to “odd”.

Kalyan answered,

Thank you Doctor.  So, does it mean that when we prove using any contrapositive we must check which contrapositive suits the relevant statement given in the question?

Nicely explained, sir.

If “which contrapositive” means “the contrapositive based on a negation within which universe”, that’s exactly right.

I closed with this:

I think the important thing is to pay attention to the universal set when determining negations; and when something odd happens, back up and think more deeply! When something doesn’t work, we are probably missing some detail.

One final comment: Have you noticed how weak the statement to be proved was? The fact is, 8n will be even not only if n is even; n can be any integer at all, and even a lot of fractions (multiples of 1/4) work! So it could have been stated more strongly as “If n is an integer, then 8n is even,” and the questions asked here would never have come up! We would know that both n and 8n are integers, so the contrapositive would become, “If 8n is not even [or, is odd], then n is not an integer,” and the proof would be fairly clean.