11
$\begingroup$

The question is:

Prove that for every three non-zero integers, a,b and c, at least one of the three products ab,ac,bc is positive. Use proof by contradiction.

My general approach to doing contradiction is as follow:

I always like to turn the statements into propositional logic, with an implication. In this case it would be like:

[For all a,b,c in the domain of non-zero integer If a,b and c are three non-zero integers], then at least one of the three products ab,ac,bc is positive.

Then I take the negation of it: (P ^ ~Q)

Assume to the contrary,there exist a,b and c that are non-zero integers and none of the three products ab,ac and bc are positive.

Now, I pick a = 1, b = -1 , c = 2

a.b = -1 a.c = 2 b.c = -2

Since a.c is positive, our assumption is false and we have a contradiction. Hence, the original statement is true.

Please feel free to share any other alternatives...(contradiction ones)

$\endgroup$
  • 7
    $\begingroup$ It really looks like you've just found a single pair that doesn't contradict the claim, and not actually proven anything (except in the case $(a, b, c) = (1, -1, 2)$). $\endgroup$ – pjs36 Nov 13 '15 at 22:23
  • $\begingroup$ @pjs36 ok.. If I were to generalize it to say a = x, b = -y and c = z, then [a.b =-ay] , [a.c = xz] and [b.c = -yz] where x, -y and z are non-zero integers.. would that help? Also, we weren't thought pigeon hole principle and so am trying not to use it. $\endgroup$ – misheekoh Nov 13 '15 at 22:27
  • $\begingroup$ I think the contradiction would be that you can find at least one triple such that all 3 products are negative. This is probably no easier to disprove than it is to directly prove the original assertion. $\endgroup$ – Mitchell Kaplan Nov 13 '15 at 22:27
  • 2
    $\begingroup$ @MitchellKaplan: exactly. I think it is outrageous the way teachers ask questions that suggest that proof by contradiction is a preferred approach. $\endgroup$ – Rob Arthan Nov 13 '15 at 22:32
  • 1
    $\begingroup$ @misheekoh: see my answer for a bit more detail about the logical structure of the proof. $\endgroup$ – Rob Arthan Nov 13 '15 at 22:51
62
$\begingroup$

The product of three negative numbers is negative. So if $ab$, $ac$, and $bc$ are all negative, then $(ab)(ac)(bc)\lt0$. But $(ab)(ac)(bc)=a^2b^2c^2$ is the product of three squares, which are all positive.

$\endgroup$
  • 2
    $\begingroup$ This is the most concise and complete solution, in my opinion. $\endgroup$ – daOnlyBG Nov 13 '15 at 23:10
  • 3
    $\begingroup$ This is extremely cute… but it also has that “pulled out of a hat” quality: for for a student looking at it, it’s hard to see how one would think it up in the first place. I think the other answers — e.g. looking at the possible combinations of parities the three numbers could have — are a bit more pedagogically helpful in terms of showing reusable techniques/approaches. $\endgroup$ – Peter LeFanu Lumsdaine Nov 15 '15 at 19:37
14
$\begingroup$

HINT: One of the following is true about the integers: (all positive), (all negative), (one positive and two negative), or (two positive and one negative).

$\endgroup$
  • 8
    $\begingroup$ Nice hint for a proof that doesn't meet the inexplicable requirement to prove it by contradiction. Another way of phrasing it is to say that if $ab$ and $ac$ are both negative, then $a$ and $b$ have opposite signs and $a$ and $c$ have opposite signs, but then $b$ and $c$ have the same signs and so $bc$ is positive. $\endgroup$ – Rob Arthan Nov 13 '15 at 22:30
8
$\begingroup$

Assume to the contrary, there exist $a$, $b$ and $c$ that are non-zero integers and none of the three products $ab$, $ac$ and $bc$ are positive.

Things generally look OK up to this point. In particular, the statement above is a good assumption to make for the desired proof by contradiction.

Now, I pick a = 1, b = -1 , c = 2

This is not OK: the assumption did not say "for any $a$, $b$ and $c$ that are non-zero integers" (which would allow us to choose any non-zero $a$, $b$, and $c$ for a counterexample), it said merely "there exist". As it turns out, there are some choices of $a$, $b$, and $c$ that do not satisfy the "none of the products" condition, but so what? All it takes to justify a "there exist" statement is to find one set of numbers that do satisfy the condition.

Here's an example of why a counterexample does not contradict a "there exists" condition. Let's try to prove this statement:

Every integer is even.

Proof by contradiction:

Assume the contrary, that there exists an integer $n$ that is not even.

Now pick $n = 2$.

But $2$ is even, therefore the assumption (that it is not even) is contradicted.

Do you see why this does not work? Can you see how the logic progresses just like the logic in your proof? (Assume there exists ____ such that ____; choose some values for the variables in the first blank; then show that for these values, the statement in the second blank is false.)

$\endgroup$
  • $\begingroup$ personal.kent.edu/~rmuhamma/Philosophy/Logic/ProofTheory/… Maybe that's why I'm confused.. because to prove existential, he showed an example.. In the same way.. To prove there exist an integer n that is not even, I would simply pick n = 3 as an example. $\endgroup$ – misheekoh Nov 13 '15 at 23:36
  • $\begingroup$ But that in this case, i'm disproving, so I can't use an example.. $\endgroup$ – misheekoh Nov 13 '15 at 23:41
  • 4
    $\begingroup$ @misheekoh Exactly. A single example does not disprove a "there exists" statement; all it says is that you chose a bad example. Maybe there is a better example that proves the statement. (In the case of $n$ that is not even, yes, $n=3$ is a much better example than $n=2$.) $\endgroup$ – David K Nov 14 '15 at 0:14
