18
$\begingroup$

I'm not expert in logic, but as far as I know, quantifiers comes before the predicates they refer to. Still, if written in english, there are statements which sounds better when you don't put all the quantifiers before. For example, the definition of a sequence of functions $f_n:\mathbb{R}\to\mathbb{R}$ converging uniformly to some function $f:\mathbb{R}\to\mathbb{R}$:

For all $\varepsilon > 0$, exists $n_0\in\mathbb{N}\ $ such that $\ n>n_0 \implies |f_n(x) - f(x)| < \varepsilon$ for all $x\in\mathbb{R}$

I have seen teachers writing this as

$$\forall\varepsilon > 0,\ \ \exists n_0\in\mathbb{R}\ \ \text{ such that } \ \ n>n_0 \implies |f_n(x) - f(x)| < \varepsilon,\ \ \forall x\in\mathbb{R}$$

Maybe an even more simple example, from probability. It's not hard to find something like

$$P[X_n=Y_n, \forall n\in\mathbb{N}]$$

where $(X_n)_{n\in\mathbb{N}}$ and $(Y_n)_{n\in\mathbb{N}}$ are collection of random variables.

I understand the motivation: if you talk about this probability, you probably will say the probability of have $X_n=Y_n$ for all $n$, and not the probability of, for all $n$, have $X_n=Y_n$. The same reasoning applies for the statement about uniform convergence. That last for all quantifier will fit better at the final of the sentence if you have to say it in words.

So my question is: are this "informal" formulas just wrong (in the formal logic point of view)? Or the formal language of logic can handle this kind of writing?

Thanks.

$\endgroup$
  • 2
    $\begingroup$ The informal approach becomes ambiguous (and that's really a problem) as soon as statements of the form $\exists x\; \Phi(x,y)\;\forall y$ occur $\endgroup$ – Hagen von Eitzen Nov 16 '15 at 17:12
7
$\begingroup$

Carl Mummert's answer is very good, but I'd like to refer specifically to the examples you have given.

Examples such as

$$\forall\varepsilon > 0,\ \ \exists n_0\in\mathbb{R}\ \ \text{ such that } \ \ n>n_0 \implies |f_n(x) - f(x)| < \varepsilon,\ \ \forall x\in\mathbb{R}$$

are perfectly fine on a blackboard: writing on it takes time, and it is a dynamic process (you see it being written), probably assisted by the lecturer's comments. Actually spelling everything out in words would take up too much time and blackboard space, and the "dynamic" plus the commentary make the text completely understandable (hopefully).

Things are very different with a stand-alone mathematical text. In there, you should (as a rule of thumb) either spell out quantifiers (and logical connectives!) in words, as in

For all $\varepsilon > 0$, there exists $n_0\in\mathbb{N}\ $ such that whenever $\ n>n_0$, we have that $\lvert f_n(x) - f(x)\rvert < \varepsilon$ for all $x\in\mathbb{R}$.

(and this is preferable), or spell everything out purely formally, like:

$$\forall\varepsilon > 0\ \ \exists n_0\in\mathbb{N}\ \ \forall n\in {\mathbb N} \ \left( n>n_0 \implies \forall x\in\mathbb{R}\ \ |f_n(x) - f(x)| < \varepsilon,\right).$$

(In the latter case, you should also probably avoid writing the formal part inline (unless it is very short).)

You can, of course, use various notational shorthands for formal writing, like writing $\forall n>n_0$ or similar, and likewise, when writing in natural language, there is also some wiggle room: for instance, you could write "for all real $x$" instead of "for all $x\in {\mathbb R}$", so there is some wiggle room in how much to spell out and how formal to be, but mixing formal language and natural language too much is bad form IMHO, makes the text harder to read and easier to write sloppily.

$\endgroup$
  • $\begingroup$ Hi tomasz, thank you for your response. I totally agree about the dynamics in the lectures. I see a lot this kind of notation in blackboards and it really makes sense, but I see very few books following this style. Yet there is some books which mimics this notational style. This is one of the reasons which motivated me do create this question. Besides that, I have a doubt: what you meant by you should also probably avoid writing the formal part inline ? What is to write inline? $\endgroup$ – diff_math Nov 17 '15 at 1:02
  • $\begingroup$ I mean, you should write it separately (as you would a longer equation), not within a paragraph of text. Usually, the only reasons for using such formal notation that I can think of are when you want to a) highlight the structure of a statement or b) express it in an unambiguous way (this can be difficult to do in natural language at times). In both cases, you would want the formal part to be clearly distinct, and besides, you have better control over alignment and line breaks this way). $\endgroup$ – tomasz Nov 17 '15 at 1:17
