Timeline for What do you call an object constructed as part of a proof?
Current License: CC BY-SA 4.0
30 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 7 at 19:21 | review | Close votes | |||
| Oct 12 at 3:05 | |||||
| Mar 31 at 19:50 | comment | added | Michael Hardy | @AlessandroDellaCorte : I don't actually understand the difference in meaning between the statement that "no finite set of primes contains every prime" and the statement that "given any finite set of primes, there exists a prime which is not in the set". $$\begin{align} & \lnot\exists\text{ finite set } S \,\,\, \forall\text{ prime } n \,\,\, n\in S. \\ {} \\ & \,\,\,\forall\text{ finite set } S\,\,\, \exists\text{ prime }n\,\,\, n\notin S. \end{align}$$ One translation says "Prime numbers are more than any proposed multitude of prime numbers" or something close to that. | |
| Mar 31 at 10:24 | comment | added | Alessandro Della Corte | @MichaelHardy I took a closer look at Euclid's original statement and proof. It seems to me that whether the proof is by contradiction or not depends on how you translate the claim in modern mathematical language. If you say "no finite set of primes contains every prime" then it is by contradiction indeed. If you say "given any finite set of primes, there exists a prime which is not in the set", then it's not. Probably the latter makes more sense, so you're right. But in any case this has little to do with the fact that the "new" prime is $n$ itself (wrong) or one of its factors (correct). | |
| Mar 30 at 16:24 | comment | added | Michael Hardy | @AlessandroDellaCorte : Only the assumption that the primes one starts with are the only primes that exist can lead authors to write that $1+\prod P$ is not divisible by any primes and "is therefore itself prime" (quoting G. H. Hardy in A Course of Pure Mathematics, Cambridge University Press, 1908, pages 122–3). Thus that error results from that assumption, and that assumption is absent when one doesn't assume at the outset that there are only finitely many primes. | |
| Mar 30 at 4:59 | comment | added | Alessandro Della Corte | @MichaelHardy …contradicting the statement that that list contained every prime number, no? It seems to me that your correct remark about the fact that $n$ is not necessarily prime but just has a prime factor other than $p_1,\dots,p_k$ has little to do with the proof being by contradiction or not. | |
| Mar 30 at 3:21 | comment | added | Michael Hardy | @AlessandroDellaCorte : I don't understand your comment. If every finite set of prime numbers can be extended to a larger finite set of prime numbers, then the list of prime numbers keeps on going. | |
| Mar 30 at 0:56 | comment | added | Michael Hardy | @SamHopkins : Chris Sangwin gave great prominence to Euclid's proof in his question. And in so doing, he misled people (in just the way so many mathematicians do about this topic). | |
| Mar 30 at 0:25 | comment | added | Zach Teitler | Igneous?? Ingenious, surely. | |
| Mar 30 at 0:04 | comment | added | Carl-Fredrik Nyberg Brodda | @AlessandroDellaCorte It’s a proof by negation, not by contradiction. I agree with Sam that a discussion about Euclid’s proof here is off-topic. | |
| Mar 29 at 21:59 | answer | added | Alessandro Della Corte | timeline score: 1 | |
| Mar 29 at 21:54 | comment | added | Alessandro Della Corte | @MichaelHardy I'm not sure I understand, although I read this opinion multiple times: if you're not arguing by contradiction, how do you conclude that there are infinitely many primes from the fact that you can generate, from any given finite set of primes, a number having divisors outside the set? | |
| Mar 29 at 21:49 | comment | added | Sam Hopkins | @MichaelHardy your comments are not relevant to this question and getting into an argument about Euclid's proof here is just a distraction. | |
| Mar 29 at 21:45 | history | edited | YCor | CC BY-SA 4.0 |
removed meta info from title
|
| Mar 29 at 21:45 | history | edited | Mohan | CC BY-SA 4.0 |
Edited the double use of $n$ and changed one to $k$.
|
| Mar 29 at 21:44 | history | edited | RobPratt |
edited tags
|
|
| Mar 29 at 20:50 | comment | added | Michael Hardy | I suspect that the erroneous belief that Euclid's proof is by contradiction originated with Dirichlet's book on number theory, published in 1859. | |
| Mar 29 at 20:48 | comment | added | Michael Hardy | $\ldots\,$A confused student may think that if $p_1,\ldots,p_n$ are the smallest $n$ primes, then $p_1\times\cdots\times p_n+1$ has been shown to be prime in every instance. That is false: $(2\times3\times5\times7\times11\times13)+1 = 59\times509.$ Then when a student learns of such counterexamples, they think that that shows Euclid's proof is erroneous. But Euclid's proof is in fact sound. | |
| Mar 29 at 20:44 | comment | added | Michael Hardy | It is unfortunate that the "standard" proof of the infinitude of primes assumes only finitely many exist and deduces a contradiction. The way Euclid did it is better: Assume $P$ is any finite set of primes (e.g. $\{\,5,7\,\}$) and show that the prime factors of $1+\prod P$ are not in $P$ (e.g. $1 + (5\times7) = 2\times2\times3\times3,$ so that there are more primes than those in $P.$ Making it a proof by contradiction adds an extra complication that serves no purpose and confuses some students, as follows:$\,\ldots\qquad$ | |
| Mar 29 at 20:21 | answer | added | David White | timeline score: 0 | |
| May 8, 2022 at 7:27 | review | Close votes | |||
| May 8, 2022 at 18:11 | |||||
| Jun 17, 2020 at 13:52 | comment | added | José Hdz. Stgo. | @ChrisSangwin: When the construction is not well motivated, people resort to the term "deus ex machina" sometimes... | |
| Jun 17, 2020 at 7:34 | comment | added | David Roberts♦ | @JoséHdz.Stgo. yes, but one might record as a scholium the (trivial) observation that the procedure $(n_1,\ldots,n_k) \mapsto 1+\prod_{j=1}^k n_j$ results in a number that is never $0$ modulo each $n_j$. | |
| Jun 17, 2020 at 5:28 | comment | added | José Hdz. Stgo. | @DavidRoberts: I don't think I would refer to the "consideration" of the number $p_{1} \cdots p_{n} +1$ in the proof of Euclid IX-20 as a scholium: mathoverflow.net/a/261056/1593 | |
| Feb 24, 2020 at 17:11 | comment | added | user44143 | How about "the construction in the proof" or "the constructive part of the proof"? Meanwhile, people sometimes replace the verb "construct" with "exhibit" for emphasis. | |
| Feb 3, 2020 at 19:15 | comment | added | Chris Sangwin | Interesting, thanks Brendan. Could you post a DOI to a computational complexity proof using the term? | |
| Feb 2, 2020 at 23:26 | comment | added | Brendan McKay | "gadget" has a specific meaning in computational complexity proofs. | |
| Feb 2, 2020 at 12:15 | comment | added | Mark Wildon | Proclus' commentary on Euclid's Elements split every theorem and proof into six parts (see e.g. jstor.org/stable/639502): enunciation, setting out, definition of goal, construction, proof, conclusion. Typically the construction involves many auxiliary lines and figures. So, if pretentiousness is not a problem, how about κατασκευή? See for instance the fourth sense 'a device, a trick' here: en.wiktionary.org/wiki/κατασκευή. | |
| Feb 2, 2020 at 11:21 | comment | added | David Roberts♦ | I think the word scholium might be partially relevant here. <strike>I seem to recall</strike> Peter Johnstone uses it to denote something like a corollary, but which follows from something in a previous proof, not from the statement of the result. (Edit: found it: footnote 7 on page xiv, in the Preface to Sketches of an Elephant) | |
| Feb 2, 2020 at 11:16 | comment | added | David Roberts♦ | One can state the infinitude of primes as: given the primes $p_1,\ldots, p_n$, the prime divisors of $p_1\cdots p_n +1$ are not among the given primes. And these new primes are what you have constructed. There are many theorems in the literature that are given as mere existence statements, but which could be restated as a construction together with a property of the constructed object. One word for this is 'proof relevant mathematics', where the content of the proof is meaningful and relevant outside the proof environment. | |
| Feb 2, 2020 at 10:31 | history | asked | Chris Sangwin | CC BY-SA 4.0 |