8

When I once realised I don't really understand how and why proof by contradiction works, I started reading about it. And apparently I wasn't the only one who felt there's something wrong about it - constructivists and intuitionists do not accept the law of excluded middle. This is what shocked me the most - I thought logic is something that has been already settled a long time ago. It appears the truth is very different though. Logic is an attempt to describe and systematize the way we reason. And if some people accept the law of the excluded middle, and some don't, then it feels the same as if some people believed 1+2=3, and others 1+2=4. If we can all agree on how basic arithmetic works, why don't we have consensus in more complicated areas of logic?

Human thought is not based on logic, but logic is based on human thought. Do you believe we will eventually have a consensus in this area? People try to solve much more complex problems, such as P vs NP. But shouldn't we focus on the basic laws of reasoning first, especially if we have doubts in that field?

Mathematics exists because of the assumption we think in the same way. So it has to be the case, maths can't be based on our personal opinions or feelings. The existence of constructivism makes it look that way though. I'm writing these words assuming you will understand them the same way I do. Otherwise, What would be the point in writing this?

  • 1
    You can see this post. Constructivism has "reasonable" grounds and constructive math is "sound" : we can discuss about it. – Mauro ALLEGRANZA Apr 25 '14 at 16:50
  • See also this post for some references. – Mauro ALLEGRANZA Apr 25 '14 at 17:04
  • 1
    It seems constructivism is making a comeback. See this highly entertaining and informative talk, The Five Stages of Accepting Constructive Mathematics. video.ias.edu/members/1213/0318-AndrejBauer – user4894 Apr 25 '14 at 17:46
  • I mean the very fact of debating whether to stick to constructivism or platonism or anything else is itself weird. Because if we are thinking which logic to choose, then maybe one day someone will say 1+1=3. – user107986 Apr 25 '14 at 18:15
  • 1
    @senderle: I agree with your observation on mathematicians' preference for constructive proofs. But they do so because non-constructive proofs sometimes don't give them much insight into why certain mathematical statements are true, while constructive proofs do. Intuitionists (though not all constructivists) reject the law of excluded middle on independent, mostly philosophical grounds. – DBK May 22 '14 at 20:50
4

Several things might be important to note. The first is that formal logic is relatively recent, by mathematical standards: it's modern version is about a century old. On the other hand informal reasoning has been around for quite some time, and there is little doubt that we can do good mathematics with it, as others have noted.

The second is that while some may reject the use of the excluded middle or even the use of the principle of explosion (also known as ex falso quodlibet), the relationship between these principles of reasoning are well explored. In particular:

  1. Classical logic is consistent if and only if intuitionistic logic is as well, as shown by the Gödel-Gentzen translation
  2. The principle of explosion is consistent if and only if minimal logic (which removes this principle) is as well. See this paper for a nice survey.

The combination of 1 and 2 shows that there is no fundamental disagreement between these various formulations of logic, just about what the statements in various logics express. But this is more a philosophical question, and mathematicians are not necessarily interested in these.

Note that there are deeper disagreements about which principles are acceptable in mathematics, more or less related to the question of finitism. In this case, there is no hope for a clear resolution as above, since consistency of non-finitary systems can not be shown to be equivalent to that of finitary systems.

This last point is essentially the failure of Hilbert's Program for building a consensus about the consistency and completeness of mathematical foundations. However, despite the prima facie failure of this program, reverse mathematics and proof theory can be seen as a rigorous way to explore the different viewpoints and find a compromise.

My conclusion is that, while these are very interesting philosophical questions that are still being explored, there is no fundamental disagreement about what constitutes a sound mathematical argument.

  • What logic was used by Godel in his incompletness theorem? Did he use the law of excluded middle? – user107986 Apr 30 '14 at 19:27
  • Actually Gödel was quite careful to not use classical reasoning to prove the incompleteness theorem, as he knew that if he did, people would likely take it to be an objection to EM rather than the more fundamental fact of incompleteness of arithmetic. Gödel was quite remarkable in his ability to understand and transcend the currents of thought of his time period. – cody May 1 '14 at 15:06
  • Hasn't constructivism the rejection of LEM started with this?: en.wikipedia.org/wiki/Controversy_over_Cantor's_theory "The rejection of Cantor's infinitary ideas influenced the development of schools of mathematics such as constructivism and intuitionism." – user107986 May 3 '14 at 14:12
3

I want to emphasize only a point, in order to give you some hints for reflections.

I believe that, history of science and of human knowledge shows us that is very very difficult to assert that there are "principles" totally immutable and indubitable.

See Euclid's Elements : Common Notions n°5 :

The whole is greater than the part.

For two millenia there were quite a great "consensus" about this kind of "assumptions".

But see Georg Cantor :

Cantor defined countable sets (or denumerable sets) as sets which can be put into a 1-to-1 correspondence with the natural numbers, and proved that the rational numbers are denumerable.

In rough words, the natural numbers are are proper subset of the rational, but we have that we as much rational numbers as natural ones.

A similar fact has been already discovered by Galileo Galilei with the so-called Galileo's paradox :