16
$\begingroup$

The informal, natural language examples are neither right nor wrong form the formal viewpoint, because the informal examples are not written in a formal way.

The general rule is that the "last quantifier" in natural language becomes the innermost quantifier in formal language. Here are some common examples of informal phrasings and their formal counterparts:

  • A sequence $(x_n)$ converges to $L$ if for all $\epsilon > 0$ there is an $N$ such that $|x_n - L| < \epsilon$ for $n > N$. Formally: $$(\forall \epsilon > 0)(\exists N)(\forall n)[ n > N \to |x_n - L| < \epsilon]$$

  • A function $f$ is continuous at a point $x$ if for every $\epsilon > 0$ there is a $\delta > 0$ such that $|f(x) - f(y)| < \epsilon$ for all $y$ with $|y-x| < \delta$. Formally: $$ (\forall \epsilon> 0)(\exists \delta > 0)(\forall y)[|x-y| < \delta \to |f(x) - f(y) | < \epsilon].$$

This is something that is rarely mentioned explicitly in textbooks, but which you have to learn as a student in order to read informal mathematics correctly. But that does not make the informal mathematics "wrong" and the formal mathematics "right". They are simply different ways of approaching the same topic.

$\endgroup$
  • $\begingroup$ The convergence definition would be probably more coherent with the informal phrasing if you write it this way: $$(\forall \epsilon > 0)(\exists N)(\forall n > N)\,[\,|x_n - L| < \epsilon\,]$$ $\endgroup$ – CiaPan Nov 16 '15 at 7:59
  • $\begingroup$ @CiaPan: thanks. I did write it that way at first, but then I decided I liked to see the $\to$ in both of the formulas, so I changed it. So I agree that the formula you wrote is appealing as a translation of the informal phrasing. $\endgroup$ – Carl Mummert Nov 16 '15 at 14:02
7
$\begingroup$

I think you're correct that in precise logical statements the quantifier should come first, and the more colloquial mathspeak is an abuse. This bothered me for a while when I went from my first logic class to my first analysis class.

$\endgroup$
  • $\begingroup$ This can be a problem sometimes, I guess. Because this abuse makes sense for some people (who speakes english or other language with similar grammar), but not for all. Japanese grammar, for instance, is very different. I'm not sure if a japanese student would translate this formulas in native language and understand why the change of position of the quantifier. Basically that's what this abuse is: a translate of native language in logic formulas (ignoring the fact that the formulas are formally wrong). $\endgroup$ – diff_math Nov 15 '15 at 16:33
6
$\begingroup$

Strictly in terms of formal logic, quantifiers are at the beginning of any formula. However, no one gives a proof that is written in the formal language. Even simple proofs would be very long and unreadable. The point is that statements like the probability example you gave can be written in the formal language.

$\endgroup$
  • $\begingroup$ I understand what you say. But about the uniform convergence example? That formula only makes sense if you know english (or other language with similar grammar), for it is just a translation of words to logic symbols. In this sense, this makes the mathematics communication less universal and more arbitrary. $\endgroup$ – diff_math Nov 15 '15 at 17:13
  • 2
    $\begingroup$ Yes, this is a good point. But it shouldn't be surprising. One advantage of a formal language is that it is unambiguous. Anyone, regardless of what natural language they speak, will interpret a sentence in the formal language in the same way. The price for this clarity of course is readability. Natural languages, because of their inherent ambiguity, are subject to many more limitations. But remember, formal languages have their limitations as well. Most notably, the Godel Incompleteness Theorem. $\endgroup$ – Tim Raczkowski Nov 15 '15 at 17:21
