Filter-closed vs. chain-closed - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T01:26:53Z http://mathoverflow.net/feeds/question/15751 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/15751/filter-closed-vs-chain-closed Filter-closed vs. chain-closed porton 2010-02-18T19:50:46Z 2010-02-26T19:33:09Z <p>Let A is a complete lattice.</p> <p>I call a subset $S$ of A <em>filter-closed</em> when for every filter base $T$ in $S$ we have $\bigcap T\in S$. (A <em>filter base</em> is a nonempty, down directed set.)</p> <p>I call a subset $S$ of A <em>chain-closed</em> when for every non-empty chain $T$ in $S$ we have $\bigcap T\in S$.</p> <p><strong>Conjecture</strong> $S$ is filter-closed if and only if $S$ is chain-closed.</p> http://mathoverflow.net/questions/15751/filter-closed-vs-chain-closed/15753#15753 Answer by Gerhard Paseman for Filter-closed vs. chain-closed Gerhard Paseman 2010-02-18T19:56:43Z 2010-02-18T19:56:43Z <p>I made a post to sci.math regarding this question. You might check that post for some suggestions. Others might check the thread for more history on that problem.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2010.02.18</p> http://mathoverflow.net/questions/15751/filter-closed-vs-chain-closed/15758#15758 Answer by Gerald Edgar for Filter-closed vs. chain-closed Gerald Edgar 2010-02-18T20:34:14Z 2010-02-18T20:34:14Z <p>How is the following related to the question...</p> <p>Let $P$ be a partially-ordered set. Suppose every chain in $P$ has a least upper bound. Then every subset of $P$ which is directed has a least upper bound.</p> <p>I needed this once, long ago, didn't find it, so included a proof in the paper. Many years later someone gave me a reference for it: Mayer-Kalkschmidt &amp; Steiner, <em>Duke Math. J.</em> 31 (1964) 287-289</p> http://mathoverflow.net/questions/15751/filter-closed-vs-chain-closed/15769#15769 Answer by Joel David Hamkins for Filter-closed vs. chain-closed Joel David Hamkins 2010-02-19T00:00:50Z 2010-02-19T01:57:29Z <p>Indeed, your conjecture is correct. </p> <p><b>Theorem.</b> If L is a complete lattice and S is a subset of L, then S is chain-closed iff S is filter-closed.</p> <p>Proof. Clearly filter-closed implies chain-closed, since every chain is a filter base. Conversely, suppose that S is chain-closed, and that A is a filter base contained in S. Note that S is trivially filter-closed with respect to any finite filter base. So suppose by induction that S is filter-closed with respect to any filter base of size smaller than |A|. Enumerate A = { a<sub>&alpha;</sub> | &alpha; &lt; |A| }. Let b<sub>&beta;</sub> be the meet of { a<sub>&alpha;</sub> | &alpha; &lt; &beta; }. This is the same as the meet of the filter sub-base of A generated by this set. This filter sub-base has size less than |A|, and hence by induction every b<sub>&beta;</sub> is in S. Also, the b<sub>&beta;</sub> are a descending chain in S, since as we take more a<sub>&alpha;</sub>, the meet gets smaller. Thus, by the chain-closure of S, the meet b of all the b<sub>&beta;</sub> is in S. This meet b is the same as the meet of A, and so we have proved that S is filter-closed. QED</p> <p>This argument is very similar to the following characterization of (downward) complete lattices (which I had posted as my original answer). </p> <p><b>Theorem.</b> The following are equivalent, for any lattice L.</p> <ul> <li><p>L is complete, in the sense that every subset of L has a greatest lower bound.</p></li> <li><p>L is filter complete, meaning that every filter base in L has a greatest lower bound.</p></li> <li><p>L is chain complete, meaning that every filter base in L has a greatest lower bound.</p></li> </ul> <p>Proof. It is clear that completeness implies filter completeness, since every filter base is a subset of L, and filter completeness implies chain completeness, since every chain is a filter base. For the remaining implication, suppose that L is chain complete. We want to show that every subset A of L has a greatest lower bound in L. We can prove this by transfinite induction on the size of A. Clearly this is true for any finite set, since L is a lattice. Fix any infinite set A. Enumerate A as { a<sub>&alpha;</sub> | &alpha; &lt; |A| }. By the induction hypothesis, for each &beta; &lt; |A|, the set { a<sub>&alpha;</sub> | &alpha; &lt; &beta; } has a greatest lower bound b<sub>&beta;</sub>. Note that { b<sub>&beta;</sub> | &beta; &lt; |A| } is a chain, because as we include more elements into the sets, the greatest lower bound becomes smaller. Thus, there is an element b in L that is the greatest lower bound of the b<sub>&beta;</sub>'s. It is easy to see that this element b is also a lower bound of A. QED</p> <p>One can describe the method as finding a linearly ordered cofinal sequence through the filter generated by the filter base. This proof used AC when A was enumerated, and I believe that this cannot be omitted.</p> <p>One can modify the argument to show that for every infinite cardinal &kappa;, then a lattice is &kappa;-complete (every subset of size less than &kappa; has a glb) iff every filter base of size less than &kappa; has a glb iff every chain of size less than &kappa; has a glb.</p> <p>Note that if the lattice is <em>bounded</em> (meaning that it has a least and greatest element), then having greatest lower bounds for every set is the same as having least upper bounds for every set, since the least upper bound of a set A is the greatest lower bound of the set of upper bounds of A. Thus, a <em>complete lattice</em> is often defined as saying that every subset has a glb and lub.</p> <p>There have been a few questions here at MO concerning complete lattices. See <a href="http://mathoverflow.net/questions/11728" rel="nofollow">this one</a> and <a href="http://mathoverflow.net/questions/11435" rel="nofollow">this one</a>.</p> <p>Questions about the degree of completeness of a partial order often arise in connection with forcing arguments, and when one is speaking of partial completeness and partial orders (rather than lattices), and the situation is somewhat more subtle. For example, a partial order P is said to be &kappa;-closed if every linearly ordered subset of P of size less than &kappa; has a lower bound. It is &kappa;-directed closed if every filter base in P of size less than &kappa; has a lower bound. With these concepts, it is no longer true that a partial order is &kappa;-directed closed if and only if it is &kappa;-closed. One example arising in forcing would be the forcing to add a slim &kappa;-Kurepa tree, which is &kappa;-closed but not &kappa;-directed closed. The difference between these two concepts is related to questions of large cardinal indestructibility, for Richard Laver proved that every supercompact cardinal &kappa; can become indestructible by all &kappa;-directed closed forcing, but no such cardinal can ever be indestructible by all &kappa;-closed forcing, precisely because the slim &kappa;-Kurepa tree forcing destroys the measurability of &kappa;.</p> http://mathoverflow.net/questions/15751/filter-closed-vs-chain-closed/16548#16548 Answer by porton for Filter-closed vs. chain-closed porton 2010-02-26T19:33:09Z 2010-02-26T19:33:09Z <p>I wrote more detailed proof based on the proof by Joel David Hamkins in <a href="http://www.mathematics21.org/binaries/filters.pdf" rel="nofollow">this online article</a>.</p>