So far as I see we can only infer that the totality of all numbers is infinite, that the number of squares is infinite, and that the number of their roots is infinite; neither is the number of squares less than the totality of all the numbers, nor the latter greater than the former; and finally the attributes "equal," "greater," and "less," are not applicable to infinite, but only to finite, quantities. [from Galileo Galilei, Dialogues concerning two new sciences (1638), transl. Crew and de Salvio, Dover. pp. 31–33.]

  • "history of science and of human knowledge shows us that is very very difficult to assert that there are "principles" totally immutable and indubitable" Then why seek for these principles, if they are NOT principles because, as you describe, they depend on personal opinions. – user107986 Apr 25 '14 at 22:20
  • You are slightly lensing the idea about whole and the part. Cantor did not show (and could not) that whole is same as part -- he showed that they are EQUALLY infinite, and equality of infinities is not same as equality of finite sets. BUT! By absolute value whole is always bigger than part. It just follows from definition (devil unbless definitions!). "Problem" only arises when you try to mentally twist part to become as big as whole (exactly what Cantor did by defining infinite subsets). No problem here. – Asphir Dom Apr 25 '14 at 23:03
  • @AsphirDom - thanks for your suggestion. What I want to express with the above example is that in an "obvious" sense, we have "more" natural numbers than even ones (see Galileo). According to Cantor's definition, with infinite set we need another way to "compare" the respective "magnitude"; with this new way, we have that an infinite set and its proper subset have the "same magnitude". Thus, when we "count" infinite set, we have that (seemingly) the "whole is greater than its part" and that the whole and its part have the same number of members. A contradiction ? 1/2 – Mauro ALLEGRANZA Apr 26 '14 at 9:15
  • No: a "change of meaning" in the methods we use to "compare" the magnitudes of mathematical objects. 2/2 – Mauro ALLEGRANZA Apr 26 '14 at 9:16
1

Classical two valued logic works well in mathematics and computer science, where a declaration that all statements are in principle either true or false is acceptable. The cost of this declaration is that only a limited class of grammatical, meaningful statements can be tested and evaluated using the methods of formal logic. This is a very large and important class, but not a comprehensive one.

Outside mathematics where the truth of statements is more a matter of observation and where the careful definitions needed by logicians and philosophers in order to ensure that statements are either true or false, the law of the excluded middle is subject to more dispute.

There are statements for which we lack information about whether they are true or false, there are paradoxical statements such as the liar paradox, there are statements that appear to be partly true, there are concerns about "necessarily" versus "contingently" true, and there are concerns about true versus provable.

There have been many logicians who have doubted the law of the excluded middle, and there are many approaches to extend logic to deal with more than the simple cases of "True" and "False" for statements.

There are multi-valued logics, the closely related concepts of fuzzy logic, intuitionistic logic, modal logic, relevance logic, and paraconsistent logic, all of which share some but not all of the assumptions and techniques of classical two-valued logic in attempts to deal with its limitations.

These various approaches overlap to a significant degree, but so far no one of them has established a clear superiority over the others, and they all have serious limitations compared with classical two-valued logic. There appears to be a strong professional rivalry among logicians of these various schools combined with a lack of understanding of competing methods and approaches. There seem to be few who believe that a more unified approach is either possible or interesting.

1

After you have worked with proof by contradiction for a while, you will wonder what the controversy was all about. It will seem like an indispensable tool and its use will become second nature. A few people have just decided not to use this tool for some reason -- like some people decide for reasons of their own not to use power tools in carpentry.

  • Welcome to Philosophy.SE! Thanks for your answer. You might consider talking a little bit about the context of your argument -- grounding it in a text is probably the most straightforward way; but just suggesting further things to explore can be helpful to future readers too – Joseph Weissman Apr 29 '14 at 22:12
  • @JosephWeissman Thanks, Joseph. I have toned and parred it down a bit. I can't cite any text on this issue. I guess I just wanted to somehow reassure the OP that mathematics as widely practiced is not some house of cards on a foundation of sand. – Dan Christensen Apr 30 '14 at 3:12
0

Logic by creation is not something magical -- it is a cleverly made (long time ago, that is why cleverly) SCANNING tool. This mental method allows us to SCAN huge variety of rather simple everyday(everyscience) life examples and problems. Because it is a SCANNING tool it needs information which is carefully prepared for it. It can not operate on chaos, same way as you can not run browser if you did not boot up your OS.

PROBLEMS start if you don't see what logic is and begin to misuse it. This what happens with your original question of interest. Prove by contradiction was designed for VERY well prepared sets of information where the total combinations can be clearly seen and exclude each other.

Logic is not the method to think. It is method to analyze data. If you have no data or poor data there is nothing to use logic for. Thinking happens when you prepare your mental/emotional data.

  • "Prove by contradiction was designed for VERY well prepared sets of information where the total combinations can be clearly seen and exclude each other." Then what about very simple proofs using the law of excluded middle like Euclid's theorem? Do constructivists accept it? en.wikipedia.org/wiki/Euclid's_theorem#Euclid.27s_proof – user107986 Apr 26 '14 at 7:20
  • @user107986 - No; see my answer in this post : what all constructivists share is the rejection of the method of existence proof "by contradiction": if we want to show that a number with a certain property P exists, we have "to show" a number n such that P(n). We ara not licensed to assert that a number with a property P exists, only when we have derived a contradiction from the assumption that such a number does not exists. – Mauro ALLEGRANZA Apr 26 '14 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.