A principle of mathematical induction for partially ordered sets with infima? - MathOverflow

A principle of mathematical induction for partially ordered sets with infima?

2010-09-09T22:51:44Z

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

www.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~~?

Answer by Harry Gindi for A principle of mathematical induction for partially ordered sets with infima?

2010-09-10T00:28:09Z

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.

Answer by François G. Dorais for A principle of mathematical induction for partially ordered sets with infima?

2010-09-10T01:01:15Z

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:

If $x \in S$ and $y < x$ then $y \in S$.
If $x \in S$ and $x < y$ then there is some $z \in S$ such that $x < z \leq y$.
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

Answer by Pete L. Clark for A principle of mathematical induction for partially ordered sets with infima?

2010-09-10T02:15:55Z

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://www.math.uga.edu/~pete/realinduction.pdf

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

Answer by Joel David Hamkins for A principle of mathematical induction for partially ordered sets with infima?

2010-09-10T11:20:09Z

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.)