# What's the problem with these alphabetic collisions?

I'm reading Halmos' Naive Set Theory.

According to the usual and natural convention "for some $y\,(x\, \epsilon \, A)$" just means "$x\, \epsilon \, A"$. It's equally harmless if the letter used has already been used with "for some-" or "for all-." Recall that "for some $x \, (x\, \epsilon \, A)$ means the same as "for some $y\, (y\, \epsilon \, A)$; it follows that a judicious change of notation will always avert alphabetic collisions.

It seems they change the letter to avoid these alphabetic collisions, but what's the problem with it? For me, it's clearer when it's stated without the letter chaging, just as in the bold text. Where are these alphabetic collisions going to be harmful? In the past, I felt confused when I saw "for some $y\,(x\, \epsilon \, A)$", I thought it was a statament about two objects.

-
This doesn't make sense. Can you give more context? –  Ted Nov 21 '12 at 16:59
The $>$ is a typo. –  Andres Caicedo Nov 21 '12 at 17:00
do you mean to use the symbol $\in$? –  Holdsworth88 Nov 21 '12 at 17:02
@Holdsworth88: The $\in$ symbol is known as $\epsilon$-relation. In fact the original notation used $\epsilon$ and you can find old papers which used it that way. Halmos' book is quite old nowadays. –  Asaf Karagila Nov 21 '12 at 17:04
I think that when Halmos writes "alphabetic collisions" he is referring to "for some $y(x\in A)$", and he suggests avoiding these by writing "for some $x(x\in A)$" instead. That is, Halmos wants to do what you want to do, and wants to avoid the sort of statement you find confusing. He is agreeing with you. –  Gerry Myerson Nov 22 '12 at 0:33

It’s really helpful for (aspiring) mathematicians to understand a couple of things that are more often taught in computer science than mathematics: a) the difference between bound and free variables in mathematical expressions, and b) the fact that the logical statements mathematicians write (especially if-then statements) often have hidden quantifiers. The following two statements mean the same thing:

If $n^2$ is even, then $n$ is even.

If $r^2$ is even, then $r$ is even.

This is because the variable in each is bound by a hidden/unwritten for all quantifier. On the other hand, the statements $n$ is even and $r$ is even do not mean the same thing, because in those, the variables are free — there is no for all or there exists quantifier (hidden or not). They are statements about a specific variable, $n$ or $r$. When combining statements that use the same letter, it’s often convenient to rename bound variables (where the particular letter is essentially meaningless) to avoid confusion.

Halmos is not saying that you should change letters when it changes the meaning.

The context for this is here, where Halmos describes what a sentence is so that he can discuss the axiom of specification. He gives his description with a set of grammatical productions. Formalizing it with Backus-Narr, it goes like this:

<letter> ::= a|b|c|...|A|B|C|... (Halmos doesn't list the <letter>s.)

<sentence> ::=
(<letter> ∈ <letter>)
| (<letter> = <letter>)
| (<sentence> and <sentence>)
| (<sentence> or <sentence>)
| (not <sentence>)
| (if <sentence> then sentence)
| (<sentence> if and only if <sentence>)
| (for some <letter>, <sentence>)
| (for all <letter>, <sentence>)


Halmos assumes the reader pretty much knows what the possible sentences mean, but he takes a moment to point out (in different words than mine, and rather incompletely for modern readers, I think) that changing letters might be useful to clarify things. Consider these two sentences:

for some x, (x ∈ B)
(x ∈ A)


The first one doesn’t “depend on x,” because x is bound by the quantifier. The second one does “depend on x”; x is free. No problem so far, but it becomes confusing if you combine the two into this compound sentence:

((for some x, (x ∈ B)) and (x ∈ A))


The meaning is unambiguous (x is in A, and B is not empty), but why not write it this way, which is clearer?

((x ∈ A) and (for some y, (y ∈ B)))


(Note that you can’t change the first x to y instead, because then the result depends on y, not x.) For another context where this renaming of bound variables is useful read about $\alpha$-conversion in the lambda calculus.

-

His claim in the first sentence is just that $$\exists{y}:\phi(x)$$ means the same as $$\phi(x),$$ because the existentially quantified variable ($y$) doesn't appear in the formula being quantified. (The first form is confusing, though, because it makes you wonder if it's a typo and should read $\exists{x}:\phi(x)$ instead.) This part of the paragraph is not related to the next part, except in that he's explaining different ways to form mathematical statements. His claim in the next sentence is that it's fine to form a sentence like $$\exists{x}:\left(\forall{x}:\phi(x)\right).$$ I don't know that I agree with that claim… surely that sentence is ambiguous at best. But no one needs to use the ambiguous form: as he concludes by pointing out, you can always choose the names of your quantified variables to avoid any such collision of notation.

-
That is not his claim. He's just saying something very simple: that since we have choice on what symbol to use, we should use that choice and avoid collisions. –  ShreevatsaR Mar 15 '14 at 3:05
How do you interpret this? "It's equally harmless if the letter used has already been used with 'for some-' or 'for all-'." –  mjqxxxx Mar 15 '14 at 5:25
See the context from the book — he's saying two separate things about the grammar he defined: One, "if the letter used does not occur in the sentence, no harm is done" (because $\exists{y}:\phi(x)$ means same as $\phi(x)$, you can just remove what's redundant). Two, "it is equally harmless if the letter used has already been used" (because $\exists{x}:\phi(x)$ and $\exists{y}:\phi(y)$ mean the same thing, we can always use a different letter). –  ShreevatsaR Mar 15 '14 at 6:39