Philosophy of Mathematics: proof by contradiction

Watch
Absent Agent
Badges: 21
Rep:
?
#1
Report Thread starter 4 years ago
#1
Proof by Contradiction is a method of proving the validity of a proposition by assuming that the opposite proposition is true when doing so would lead to a contradiction.

However, my concern is that the contradiction so reached only proves the invalidity of the opposite proposition; it does not guarantee that the contradictory conclusion reached necessarily determines the truth of the opposite proposition. The best example I can think of is the statement of the falling bodies in a gravitational field (of course, this is not a mathematical proposition, but it does very well highlight the problem). So Aristotle was the first person to claim that heavy objects fall faster than lighter ones, but it took Galileo to theoretically prove that this cannot be true, and his argument runs as follows:

If an heavy object falls faster than a lighter one, then when the lighter object is combined with the heavy object, the lighter object should ****** the motion of the heavier object. But the objects combined together have a greater mass than the heavier object alone, and so it follows from the the initial premise that combined objects should fall faster than heavier object, which is a contradiction.

Even though the argument convinces us that Aristotle's claim is false, it does not tell us what the true statement is, and this can easily be understood if we reverse the initial premise. Let's now assume that heavier objects fall slower than lighter objects, and, following the same line of argument as above, it follows that the heavier object when combined with a lighter object should ****** the motion of the lighter one, and this would be consistent with their combined state, because the combined objects would then fall slower than themselves individually, which agrees with the premise.

In mathematics, a simple application of the proof-by-contradiction is to prove that the \sqrt2 is irrational, for example. Of course, it would be very bizarre to assume that square root of two has some other property than just being irrational that the proof fails to take account of, but would it not possess a property that somehow would explain its irrationality?

The apparent hopelessness in science is overcome by subjecting scientific theories to experimental observations, whose refutation demands modification of the theory, but how would mathematics or logic overcome this problem of providing a direct proof for mathematical theorems?
0
reply
Implication
Badges: 18
Rep:
?
#2
Report 4 years ago
#2
This may not be the most satisfying response, but I think the short answer is that you've slightly misunderstood how a proof by contradiction works. And I think the root cause of that is vagueness in your use of the word 'opposite'.

To prove statement P to be true using contradiction, we assume the negation of P. That is, we assume that P is false (and not necessarily that the 'opposite' of P is true). Depending on how you define 'opposite', it may the case that these are equivalent, but it isn't necessarily so.

For example, if we assume that x is a real number, then by your definition of 'opposite', the opposite claim to 'x is rational' is 'x is irrational'. However, the proof doesn't work because these are opposite statements, but because the statement that the claim 'x is rational' is false is equivalent to the statement that 'x is irrational' is true. This is because real numbers are either rational or irrational.

In your physics example, the same doesn't hold. By assuming 'heaver objects fall more quickly' and arriving at a contradiction, we have NOT demonstrated that heavier objects fall more slowly, but that they do not fall more quickly. In other words, we have shown that objects fall more slowly OR that they fall at the same rate (and in fact the latter is true).

In short, we need to assume that the negation of a statement is true rather than the opposite of it, and these are not always equivalent.


Incidentally, I'm not sure the assumption that 'heavier objects fall more quickly' entails the truth of the statement that a lighter object should ****** a heavier one if combined. To validly prove P by contradiction, we have to make deductively valid inferences from ~p ('not P') to a contradiction, otherwise it could be the intermediary inferences rather than the negation-assumption that is false. But that's probably for a better physicist than me to clarify.

Posted from TSR Mobile
0
reply
Absent Agent
Badges: 21
Rep:
?
#3
Report Thread starter 4 years ago
#3
(Original post by Implication)
This may not be the most satisfying response, but I think the short answer is that you've slightly misunderstood how a proof by contradiction works. And I think the root cause of that is vagueness in your use of the word 'opposite'.

To prove statement P to be true using contradiction, we assume the negation of P. That is, we assume that P is false (and not necessarily that the 'opposite' of P is true). Depending on how you define 'opposite', it may the case that these are equivalent, but it isn't necessarily so.

