1

I find myself wanting to talk about parts of a proof, e.g. the role played by mathematical expressions within a proof.

When proving a theorem it is common to construct some kind of object and then prove this has certain properties. E.g. in the standard proof that there are infinitely many primes we assume the primes are finite $p_1,\cdots, p_k$ and the consider $n=p_1\times \cdots \times p_k +1$. We then establish properties of $n$ which lead to a contradiction. What do you call the act of constructing $n$, or $n$ itself?

I think that having names for things is important, especially when talking about them. For example, many simple proofs by contradiction could be a contrapositive instead. Having a word "contrapositive" is very helpful indeed in discussing such proofs, and explaining to students the difference between contradicting the hypothesis, and a general external contradiction such as $1=0$.

The word "ansatz" is widely used "is an educated guess or an additional assumption made to help solve a problem, and which is later verified to be part of the solution by its results" (Wikipedia). I find having a word for an ansatz is very helpful.

I don't have a word for "a particular object constructed as a device within a proof, built to establish certain conditions must hold".

I have lots of other examples of such objects, but no name for them.

My favourite proposal at the moment is "gadget", or "proof-gadget" for emphasis. This is a relatively positive, utilitarian word (not used elsewhere in mathematics as far as i can tell). Gadgets are something which a built for a particular purpose, and are often igneous.

I can, of course, use words as I see fit (The Humpty Dumpty defence) but I'd like to ask if anyone knows of words used routinely for this purpose?

Thanks, Chris

YCor
  • 60,149
Chris Sangwin
  • 182
  • 1
    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. – David Roberts Feb 02 '20 at 11:16
  • 2
    I think the word scholium might be partially relevant here. I seem to recall 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) – David Roberts Feb 02 '20 at 11:21
  • Proclus' commentary on Euclid's Elements split every theorem and proof into six parts (see e.g. https://www.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: https://en.wiktionary.org/wiki/κατασκευή. – Mark Wildon Feb 02 '20 at 12:15
  • 3
    "gadget" has a specific meaning in computational complexity proofs. – Brendan McKay Feb 02 '20 at 23:26
  • Interesting, thanks Brendan. Could you post a DOI to a computational complexity proof using the term? – Chris Sangwin Feb 03 '20 at 19:15
  • 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 24 '20 at 17:11
  • @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: https://mathoverflow.net/a/261056/1593 – José Hdz. Stgo. Jun 17 '20 at 05:28
  • @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$. – David Roberts Jun 17 '20 at 07:34
  • @ChrisSangwin: When the construction is not well motivated, people resort to the term "deus ex machina" sometimes... – José Hdz. Stgo. Jun 17 '20 at 13:52
  • 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$ – Michael Hardy Mar 29 '24 at 20:44
  • $\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. – Michael Hardy Mar 29 '24 at 20:48
  • I suspect that the erroneous belief that Euclid's proof is by contradiction originated with Dirichlet's book on number theory, published in 1859. – Michael Hardy Mar 29 '24 at 20:50
  • 2
    @MichaelHardy your comments are not relevant to this question and getting into an argument about Euclid's proof here is just a distraction. – Sam Hopkins Mar 29 '24 at 21:49
  • @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? – Alessandro Della Corte Mar 29 '24 at 21:54
  • 1
    @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. – Carl-Fredrik Nyberg Brodda Mar 30 '24 at 00:04
  • Igneous?? Ingenious, surely. – Zach Teitler Mar 30 '24 at 00:25
  • @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). – Michael Hardy Mar 30 '24 at 00:56
  • @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. – Michael Hardy Mar 30 '24 at 03:21
  • @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. – Alessandro Della Corte Mar 30 '24 at 04:59
  • @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. – Michael Hardy Mar 30 '24 at 16:24
  • @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). – Alessandro Della Corte Mar 31 '24 at 10:24
  • @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. – Michael Hardy Mar 31 '24 at 19:50

2 Answers2

1

Two kinds of "objects" popping up in proofs come to my mind:

  1. One defines object X and then proves that X has some required properties. In this case I'd call X a "candidate" when introducing it, and I think this is not uncommon.

  2. One assumes something and then defines the object Y (as the number $n$ in your example) to disprove it. In this case I'd call Y just a "counterexample", no? In your case, $n$ is a counterexample to the claim that the prime divisors of any number are among $p_1,\dots,p_k$.

I'm not saying that those are the only cases of "objects in proofs", but perhaps they're the most important ones, and I can't immediately point at cases that are really so different from 1. or 2.

Alessandro Della Corte
  • 4,263
0

This question was asked four years ago, but never got an answer (though, it had some discussion in the comments). This question could have also been asked on academia.SE but it's not clear it's really on topic there either. Let me try to answer so that this doesn't linger forever on the unanswered queue.

