The well known proving method by "reductio ad absurdum" consists of deducing a false statement Q from a hypothesis P. Accordingly, from P => Q we obtain ~Q => ~P.
Sometimes this method is extended to paradoxes. That is to say, from a hypothesis P we deduce a paradox (Q ~Q), and as a consequence P is rejected.
Notice that a paradox is neither false nor true. The negation of a false statement becomes true and vice versa. By contrast, the negation of a paradox becomes the same paradox. I think that paradoxical situations due to their nature to the construction method. Accordingly, they are independent from any axiom system.
To illustrate this topic consider the following paradox.
The well-know novel by Cervantes "Don Quijote", contains the next story.
In a small town, there was a bridge at the beginning of which a policeman ask each passerby which is his goal. If his answer is correct, nothing occurs. By contrast, if the answer is not correct, at the end of the bridge, an executioner must kill him.
Once upon a time, when the policeman asked a passerby for his goal, he answered: I am going to be killed by the executor.
Indeed, if the executor kills him, then his answer is true, and he must not be killed. By contrast, if the executor does not kill him, then his answer is false, and he must be killed.
Which are the inconsistent axioms in this case? Have we to deduce that bridges do not exist? Maybe, do not exist policemen or executioners? Maybe, do not exist either answers or questions?
Juan-E, the example you give is exactly logically equivalent to a whole class of such conundrums, all the way to and including Gödel's incompleteness theorem itself.
They're sometimes called 'nonanswerable statements' which is a better descrition than paradoxes, but I would say that there is a semantic inconsistency in your question : reduction ad absurdum does not involve nonanswerable statements, but indeed fasified propositions, and such demonstrations are an essential tool in establishing proof. For instance, one can quite very easily demonstrate the invariability of the speed of light with a simple "reductio ad absurdum" argument.
Narrowly defined paradoxes are useful in proofs that involve the very essence of what a paradox is, which in turn can lead to profound insights into reality: e.g. , well, Gödel's proof.
For a solid book-length discussion and examples of "reduction to the absurd" used in proofs, and the logical limitations of paradoxes, read Noson Yanofsky 's "The Outer Limits of Reason: What Science, Mathematics, and Logic Cannot Tell Us"
Dear H. Chris,
Perhaps I have not explained correctly, or perhaps you have not understand my ironic style. I know that "reduction ad absurdum does not involve nonanswerable statements". This is why I criticize that sometimes it is confused.
A classical example can be Russell's paradox. In a first stage, was interpreted as a proof for the inconsistence of set theory. Now, the consequence of Russell paradox is not to reject the axioms of set theory. By contrast, what is rejected is the construction method underlying in this paradox. Accordingly, what is rejected is to consider as a set the set of all sets, or each non extensible set.
In spite of being true or false, Cantor's theorem is shown frequently on similar methods.
For instance, see this article by A.A.Zenkin
http://www.ccas.ru/alexzen/papers/CANTOR-2003/Zenkin%20BSL-2.pdf
Likewise, in this one
https://www.researchgate.net/publication/258316557_Yet_another_paradox_in_Set_Theory._Cantor's_Theorem_revisited
I have proved that, by means of other classical method for Cantor's Theorem, it is possible to shown the non-existence of an existing function.
Article Yet another paradox in Set Theory. Cantor's Theorem revisited
Juan,
your logic is not my logic.
Your Q ~Q is simply a false proposition (whatever the truth-value of Q is).
Calling this proposition a paradox should neither help nor harm. Nevertheless it harmed you by suggesting you the statement 'a paradox is neither false nor true' which may be right in some other context but not when reasoning on indirect proofs in the framework of propositional logic.
Dear Ulrich,
I have not any own logic. However, one of the foundational logical laws states that if a predicate is false its negation is true. Accordingly, if you assume that
Q ~Q
is false then its negation ~(Q ~Q) must be true. According to the Morgan Law,
~(Q ~Q) is equivalent ~Q Q, and by virtue of the commutativity of , the later leads to the initial one Q ~Q. Thus, your claim that Q ~Q is false implies that it is true. This is the consequence or the universal logical laws.
I guess that your claim is a consequence of your personal preferences or intuition. By contrast, my proof is impersonal and can be carried out by a computer.
Nevertheless, if you can obtain your claim from the laws of logic, I will appreciate your contribution.
All paradoxes I know, included the Russell's one, fit into this pattern (O ~Q).
Somebody call it nonanswerable statement. But as far as I know, nonanswerable is not a truth-value. In dichotomic logic, the only truth-values are TRUE and FALSE.
Best regards.
Juan,
The negation of an equivalence does not work as you assume: actually
~(A B) (A ~B) (a bit anti-suggestive but true).
So the negation of the false proposition Q~Q is the true proposition QQ. No paradox! To come back to proofs: If one was able to show
P => (Q~Q) one concluded something definitely FALSE. This can only happen for P FALSE (you recall: from a false premise you can deduce everything) . Hence we have proved ~P. Fully conventional application of propositional logic. Never mind.
The statement " I am going to be killed by the executor." is a statement in future tense. You cannot tell if its true or false, at most that it is probable.
Dear Oscar.
I can say that it will be true or false in the future when the passerby passes the bridge.
Suppose that tomorrow you add two apples to a box that contains three. You can say that the box will contain 5 apples. Of course, you can die today and will not be able to add the apples. It does not matter. The logical laws will keep in the future. The claim is true under the condition that you will add the two apples.
Dear Ulrich,
The expression Q ~Q is the conjunction of both (Q => ~Q) ⋀(Q ~Q)⋁(~Q => Q) (Morgan law). Both statements are contraditions. Therefore, assuming that Q ~Q is false leads to a contradction. By reductio ad absurdum, Q ~Q must be true. As you can see, the assumptoion that Q ~Q implies that it is true.
To see this fact, I have only used the Morgan law together with the method reductio ad absurdum. Can you prove that this laws are wrong?
~(Q => P) = ~Q
According to De Morgan's laws the negation of a conjunction
is a disjunction of negations.
~((Q => ~Q) ⋀(Q ~Q) V ~(~Q => Q)
~(~Q V ~Q) V ~(~~Q V Q)
Q V ~Q
It is a tautology, as expected. The negation
of a contradiction is a tautology.
Regards,
Joachim
Dear Joachim,
Let us see your derivation:
1) ~((Q => ~Q) ⋀(Q ~Q) V ~(~Q => Q)
3) ~(~Q V ~Q) V ~(~~Q V Q)
4) Q V ~Q
How can you obtain 3) from 2) ?
You are supposing that ~(Q => ~Q) is the same that ~(~Q V ~Q) . I think that you forget to remove a negation. The derivation must be as follows.
~(Q => ~Q) leads to ~(Q ∧ ~Q), and the latter leads to (~Q ∨Q). In addition, in the step 3) you add a new negation without substituting ∨ by ∧. I think that 2) do not lead to 3).
In addition, Q V ~Q is a tautology provided that the disjunction is an exclusive OR.
But you forget that it is derived from (Q => ~Q), which negates the exclusivity. Accordingly Q V ~Q cannot be exclusive.
Oh Juan,
you made a simple error in a simple logical argument and can't see it even after your nose was pushed on it? Perhaps Joachim's fully spelled out version will convince you. Thanks Joachim.
x=>y is equivalent to ~x V y.
x y x=>y
0 0 1 Ex falso quodlibet sequitur
0 1 1 Ex falso quodlibet sequitur
1 0 0
1 1 1 Verum sequitur ex quodlibet
Regards,
Joachim
Dear Joachim, are you sure?
See an example
X denotes the stament "Merkel is dead"
Y denotes the statement "Merkel is German"
Of course Y is true because Merkel is German. By contrast, X is false; In addition the disjunction ~X ∨ Y is true because so are both ~X and Y. Accordingly it is not an exclusive OR.
Can you deduce that "Merkel is dead" leads to "Merkel is German"?
Are all dead people German?
As I have said before, X => Y is equivalent to ~X∨Y provided that the disjunction is an exclusive OR. However, when you start from Q ~Q, the disjuntion Q∨~Q cannot be exclusive, because you are assuming that Q is true if and only if ~Q is also true.
To Ulrich,
I think that Joachim does not convince me. To convince me he must show that all dead people are German.
Juan-Esteban,
the problem here is that you are confusing propositional
logic with predicate logic. Quantifiers like "for all", and
"there is" are not part of propositional logic.
> As I have said before, X => Y is equivalent
> to ~X∨Y provided that the disjunction
> is an exclusive OR.
No, it's the simple OR. Unfortunately there is
no English version, but you will understand the table:
http://de.wikipedia.org/wiki/Implikation#Wahrheitsfunktionale_Implikation
See also
http://es.wikipedia.org/wiki/L%C3%B3gica_proposicional#Formas_normales
Regards,
Joachim
Dear Joachim,
You are right and your contributions in RG are always cleaver, but your argument does not fit into this thread.
As you can see, the example of "Merkel is dead" etc.. does not fit into your argumentation. This thread does not deal with propositional logic, but proving methods. When I write p => q, I am saying that there is some method that starting from p leads to q. By contrast, you mean that q is true whenever so is p, disregarding the existence of any proving method.
The equivalence you have exposed is an abstraction. This is not the topic of this thread. This thread is entitled "Can paradoxes be used in proofs? ". Accordingly this thread deals with proofs, that is, with proving methods. Even multivalued logic can be involved in this thread.
Finally, what Ulrich has claimed is that ( Q ~Q) is false, and I have rejected this claim. To be right, Ulrich interprets that this equivalence cannot be done. This interpretation does not fit into this thread. I am supposing that there is a method that starting from Q leads to ~Q, and starting from ~Q leads to Q; for instance see Russell's paradox. Accordingly, if the deriving method exists, the equivalence exists, and we have to assign a true value to ( Q ~Q). This is not possible in dichotomic logic because if you suppose that it is true, one can deduce that it is false and vice versa. To assign a truth-value avoiding any contradiction, it is to be 1/2, for instance in the scope of a fuzzy logic.
Otherwise, the Russell's paradox would be a nonsense that would be caused laugh to scientific community. It is just in this case when the paradox is avoided by rejecting its constructing method. Accordingly, to be called set, any collection is required to be extensible. However, in other cases, paradoxes are accepted in proving methods. I have exposed some of them, and this is why I have opened this thread.
Finally, if, according to Ulrich, Russell's paradox is false, then by reduction ad absurdum the axioms of set theory would be false. This is not the case. What is rejected is the paradox construction instead. Accordingly, the paradox is rejected instead of axioms of set theory. However, paradoxes are used in some proving methods. This is the question.
Best regards and thank you for your clever contribution.
Juan-Esteban
P.S.
To see that (Q ~Q) cannot be false, suppose that the truth-value of Q is x. As a consequence the truth-value of ~Q must be 1-x. The equivalence leads to x = 1-x; therefore 2x=1 and x = 1/2. This result requires a multivalued logic. In dichotomic logic cannot assign any truth value either to Q or ~Q.
Juan,
when you tried to compute the negation of ( Q ~Q) you argued with rules of double negation and Morgan laws. Now, that it is clear that you simply mistook
~A~B for the negation of AB, such reasoning no longer fits the thread.
You really should refresh your memory with respect to the logic of proofs.
Dear Ulrich,
The question is very simple. The truth-value of the statement ( Q ~Q) depends on the truth-values assigned to each component. If you claim that ( Q ~Q) is false, your are assigning the truth-value 0 to ( Q ~Q) .
What is the truth-value that you assign to Q in order to obtain 0? Notice that two statements are equivalent if and only if both have the same truth value. Accordingly, ( Q ~Q) means that the truth-value of Q is equal to the one of ~Q.
Accordingly the equation that the truth values must satisfy is x = 1 -x. This equation has no integer solution. The only solution is 0.5. Since dichotomic logic only admits integer truth-value, that is, 0 or 1, the problem of assigning a truth-value to an statement Q satisfying the relation ( Q ~Q) has no solution in dichotomic logic.
If you do not agree with me, please, say what is the truth value that you assign to Q in order to obtain 0 for the statement ( Q ~Q) .
Of course, you can negate ( Q ~Q), that is to say, you can negate that this formula can be proved. However, paradoxes arise from procedures in which such a formula is proved. For instance, see Russell's paradox. In the Russell paradox, the equivalence ( Q ~Q) is proved, consequently you cannot reject this equivalence. What is rejected is the construction method.
Summarizing: ( Q ~Q) is a paradox provided that can be proved, therefore this statement cannot be rejected. What must be rejected is its construction method.
What your are claiming is that ( Q ~Q) cannot be deduced, but this is your bad interpretation of the question. Paradoxes can be deduced. See this link,
http://en.wikipedia.org/wiki/Russell's_paradox
Dear Ulrich,
I recommend you to take a glance at the fuzzy set theory and fuzzy logic.
Denoting by µ:P -> [0,1] the function sending each statement into its truth-value, fuzzy logic is based upon this axiom.
Ax1) P => Q if and only if µ(P) ≤ µ(Q).
As a consequence, P Q if and only if µ(P) = µ(Q).
Fuzzy sets consit of assignig truth-values in [0,1] to membership statements like x ∈ E.
Accordingly, if µ(x ∈ E) = µ(x ∉E), then (x ∈ E) (x ∉ E). This is an example in which the statement Q ~Q is true.
Dear Peter,
I am not a believer in any logic. By contrast, I think that logical systems are empiric sciences that only have to be accepted by their success in their applications. According to this fact, what I have stated in my message are only axioms of other authors. If you think that any of them is wrong, here you have the bibliography. Any mistake you can find in any of these texts, you can expose to the corresponding author.
Kind regards.
Juan Esteban
Bibliography
J. Baldwin, “A New Approach to Approximate Reasoning using a Fuzzy Logic”. Fuzzy
Set and Systems, 2, pp. 309.325, 1979.
• J.L. Castro, M. Delgado, “Fuzzy Systems with Defuzzification are Universal
Approximators”. IEEE Trans. on Systems, Man and Cybernetics 26, pp. 149-152, 1996.
• D. Driankov, H. Hellendorn, “Fuzzy Logic with Unless-Rules”. Report IDA- RKL-92-TR
50, Laboratory For Representation of Knowledge in Logic, Dept. of Computer and
Information Science, Linkoping University, Sweden , 1992.
• D. Dubois, H. Prade, “Gradual Inference Rules in Approximate Reasoning”. Information
Sciences, 61, pp. 103-122, 1992.
• G. Epstein, “Multiple-Valued Logic Design: An Introduction”. Institute of Physics
Publishing, Bristol, U.K., 1993.
• M.M. Gupta, J. Qi, “Theory of T-norms and Fuzzy Inference Methods”. Fuzzy Sets and
Systems, 40, pp. 431-450, 1991.
• B. Kosko, “Fuzzy Systemas are Universal Approximators”. IEEE Trans. on Computers,
43(11), pp. 329-332, 1994.
• J.C. Muzio, T. Wesselkamper, “Multiple-Valued Switching Theory”. A. Hilger, Bristol,
U.K., Boston, 1986.
• V. Novak, “Fuzzy Logic as aBasis of Approximate Reasoning”. In Fuzzy Logic for the
Management of Uncertainty, ed. L.A. Zadeh and J. Kacprzyk, pp. 247-264. Wiley
Interscience, New York, 1992.
• W. Pedrycz, “Fuzzy Control and Fuzzy Systems”. RSP Press, New York, 1993.
• W. Pedrycz, “Fuzzy Sets Engineering”. CRC Press, Boca Raton, FL, 1995.
• H. Rasiowa, “Toward Fuzzy Logic”. In Fuzzy Logic for the Management of Uncertainty,
ed. L.A. Zadeh and J. Kacprzyk, pp. 5-25. Wiley Interscience, New York, 1992.
• N. Rescher, “Many-Valued Logics”. McGraw-Hill, New York, 1969.
• E. Trillas, L. Valverde, “On Implication and Indistinguishability in the Setting of Fuzzy
Logic”. In Management Decision Support Systems Using Fuzzy Sets and Possibility
Theory, Eds. J. Kacpryzk, R.R. Yager, pp. 198-212, Verlag, TÜV Rheinland, Köln, 1985.
• Y. Tsukamoto, “An Approach to Fuzzy Reasoning Method”. In Advances in Fuzzy Set
Theory and Applications, ed. M. Gupta, R. Ragade, R. Yager, pp. 137-149. North-
Holland, Netherlands, 1979.
• R.R. Yager, “Approximate Reasoning as a Basis for Rule-Based Expert Systems”. IEEE
Trans. on Systems, Man and Cybernetics, 14(4), pp. 636-643, 1984.
• L.A. Zadeh, “Outline of a New Approach to the Analysis of Complex Systems and
Decision Processes ” IEEE Trans. on Systems, Man and Cybernetics, 3(1):28-44, 1973.
• L.A. Zadeh, “The Concept of a Linguistic Variable and its Application to Approximate
Reasoing” (parts I and II). Information Sciences, 8, pp. 199-249, pp. 301-357, 1975.
• L.A. Zadeh, “A Theory of Approximate Reasoning”. In Machine Intelligence, ed. J.
Hayes and J. Michie, vol. 9, pp. 149-194, Halstead Press, New York, 1979.
• L.A. Zadeh, “Fuzzy Logic”. IEEE Computer, 21(4), pp. 83-92, 1988.
• L.A. Zadeh, “Knowledge Representation in Fuzzy Logic”. IEEE Trans. on Knowledge
and Data Engineering, 11(1), pp. 89-100, 1989.
• L.A. Zadeh, “Fuzzy Logic, Neural Networks and Soft Computing”. Communications of
theACM, 37(3), pp. 77-84, 1994a.
• L.A. Zadeh, “Soft Computing and Fuz
Statements refering to the future cannot be true or false in the moment they are done. I mean, it is not correct to judge the truth value of the statement "I came to be killed by the executor" depending of what happens later. For example, the executor can have a stroke and die before he kills someone, etc. One can establish the truth by hypnosis or using a lie detecting system - and we see if the person says the truth or not about his goal. Depending of his behavior, we can later kill him. Someone can have the goal "to be killed at the end of the bridge" and never realize this goal, because he told the truth. It is really in the nature of things that some goals cannot be realized with given methods. Someone more inventive has the goal to be killed, tells that he has another goal, is detected as a liar and is killed. This time there is no paradox.
Dear Mihai,
Indeed, the future becomes present, and until that moment, there is no paradoxical situation.
The paradox arises when the executor must take a decision.
No. A paradox cannot be used in a proof.
A paradox only shows that logic and mathematics can be incorrectly applied.
The liar paradox is used in several forms. The bridge situation had 4 judges to determine the truth of the statement about destination and purpose. A person can only be executed if the destination and purpose are not met. The judges must either follow the person or obtain other evidence of lack of intent. A person whose destination and purpose is to be hanged after crossing the bridge must be hanged. Otherwise, the judges have not done their job, which is to ascertain if the person is telling the truth. After the hanging, the judges can declare he did not lie and that they allowed him to reach his goal and destination.
>The well known proving method by "reductio ad absurdum" consists of deducing a false statement Q from a hypothesis P. Accordingly, from P => Q we obtain ~Q => ~P.
This method holds iff you tray to prove the sentence W which is formulated in consistent theory T based on bivalent logic or intuitionistic logic. For example ZFC is inconsistent.
- Badges
- Science topic