How do we know if a mathematical proof is valid?

Question

Georg Cantor has showed there are more real numbers than natural numbers in his diagonal argument. Assuming that two sets have the same size if we can make a pair up elements from set A with elements from set B. Now if we make a list of natural numbers, then no matter what list of real numbers we provide, there will always be another number that's not on the list (created by adding '1' to diagonal of the list, for example).

Now, it's a proof that there are more reals. But what if I told you, before Cantor, that there are equally many reals and natural numbers, because we can make a list of natural numbers and assign a real number to each natural number? I will tell you, look, it can't be the case there are more real numbers, because there are infinitely many nautral numbers and you will never run out of natural numbers to pair them up with real numbers!

Would it be considered a valid proof? Actually, wasn't it considered a valid proof until Cantor came up with his theory? What if there are other such theorems in mathematics commonly believed to be true, with accepted proofs, and some day someone will come up with a counterexample, disproving them? Does it mean we can never be sure if a mathematical proof is valid?

Your example would not be a valid proof. Or rather, it would be a valid proof for a different statement: What you have proved is that there are not more natural numbers than there are real numbers. — celtschk, Aug 20 '14 at 19:02
I do accept Cantor's diagonal argument. My goal was to show that if I told you there aren't more real numbers than natural numbers, I would probably manage to make people believe it, presenting a proof. The proof would be considered valid until someone would find a counterexample debunking my theorem - using diagonal argument. — user107986, Aug 20 '14 at 21:54
@user107986: No, according to what you wrote this was *not* your point. I don't think anybody ever doubted that there are not more natural than real numbers (well, there might have been some who thought the question did not make sense). However you presented it as a proof that there are *equally many* natural numbers as there are real numbers, which it is not. — celtschk, Aug 23 '14 at 07:31
I guess people before Cantor's set theory believed there are equally many natural and real numbers. My point, again, wasn't an attempt to disprove his theorem! I was just showing that we can easily construct a "proof" of some theorem that people will consider valid, until someone comes up with a counterexample! That's why I presented a proof that there are as many real numbers as natural numbers, which is wrong (and I know it). — user107986, Aug 23 '14 at 19:00
A mathematician would not consider a proof to be correct just because he believes the proven statement to be correct. And it is not hard to see that your proof does not prove that there are equally many natural and real numbers, even for someone who believes there are. — celtschk, Aug 24 '14 at 22:22
But mathematicians believe in a firm distinction between belief and proof. — AndrewC, Sep 11 '14 at 19:57
Yes, but the fact they believed it means they considered it a valid proof. Until Cantor presented his diagonal argument. — user107986, Sep 11 '14 at 20:11
I think Wittgenstein had some interesting things to say about this. He argued that people were misled in believing that Cantor had discovered a new fact, and argued that he really created a new method of dealing with infinite numbers. I agree with you 100% about mathematicians' beliefs about infinite sets. Cantor didn't discover anything, he described a new way of talking about maths that involved different levels of infinity based on the idea of a bijection and equipollence. It's still distinctly different from finite sets, and most people (including mathematicians) don't realise this — Franz, Jul 22 '17 at 08:10
Cantor's proof of the uncountability of the reals was not accepted for many years. Then it was accepted, now it is so fundamental to so much that it is practically gospel. But without this proof at the beginning, there would be a very different Set Theory. How do we know if any proof is valid? Well, as pointed out in other answers, many proofs are found to be invalid when someone comes along with a different perspective and finds the flaw in the original proof. Otherwise, the acclaim of peers does the trick. Taking Cantor as an example, many people have objected to his proof of the uncountabil — Jeremy C, Sep 22 '20 at 20:52

score 9 · Answer 1 · edited Sep 23 '20 at 02:06

9

Some comments.

1) Well before Cantor, it was already known that we may "have troubles" in comparing infinite collections of numbers ; see, at least, Galileo's paradox.

2) Of course, the purported proof : "that there are equally many reals and natural numbers, because we can make a list of natural numbers and assign a real number to each natural number" is simply wrong. We may pair, e.g. the natural number 2 with the real number 2.0, of course, but we will have in any case "unpaired" numbers like sqrt(2).

3) The history of mathematics is full of "wrong" proofs : they have been corrected. See for example Girolamo Saccheri's proof of Euclid's fifth postulate in his Euclides ab omni naevo vindicatus (Euclid Freed of Every Flaw - 1733).

4) Also if it is a "minority" part in the mathematics community, there are some mathematicians who do not agree on the validity of some methods of proof commonly used by the "mainstream" mathematicians; see Intuitionism in the Philosophy of Mathematics and Intuitionistic Logic.

