Discrete Math: Proof by contradiction

[SolarMidnite]

Homework Statement

Using contradiction, prove that for every four positive real numbers c, d, e and f, at least one of c, d, e, f is
greater than or equal to the average of c, d, e, f.

Homework Equations

I don't believe that there are any relevant equations for this problem. I do know that we have to suppose that the negation of the statement is true, show that this supposition leads to a contradiction and then conclude that the statement to be proved is true.

The Attempt at a Solution

I am finding it difficult to translate the above statement into predicate logic because I have only worked with two variables and there are four in this problem! Here is my attempt but I think that I'm way off.

\forall (c \wedge d \wedge e \wedge f) \in ℝ⁺, \exists(c \vee d \vee e \vee f) \in ℝ⁺ \geq (c+d+e+f)/4

The negation in words might be something like: at least one of the four positive real numbers c, d, e and f will be less than the average of c, d, e, f.

 

[Mark44]

Homework Statement

Using contradiction, prove that for every four positive real numbers c, d, e and f, at least one of c, d, e, f is
greater than or equal to the average of c, d, e, f.

Homework Equations

I don't believe that there are any relevant equations for this problem. I do know that we have to suppose that the negation of the statement is true, show that this supposition leads to a contradiction and then conclude that the statement to be proved is true.

The Attempt at a Solution

I am finding it difficult to translate the above statement into predicate logic because I have only worked with two variables and there are four in this problem! Here is my attempt but I think that I'm way off.

\forall (c \wedge d \wedge e \wedge f) \in ℝ⁺, \exists(c \vee d \vee e \vee f) \in ℝ⁺ \geq (c+d+e+f)/4

The negation in words might be something like: at least one of the four positive real numbers c, d, e and f will be less than the average of c, d, e, f.

The negation of your statement would be, that, given any four positive real numbers, none is greater than or equal to the average.

Or equivalently, given any four positive real numbers, all are less than the average.

 

[Coto]

To get you started, consider that a contradiction starts with the negation, that none of c,d,e, or f are greater than or equal to their average, and therefore are all strictly less than their average.

Rather than translating the entire statement into logical symbols, start by just translating the negation. In other words,

\forall c,d,e,f \in \mathbb{R}^+, let A = \frac{c+d+e+f}{4}, and assume c < A, d < A, e < A, f < A.

Starting from that assumption, can you show that there is a contradiction?

 

[Mark44]

\forall (c \wedge d \wedge e \wedge f) \in ℝ⁺, \exists(c \vee d \vee e \vee f) \in ℝ⁺ \geq (c+d+e+f)/4

On a side note, you are misusing symbols in what you wrote. The \wedge and \vee symbols should be used between statements that have truth values, not between numbers. Instead of writing, for example, a \wedge b, just write a and b.

 

[SolarMidnite]

On a side note, you are misusing symbols in what you wrote. The \wedge and \vee symbols should be used between statements that have truth values, not between numbers. Instead of writing, for example, a \wedge b, just write a and b.

So, would it be acceptable to write \forall(c and d and e and f) then? Or is it \forallc,d,e,f as in Coto's post above?

 

[SolarMidnite]

To get you started, consider that a contradiction starts with the negation, that none of c,d,e, or f are greater than or equal to their average, and therefore are all strictly less than their average.

Rather than translating the entire statement into logical symbols, start by just translating the negation. In other words,

\forall c,d,e,f \in \mathbb{R}^+, let A = \frac{c+d+e+f}{4}, and assume c < A, d < A, e < A, f < A.

Starting from that assumption, can you show that there is a contradiction?

It definitely helped to read the statement more clearly by getting the average of c,d,e,f out of the way and letting A represent it. I know that with contradiction statements we would have to sat that c,d,e,f (all four) cannot be both greater or equal to their average and less than their average at the same time. How do I show that one of c, d, e or f is greater than or equal to the average? Would I let, for example, c equal a number and show that it is greater than A? Because I know we are not supposed to substitute variables for numbers in these proofs.

 

[Coto]

So, would it be acceptable to write \forall(c and d and e and f) then? Or is it \forallc,d,e,f as in Coto's post above?

Don't let notation bog you down. Either is acceptable in a proof like this.

I know that with contradiction statements we would have to sat that c,d,e,f (all four) cannot be both greater or equal to their average and less than their average at the same time. How do I show that one of c, d, e or f is greater than or equal to the average? Would I let, for example, c equal a number and show that it is greater than A? Because I know we are not supposed to substitute variables for numbers in these proofs.

You don't need to show that any of them are greater than or equal to the average. If you did, you would be proving your original statement as it stands.

The idea here is to assume that none of them are greater than or equal to the average, and by making this assumption, you need to show that you will arrive at a logical contradiction.

 

[SolarMidnite]

Okay, I won't fuss about the notation! I just thought it might be interpreted a different way depending on the commas.

You don't need to show that any of them are greater than or equal to the average. If you did, you would be proving your original statement as it stands.

The idea here is to assume that none of them are greater than or equal to the average, and by making this assumption, you need to show that you will arrive at a logical contradiction.

Ohh, I see. So in that case, do I have to demonstrate that none of them are greater than or equal to the average? (In other words, show that all of them will be less than the average) How would I go about doing that? I don't think that it would be correct if I gave examples with numbers for c,d,e,f being less than the average because the statement is universal and all possible examples would have to be stated.

 

[Coto]

Not quite. In a "proof by contradiction", the idea is to show that by making the assumption that the statement is false, that you would come to a logical contradiction. If you've assumed the statement to be false and arrive at a logical contradiction, then the statement must have been true.

In your case you start the proof by assuming the statement is false. That is, you start by assuming that c < A, d < A, e < A, f < A. Starting with that "fact", you need to show that this assumption violates something you know to be true. In this case you want to show that in making that assumption you violate the definition of average.

 

[SolarMidnite]

How is the definition of average violated? By plugging in numbers for c, d, e and f, I can understand why c < A, d < A, e < A, f < A would not work because suppose c=1, d=2, e=3, f=4. If we took the average of these numbers, we get A = 2.5. So, c=1 is less than A=2.5, and d=2 is less than A = 2.5. But, e=3 is not less than the average A = 2.5 and f=4 is not less than the average A. I don't know how to show this without using numbers.

 

[Coto]

You have essentially done precisely what you need to do :).

Assuming c,d,e,f < A, what does this say about c+d+e+f? What does this imply about A? Why is this a contradiction?

Hint: If c,d,e,f < A then c+d+e+f < 4A.

P.S. I'm heading to bed, but you should be able to figure it out from here. Think about it until you get it because the solution is here.

 

[SolarMidnite]

Okay I'm going to keep thinking it through, thank you very much for your help!