How to keep quantifiers organised in a proof?

Question

I’m self-studying Tao’s Analysis I. There are instances when trying to write (or even read) a proof, it becomes difficult to keep track of quantification of variables—both universal and existential. I agree that these are most explicitly visible in a formal proof (with proper syntactical and logical rules), but most of us write proofs in English.

The trouble with this style, at least for me, arises when we try to extend the quantification of variables beyond a single sentence. For instance, “For all $n\ge 1, P(n)$ holds. $P(n)$ implies $Q(n)$. Hence $Q(n)$ holds for all $n\ge 1$.” In this example it was implicitly quite clear that $n$ was a bound variable in the second sentence too. But in quite convoluted arguments, keeping track of this kinda stuff can be daunting.

But even then, I have seen some instances where, even in English, this can made more explicit. For instance, in “There exists an $n_0$ such that $P(n_0)$ holds. Fix this $n_0$. ...”, it is quite clear that $n_0$ is existentially instantiated in what follows.

How to be explicit and clear about this? I’m looking for some suggestions on this from you mathematicians. How do you take care of this?

Answer 1

I also had this issue when learning. The short answer is you just develop a system which works for you, and you just get used to things by reading/practicing more.

I'll just illustrate with a simple example of what helped me. For instance, if I'm writing an $\epsilon, \delta$ proof for proving a certain function is uniformly continuous, I would first write down/think in my mind what the statement to be shown is, and I would write all the quantifiers explicitly. So if I want to show $f:X \to Z$ is uniformly continuous ($X$, $Z$ being metric spaces say), then I would first write down for myself: \begin{align} \forall \epsilon > 0, \exists \delta > 0: \, \forall x,y \in X, \, \, \text{if $d_X(x,y)< \delta$ then $d_Z(f(x), f(y)) < \epsilon$}. \end{align}

Something which helped me was to introduce variables in the same order as they appear in the statement to be proven. For example, in the above statement, $\epsilon$ is the first thing to appear, and it appears with a universal quantifier. Hence, the very first sentence of my proof would always start

"Let $\epsilon > 0$ be an arbitrary number."

And I would add in the adjective "arbitrary", purely for emphasis, because for some reason it just helped me to register that it is a universally quantified object.

Then, the next thing which appears in the statement to be proven is $\delta$, and it appears with an existential quantifier. So, after some relevant steps, I would say

"Choose $\delta = ...$"

or

"Define $\delta = ...$"

Once again, I add in an adjective in front of the $\delta$ to make it clear (atleast to myself) that it is an existential quantifier. Then the next step of the proof requires the universally quantified $x,y$. So, I would say something like

Take any $x,y \in X$ such that $d_X(x,y) < \delta$.

Hopefully you get the gist; I basically introduce variables in the exact same order as they appear in a mathematical statement, and when I introduce them in my proof, I add adjectives in front to emphasize to myself what kind of quantifier it is.

---

So, for example, if I have to prove that $f: \Bbb{R} \to \Bbb{R}$ defined by $f(x) = \sin(2x)$ is uniformly continuous on $\Bbb{R}$, here's how I'd structure the argument:

Let $\epsilon > 0$ be an arbitrary number. Now, choose $\delta := \dfrac{\epsilon}{2}$. Take any $x,y \in \Bbb{R}$ such that $|x-y| < \delta$. Then, we have \begin{align} |\sin(2x) - \sin(2y)| & \leq \sup_{\xi \in \Bbb{R}}\left|\dfrac{d}{d \xi} \sin(2\xi) \right| \cdot |x-y| \tag{Mean-value theorem} \\ & \leq 2 \cdot \delta \\ &< \epsilon \tag{by definition of $\delta$} \end{align} Since $\epsilon > 0$ was arbitrary, this proves $f$ is uniformly continuous on $\Bbb{R}$.

Hopefully that's helpful.

---

Edit: Your purpose:

Of course, the manner in which you structure an argument heavily depends on who you're writing for, and also how comfortable you are with subject material. For example, are you in an introductory proofs course writing an assignment? Are you in final year of a math specialist program? Basically, you need to know your audience and the level of detail necessary for a certain argument.

