43
$\begingroup$

Recently I learned that there is a useful analogue of mathematical induction over $\mathbb{R}$ (more precisely, over intervals of the form $[a,\infty)$ or $[a,b]$). It turns out that this is an old idea: it goes back to Khinchin and Perron, but has for some reason never quite caught on and thus keeps getting rediscovered. A nice recent paper is

http://alpha.math.uga.edu/~pete/Kalantari07.pdf

[As a side note, I gave a talk two days ago in the VIGRE Graduate Seminar at UGA -- essentially, a colloquium for graduate students, with talks which are supposed to be accessible to first and second year students -- about induction over the real numbers with applications to snappy proofs of essentially all the basic "hard theorems" of honors calculus / elementary real analysis. It was a smashing success: the students both enjoyed stretching their minds around this new form of induction and appreciated the application to consolidated proofs of theorems which were, in their recent memeory, not so quick or easy to prove.]

The way I like to state the principle is a little different from Kalantari's approach. [I actually got confused by Kalantari's "axioms for induction" when I first saw them and was under the impression that they were wrong. In fact I was wrong, and he quickly responded to my email on the subject, setting me straight and, kindly, mentioning that others had made the same mistake.] Here's my preferred version:

Let $(X,\leq)$ be a totally ordered set with a least element, which we may as well call $0$.

Say that $X$ has infima if...every nonempty subset $S$ of $X$ has an infimum.

Say that $S \subset X$ is an inductive subset if all of the following hold:
(POI1) $0 \in S$.
(POI2) For all $x \in S$, if there exists $z \in X$ such that $x < z$ -- in other words, if $x$ is not a maximum element of $X$ -- then there exists $y > x$ such that the interval $[x,y]$ is contained in $S$.
(POI3) For all $x \in X$, if $[0,x) \subset S$, then $x \in S$.

Finally, we say that $X$ satisfies the principle of ordered induction if the only inductive subset of $X$ is $X$ itself.

Theorem: For a totally ordered set $X$ with a minimum element, TFAE:
(i) $X$ has infima.
(ii) $X$ satisfies the principle of ordered induction.

The proof is straightforward. Applying this to half-closed intervals as above gives real induction. Also, applying it to a well-ordered set recovers transfinite induction exactly as it is usually stated -- i.e., with an extra axiom for "limit elements", even though one could formally combine (POI2) and (POI3) into a single case.

This issue came up on Tuesday on our sister site math.SE -- someone asked whether there was such a thing as real induction -- and I answered it, yes, as above. Then someone commented on my answer: what about generalizations to partially ordered sets?

