# noetherian induction

So I think I've misunderstood the principle of Noetherian induction as stated in the Hartshorne exercise II.3.16, or his statement is slightly incorrect. He says: "Let $X$ be a Noetherian topological space, and let $\mathscr{P}$ be a property of closed subset of $X$. Assume that for any closed subset $Y$ of $X$, if $\mathscr{P}$ holds for every proper closed subset of $Y$, then $\mathscr{P}$ holds for $Y$. (In particular, $\mathscr{P}$ must hold for the empty set.) Then $\mathscr{P}$ holds for $X$."

Why does $\mathscr{P}$ hold for the empty set? What if $\mathscr{P}$ is the property of being nonempty and $X = \varnothing$?

-
It just means that you can't use induction to prove that $X$ is nonempty (which is not surprising). –  trutheality Jun 26 '11 at 20:36

$\mathscr P$ holds for the empty set $\varnothing$ because it holds for every proper closed subset of $\varnothing$.

You should not let the fact that there is no proper closed subset of $\varnothing$ confuse you!

-
And yet I did... "Vacuously true" things have confused me in the past. –  Justin Campbell Jun 26 '11 at 20:42

It is just as Mariano says.

The situation here is completely analogous to the fact that if one wishes to prove a statement is true for all natural numbers by strong induction (or more generally for a family of values indexed by a well-ordered set) then, logically speaking, one does not have to single out a "base case" $P(0)$, because the induction step allows us to deduce $P(0)$ from $P(n)$ for all $n < 0$, of which there are none.

Many other people have found this confusing. (I believe it came up in a MO question asked by Bjorn Poonen a while back, which is not to imply that he was confused by it!) In practice, this little logical filigree doesn't seem to save any time: you still have to know how to prove $P(0)$ assuming nothing, and the argument for this is usually rather different and often easier than the general induction step(s).

Added: Just to place the last card on the table, this "Noetherian induction" is really exploiting the fact that (by definition) a topological space is Noetherian iff its closed sets satisfy the Descending Chain Condition, which in order-theoretic terms is expressed by saying that the containment relation among closed subsets is a well-founded partial ordering (or sometimes "well-partial ordering"). A partial ordering $(X,\leq)$ is well-founded iff every nonempty subset has a minimal element and this shows that a subset $Y$ of $X$ with the property:

$\forall x \in X \ (\forall y \in X, y < x \implies y \in Y) \implies x \in Y$

must be all of $X$: if not, consider the least element of $X \setminus Y$.

-
The phenomenon of the "special case" sometimes also makes an appearance in "usual" induction (e.g., the 'proof' that all elements of a finite set are equal fails because the inductive argument does not apply for the case $P(1)\Rightarrow P(2)$). And sometimes it occurs at locations other than the base for strong induction. The proof that a factorization into primes exists is a strong-induction proof in which the general proof fails for all primes, and a special argument is given for the case of primes. (Not a correction, just an addition to your answer). –  Arturo Magidin Jun 26 '11 at 21:49
Nice metaphor, that logical filigree. I had to look up the word in a dictionary and was surprised to learn that it came from the French filigrane ( of which the translation into modern English is watermark ). It is always instructive to read you, even if one thinks one knows about Noetherian induction! –  Georges Elencwajg Jun 26 '11 at 22:07
From a more general perspective, one may view Noetherian topological spaces as topological analogs of the order-theoretic notion of a well-quasi-order. For example see Jean Goubault-Larrecq, On Noetherian Spaces. –  Bill Dubuque Jun 26 '11 at 23:22

I believe that the answer lies hidden within the depth of "vacuously true argument".

An argument of the form $\forall x\varphi$ is true if and only if there is no $x$ such that $\lnot\varphi(x)$.

An example I often used with my students was "If it I am drinking beer during the class then you are all elephants" (or something similar along these lines, usually including alcohol of some sort and a ridiculous entailment). It does not matter that I am talking to people, because I am now allowed to drink alcohol during class (as a teacher/TA anyway).

If we say that $P(x)$ holds for $x$ if for all $y<x$ holds $P(y)$. In this case $<$ is proper inclusion of closed subsets; since there are no proper subsets of the empty set, the argument $P(x)$ holds for $\varnothing$ vacuously, as above.

-
Examples should always include alcohol. –  Mariano Suárez-Alvarez Jun 26 '11 at 20:51
@Mariano: I agree, this is the most alcohol I am allowed to bring into the classroom... –  Asaf Karagila Jun 26 '11 at 20:57
You can drink before going to class, though... The possibilities are endless! :) –  Mariano Suárez-Alvarez Jun 26 '11 at 21:07
@Mariano, I can. But if I am out of beer in my office then there is no feasible source of alcohol around. Sadly it happens more than I wish for. –  Asaf Karagila Jun 26 '11 at 21:11