For example, if we assume that x is a real number, then by your definition of 'opposite', the opposite claim to 'x is rational' is 'x is irrational'. However, the proof doesn't work because these are opposite statements, but because the statement that the claim 'x is rational' is false is equivalent to the statement that 'x is irrational' is true. This is because real numbers are either rational or irrational.

In your physics example, the same doesn't hold. By assuming 'heaver objects fall more quickly' and arriving at a contradiction, we have NOT demonstrated that heavier objects fall more slowly, but that they do not fall more quickly. In other words, we have shown that objects fall more slowly OR that they fall at the same rate (and in fact the latter is true).

In short, we need to assume that the negation of a statement is true rather than the opposite of it, and these are not always equivalent.


Incidentally, I'm not sure the assumption that 'heavier objects fall more quickly' entails the truth of the statement that a lighter object should ****** a heavier one if combined. To validly prove P by contradiction, we have to make deductively valid inferences from ~p ('not P' to a contradiction, otherwise it could be the intermediary inferences rather than the negation-assumption that is false. But that's probably for a better physicist than me to clarify.

Posted from TSR Mobile
Yeah, you are correct! I used the word opposite to refer to the statement of the converse truth, but I also didn't make a distinction between the truth-value of one proposition and truth-value of alternative forms of the same proposition, perhaps because I thought the certainty of a truth-value (whether that would be truth or falsity) of a proposition does not entail the truth of any alternative forms of the same proposition.

So, for example, the proof that "\pi is rational is false" does not prove that the statement "\pi is irrational is true". But, as I said, this would be very vague, because we tent to think that proving that the former statement is false does not leave us with any alternatives but only the latter, hence I gave the physics example.

Of course, this is not a philosophical position, its just a sceptical speculation about the certainty of indirectly proving a statement.
0
reply
admonit
Badges: 10
Rep:
?
#4
Report 4 years ago
#4
(Original post by Absent Agent)
So, for example, the proof that "\pi is rational is false" does not prove that the statement "\pi is irrational is true".
Why not? A number may be either rational or irrational. There is no other options. In fact irrational numbers are defined in negative form: "an irrational number is a real number that cannot be expressed as a ratio of integers", which means not rational number.
1
reply
Absent Agent
Badges: 21
Rep:
?
#5
Report Thread starter 4 years ago
#5
(Original post by admonit)
Why not? A number may be either rational or irrational. There is no other options. In fact irrational numbers are defined in negative form: "an irrational number is a real number that cannot be expressed as a ratio of integers", which means not rational number.
The point I was making was not so much about irrational numbers as it was about the proof itself: If it is certain that the square root of two cannot be expressed as the ratio of two integers, then how would you know that it cannot be expressed as the ratio of two other irrational numbers, which the proof by contradiction would not reveal. Perhaps Euler's identity, e^{i\pi}+1=0, could be an example. How could the irrational numbers e and pi fit together as such when their values were indeterminate?
0
reply
Mathlete18
Badges: 2
Rep:
?
#6
Report 4 years ago
#6
(Original post by Absent Agent)
The point I was making was not so much about irrational numbers as it was about the proof itself: If it is certain that the square root of two cannot be expressed as the ratio of two integers, then how would you know that it cannot be expressed as the ratio of two other irrational numbers, which the proof by contradiction would not reveal. Perhaps Euler's identity, e^{i\pi}+1=0, could be an example. How could the irrational numbers e and pi fit together as such when their values were indeterminate?
I don't get your point? You're right, there's nothing saying it can't be expressed as the ratio of two other irrational numbers, but that's nothing to do with whether it's a rational number or not - which is what the proof is trying to establish.

