5
$\begingroup$

Part of a proof requiring you to prove that if $x^2$ is odd then $x$ is odd (given that $x \in \mathbb{N}$). It is my understanding that the contrapositive is used for this as follows.

$x=2n, n \in \mathbb{N}$

$\Rightarrow x^2 = 4n^2$

$\Rightarrow x^2$ is even

Then using the contrapositive:

$\Rightarrow \lnot Even(x^2) \rightarrow \lnot Even(x)$

Now the Law of the excluded middle:

$\Rightarrow Odd(x^2) \rightarrow Odd(x)$

So reasonably straight forward. However, my issue with this is whilst $x^2$ is even, it is even more strictly defined as a multiple of $4$. So in the contrapositive sense it doesn't feel right that it can be any even number. So what happens if that said number is 6? Not strictly divisible by 4 but still even. This is a bit difficult because this proof's conclusion is actually correct and any squared integer is either divible by 4 or odd. But that was found through exhaustion in a different way. Using the law of the excluded middle after saying that it wasn't just any even number seems spurious.

Could someone please clarify if I am right with reservation about this? If not, please explain (without just saying it is contrapositive, therefore). I feel like there should be a continuing connection between the definition of what type of even and what can be deduced from that.

$\endgroup$
12
  • $\begingroup$ What is the definition of $\operatorname{Odd}(n)$? $\endgroup$ Aug 13 '17 at 17:15
  • 1
    $\begingroup$ @HagenvonEitzen 'is even' and 'is odd', I think $\endgroup$
    – Shuri2060
    Aug 13 '17 at 17:15
  • 2
    $\begingroup$ Any number divisible by $4$ is even. Every even square is divisible by $4$. The first of these is relevant to the proof, the second is not. $\endgroup$ Aug 13 '17 at 17:16
  • 4
    $\begingroup$ I think I'm seeing your point, and I think the answer below by @NoahSchweber addresses it. The first part of the proof may establish more than $x^2$ being even, but it establishes that $x^2$ is even, which is what we need. If we have $p\implies (q \wedge r)$, then we have $p\implies q$, so we have $\neg q \implies \neg p$. $\endgroup$ Aug 13 '17 at 17:32
  • 3
    $\begingroup$ ^ Yes.$$(p\implies(q\land r))\iff(\neg (q\land r) \implies \neg p)\iff(\neg q\lor\neg r) \implies \neg p)\iff((\neg q\ \implies \neg p)\land(\neg r\ \implies \neg p))$$ We only need the first statement in our proof. $\endgroup$
    – Shuri2060
    Aug 13 '17 at 17:36
11
$\begingroup$

Ignore the broader proof - do you agree with the assertion "If $x$ is divisible by $4$, then $x$ is even?" This is all that's going on. We're always allowed to "forget" information in a proof, and this has nothing to do with the excluded middle. When you conclude "$x^2$ is even," this in no way implies that you've concluded "$x^2$ is even and that's the most that can be said."

$\endgroup$
12
  • 1
    $\begingroup$ It's this forgetting of information that I find tenuous. We are concluding that $x^2$ is only some of the even numbers though. Is there an explanation why? $\endgroup$
    – AER
    Aug 13 '17 at 17:33
  • 2
    $\begingroup$ If you're in Paris, then you're in Europe. Even more particularly, you're in France. However, "if you're not in Europe, then you're not in Paris," is still a valid application of the contrapositive, even though we've "forgotten" the information about being in France. $\endgroup$ Aug 13 '17 at 17:35
  • $\begingroup$ @GTonyJacobs I think this is the actual answer. Please submit this. $\endgroup$
    – AER
    Aug 13 '17 at 17:38
  • 1
    $\begingroup$ @AER Too bad, it's true. (Also, what does the Monty Hall problem have to do with this?) Regardless of whether it seems spurious, it is a thing you can do. Think about it: do you understand why more powerful statements ("$a$ is divisible by $4$") imply weaker ones ("$a$ is even")? If not, why not? If so, that's why that's a valid step in a proof. Proofs are "truth-preserving;" they're not required to "conserve information" in any sense, the only requirement is that they follow rules which will never lead you from true statements to a false statement. $\endgroup$ Aug 13 '17 at 17:41
  • 2
    $\begingroup$ @AER That's a different kind of information at play. This is the danger with using informal language to explain things. At its core, all this is is modus ponens: from $A$ and $A\implies B$, we can conclude $B$, regardless of whether $B$ is enough to imply $A$. Our proofs don't have to be "reversible." $\endgroup$ Aug 13 '17 at 17:47