3
$\begingroup$

ab and ac negative => sign(b) = sign(c) => bc positive

$\endgroup$
3
$\begingroup$

You can't prove this with just an example.

By contradiction, suppose $ab<0$, $ac<0$ and $bc<0$.

Since $ab<0$, then either $a<0$ and $b>0$, or $a>0$ and $b<0$.

In the first case, the condition $ac<0$ implies $c>0$, but then $bc>0$. In the second case $bc<0$ implies $c>0$, but then $ac>0$.

Both cases give a contradiction.

$\endgroup$
  • $\begingroup$ so I guess when doing contradiction, I will have to assume a generalized case that somehow show that my assumption is false? $\endgroup$ – misheekoh Nov 13 '15 at 22:38
  • 3
    $\begingroup$ @misheekoh A counterexample could prove the statement is false, not that it's true. $\endgroup$ – egreg Nov 13 '15 at 22:44
3
$\begingroup$

Map each of $a,b,c$ to its sign: $$ sign\colon x \mapsto \frac x {\lvert x \rvert}\colon\{a,b,c\}\to \{-1,1\}. $$ If the image of $sign$ is just $\{-1\}$ or just $\{1\}$, then all of $a,b,c$ have the same sign, and the product of any two of them is positive. If the image of $sign$ is all of $\{-1,1\}$, then by the pigeonhole principle some two distinct $x,y\in \{a,b,c\}$ have the same sign, and then $xy$ is positive.

$\endgroup$
2
$\begingroup$

This is an attempt to answer the question about the logic here implicit in misheekoh's comment. What we are trying to prove is:

$$ \forall a, b, c \in \Bbb{Z}_{\neq0}(ab > 0 \lor ac > 0 \lor bc > 0) $$

To do this by contradiction, we negate the above to give:

$$ \exists a, b, c \in \Bbb{Z}_{\neq0}(ab \le 0 \land ac \le 0 \land bc \le 0) $$

and try to derive a contradiction from that. So we suppose we have $a, b, c \in \Bbb{Z}_{\neq0}$ such that

$$ ab \le 0 \land ac \le 0 \land bc \le 0 $$

and we observe that none of the products can be zero so we have

$$ ab < 0 \land ac < 0 \land bc < 0 $$

from which we can conclude that $a$ and $b$ have opposite signs and that $a$ and $c$ have opposite signs, so that $b$ and $c$ must have the same sign contradicting $bc < 0$.

However, what we did in the end game of this proof is a direct proof of:

$$ \forall a, b, c \in \Bbb{Z}_{\neq0}(ab > 0 \lor ac > 0 \lor bc > 0) $$

thought of as:

$$ \forall a, b, c \in \Bbb{Z}_{\neq0}(\lnot(ab > 0 \lor ac > 0) \Rightarrow bc > 0) $$ without any need for a proof by contradiction.

Why do teachers encourage illusory non-constructive proofs?

$\endgroup$
  • 2
    $\begingroup$ "Why do teachers encourage illusory non-constructive proofs?" -- probably because Barry Cipra's answer is about 1/10 the length of yours ;-p $\endgroup$ – Steve Jessop Nov 14 '15 at 13:22
  • 1
    $\begingroup$ More seriously, as a didactic exercise it's important for the questioner to carry out at least one proof by contradiction, since the question demonstrates that currently they aren't able either to write one or to assess one for correctness. It might be a bit beyond both teacher and student to use for this exercise a concrete result that is not provable in constructive logic, such that proof by contradiction is actually "necessary", so instead you add an arbitrary restriction for the purposes of the exercise. $\endgroup$ – Steve Jessop Nov 14 '15 at 13:24
  • $\begingroup$ The original statement cannot be proved constructively, in the precise sense of "constructive proof". In general, there is no way to determine effectively which of the products is positive (even if we make simplifying assumptions such as $c = -1$ and $a = -b$) and so there can't be a constructive proof that one of the products is positive. The equivalence of formulas near the end of this answer is also not constructively valid; $(A \lor B)$ is not constructively equivalent to $(\lnot A) \to B$. So the non-constructiveness in this problem is not illusory. $\endgroup$ – Carl Mummert Nov 15 '15 at 11:58
  • $\begingroup$ Of course there is a constructive proof: a is positive or negative. b is positive or negative. c is positive or negative. There are eight possible combinations how a, b, c could each be positive or negative, and in each case one (or more) of the products are positive. $\endgroup$ – gnasher729 Nov 15 '15 at 17:33
  • $\begingroup$ Even simpler: Of three numbers, either at least two are positive, or at least two are negative. In each case we have two numbers with a positive product. $\endgroup$ – gnasher729 Nov 15 '15 at 17:34
2
$\begingroup$

So simple to answer but also so easy to trick those who want it to be difficult.

The Simple Answer is:-

Regardless of the sign of a, b, or c, (Oxford comma included to negate the possibility of some smart alec trying to imply boolean logic in this answer) the product will always be positive when like signed elements are multiplied.

As there are only 3 elements, at least one of the products is therefore positive.

$\endgroup$
1
$\begingroup$

Assume we have some nonzero numbers such that each pairwise product is negative. Therefore we don't have two positive numbers (their product would be positive), and we don't have two negative numbers (their product would be positive), so we have at most one positive and one negative number, for a total of two numbers. Contradiction to "we have three numbers".

$\endgroup$

protected by user26857 Nov 18 '15 at 23:37

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.