edited Sep 23 '20 at 02:06

Mary

1,948
1
7
25

answered Aug 20 '14 at 09:22

Mauro ALLEGRANZA

35,764
3
35
79

1

To me, the existence of intuitionism is surprising. Some people must have had a reason to stop doing classical mathematics and move to intuitionism. What was the main reason for doing so? Also, there must be a reason why they are a minority. – user107986 Aug 20 '14 at 09:43
1

@user107986 - Try with the *SEP*'s entries for a useful introduction. You can see also this [post](http://philosophy.stackexchange.com/questions/10055/what-are-the-truth-values-of-intuitionistic-logic) for some discussion. – Mauro ALLEGRANZA Aug 20 '14 at 13:22
Dear me! User107986, intuitionism is not different from "classical mathematics". Classical maths is obviously very strongly rooted in what we now call intuitionism. You seem to be making a habit of misusing terminology. – nwr Aug 20 '14 at 21:51
@NickR Incorrect. Intuitionism is an unusual, minority approach, which contradics classical mathematics. Classical mathematics cannot be rooted in intuitionism because it preexisted for centuries. – AndrewC Aug 20 '14 at 22:45
@AndrewC Are you suggesting that Euclidean Geometry is not intuitional in its character. Wikipedia defines intuitionalism as : "That is, given a set of axioms, the only propositions that can exist are those that can be constructed, directly or indirectly, by these axioms. " – nwr Aug 20 '14 at 22:52
"We may pair, e.g. the natural number 2 with the real number 2.0, of course, but we will have in any case "unpaired" numbers like sqrt(2)." I don't think that is a sufficient argument against the OP's "proof". In my list of natural numbers, I might pair 3 with sqrt(2). No problem. I don't have to pair 3 with 3.0 -- since I've got an infinite number of naturals to play with I can just come back later in the list an maybe pair 120 with 3.0. – MattClarke Aug 21 '14 at 04:33
3

