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

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.

• 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)$). Nov 13 '15 at 22:23
• @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. Nov 13 '15 at 22:27
• 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. Nov 13 '15 at 22:27
• @MitchellKaplan: exactly. I think it is outrageous the way teachers ask questions that suggest that proof by contradiction is a preferred approach. Nov 13 '15 at 22:32
• @misheekoh: see my answer for a bit more detail about the logical structure of the proof. Nov 13 '15 at 22:51

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.

• This is the most concise and complete solution, in my opinion. Nov 13 '15 at 23:10
• 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. Nov 15 '15 at 19:37

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).

• 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. Nov 13 '15 at 22:30

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.

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.)

• 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. Nov 13 '15 at 23:36
• But that in this case, i'm disproving, so I can't use an example.. Nov 13 '15 at 23:41
• @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$.) Nov 14 '15 at 0:14

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

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

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

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.

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?

• "Why do teachers encourage illusory non-constructive proofs?" -- probably because Barry Cipra's answer is about 1/10 the length of yours ;-p Nov 14 '15 at 13:22
• 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. Nov 14 '15 at 13:24
• 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. Nov 15 '15 at 11:58
• 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. Nov 15 '15 at 17:33
• 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. Nov 15 '15 at 17:34

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