13
$\begingroup$

I work at a four-year teaching school, where we pride ourselves on teaching pure math, proof, and a rather obsessive carefulness of work. Recently I have been criticized for saying that "Let $x \in A$" is often a good way to begin a proof of a statement about all elements of $A$. The criticism is based on the objection that $A$ could be empty, in which case there is no $x$ to be in $A$. The issue affects quite a lot of mathematical content, because more than half of our proofs are proofs of universal statements, and most of them begin this way.

I have objected that if $A$ is empty, then any universal statement $\forall x \in A ...$ is vacuously true, but people are telling me that this needs to be dealt with as a special case, or else the proof is technically incorrect, etc.

I have appealed to normal mathematical conventions, without success. Our department prides itself on being more careful than normal working mathematicians. Convention can do what it will, but we intend to be right!

I have appealed to serious logic, by talking about the underlying meaning of "Let $x \in A$." In my reading it plays a dual role of symbol introduction ("Use $x$ to represent a single thing") and assumption ("Assume $x \in A$"). But these arguments have no traction -- "our students can't be expected to understand clever subtleties of metalogic."

I fear the only option remaining is to appeal to authority -- some specific authority who says this act of "Let $x \in A$" has some sort of seal of approval. Maybe such an authority is here?

From this question you might thing I work with fools, but they're really very wonderful and intelligent people, and the sense of family here is unusually strong. Like family, they drive me out of my head sometimes. Probably it's mutual.

So I suppose I have two questions: 1. Am I right? 2. Is there any hope for me to persuade my colleagues that I'm right?

(3. But social advice would be welcome too.)

Thank you,

Anonymous Coward

$\endgroup$
7
  • 5
    $\begingroup$ I think you're right, but we don't handle social questions here, so I'm afraid this question is off-topic. I'll say that I think this sort of objection is very picayune and without merit if it is raised each and every time -- one dispenses with such things in the first week of class and it "goes without saying" henceforth. Aiming for clarity and naturalness of expression is much more important than satisfying the petty-minded demands of pedantic colleagues. $\endgroup$
    – Todd Trimble
    Nov 23, 2010 at 13:18
  • 5
    $\begingroup$ However, to temper my withering contempt just a bit: it's really not a bad idea to get into (and teach your students) the habit of thinking about the empty case, because even grown mathematicians slip up here. An example might be: how many connected components does the empty space have? $\endgroup$
    – Todd Trimble
    Nov 23, 2010 at 13:31
  • 5
    $\begingroup$ I vote for Todd's second response, but this has to be done with care. You don't want to send students out spending too much time thinking and talking about the empty set. But they should know that it can be an issue and therefore should be considered in advance. It is well-known that a certain mathematician currently living in France has flustered many a speaker by simply asking "but what about the empty set?" after a theorem has been stated. $\endgroup$
    – Deane Yang
    Nov 23, 2010 at 13:47
  • 2
    $\begingroup$ I don't see why this is off-topic. You have a point that actual professors at a four-year college are confused about. What better place for him or her to turn than here? $\endgroup$
    – arsmath
    Nov 23, 2010 at 16:29
  • 1
    $\begingroup$ Is there an underlying tension between platonists and formalists here, or am I reading into things? $\endgroup$ Nov 23, 2010 at 17:59

5 Answers 5

25
$\begingroup$

Please print this and hang it on your office door for your colleagues to see.

The inference rule for $\forall x \in A . \phi(x)$ is as follows (in natural deduction style): $$\frac{\begin{matrix}[x\in A] \\\\ \vdots \\\\ \phi(x)\end{matrix}}{\forall x \in A . \phi(x)}$$ This rule is valid for every set $A$. It can be understood as follows: if from the assumption $x \in A$ we prove $\phi(x)$ then we may conclude $\forall x \in A . \phi(x)$ (and the assumption $x \in A$ is thus discharged, which is indicated by the square brackets).

Translating this to English we get the following recipe: in order to prove $\forall x \in A . \phi(x)$ it is sufficient to prove $\phi(x)$ from the assumption $x \in A$. In other words, a proof of the form

Let $x \in A$. ... Therefore $\phi(x)$.

is a valid proof of $\forall x \in A . \phi(x)$. Irrespective of whether $A = \emptyset$.

Let us also look at the special case when $A = \emptyset$. I will use the above inference rule to show that $\forall x \in \emptyset . \phi(x)$ is valid, irrespective of $\phi$. Recall that the empty set satisfies $y \not\in \emptyset$, whatever $y$ is.

Let $x \in \emptyset$. Also, from the defining property of $\emptyset$ we have $x \not\in \emptyset$. We have the contradiction $x \in \emptyset$ and $x \not\in \emptyset$, and from contradiction it follows that $\phi(x)$ holds.

In conclusion: it is not the case that $\forall x \in \emptyset . \phi(x)$ requires a special proof method. Quite the opposite, the fact that $\forall x \in \emptyset . \phi(x)$ is always true is proved from the usual inference rule for universal quantification.

$\endgroup$
2
  • 5
    $\begingroup$ +1 for the first line... $\endgroup$ Nov 23, 2010 at 14:41
  • $\begingroup$ "Please print this and hang it on your office door for your colleagues to see", and bring at least one copy with you to class. $\endgroup$
    – user5810
    Nov 23, 2010 at 15:31
11
$\begingroup$

Logically you are quite right.

It may pacify your doubters if you reword as "Suppose $x \in A$", which makes it more apparent that you are proving an implication of the form "$x \in A$ implies $x$ has the desired property".

Stylistically, your doubters are entitled to their opinion that it is better to make the trivial case explicit, but that opinion is not mine.

$\endgroup$
8
$\begingroup$

I'm going to take a guess as to what your colleagues are worried about (though they are basically wrong to worry about it for the reasons that Andrej outlines). In classical first-order logic this sentence is a tautology: $$ \forall x. \phi(x) \implies \exists x. \phi(x), $$ but the same rule with bounded quantifiers is false: $$ \forall x \in A. \phi(x) \implies \exists x \in A. \phi(x). $$

This is only reason why I imagine they would be worried. I could imagine that the occasional student could start with "Suppose there exists an $x \in A$ such that $\phi(x)$..." and somehow slip and concludes that there exists an $x$ such that $\phi(x)$.

The reason for the difference between the the unbounded and bounded quantifiers is that classical first-order logic assumes that the universe of discourse is not empty. The correct rules of inference when the universe of discourse can be empty is known as free logic. It's discussed in great depth in this article at the Stanford Encyclopedia of Philosophy.

$\endgroup$
7
$\begingroup$

I have to say that I find this topic slightly ridiculous. Of course you can start a proof of a universal statement with something "Let $x\in A$." (!!!) There are a lot of places where professional mathematicians tend to be sloppy (putting quantifiers both in front and behind a formula, writing sets without curly brackets, not distinguishing properly between the subset and proper subset relation, and so on), but this is not one of them. Obsessing about something like this is, I said it before, just ridiculous.

I could write something about the rule of universal introduction in predicate calculus and other things from a logical perspective, but I won't.
I am convinced that once you start obsessing over formalities on this level (i.e., in the worst case interpretation, skipping a case distinction with one completely trivial case), you will very quickly loose the view of the big picture. Mathematics is too difficult and too beautiful to get tied up in such a discussion.

$\endgroup$
5
$\begingroup$

I agree with the previous answers, but it seems worthwhile to separate two points. (1) You are right to use "Let $x\in A$" even when $A$ might be empty. (2) Even if you had been wrong, such matters can be handled once and for all, the first time they come up in a course, and ignored thereafter, so it is silly to make them into a big deal.

$\endgroup$

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