10
$\begingroup$

If you're in Paris, then you're in Europe. Even more particularly, you're in France. However, "if you're not in Europe, then you're not in Paris," is still a valid application of the contrapositive, even though we've "forgotten" the information about being in France.

"You're in Paris." $\longleftrightarrow x$ is even.

"You're in Europe." $\longleftrightarrow x^2$ is even.

"You're in France." $\longleftrightarrow x^2$ is a multiple of $4$.

$\endgroup$
3
  • $\begingroup$ It's literally modus ponens but with contrapositive. I'm such an idiot... $\endgroup$
    – AER
    Aug 13 '17 at 18:15
  • 1
    $\begingroup$ Don't be too hard on yourself. It's good to grapple with these ideas. Makes them more solid for more confusing situations in the future. :) $\endgroup$ Aug 13 '17 at 18:18
  • 1
    $\begingroup$ This is some delightful exposition. $\endgroup$ Aug 14 '17 at 14:16
3
$\begingroup$

It is not a law of excluded middle that you need to prove that every integer is either even or odd. Excluded middle applies equally to integers and reals, but not every real is even or odd. To prove this property requires a property of integers, such as the division algorithm (divide by 2, look at remainder).

$\endgroup$
2
  • $\begingroup$ Agreed. I meant with integers. Updated question to remove this lack of clarity. $\endgroup$
    – AER
    Aug 13 '17 at 17:27
  • 1
    $\begingroup$ Euclid made this same mistake, so OP is in good company. $\endgroup$
    – saulspatz
    Aug 13 '17 at 19:12
2
$\begingroup$

Let $(p(x)\equiv2\mid x), (q(x)\equiv2\mid x^2), (r(x)\equiv4\mid x^2)$.

Then we have

$$(\forall x\in\Bbb Z)\quad(2\mid x\implies4\mid x^2)$$ $\implies$ $$(\forall x\in\Bbb Z)\quad(2\mid x\implies(2\mid x^2\land 4\mid x^2))$$ $\implies$ $$(\forall x\in\Bbb Z)\quad(\neg (2\mid x^2\land 4\mid x^2) \implies 2\nmid x)$$ $\implies$ $$(\forall x\in\Bbb Z)\quad((2\nmid x^2\lor4\nmid x^2) \implies \neg 2\nmid x)$$ $\implies$ $$(\forall x\in\Bbb Z)\quad((2\nmid x^2 \implies 2\nmid x)\land(4\nmid x^2 \implies 2\nmid x))$$ $\implies$ $$(\forall x\in\Bbb Z)\quad(2\nmid x^2 \implies 2\nmid x)\land(\forall x\in\Bbb Z)\quad(4\nmid x^2 \implies 2\nmid x)$$ $\implies$ $$(\forall x\in\Bbb Z)\quad(2\nmid x^2 \implies 2\nmid x)$$


Now I think your confusion comes from considering $(\forall x\in\Bbb Z)\quad(4\nmid x^2 \implies 2\nmid x)$ which is also true.

Then $(4\nmid6)\implies(x^2=6\implies4\nmid x^2)$, and so we get

$$(\forall x\in\Bbb Z)\quad (x^2=6\implies4\nmid x^2\implies2\nmid x)$$

and we end up with the bizarre statement

$$(\forall x\in\Bbb Z)\quad(x^2=6\implies x\text{ is odd})$$

But of course, there is no such integer whose square is $6$ (and in fact, this is a valid proof of that being the case if we also use 'the square of an odd is odd').

For all integers, $x^2=6$ is false, and we can prove anything with a false premise. In general,

$$\neg P\implies(P\implies Q)$$

is true for any statements $P$ and $Q$.

$\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.