@NickR Absolutely. Intuitionism is a 20th century movement which rejected several aspects of classical mathematics, including the law of the excluded middle (that which is not true is false), so that proof by contradiction was not admitted. Euclid on the other hand, was completely happy with proof by contradiction and used it regularly. – AndrewC Aug 21 '14 at 06:00
@NickR - I strongly follow AndrewC's comment. I've used [Intuitionism](http://plato.stanford.edu/entries/intuitionism/) as the name of the math & phil school founded by Brouwer, according to the "standard" usage and the related SEP's entry. I'm not saying that they "discovered" the role of *intuition*. I do not know about "intuitionalism" ... – Mauro ALLEGRANZA Aug 21 '14 at 06:10
@user107986 Intuitionism is one of the reactions to the paradoxes that shook mathematics back then. Another response was formalism. Simplifying, it's because intuitionism frustratingly restricted the tools a mathematician could use in a proof, whereas formalism just restricted the sets a mathematician could construct, and the formalists painstakingly showed they could construct the sets mathematicians typically studied. "_Classes_" (with restricted operations) allowed collections that weren't sets, so you could reconstruct nearly all classical mathematics in formalism, but not in intuitionism. – AndrewC Aug 21 '14 at 06:15
@MauroALLEGRANZA It is impossible for me to fully reply to your comment in the allowable space. Let me say this: Euclidean Geometry is precisely the theory that follows from the five stated axioms. Its theorems correspond precisely to the straight edge and compass constructions which can be performed in the plane. Not only that, but it is a "complete" theory in the Godelian sense. Every theorem/construction can be proven/performed. It therefore has a strongly intuitionalist character, according to the wikipedia definition of intuitionalism I have stated in my previous comment. – nwr Aug 21 '14 at 16:25
@AndrewC If you are still interested, please refer to my comment to Mauro Allegranza (above). I am not suggesting that every aspect of Euclid is intuitional, only that it is strongly intuitional in its character. – nwr Aug 21 '14 at 16:30
1

As a new user to PSE, it is amazing to me that this question has received two up votes. Not only does the poster fail to understand what constitutes a valid proof, but he seems to think that the collective opinions of the greatest minds in the last 120 years of mathematics are all wrong, and that his naive hand waving proves it. Surely we have a duty to say why. – nwr Aug 21 '14 at 16:34
1

@NickR You have read the first couple of lines of the wikipedia entry, but have failed to grasp the difference between the intuitionists and classical mathematics. All formulations permit only those things which follow from the axioms, and all permit constructive proofs. The difference is not there, it's in what the intuitionists disallow. Reasoning purely from axioms is very much a formalist approach too. Saying Euclid's work was intuitionist in characcter is like saying Shakespeare was a postmodernist. It's both a meaningless anachronism and doesn't fit the facts. – AndrewC Aug 22 '14 at 00:08
@NickR Similarly, your assertion that Euclidian Geometry is complete would upset Godel, who proved that any mathematical theory cannot be both consistent and complete. We believe Euclidian Geometry is consistent, and thus we do _not_ believe it is complete. In Godel's work, _complete_ means that every truth is provable, not that every theorem has a proof. The term for a mathematical theory where every theorem has a proof is _a mathematical theory_! – AndrewC Aug 22 '14 at 00:13
@AndrewC It is a mathematical theorem that Euclidean Geometry is complete (in the Godelian sense). That means that every (truth) theorem which follows from the axioms can be proven. The theorems correspond exactly to the permissible straight-edge and compass CONSTRUCTIONS permissible in the plane. Completeness says that constructive proofs exist. It doesn't matter that Euclid may have used a reductio argument because a non-reductio argument exists. Inuitionism is about getting away from the "horrors" of Cantor and returning to "sound footing". I assume you are not a mathematician. – nwr Aug 22 '14 at 00:19
@AndrewC You also do not appear to understand Godels result, which applies to arithmetic, not geometry. – nwr Aug 22 '14 at 00:22
@NickR Hehe, I'd overlooked that whilst you can construct all integer multiples of some given length in Euclidian Geometry, it's not strong enough to express the first order logic of arithmetic. Oops. BTW, Completeness does _not_ say _constructive_ proofs exist for every theorem, it says every theorem is provable within the formal system. It has been proven that there are non-constructive theorems from classical logic that are unprovable in the intuitionist logic, so your assertion that there are intuitionist proofs for all of classical Geometry is false. – AndrewC Aug 22 '14 at 01:41
@NickR (A system doesn't have to _be_ arithmetic to be able to _express_ the first order logic of integer arithmetic, so whether it looks like geometric isn't relevent, it's the expressive power of the system that matters, but I assume you knew all that and were just using shorthand.) – AndrewC Aug 22 '14 at 01:43
@AndrewC Cheers dear. Godel's result requires that a system be able to perform arithmetic. It's proof shows that one can always construct a Diophantine equation that cannot be solved. Have a good night. I'm off to make dinner. – nwr Aug 22 '14 at 01:49
1

@NickR "I assume you are not a mathematician." As it happens, I have an MSc and PhD in Mathematics from one of the UK's top five mathematics research universities. If your *ad hominem* wasn't _intended_ to offend, then it was extremely poorly worded. – AndrewC Aug 22 '14 at 02:30

score 3 · Answer 2 · edited Sep 11 '14 at 14:04

Your argument is not valid for the following reason :

It is not enough to show that you can assign a real number to each natural number. You must also show that you can assign a natural number to each real number.

Logically, you must show A implies B and B implies A in order to prove that A and B are equivalent.

Infinity produces several truths contrary to our immediate intuitions. The apparent fact that one infinity may not be "big enough" to accommodate another infinity is just one example.

score 2 · Answer 3 · answered Sep 11 '14 at 18:39

There was Alfred Kempe's (in)famous proof of the Four Colour Theorem given in 1879, which was widely accepted and only shown to be incorrect in 1890. (Almost the exact same proof is used to show the weaker result that every planar map can be coloured using only five different colours, and that version is correct). (And importantly for mathematicians but not for this discussion, the flaw in the proof was fatal and couldn't be fixed; later correct proofs were much more difficult and completely different).

So taking that proof as an example, for 11 years people "knew" that the proof was correct, but it turned out to be wrong. (Reading the proof, it was a rare situation where the flaw was reasonably obvious for a 21st century software developer who has a different way of looking at problems than a 19th century mathematician). It seems that in practice we cannot know that a mathematical proof is valid. In theory we could - if they had been clever enough, people in 1880 would have looked at Kempe's proof and spotted the flaw. But in practice, they were not.

Or look at Wiles' proof of Fermat's "Last Theorem". To me, it's a nice read. The words are put together nicely. It looks like really clever mathematics to me. I don't understand one word of it. (This is different from things written by the many crackpots with similar proofs; there are many where I don't understand one word either but they stink). I'm sure when he published it, he knew the proof couldn't be valid, because it is so complicated, it's impossible to get it right the first time. Mistakes were found, they were fixed, and now if there are any flaws making the proof invalid, there is nobody clever enough to find them. There may be no flaws. There is actually a good chance that there are no flaws. I don't think we can say we know it is valid. We can say that those mathematicians who understand the subject believe that there is a good chance that it is valid, and if not, there is a very good chance of turning it into a valid proof with few changes.

(In actual fact, Wiles' first proof contained a flaw and it was about a year until he saw how to patch it.) — AndrewC, Sep 11 '14 at 20:21

score 1 · Answer 4 · answered Nov 06 '14 at 16:27

The question may gain distinguishing what kind of validity you are seeking for.

On the one hand, you may be "simply" interested in using the state of the art mathematical tools to ensure that your engineering project as a consistent specification and that the thing that you built map exactly that. If that's what you are interested for, proof assistant may be an interesting entry point.

On the other hand you may be interested with more ontological concerns, like knowing if mathematical objects reveals eternal underlying truths or if their are just mere mental representations resulting from an ugly patchwork of cognitive biases. If that's what you are looking for, you may look up for realism, idealism, solipsism as entry points.

score 1 · Answer 5 · answered Nov 21 '15 at 04:19

Every mathematical proof is done within the scope of formal system. Such a formal system is:

A set of symbols that can be used
A grammar to define what sequences of symbols (sentences) are well formed
A set of axioms
A set of inference rules to go from one sentence to another

Over time, the formal systems that are accepted shift to accommodate new discoveries or problems with old results. In the case of the infinite sets you describe, it was the shift to the set of axioms towards modern set theories that lead Cantor to challenge the conventional thinking.

As a result, you could still write any of the old proofs, and claim them to be proofs, but they would no longer be of value because the newer set of axioms had become the "preferred" set of axioms. Proofs using other axioms were simply less useful.

We also see this today with the difference between proofs in ZF and ZFC. Mathematicians are divided about the validity of the Axiom of Choice (the C in ZFC). A proof done in the formal system of ZF's set theory is considered more valuable than a comparable proof done in a formal system of ZFC's set theory.

score 0 · Answer 6 · answered Nov 06 '14 at 02:37

Surely people have made incorrect arguments that have been generally accepted as valid until they were examined more closely.

But I don't think your imaginary pre-Cantor example could have been one of them, because, when presented with that argument, the first thing any mathematician would have asked is: What exactly do you mean by "same size"? What exactly do you mean by "bigger"?

Then one of four things would have happened:

1) You might have given Cantor's definitions, in which case it would have been immediately obvious that your argument proves nothing.

2) You might have given some other definition which would have made it immediately apparent that your argument proves nothing.

3) You might have given some other definition according to which your argument is entirely correct (but not in conflict with Cantor's, because you and he are using the same words to mean different things).

4) You might not have had a precise answer, in which case the mathematician would have immediately known that you were talking nonsense.

