Timeline for Nontrivial theorems with trivial proofs
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 11, 2023 at 7:10 | comment | added | bof | Which of Cantor's proofs of the nondenumerability of the continuum is considered "trivial", the one that uses the machinery of decimal expansions, or the one that just uses the completeness of the real line? I haven't read the latter but I'm guessing it uses something like "a bounded increasing sequences converges." | |
| Dec 30, 2022 at 10:03 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
a minor typo
|
| May 9, 2014 at 1:10 | comment | added | Joshua Grochow | I think the reason I'd consider diagonalization nontrivial is that essentially the same proof shows that the Halting problem is undecidable, yet this is a proof that undergrads often struggle with until they've seen it ~half a dozen times. (The first five times or so it never seems to stick...) But perhaps its use there is/feels more subtle, since you've got Turing machines eating Turing machines, which is a little more meta than lists of digits... | |
| Jun 26, 2013 at 16:42 | comment | added | Joel David Hamkins | Michael, to be more explicit, my view is that the original Cantor proof, using intersection of intervals, is fundamentally the same as the usual modern presentation using digits. It is a mere stylistic difference, since restricting the first finitely many digits of a real number is the same as restricting to an interval. Thus, I don't agree with your assertion that Cantor's original argument was not a "diagonal" argument. Rather, I regard it as the very first diagonal argument. | |
| Jun 21, 2010 at 18:58 | vote | accept | Michael Hardy | ||
| Jun 21, 2010 at 18:58 | |||||
| Jun 21, 2010 at 0:54 | comment | added | Joel David Hamkins | Yes, perhaps the diagonal method only seems trivial now, because it has permeated all of logic. The essence of the method is to accomplish a list of things by accomplishing the n-th thing on the n-th step of a construction. Isn't this trivial? Cantor's original argument follows this diagonal form, for he omits the n-th real on a given list with the n-th closed set, and then intersects them to find a real not on the list. I find this to be essentially identical to the typical digit argument that one finds in an undergraduate analysis course today. | |
| Jun 21, 2010 at 0:32 | comment | added | Victor Protsak | The diagonal proof is short and elegant, but I personally don't consider it trivial. | |
| Jun 20, 2010 at 8:49 | comment | added | Peter LeFanu Lumsdaine | @Joel: do you recall a rough reference for that historical context (that Cantor had the diagonal argument before the closed sets one)? I'd be interested to see it! @Ilya: I think both the diagonal argument and the infinitude of primes are, at least, "trivial once you see them" - far from trivial to come up with in the first place, but very straightforward to understand, or to explain to somebody - which is surely the kind of "tirival" that's being asked about? | |
| Jun 20, 2010 at 4:24 | history | made wiki | Post Made Community Wiki by Kim Morrison | ||
| Jun 20, 2010 at 2:42 | comment | added | Ilya Grigoriev | Is this proof really trivial, or is it just that we were all forced to learn it? Is it trivial that there are infinitely many primes? | |
| Jun 20, 2010 at 2:05 | comment | added | Joel David Hamkins | Well, my view is that the theorem is still profound today and the proof is trivial, however things may have seemed in 1870, and so it seems to be an example of what you requested. | |
| Jun 20, 2010 at 1:36 | comment | added | Michael Hardy | Cantor's original paper showing uncountability of the reals was primarily concerned with proving that real transcendental numbers exist. And as I said, it wasn't done by diagonalization. But my objection to considering this particular proof trivial is still there. | |
| Jun 20, 2010 at 1:36 | comment | added | Joel David Hamkins | Michael, my understnanding of the history is that Cantor understood his argument as a diagonalization, but published it as an intersection of closed sets argument as you decribe in order to satisfy prevailing mathematical winds concerning completed infinities and whatnot; in a sense the world was not yet ready for his way of thinking. His later general argument showing that the power set P(X) is larger than X is a direct diagonalization. | |
| Jun 20, 2010 at 1:25 | comment | added | John Stillwell | Also, diagonalization gives a trivial proof that transcendental numbers exist -- a result whose first proof (by Liouville) was considerably less trivial. | |
| Jun 20, 2010 at 1:24 | comment | added | Michael Hardy | I hesitate to agree with this one. Cantor's original uncountability proof was not a diagonal argument and did not mention digits at all, and the argument that does mention digits relies on the fact that the numeral system actually behaves in certain ways. And if a mathematician in about 1870 had been handed the question of whether there is some sequence that contains all reals, I don't think one would consider it a routine exercise. | |
| Jun 20, 2010 at 1:16 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |