Philosophy of Mathematics: proof by contradiction
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 retard 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 retard 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 [text]\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?
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 retard 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 retard 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 [text]\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?
(edited 7 years ago)
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 retard 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
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 retard 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
(edited 7 years ago)
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 retard 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
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 retard 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 " is rational is false" does not prove that the statement " 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.
(edited 7 years ago)
Original post by Absent Agent
So, for example, the proof that " is rational is false" does not prove that the statement " 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.
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, [text]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?
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, [text]e^{i\pi}+1=0
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.
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.
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.
(edited 7 years ago)
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?
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.
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.
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.
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?
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.
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
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
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 #
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.
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
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.
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
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.
Quick Reply
Related discussions
- proof by contradiction
- Maths and Philosophy?
- KCL deferred entry
- Regretting degree choice
- N/A
- N/a
- Recursion Q
- A2 maths Proof by Contradiction
- University Options for Math/Statistics and Philosophy Joint Degree
- kings clearing
- proof by contradiction
- supercurricular ideas for mathematics and philosophy?!?!
- Would this A Level combination be okay?
- unsure on uni courses
- Mathematics and Philosophy Entry Grades
- Managing Workload at Uni
- A levels for PPE course ( philosophy, politics and economics )
- Lancaster Uni Uncovered - Tips and Useful links
- Is maths and philosophy just as employable as a maths degree?
- Computer Science, AI - Lancaster vs Sheffield
Latest
Last reply 1 minute ago
yet to receive a woodhouse interviewLast reply 2 minutes ago
Official London School of Economics and Political Science 2024 Applicant ThreadLast reply 4 minutes ago
Medical doctor degree apprenticeship 2024Last reply 5 minutes ago
Children to no longer be prescribed puberty blockers, NHS England confirmsLast reply 10 minutes ago
UAL Bsc Fashion Management and fashion marketingLast reply 11 minutes ago
Choosing Subjects for S5 to study Software engineering in the UkLast reply 12 minutes ago
narrowly missing offer conditionsLast reply 12 minutes ago
R u 18-25 & studying in a England Uni, spare a few mins to fill my survey. 1 wk left.Last reply 18 minutes ago
Official University of St Andrews Applicant Thread for 2024Last reply 18 minutes ago
LAW: How to answer a problem question in Contract LawLast reply 20 minutes ago
LSE anthropology and law 2024Posted 23 minutes ago
UNIT 7 ASSIGNMENT 2 D3 AND 4 (health and social care)Last reply 25 minutes ago
LSE International Social and Public Policy and Economics (LLK1) 2024 ThreadLast reply 25 minutes ago
JK Rowling in ‘arrest me’ challenge over hate crime lawLast reply 26 minutes ago
Official: Queen's University Belfast A100 2024 Entry ApplicantsTrending
Last reply 1 day ago
Why is the political left now censorious and authoritarian??Last reply 1 week ago
TSR Goes Green: How important will the environment be in this year's election?Last reply 3 weeks ago
Is University of Birmingham prestigious and respected well enough in UK ?Trending
Last reply 1 day ago
Why is the political left now censorious and authoritarian??Last reply 1 week ago
TSR Goes Green: How important will the environment be in this year's election?Last reply 3 weeks ago
Is University of Birmingham prestigious and respected well enough in UK ?