score 0 · Answer 7 · answered Jan 11 '18 at 01:36

I do not think I will post a definite opinion about the question debated. Instead I will express doubt of the very logical validity of a statement that there are so and so many this kind of numbers or that kind of numbers, at least not before one defines what one means by the words "is" or "are" related to numbers.

A number is not anything that exists before you have a situation where you can formulate a number that describes that situation quantitively. So instead of proving how many numbers you have, or there is, I think the only logically valid way is to prove in which situations you can formulate a certain kind of number.

SonOfThought · Answer 8 · 2020-09-23T07:58:51.557

In Mathematics we can find comparatively more concrete ideas. But some are rather abstract. In the case of the former one, if we got the proof by more than one method we can make sure that the proof is valid. Eg: We can prove the Pythagoras Theorem by different methods and many men have already 'lived with it' and solved the problems in their real life situations. So we know that Pythagoras Theorem is valid in our world. But this is not the case of some abstract ideas like real numbers, complex numbers etc.

When mathematics is concerned we have to deal all its different branches as a whole.

In the case of Mathematics, to know, to make sure etc. means 'to get the proof of something'. I don't wish to keep any suspense in your reading my answer.

In this case, a mathematician wouldn't be a much better analyzer than a layman. Both of them would say: "It is impossible".

We never say that something is a proof if it can't be explained clearly at least to one higher authority. Even though someone says he got a proof that couldn't be explained, we wouldn't admit it. We would hesitate even to say that he knows it.

Mathematics is stubborn in its approach. So I will have to deal this question mathematically / rationally.

Mathematicians will often expand this question up to any extent like this (here, 'know if' means 'prove'):

Know if [Know if {Know if (Know if a mathematical proof is valid)}]

The number of persons who can 'get out of' even from the double bracket would be a finger-limit and eventually it reaches one. Then we will reach a situation as I mentioned earlier. So we can conclude that it is impossible.

Even if all the humans are transferred to another mathematical world, this limit would always reach one. It would be better to treat as a non-mathematical world if it is a world without one and two.

How do we know if a mathematical proof is valid?

8 Answers8