As posted above, the definition of a number being irrational is literally "That it is not rational"...therefore, if you assume root(2) is rational and reach a contradiction it must be false that root(2) is rational. I.e. "root(2) is not rational" which is the very definition of irrational.
0
reply
Absent Agent
Badges: 21
Rep:
?
#7
Report Thread starter 4 years ago
#7
(Original post by Mathlete18)
I don't get your point? You're right, there's nothing saying it can't be expressed as the ratio of two other irrational numbers, but that's nothing to do with whether it's a rational number or not - which is what the proof is trying to establish.

As posted above, the definition of a number being irrational is literally "That it is not rational"...therefore, if you assume root(2) is rational and reach a contradiction it must be false that root(2) is rational. I.e. "root(2) is not rational" which is the very definition of irrational.
Well, what I'm trying to say is that, silly as it sounds, proving that "x is rational" is false does not mean that "x is irrational" is true, even though it might actually be the case that x is indeed irrational, because we have not extinguished the possibility that" x is not irrational" without inferring its truth from the truth of its negation.

edited the part in bold.
0
reply
Mathlete18
Badges: 2
Rep:
?
#8
Report 4 years ago
#8
(Original post by Absent Agent)
Well, what I'm trying to say is that, silly as it sounds, proving that "x is rational" is false does not mean that "x is irrational" is true, even though it might actually be the case that x is indeed irrational, because we have not extinguished the possibility "that x is irrational" without inferring its truth from the truth of its negation.
But it does imply "x is irrational" is true, because if it was not true then we have both "x is rational" is false, and "x is irrational" is false. I.e. "x is neither rational or irrational"

But x either can be expressed as the quotient p/q of two integers, p and a non-zero q, or it cannot. If it can, then it is defined as a rational number. If it cannot then that is the definition of an irrational number.

Put another way, the set of rational numbers and irrational numbers partition the real numbers.

Thus "x is neither rational or irrational" is itself a contradiction if x is a real number.

Can you highlight which bit doesn't make sense to you?
0
reply
Mathlete18
Badges: 2
Rep:
?
#9
Report 4 years ago
#9
(Original post by Absent Agent)
Well, what I'm trying to say is that, silly as it sounds, proving that "x is rational" is false does not mean that "x is irrational" is true, even though it might actually be the case that x is indeed irrational, because we have not extinguished the possibility that" x is not irrational" without inferring its truth from the truth of its negation.

edited the part in bold.
In reply to your edited text - we have though.

By definition of an irrational number (literally "not rational") then "x is not irrational" is the same as "x is not (not rational)" = "x is (not not) rational" = "x is rational" which we have assumed by hypothesis ("...proving that "x is rational" is false...") is false. Therefore we have that "x is not irrational" is indeed false.
1
reply
Absent Agent
Badges: 21
Rep:
?
#10
Report Thread starter 4 years ago
#10
(Original post by Mathlete18)
In reply to your edited text - we have though.