5
$\begingroup$

The proper usage of a formal notation or of a more informal one depends particularly on the context of presentation. It is essential to whom we communicate an idea and this should guide us to use a suitable level of formal notation.

Here is an excerpt from P.R. Halmos' instructive paper How to write Mathematics regarding the aspect:

What about the usage of logical symbols?

P. R. Halmos: Here is a sample :

"Prove that any complex number is the product of a non-negative number and a number of modulus $1$."

...

One way to recast the sample sentence of the preceding paragraph is to establish the convention that all "individual variables" range over the set of complex numbers and then write something like $$\forall z\exists p\exists u [(p=|p|) \wedge (|u|=1) \wedge (z=pu)]. $$

I recommend against it. The symbolism of formal logic is indispensable in the discussion of the logic of mathematics, but used as a means of transmitting ideas from one mortal to another it becomes a cumbersome code. The author had to code his thoughts in it (I deny that anybody thinks in terms of $\exists, \forall, \wedge$, and the like), and the reader has to decode what the author wrote ; both steps are a waste of time and an obstruction to understanding. Symbolic presentation, in the sense of either the modern logician or the classical epsilontist, is something that machines can write and few but machines can read.

Hint: You might also have a look at the related question Why there is no sign of logic symbols in mathematical texts?

$\endgroup$
  • 2
    $\begingroup$ I can attest that, after years of training and practice, it is possible to learn to think directly in terms of $\exists$, $\forall$, and the like, but this is only likely to happen in a very few specialties of mathematical logic where we work with such things on a daily basis. When I teach analysis or abstract algebra, I switch back to the normal, informal treatment of quantifiers. I think that even most people who work in formal logic would agree with Halmos. For example, in our published papers, we only use formal notation when strictly necessary, and avoid it otherwise. $\endgroup$ – Carl Mummert Nov 16 '15 at 14:05
  • $\begingroup$ @CarlMummert: Many thanks for your contribution. Good to see, that you essentially agree based upon your personal, professional practicing and teaching experience. $\endgroup$ – Markus Scheuer Nov 16 '15 at 14:24
  • $\begingroup$ How to write Mathematics seems to be a good reading, thanks for recommending. Also I will take a look at the another question. $\endgroup$ – diff_math Nov 17 '15 at 0:02
  • $\begingroup$ About Halmos example, I must say that I think he exaggerated a little. Would be better to not consider all variables ranging over the complex and write something like $$\forall z\in\mathbb{C},\ \exists p\in\mathbb{Z}_{\geq 0},\ \exists u\in\mathbb{C},\ (|u|=1,\ z = pu)$$ This is still readable. $\endgroup$ – diff_math Nov 17 '15 at 0:49
  • 1
    $\begingroup$ @Markus Scheuer It's fine to keep the comments, thanks. $\endgroup$ – diff_math Nov 18 '15 at 3:52
3
$\begingroup$

I think that, at this point, it's useful to point out what "formal logic" actually is. Formal logic is reasoning based on the form of the statement, i.e., its syntax. For example, the statement $(X\land Y)\rightarrow X$ is true not because you know something about the individual meaning of $X$ and $Y$ but because all statements of that form are true.

In formal logic, we use a fixed syntax, to make this reasoning based on form simpler. In particular, this syntax places quantifiers ahead of the thing being quantified over: we write "$\forall x\,\varphi$" not "$\varphi,\, \forall x$".

When writing informally (and, here, informal really means "casual", rather than "not based only on the form of the sentence"), this order is often reversed because, everyday English is more flexible than the syntax of first-order logic.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.