The argument I gave above for uniform continuity of $f(x) = \sin(2x)$ is something I would have written in my first year calculus course, if $\epsilon, \delta$ arguments are new to me, and if I was writing for an assignment. As mentioned in the comments, sometimes, certain adjectives are unnecessary, like the use of "arbitrary" in my proof above. Because that is already implied by the word "let", and this is common writing practice in math texts. Depending on the circumstances, I think the following one-liner would even suffice:

Since $f$ has a bounded derivative on $\Bbb{R}$, it is Lipschitz continuous on $\Bbb{R}$, and hence uniformly continuous.

But of course, if its your first introduction to a subject, it is always best to be very explicit about your proof strategy and your subsequent reasoning.

Answer 2

I would argue that trouble arises not when the quantifiers are extended to several sentences, but when it is unclear what the variables are doing in the first place. If you know why we are introducing some variable, and what it's purpose is, it's almost obvious what which quantifiers are attached to which variables. When you say

But in quite convoluted arguments, keeping track of this kinda stuff can be daunting.

the trouble isn't the quantifiers, it's the convoluted arguments.

---

When writing, there's actually a really nice solution to this: give your reader a roadmap of the proof. "First, I will do this, then show that this thing is bounded by that, which will give us what we want." or something similar. It doesn't have to be long, just something descriptive enough so that your reader knows what you're doing when you introducing your fourth quantifier. Many authors omit this "roadmap" because it's assumed (often to the detriment of the writing) that you already have one formed in your head.

For reading, that's a bit harder. The best you can do is be familiar with the "standard" arguments, and really understand your definitions—that way you know what the author is trying to say. This is something you get better at over time. As an exercise, you can try to write your own roadmap after you've finished the proof.

Answer 3

There are lots of texts on how to write understandable math. Most agree that you should keep symbology to the minimum. I'm particularly partial to Knuth, Larrabee and Roberts' Mathematical writing (a PDF version here). For how to organize and structure proofs in general, see Hammack's The book of proof.

Answer 4

As long as each variable is only bound once, you can just treat its binding as a definition, and it's understood that its definition continues to hold for all further instances. It can increase clarity to make sure a name is used only for one thing. In your first example, you want your second sentence to still have $n$ being an arbitrary number, but then you want to pull back to talking about all $n$ in the last sentence. You can instead say:

Let $n_0$ be an arbitrary number greater than or equal to 1. P($n_0$) implies Q($n_0$). Since $n_0$ was arbitrary, Q(n) holds for all n≥1.

In your second example, you can say

Let $n_0$ be such that P($n_0$)

If you are using the same name in different binding, you should look at whether you can use different names. If not, separating into different paragraphs for different bindings might help. You can also use such phrases as "We now take $n_0$ to instead be" to make it more explicit that there's a new binding.

Another option is indenting; each indentation level represents one quantifier. Here's a rough draft that you could start with:

<For all n>:
|  P(n)
|  P(n) -> Q(n)
V  Q(n)
</For all n>

Answer 5

You may want to consider adopting a Fitch-style format for your proofs, at least when you are in the process of finding them. See this post for a formal version, though you need only the context headers (conditional or universal subcontexts) to deal with quantified variables in a semi-formal proof. If you do adopt a Fitch-style format, not only will it be crystal clear what the scope of each quantified variable is, but also it will be hard to make any incorrect accidental quantifier swaps.

Your example would be simply written as:

  Given any natural $n ≥ 1$:
    $P(n)$.
    Thus $Q(n)$.
  Therefore $Q(n)$ for every natural $n ≥ 1$.

You can see that the proof structure itself makes it completely obvious that the $n$ in lines 2 to 3 are bound within the subcontext "natural $n ≥ 1$", and you can leave that subcontext only by invoking the $∀$-intro rule. Accidentally swapping "$∀∃$" to get "$∃∀$" is a common error among students since the quantification contexts are not clear to many of them, but it will be impossible to make sure errors if you make the contexts explicit as in Fitch-style. Anecdotally, I once had a complicated measure theory proof in my head, or so I thought, until I wrote it down in Fitch-style and found that I was stuck due to precisely this kind of error.