By definition of an irrational number (literally "not rational" then "x is not irrational" is the same as "x is not (not rational)" = "x is (not not) rational" = "x is rational" which we have assumed by hypothesis ("...proving that "x is rational" is false..." is false. Therefore we have that "x is not irrational" is indeed false.
Yeah, that makes intuitive sense to me. But can we apply this in the proof that root(2) is irrational, by first assuming that root(2) can somehow be expressed such that it would be irrational and then we prove that it's true?
1
reply
Mathlete18
Badges: 2
Rep:
?
#11
Report 4 years ago
#11
(Original post by Absent Agent)
Yeah, that makes intuitive sense to me. But can we apply this in the proof that root(2) is irrational, by first assuming that root(2) can somehow be expressed such that it would be irrational and then we prove that it's true?
Hmm now that's a whole different ball game!! I get what you're asking though, and I suppose all I can say is that very question is a good reason as to why proof by contradiction is so powerful!

The issue lies in how do you represent a generic number as being irrational? Representing a rational number is easy since it is defined as being expressible as the quotient p/q of two integers, p and a non-zero q. Whereas being irrational is therefore defined as not being able to represented as such. It doesn't have any uniquely expressible form with which to test it's properties.

Another issue with the idea of assuming root(2) is indeed irrational is that there's no value in anything you deduce from therein out because a false can imply a truth so even if you get results that are true there's nothing to imply your initial assumption was true as well. However truths cannot imply falsities which is why, with proof by contradiction, if you reach a falsity you must have started with a false, and therefore the negation of your original assumption must be true.
0
reply
Mathlete18
Badges: 2
Rep:
?
#12
Report 4 years ago
#12
(Original post by Absent Agent)
Yeah, that makes intuitive sense to me. But can we apply this in the proof that root(2) is irrational, by first assuming that root(2) can somehow be expressed such that it would be irrational and then we prove that it's true?
Looking on here, it appears there are constructive proofs though...just giving them a read myself now

https://en.wikipedia.org/wiki/Square_root_of_2
0
reply
Mathlete18
Badges: 2
Rep:
?
#13
Report 4 years ago
#13
(Original post by Mathlete18)
Looking on here, it appears there are constructive proofs though...just giving them a read myself now

https://en.wikipedia.org/wiki/Square_root_of_2
That's actually very clever - it basically proves that the difference between root(2) and any rational number (a/b) is always greater than or equal to 1/3b^2 and so cannot itself be a ration number or there would exist a p and q such that root(2) = p/q and therefore setting a = p and b = q would yield root(2) - (a/b) = 0 #
0
reply
Absent Agent
Badges: 21
Rep:
?
#14
Report Thread starter 4 years ago
#14
(Original post by Mathlete18)
Hmm now that's a whole different ball game!! I get what you're asking though, and I suppose all I can say is that very question is a good reason as to why proof by contradiction is so powerful!

The issue lies in how do you represent a generic number as being irrational? Representing a rational number is easy since it is defined as being expressible as the quotient p/q of two integers, p and a non-zero q. Whereas being irrational is therefore defined as not being able to represented as such. It doesn't have any uniquely expressible form with which to test it's properties.

Another issue with the idea of assuming root(2) is indeed irrational is that there's no value in anything you deduce from therein out because a false can imply a truth so even if you get results that are true there's nothing to imply your initial assumption was true as well. However truths cannot imply falsities which is why, with proof by contradiction, if you reach a falsity you must have started with a false, and therefore the negation of your original assumption must be true.
(Original post by Mathlete18)
Looking on here, it appears there are constructive proofs though...just giving them a read myself now

https://en.wikipedia.org/wiki/Square_root_of_2
Yeah, I think I'm beginning to make sense of it all. And thanks for the link! I did see that before, but I was more interested in the conceptual understanding of it, which I think I'm starting to gain.
0
reply
Mathlete18
Badges: 2
Rep:
?
#15
Report 4 years ago
#15
(Original post by Absent Agent)
Yeah, I think I'm beginning to make sense of it all. And thanks for the link! I did see that before, but I was more interested in the conceptual understanding of it, which I think I'm starting to gain.
Glad to hear it! Delving into the really philosophical side of things, technically I should point out that Proof by Contradiction relies on what's called "The Law of the Excluded Middle" ~ Basically that either a statement is true, or it's negation is true.

Worth a read if you're interested:

https://en.wikipedia.org/wiki/Law_of_excluded_middle
0
reply
Mordencranst
Badges: 0
Rep:
?
#16
Report 4 years ago
#16
Also on the really philosophical side of things. If you really wish to pursue this line, there's an entire field of intuitionistic logic which rejects the law of the excluded middle (thought not that A&¬A is necessarily false) and more to the point rejects one of the central pillars of proof by contradiction, that ¬¬A is tautologically equivalent to A (thus making the whole edifice of proof by negation flawed, given that the best a reductio ad absurdum based proof can do is lead you to ¬¬A for some A). I won't go into it here, but there are a lot of (quite technical) argument motivating logical and mathematical intuitionism. The OP's doubts are by no means either unique or easily answered.
1
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

Should the school day be extended to help students catch up?

Yes (96)
27.51%
No (253)
72.49%

Watched Threads

View All