With any question about writing, in addition to the guiding principle of not inventing new terminology for something that already has standard terminology, another good guiding principle is do what's best for your reader. Having prepared thousands of pages of writings in my research and teaching, I've found that what's best for the reader is usually whatever is clearest. Hence, when I make a construction in one of my papers and want to refer to it elsewhere in the paper, I give it a numbered environment, just like an equation, definition, lemma, proposition, theorem, conjecture, etc.

Construction 2.1: Under the assumption that there are only finitely many primes $p_1, \dots, p_k$, let $P = p_1p_2\cdots p_k + 1$.

Later in the paper, maybe I need to do the same trick again, and can say "Using the same technique as Construction 2.1, we now ..."

I've also had things like:

Standing Hypothesis 1.1: We assume all model categories are cofibrantly generated in this paper.

or

Agreement 2.1: Let us agree that by "operad" we mean "reduced operad" in what follows.

I think this is MUCH clearer than words like Scholium and Ansatz, that have the potential to throw off readers who have not seen words like that before. I teach so many students from Asia for whom English is already a second language, and words that draw from yet a third language tend to throw them off quite a lot.

Now suppose you're teaching a course on proof-writing, or writing a paper about how we write mathematics, and want a way to refer to the general idea of a construction done inside a proof. In that case, I think "gadget" is a good choice, even though it has a technical meaning elsewhere, because most students/readers know what a gadget is, especially if I mention the real-world meaning of the term and why I chose that word for this concept. Based on the comments, it sounds like there is no standard term. If you want to avoid "gadget" because of the connection to computational complexity, you can use "gizmo" instead.

Lastly, I want to point out that one way to avoid gizmos in proofs is to create lemmas, following Terry Tao's advice. You could imagine doing all your writing in such a way that, wherever you were constructing something inside a proof, you deliberately pulled that out into a lemma like:

Lemma 3.1: If $L = \{p_1, \dots, p_k\}$ is a finite list of prime numbers, then $P = p_1\cdots p_k + 1$ is divisible by a prime not in $L$.

This technique of writing is extremely clear and helps the reader focus on one proof at a time, instead of a proof within a proof. Incidentally, this gives me another idea. You could use "inception" to refer to the phenomenon of proofs/constructions within existing proofs of other statements.

David White
  • 29,779
  • I hope you wouldn't put Lemma 3.1 in a paper. I guess it's true, since there is no such list, but I'd call that a misleading kind of truth since it tempts so much to the analogous false statement where "finite list containing all prime numbers" is replaced by "finite list containing only prime numbers". By contrast, "… then $p_1\dotsm p_k + 1$ is divisible by a prime not on the list" leads to no such confusion. – LSpice Mar 29 '24 at 20:26
  • 1
    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×7)=2×2×3×3,$ 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$ – Michael Hardy Mar 29 '24 at 20:52
  • $\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. – Michael Hardy Mar 29 '24 at 20:53
  • 1
    David, Might Lemma 3.1 be clearer as: If $p_1,\ldots,p_k$ is a finite list of prime numbers, then $P=p_1\cdots p_k+1$ is divisible by a prime that is not in the list. From there, most students would agree that there can't be a finite list that contains every prime number. – Joe Silverman Mar 29 '24 at 21:27
  • 3
    The purpose of this answer was to focus on how to write in general, not on this specific lemma, that I only chose because it was in the original post. Since the choice seems to have generated heat, I rephrased it as suggested by @JoeSilverman. Thanks. I know that some people have very strong feelings about this proof regarding the infinitude of primes, but I encourage readers to focus on the main point of the answer, not on the example. As a topologist, I would have preferred an example of proof writing in topology, but trying to align with the OP here. – David White Mar 29 '24 at 21:39
  • 4
    @MichaelHardy Let's not get off topic. The question is about proofs within proofs, not about the infinitude of primes. The OP only used this proof because it's well known. Let's avoid digressing into opinions about the proof itself, and instead focus on the question, which involves math writing. – David White Mar 29 '24 at 21:40
  • 2
    I agree that "gadget" is a fine word, and the fact that it has a technical meaning in one subfield isn't such a big deal: the list of words that have technical meanings is very long. I also agree that the discussions of Euclid's proof in the comments are off topic here. – Sam Hopkins Mar 29 '24 at 21:51
  • 1
    Along the lines of "gizmo", there's "whatsis", "thingamabob", "whatchamacallit", and "doohickey". Can't wait to see this in a math paper: "Thingamabob 3.1 follows immediately from Doohickey 2.7". – Gerry Myerson Mar 29 '24 at 22:02