19
$\begingroup$

I must once again resort to the advice of this great community.

As I was reading about the pigeonhole principle something about its proof struck me as odd. Allow me to explain:

After reading the "The Foundations: Logic and Proofs" chapter in Rosen's "Discrete mathematics and its applications" book I was left with the feeling/notion that I can (and I ought to) describe all my proof's statements in symbols.

Yet, as you can see in the pigeonhole principle's proof:

We use a proof by contraposition. Suppose none of the k boxes has more than one object. Then the total number of objects would be at most k. This contradicts the statement that we have k + 1 objects.

Without a doubt it has more English words than symbols. Yet the proof is actually without flaws. I struggle with the fact that I can't convert it into the A -> B format (I hope you understand what I'm trying to convey).

However, is there a way to symbolically represent what it states (as I'm trying to put it in my mind)?

Or the only way to argue for this proof, is by using words?

And if so, is there any guide or principle that should tell us when to use words or symbols in our proofs?

$\endgroup$
9
  • 49
    $\begingroup$ Contrary to what many (probably naive) students think, there is nothing wrong with using "words" (or natural language) to express mathematical ideas or logic as long as one is careful to avoid ambiguity. Purely symbolic statements can actually be unnecessarily difficult to decipher. $\endgroup$
    – Deepak
    Mar 21, 2018 at 2:38
  • 12
    $\begingroup$ As is said about code, proofs must be written for people to read, and ... oh wait that's it, mostly. $\endgroup$
    – AakashM
    Mar 21, 2018 at 10:58
  • $\begingroup$ @Deepak Agreed. The need for symbols or symbolic language to represent mathematical concepts should not be forced if the concepts can be better understood without them. For example: "all right angles are equal to one another" is more simply stated than "For all right angles x there does not exist a right angle y such that x does not equal y." $\endgroup$
    – mbomb007
    Mar 21, 2018 at 15:47
  • $\begingroup$ @mbomb007, while you're right, I think that's because of the unnecessary negation; "all right angles are equal to one another" is surely not that different from "for all right angles $x$ and $y$, $x = y$". To be sure one can do without the names, but I'd much rather my students named too many things than too few! ("It" is the bane of beginning proof-writers, I think, to the extent that I try to ban "it" from proofs submitted in my class.) $\endgroup$
    – LSpice
    Mar 21, 2018 at 17:42
  • 1
    $\begingroup$ @Deepak I would like to add that, in my experience, there is also nothing wrong with using symbols to handle things that are awkward to express in words. And I would urge to you try the experiment, and see where pure symbol manipulation can actually help, both in finding a proof and in writing it down clearly. See Edsger W. Dijkstra's EWD1300 for a starting point. $\endgroup$
    – MarnixKlooster ReinstateMonica
    Mar 21, 2018 at 19:33

12 Answers 12

Reset to default
44
$\begingroup$

Your plan is exactly backwards.

All proofs should be readable as English prose, i.e. sentences arranged into paragraphs. Symbols may be used as needed, but they need to be human-readable. If you've defined enough symbols, you can write parts of the proof entirely in symbols, provided that they can be parsed back into English.

For example, $$\forall\ x\in\mathbb{R}, \exists\ y\in \mathbb{Z}: x\ge y$$ reads as "For all real numbers $x$, there is an integer $y$, such that $x$ is greater than or equal to $y$."

$\endgroup$
12
  • 1
    $\begingroup$ You could rephrase that as "Assume that for each box there exists at most one object contained within it. Then the sum (over boxes) of the number of objects in each box is at most $k.$" Writing this in symbols is probably best done by modelling each box as a set, labelling your sets $S_{i}$ for $1\leq i \leq k,$ say, and saying, $$[\forall i\in\{1,\ldots,k\}, \lvert S_{i} \rvert\leq1] \implies \sum_{i=1}^{k} \lvert S_{i}\rvert\leq k.$$ $\endgroup$
    – Will R
    Mar 21, 2018 at 3:28
  • 15
    $\begingroup$ @EmannuelWeg In general, however, you should not worry about this kind of symbolic nonsense. If you write everything in symbols then maybe your proof will be more precise, but no one will want to read it. If nobody reads it, then what is the point in writing it down? $\endgroup$
    – Will R
    Mar 21, 2018 at 3:34
  • 4
    $\begingroup$ @Lawrence But maybe a computer will follow along with your proof... $\endgroup$
    – Mario Carneiro
    Mar 21, 2018 at 12:50
  • 10
    $\begingroup$ @DerekElkins: Is that computer deciding whether your paper/book is deserving of publication, or awarding you grants, or even a job opportunity, based on the quality of your previous work? $\endgroup$
    – Will R
    Mar 21, 2018 at 12:53
  • 1
    $\begingroup$ @Dair Your sarcasm is one level too high for me, I think. The substitution rules are simple, and they are even used in pedagogical material for that reason, but actually the role of the formalism is overstated in this case. It's not difficult for a human to learn the symbol translation well enough to read the average Metamath proof without too much difficulty, and this actually works pretty well on human-written Metamath proofs. However, if a proof is computer-generated, it will often (a) be very long, (b) follow a strange pattern and (c) be very repetitive, which all make it hard to read. $\endgroup$
    – Mario Carneiro
    Mar 22, 2018 at 7:05
19
$\begingroup$

Don't worry, be happy. It is okay. There are symbols that can be used, but using more of them doesn't really make the logic better. $$\begin{array}{|l}\lVert C\rVert=k\\\lVert\,\bigcup_{B\in C} B\,\rVert=k+1\\\hline~\begin{array}{|l}\forall B\in C~(\lVert B\rVert\leq 1)\\\hline\lVert\,\bigcup_{B\in C}B\,\rVert \leq k\\\bot\end{array}\\\neg\forall B\in C~(\lVert B\rVert\leq 1)\\\exists B\in C~(\lVert B\rVert>1)\end{array}$$ "Given that we have a collection of boxes and the total number of items in the boxes is one more than the number of boxes, then since if each box had no more than one item inside, there could be no more items than the number of boxes, contrary to what was given, therefore there must be some box(es) in the collection with more than one item inside."

$\endgroup$
3
  • 6
    $\begingroup$ While this proof is correct, it is not equivalent to the original. The original distinguishes "box" from "object", while this does not. The symbolic proof allows for the possibility that the boxes are arranged like Russian nesting dolls. Depending on the axioms used (e.g. foundation) even wilder behavior is possible. $\endgroup$
    – vadim123
    Mar 21, 2018 at 14:47
  • 1
    $\begingroup$ @vadim123: I'd argue that's a pretty good case for writing the proof in plain English either way. As one who hasn't done Maths in a while, the symbolic proof looked borderline impenetrable whereas the English explanation did not. $\endgroup$
    – Denis de Bernardy
    Mar 21, 2018 at 21:09
  • 4
    $\begingroup$ @vadim123 Indeed! There's no specification that $C$ is a collection only of boxes which are sets only of items. To the very point: The more one insists on rigorous symbolic representation, the more one needs to define structures which were implicit in the natural language; which certainly will not make the proof less obtruse. $\endgroup$
    – Graham Kemp
    Mar 22, 2018 at 0:36
16
$\begingroup$

A lot of this also comes down to writing style. These sorts of proofs aren't just a computational exercise; they're meant to express an idea, to be read and understood, just like any prose writing in any philosophy book. Different writers will want to emphasize different parts, and the same writer may want to express the same proof differently for different audiences. Different branches of mathematics will use different symbols to different degrees.

One key difference between mathematical writing and other writing is that we've incorporated lots of symbols as a way of eliminating ambiguity and removing redundancy, because as mathematicians we are very concerned with being unambiguous, since so much of our work depends on precise definitions. But the symbols are not inherent to mathematical writing, they developed over millennia.

So the symbols aren't necessarily instead of than words, they're in addition. Symbols are only another way to express what we could already express through words and diagrams. How then should you know whether to use more symbols or fewer? The same way you would pick up any writing style: by reading lots of different examples (e.g., textbooks and papers) by different authors, by writing a lot, and by finding trusted writers (published mathematicians) to read and critique your work.

$\endgroup$
1
  • 4
    $\begingroup$ I like the practicality of this advice; it is the only one I've seen that advises that the poster gather data and use it to make the decision on his or her own, rather than simply adhering to another user's impression of community consensus. $\endgroup$
    – LSpice
    Mar 21, 2018 at 17:47
13
$\begingroup$

And if so, is there any guide or principle that should tell us when to use words or symbols in our proofs?

It greatly depends on what you are trying to do with your proofs.

If you "just want to do math," then you should use whatever combination of symbols and words is clearest. You do need to make sure all of your terms are rigorously defined, but symbols can suffer that problem just as easily as words:

$$ R = \{x|x\notin x\} \\ R \in R \iff R \notin R $$

On the other hand, there are situations around the foundations of mathematics where thinking of proofs as sequences of purely symbolic statements is useful, without regard for what they may mean in English or another language. This is particularly important for Gödel numbering and its progeny such as the incompleteness theorems. This does not mean that you actually have to write proofs in symbols. It just means that, when proofs are themselves the objects of study, they are easier to reason about if they are written in a formal language. As another example, the "standard" set theory, Zermelo-Fraenkel set theory (ZFC), never defines the symbol $\in$, instead treating it as a primitive operation.

On the third hand, sometimes you may want to use an interactive proof assistant or something similar, especially for large or complex proofs which may otherwise be difficult to verify. These systems are generally not "smart" enough to deal with natural language proofs, so you usually have to write entirely in symbols or some formal language, similar to a programming language. Depending on the circumstances, it may or may not be useful or even feasible to prepare a human readable "translation" of such a symbolic proof. For example, the four color theorem originally did not have a readily comprehensible human proof.

$\endgroup$
2
  • 1
    $\begingroup$ The FCT still does not have any human-readable proof to my knowledge, although the case analysis has been slightly improved from the original to ~1400 cases or so. $\endgroup$
    – Mario Carneiro
    Mar 21, 2018 at 12:52
  • $\begingroup$ @Mario: Wikipedia claims the existence of a proof of the snark theorem, which could be a human readable proof for all I know. But it's really unclear to me. $\endgroup$
    – Kevin
    Mar 21, 2018 at 15:35
10
$\begingroup$

Here is a way to put more symbols into the proof.

Let $t$ be the total number of objects, and for $j=1,2,\ldots,k$ let $n_j$ be the number of objects in box $j$. Suppose $\forall j\ n_j\le1$. Then $$t=\sum_{j=1}^k n_j\le\sum_{j=1}^k1=k\ .$$ This is a contradiction since $t=k+1$. So we have $\neg(\forall j\ n_j\le1)$, that is, $\exists j\ n_j>1$.

The point is, is this better than the original? Do you find it easier to understand and/or more convincing than the original? If so, go for it.

As for me, I'm with @vadim123 and the comment by @Deepak. IMHO the original is clear, understandable and convincing, and the proof I have given above is basically a waste of time.

$\endgroup$
1
  • $\begingroup$ You are completely right. it comes down to ambiguity and simplicity. Thanks you very much. $\endgroup$
    – Emannuel Weg
    Mar 21, 2018 at 2:55
8
$\begingroup$

Natural language contains more redundancy and is therefore more robust against errors. When you write proofs, chances are that you will sometimes make mistakes. This is not a feature of mathematics, but of life in general. If you mistype a character in a symbolic proof, it can become utterly undecipherable — and wrong, but that's not the biggest issue. If people understand your story, they can reconstruct a symbolic proof from your story if they want.

If you write your proof in plain English and repeat important things, it is easier for the reader to recall past things when needed and fill in the holes when you leave them. Natural language is redundant, and therefore messages go through better.

If you ever grade a math exam, you will learn the hard way that people will forget all kinds of silly things and write things unclearly. A fully symbolic proof is readable only if it's completely correct, a language-oriented proof is readable if it's at least somewhat correct.

Symbolic proofs only contain the proof. A good proof in words contains more: it describes what is going on and motivates maneuvers instead of only executing them. This makes a difference to whoever reads your text, including yourself.

$\endgroup$
1
  • $\begingroup$ Note that the calculational proof format (see my answer) gives all: symbols, and hints (both explanations and motivations). $\endgroup$
    – MarnixKlooster ReinstateMonica
    Mar 22, 2018 at 20:56
6
$\begingroup$

The advantages of the symbolic representation are that:

  • You have a greater degree of confidence that what you're doing is actually formal logic and not wishy washy argumentation.
  • You are not forgetting something.
  • It's much more difficult to write ambiguously with mathematical symbols. English and pretty much all other natural languages don't have a proper way to denote parentheses. Unambiguous English is often verbose and annoying to read.

That said, it is generally easier to read natural language than mathematical symbols. Your documents should be made to optimise the reader's experience, not to impress them with your mastery of mathematical notation.

Just know that a formal proof is one written in a formal language. If you can translate a natural language proof into one written with mathematical symbols then it's okay, not the other way around. Meaning that symbolic proofs don't have to "sound right" in English, while English proofs have to be unambiguously translatable to mathematical notation.

$\endgroup$
1
  • 1
    $\begingroup$ I think that all of the advantages you list are advantages of skill and familiarity with proof-writing, and none has much to do with symbols. An experienced mathematician is just as likely to be able to ensure that he or she has met these conditions in a natural-language as in a symbolic proof; an inexperienced mathematician is just (or at least almost) as likely to miss one of these conditions with a symbolic proof as with a natural-language one. $\endgroup$
    – LSpice
    Mar 21, 2018 at 17:45
5
$\begingroup$

I really like all the answers here but there's a point that I think is somewhat implied, but not explicitly stated in any of them.

The symbols in mathematics are there as an extension of the language (English in this case), not a replacement of it. A statement can always be written in just words, but this is often unnecessarily verbose: "if one more than three times a real number is four, then that number must be one". Equivalently, we could also write it with just symbols (though this depends on a sufficient amount of symbols being defined), but the statement often ends up less clear and requires being deciphered: "$[(x\in\mathbb{R})\wedge (1+3x=4)] \Rightarrow(x=1)$".

If we use language, and allow the symbols to come into play only when they make the statement clearer, we can strike a good balance of readability: "if $x$ is a real number and $1+3x=4$, then $x=1$".

Proofs are the way of communicating logical statements, so the main goal of a proof (after being correct) is to be readable. This means that, in addition to being clear and precise, the best way to present a proof is the way that will make it most understandable to your intended reader what it's saying.

$\endgroup$
1
  • $\begingroup$ I think that an important pseudo-exception to "a statement can always be written in just words" is that a variable-heavy statement probably cannot be, unless you allow the 'words' to be variable names, or engage in tiresome indexing that is essentially the same ("the product of one number and the sum of two others is the sum of the product of the original number with the first summand, and the product of the original number with the second summand" is the best I can do even for a simple formula with just three variables). $\endgroup$
    – LSpice
    Mar 21, 2018 at 17:50
5
$\begingroup$

I have a PhD in Mathematics, when I started school I always thought I wanted to use more symbols than words. However, often you cannot do this. A proof is not solving a problem, it is much more! It should certainly contain many words. When you are learning to write proofs, you should actually use more words to make sure your statements are as accurate as possible! As you grow in your mathematical backrground, you will be able to become more concise in your proofs, but this will take time. Your goal in writing a proof should not be length, but rather to explain each step with complete clarity.

$\endgroup$
1
  • 3
    $\begingroup$ I think a proof is solving a problem (at the very least, the problem of not having a proof). Maybe you mean something like "writing a proof is not the same as solving a routine computational problem"? $\endgroup$
    – LSpice
    Mar 21, 2018 at 17:51
4
$\begingroup$

I'm going to agree with Kevin that it depends on what you're trying to do.

  • If you're trying to work out the proof of a statement, symbols and shorthand is very handy to express your thoughts succinctly on paper, or on a board. Then you can (hopefully) assemble them into a proof. Symbols are also good for crystallizing a vague thought into a precise mathematical statement.

  • When it's time to write it down for someone else to read, though, symbols can increase the semantic density, making it very hard to communicate effectively. And when used incorrectly, as students often do, symbols can obscure what might be otherwise coherent arguments.

Obligatory quote from Paul R. Halmos in How to Write Mathematics:

The best notation is no notation; whenever it is possible to avoid the use of a complicated alphabetic apparatus, avoid it. A good attitude to the preparation of written mathematical exposition is to pretend that it is spoken. Pretend that you are explaining the subject to a friend on a long walk in the woods, with no paper available; fall back on symbolism only when it is really necessary.

$\endgroup$
1
$\begingroup$

Just doing to add to something that's been said probably.

My lecturers have always said that the real aim of a proof is to convince the reader that they understand what's going on just as well as you. If you can do that using words alone, and symbols won't make it any easier, that's brilliant. If you feel your answer is entirely rigorous, and any possible question an individual has can be answered by reading the proof more carefully then you're lovely and finished.

Symbols and equations should only be used as an extension of English prose, and if you don't need them then don't use them as an excuse for handwavery. Symbols should be the same as diagrams, something to help you explain, and rarely an excuse for an explanation.

$\endgroup$
1
$\begingroup$

For completeness, here is the theorem from Rosen's book that this question uses as an example (Section 6.2 The Pigeonhole Principle, Theorem 1):

THE PIGEONHOLE PRINCIPLE If $k$ is a positive integer and $k+1$ or more objects are placed into $k$ boxes, then there is at least one box containing two or more of the objects.

And for concreteness, here is how I would prove this.

Consider the bag (or 'multi-set', or 'set but allowing duplicates') $B$ having $k$ elements (the "boxes") whose sum (the total number of "objects") is at least $k+1$, then $% \require{begingroup} \begingroup \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} %$ $$\calc \text{max}(B) \op\ge\hints{Dijkstra's 'generalized pigeonhole principle',}\hint{which holds for any bag of numbers} \text{average}(B) \op=\hints{by the definition}\hint{-- to exploit our knowledge of sum and size} \text{sum}(B) / \left|B\right| \op\ge\hint{sum is at least $k+1$, size is $k$} (k+1) / k \op\gt\hint{using $k>0$} 1 \endcalc$$ Or in words, $B$ has at least one element ("box") larger than 1 (having more than one "object").

For me, a proof like this is often much easier to follow than a natural language paragraph of text. (I know this is a minority viewpoint and experience, but for those who often fail to understand natural language proofs, I suggest you try finding the level of symbol manipulation that helps you and your readers best. Dijkstra's EWD1300 could be helpful for you. He expresses the "desire to let the symbols do the work —more precisely: as much of the work as profitably possible—.")

Also, this proof was very easy to construct, given the basic $\;\text{min} \le \text{average} \le \text{max}\;$ principle (which I learned from EWD980 and EWD1094): at every step there is really only one sensible thing to do.

$% \endgroup %$

$\endgroup$
2
  • $\begingroup$ Maybe I'm just being misled by the name, but it seems a bit strange to use the generalised pigeonhole principle to prove the pigeonhole principle. $\endgroup$
    – LSpice
    Mar 23, 2018 at 10:39
  • $\begingroup$ Well, Rosen is "proving" it using the concepts of objects and boxes, i.e., pigeonholes, so is doing essentially the same. And I think the only reason why one would call the theorem $\;\text{min}(B) \le \text{average}(B) \le \text{max}(B)\;$ a "generalized pigeonhole principle" or (Dijkstra) "Purified Pigeonhole Principle" is for historical reasons. It is just a theorem in the theory of bags / multi-sets. So I agree that it probably just the name. :-) $\endgroup$
    – MarnixKlooster ReinstateMonica
    Mar 23, 2018 at 12:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .