Overspecifying a mathematical argument


21 May 1981

Using the right notation is key to proving theorems elegantly. To get this message across, Van Gasteren and Dijkstra explained why they were dissatisfied with the notation that Courant and Robbins had used in a particular proof concerning the prime decomposition of a natural number m. The notation under scrutiny was:

"m = p1 p2 ... pr = q1 q2 ... qs"

where the p's and q's denote prime numbers. According to Van Gasteren and Dijkstra, the previous equations are too specific due to the usage of the subscripts: Courant and Robins had represented two sequences of primes instead of two bags of primes. Since a sequence is a bag with an imposed ordering and this ordering is not needed in the proof, Courant and Robins's notation was too specific. The ordering of the primes is not needed, the subscripts are pure overhead. This "clumsiness" becomes apparent when reading the conclusion of Courant and Robbins:

"Hence the prime decomposition of m must be unique, aside from the order of the factors." --cited by Van Gasteren and Dijkstra in AvG5/EWD788 - 7


1 Comment

Overspecifying or overinterpreting?

I don't have access to Courant and Robbins book at the moment, so cannot go through their account to see whether there's really any clumsiness. But I wonder what do you do when you want to say: "let $m$ be a product of $r$ prime numbers"? The use of subscripts do not imply any ordering, but provides $r$ labels to distinguish them. While I'm not sure why C&R add "aside from the order of the factors" in their conclusion, I think it might just be a case of overinterpreting on the part of VG and D.