There is a well-known principle of induction on partially ordered sets satisfying the descending chain condition, or equivalently, in which every nonempty subset has a minimum. This is called, by mathematicians of various stripes, well-founded induction or Noetherian induction. (As far as I can see it should be called Artinian induction. Anyone want to address that? Edit: I am satisfied by Dave Anderson's comment below.)

Note that a partially ordered set with DCC need not have a minimum element, which is certainly necessary for the above setup in totally ordered sets. But this isn't a big deal: if $(X,\leq)$ is a poset satisfying DCC, the poset $X_0$ obtained by adjoining a minimum element $0$ still satisfies DCC, and nothing is lost here.

[Edit: as Francois Dorais points out, adding a minimum is not enough; still a partially ordered set satisfying DCC need not have infima. So what I am asking about really is different from Noetherian induction.]

After a little thought I was optimistic that there should be a version of induction partially ordered sets with a minimum element. I even thought that the right definition of inductive subset should be essentially the one given above, with (POI2) modified slightly to

(POI2'): for every $x \in S$ and $z \in X$ with $x < z$, there exists $y \in (x,z]$ such that the entire interval $[x,y]$ is contained in $S$.

And then I tried to prove that any poset with a minimum and having infima satisfies the principle of ordered induction. And I couldn't. Eventually I found the following counterexample: let $A$ be an infinite set and $X = 2^A$ be its power set, partially ordered by inclusion. Of course $X$ has infima: take the intersection. Let $S$ be the collection of all finite subsets of $A$. Then $S$ satisfies (POI1), (POI2') and (POI3) but is proper.

Neither can I think of some small modification of (POI2') which evades this example. I still think there should be some kind of principle of induction in partially ordered sets with infima, but I don't know what to do. Can anyone state such a principle which recovers as special cases as a special case the principle of ordered induction and the principle of Noetherian induction?

$\endgroup$
16
  • 3
    $\begingroup$ About the terminology: I always thought "noetherian" induction came from the fact that Spec of a noetherian ring has the DCC property you mention (due to the order-reversing nature of the functor)... whereas Spec of an artinian ring tends to be rather uninteresting, set-theoretically. $\endgroup$ Sep 9, 2010 at 23:28
  • 3
    $\begingroup$ As a side remark: induction over totally ordered sets with minimum element is rather familiar to analysts, especially to PDE people. In fact it is so universal in evolutionary PDEs, I think every paper I've read in the subject uses it somewhere or another. $\endgroup$ Sep 9, 2010 at 23:38
  • 1
    $\begingroup$ Small point: I think you've misstated POI3. You wrote: For all x∈S, if [0,x)⊂S, then x∈S. Do you mean: For all x∈**X**,... ? As you stated it, POI3 is vacuously true. $\endgroup$
    – Steve Kass
    Sep 9, 2010 at 23:45
  • 1
    $\begingroup$ @Pete: the references in the later paragraphs to (i),(ii), (iii) should be to (POI1), (POI2), and (POI3), for clarity. $\endgroup$ Sep 9, 2010 at 23:46
  • 4
    $\begingroup$ If you look way back at the original work, you find that the Heine-Borel theorem was thought of as a kind of "continuous induction" for intervals [a,b] in the real line. $\endgroup$ Sep 10, 2010 at 0:26

4 Answers 4

15
$\begingroup$

Something very close to François' conditions achieves the desired if-and-only-if version of the theorem for partial orders, providing an induction-like characterization of the complete partial orders, just as Pete's theorem characterizes the complete total orders.

Suppose that $(P,\lt)$ is a partial order. We say that it is complete if every subset $A$ has a least upper bound $sup(A)$ and a greatest lower bound $inf(A)$. This implies that $(P,\lt)$ has a least and greatest element, and in this case, it is easy to see that completeness is equivalent to the assertion that every set has a greatest lower bound (the least upper bound of a set with upper bounds is the greatest lower bound of its upper bounds). The complete partial orders are exactly the complete lattices.

For the purpose of this question, let us define that $S\subset P$ is inductive if the following occur:

  • (1) $S$ is downward closed: $y\lt x\in S\to y\in S$;
  • (2) $S$ has no largest element, except possibly the largest element of $P$;
  • (3) If $d=sup(A)$ for some $A\subset S$, then $d\in S$.

In (2), by a largest element, I mean an element that is larger than all other elements (in distinction with maximal element, a weaker concept). Conditions (2) and (3) are both slightly weaker than François' conditions. The difference in (2) is that we no longer assume that a condition $x\in S$ can be extended in any particular direction, and the difference in (3) is that we are not assuming here that $P$ is complete, but only that $S$ contains the suprema of its subsets, when these suprema exist.

Lastly, define that a partial order $(P,\lt)$ has partial-order induction if the only inductive set is all of $P$.

Theorem. For any partial order $(P,\lt)$, the following are equivalent:

  • $(P,\lt)$ is complete.
  • $(P,\lt)$ has least and greatest elements and satisfies partial-order induction.

Proof. For the forward implication, suppose $(P,\lt)$ is complete. It follows that $(P,\lt)$ has least and greatest elements, since these are the sup and inf of the emptyset. Suppose that $S\subset P$ is inductive. By (3) we know $sup(S)\in S$, which would make it the largest element of $S$, contrary to (2), unless $sup(S)$ is largest in $P$, in which case $S=P$ by (1). So $(P,\lt)$ has partial-order induction.

Conversely, suppose that $(P,\lt)$ has least and greatest elements and satisfies partial-order induction. We want to prove completeness. Suppose $B\subset P$ is nonempty and has no greatest lower bound. Let $S$ be the set of lower bounds of $B$. This is closed downwards, and so (1) holds. Since $B$ has no greatest lower bound, it follows that $S$ has no largest element, and so (2) holds. Finally, if $A\subset S$ and $sup(A)$ exists in $P$, then it remains a lower bound of $B$, since every element of $B$ is an upper bound of $A$ and $sup(A)$ is the least upper bound of $A$. Thus, (3) holds and so $S$ is inductive, contrary to the fact that it contains no elements of $B$. Thus, $B$ must have a greatest lower bound after all, and so $(P,\lt)$ is complete. QED

Note that when $(P,\lt)$ is a total order, then these concepts reduce to the conditions Pete mentions in the question (adding a least and greatest element if necessary). Thus, this theorem seems to be the desired generalization.

(I have deleted my other answer to the question, as it was based on a misunderstanding of the question.)

$\endgroup$
6
  • $\begingroup$ Nice answer, Joel! I still wonder, since my condition 1 was not necessary, whether there is a variation of just 2 & 3 that has an if-and-only-if characterization. $\endgroup$ Sep 10, 2010 at 18:25
  • 1
    $\begingroup$ I also wonder this---I played around with many variations before hitting on this one. Your argument avoiding (1) in effect uses completeness, and I don't know any nice characterization avoiding (1) without assuming some completeness. Another question is: can we get a nice characterization that doesn't require the maximal element? I need this in order to know $sup(S)$ exists, and don't have any nice characterization without the maximal element. $\endgroup$ Sep 10, 2010 at 20:14
  • $\begingroup$ Notational nit: in the terminology I am familiar with, a complete partial order (cpo) is a strictly more general notion than a complete lattice. en.wikipedia.org/wiki/Complete_partial_order $\endgroup$ Sep 11, 2010 at 18:29
  • $\begingroup$ The "lt" in part 2 seems to be missing the backslash. $\endgroup$ Sep 11, 2010 at 18:30
  • $\begingroup$ Excellent! Thanks to both Joel and François -- as ever, I can only accept one answer. I think this is a real MO success story. $\endgroup$ Sep 11, 2010 at 19:07
13
$\begingroup$

In my humble opinion, the general principle should have a very similar proof to the original principle to be considered a proper generalization. After reconstructing a proof of your original principle, I obtained the following generalization.

Theorem. Let $X$ be a poset in which every nonempty set has an inf. (Note that $X$ has a minimal element $0$ and that every set which is bounded above has a sup.) If $S \subseteq X$ is such that:

  1. If $x \in S$ and $y < x$ then $y \in S$.
  2. If $x \in S$ and $x < y$ then there is some $z \in S$ such that $x < z \leq y$.
  3. Every subset of $S$ which is bounded above (in $X$) has its sup in $S$.

Then $S = X$. (Note that 3 formally implies that $0 \in S$ since $0$ is the sup of the empty set.)

This is slightly different than the original principle, but one recovers the original principle by applying the above theorem to the subset $S' = \{x \in X : [0,x] \subseteq S\}$ instead of $S$.


After writing down the proof I had in mind, I realized that condition 1 is not necessary.

Proof of Theorem. Suppose $y \notin S$. Let $x = \sup\{z \in S : z \leq y\}$. By 3, $x \in S$ and so $x < y$. By 2, there is a $z \in S$ such that $x < z \leq y$, which contradicts the definition of $x$. QED

$\endgroup$
7
  • 2
    $\begingroup$ @Francois: I will need to check this over, but if it works as you say (of which I have very little real doubt), then this will absolutely be the answer to my question! Note that the distinction between $S$ and $S'$ is analogous to the distinction between "weak" versus "strong" induction, and it's something I had been thinking about as well. $\endgroup$ Sep 10, 2010 at 1:18
  • $\begingroup$ François, I've been looking at the same idea! But this gives only one direction of Pete's iff. For example, a partial order consisting of a single antichain has your inductive property vacuously, since there are no inductive sets, but it does not have greatest lower bounds for all subsets (for example, there is no minimal element). I think we should be able to find an if-and-only-if characterization! $\endgroup$ Sep 10, 2010 at 1:42
  • $\begingroup$ @Joel: Yes, I've been thinking about Pete's if-and-only-if characterization of completeness too but I haven't found any good leads. $\endgroup$ Sep 10, 2010 at 1:49
  • $\begingroup$ I agree -- I'm looking for an iff as well. Let me know if you come up with anything. $\endgroup$ Sep 10, 2010 at 2:03
  • 1
    $\begingroup$ @AIM_BLB As the post explains, I came up with this theorem after reading Pete L. Clark 's post somewhere between September 9 and September 10, 2010. I couldn't possibly claim originality here: it's very likely someone else came up with this before me but I have no idea if anyone published this before. (If you're looking for a citation, the 'cite' button will give you what you need.) $\endgroup$ Feb 19, 2019 at 4:43
3
$\begingroup$

This is a reply to Cam's question.

No, I did not base my talk directly on Kalantari's article, although I think it would be possible to do so. Instead I wrote up some lecture notes before the talk (and polished them a bit afterwards, once I realized I was on to something). See

http://alpha.math.uga.edu/~pete/realinduction.pdf

This document is not intended for publication. Please feel free to use it as you see fit.

$\endgroup$
2
$\begingroup$

A very nice generalization of indexing by a well-ordered set and using induction to prove something is provided by the notion of a $\kappa$-good tree for $\kappa$ a (usually infinite) regular cardinal see this MO question. To see it put to use in homotopy theory, take a look at Lurie's Higher topos theory A.1.5, A.2.8, and A.3.3, where it is used to prove (indirectly) that functor categories (and simplicially enriched functor categories) A^C where A is a combinatorial (resp. combinatorial simplicial) model category admit fibrant and cofibrant replacement functors (this follows by the small object argument once we prove that A^C is itself combinatorial).

The key here is the regularity of the cardinal $\kappa$, which allows us to take downward closures of $\kappa$-small subsets with impunity as well as enlarge subsets until certain diagrams commute (that is, given some diagrams commuting in the limit, we can find $k$-small subset B for which the diagram commutes in the limit of B.

$\endgroup$
4
  • $\begingroup$ I'm sorry to say that this is a little too highfalutin for me to evaluate on the spot. But I'll take your word for it that this is yet another kind of induction and give you +1 for mentioning it. $\endgroup$ Sep 10, 2010 at 1:23
  • $\begingroup$ Actually, rereading your question, this doesn't appear to answer it. Sorry for wasting your time. $\endgroup$ Sep 10, 2010 at 1:44
  • $\begingroup$ If you respond in a comment that you've seen my comment, I will delete this answer. $\endgroup$ Sep 10, 2010 at 1:44
  • $\begingroup$ Well, yes, I've read the comment. So you can delete the question if you like, although I am not myself pushing for this. $\endgroup$ Sep 10, 2010 at 1:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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