Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let A is a complete lattice.

I call a subset $S$ of A filter-closed when for every filter base $T$ in $S$ we have $\bigcap T\in S$. (A filter base is a nonempty, down directed set.)

I call a subset $S$ of A chain-closed when for every non-empty chain $T$ in $S$ we have $\bigcap T\in S$.

Conjecture $S$ is filter-closed if and only if $S$ is chain-closed.

share|improve this question
    
Would you mind defining "chain" for completeness sake? I am guessing it is just a decreasing sequence, but it would be nice to nail this down before I think too hard about it. –  David Speyer Feb 18 '10 at 19:54
    
The formulation of filter-closed is presumably wrong, one instance of A should be S –  Gerald Edgar Feb 18 '10 at 20:19
    
A chain is subset of a poset on which the induced order is complete. –  Michael Greinecker Feb 18 '10 at 20:20
    
A chain is a totally-ordered set. –  Gerald Edgar Feb 18 '10 at 20:20
    
Thanks, Gerald Edgar. A changed to S. –  porton Feb 18 '10 at 20:27
add comment

4 Answers 4

up vote 6 down vote accepted

Indeed, your conjecture is correct.

Theorem. If L is a complete lattice and S is a subset of L, then S is chain-closed iff S is filter-closed.

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α | α < |A| }. Let bβ be the meet of { aα | α < β }. 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β is in S. Also, the bβ are a descending chain in S, since as we take more aα, the meet gets smaller. Thus, by the chain-closure of S, the meet b of all the bβ 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

This argument is very similar to the following characterization of (downward) complete lattices (which I had posted as my original answer).

Theorem. The following are equivalent, for any lattice L.

  • L is complete, in the sense that every subset of L has a greatest lower bound.

  • L is filter complete, meaning that every filter base in L has a greatest lower bound.

  • L is chain complete, meaning that every filter base in L has a greatest lower bound.

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α | α < |A| }. By the induction hypothesis, for each β < |A|, the set { aα | α < β } has a greatest lower bound bβ. Note that { bβ | β < |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β's. It is easy to see that this element b is also a lower bound of A. QED

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.

One can modify the argument to show that for every infinite cardinal κ, then a lattice is κ-complete (every subset of size less than κ has a glb) iff every filter base of size less than κ has a glb iff every chain of size less than κ has a glb.

Note that if the lattice is bounded (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 complete lattice is often defined as saying that every subset has a glb and lub.

There have been a few questions here at MO concerning complete lattices. See this one and this one.

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 κ-closed if every linearly ordered subset of P of size less than κ has a lower bound. It is κ-directed closed if every filter base in P of size less than κ has a lower bound. With these concepts, it is no longer true that a partial order is κ-directed closed if and only if it is κ-closed. One example arising in forcing would be the forcing to add a slim κ-Kurepa tree, which is κ-closed but not κ-directed closed. The difference between these two concepts is related to questions of large cardinal indestructibility, for Richard Laver proved that every supercompact cardinal κ can become indestructible by all κ-directed closed forcing, but no such cardinal can ever be indestructible by all κ-closed forcing, precisely because the slim κ-Kurepa tree forcing destroys the measurability of κ.

share|improve this answer
1  
This is correct but there is a subtlety with the question. It is not sufficient to show that S is by itself a complete lattice, you also need that the meets of filters in S are the same as those computed in the enveloping complete lattice A. A small variation of your argument does this. –  François G. Dorais Feb 19 '10 at 0:10
    
Francois, you are right. I was mainly thinking just about whether completeness is equivalently characterized by filters and chains for a lattice. But the same idea works, and I'll edit my answer accordingly. –  Joel David Hamkins Feb 19 '10 at 1:03
    
Note: It isn't generally true that S will be a complete lattice, for it needn't even be a lattice. For example, perhaps S is an antichain in the larger lattice. This is trivially chain-closed, since all chains in S have only one element. (And it is also trivially filter-closed, since all filter bases subset S also have only one element.) –  Joel David Hamkins Feb 19 '10 at 3:13
    
"This filter sub-base has size less than |A|" - why? –  porton Feb 23 '10 at 21:15
    
Can we add an additional equivalent statement to the formulation of the conjecture we have proved? (such as: the meet of T is in S for every non-empty subset T of S) –  porton Feb 23 '10 at 21:17
show 11 more comments

How is the following related to the question...

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.

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 & Steiner, Duke Math. J. 31 (1964) 287-289

share|improve this answer
    
No, your answer is on a different problem than I asked. –  porton Feb 18 '10 at 20:51
1  
@Porton: It's not that different. Your chain-closed subset S is a poset where each chain has a greatest lower bound. By the (dual of the ) above, every filter in S has a greatest lower bound in S. All you need to check is if this greatest lower bound is indeed the same as the one in A. You will figure that out pretty quickly by looking at the proof... –  François G. Dorais Feb 18 '10 at 21:20
add comment

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.

Gerhard "Ask Me About System Design" Paseman, 2010.02.18

share|improve this answer
    
I don't see your post in sci.math! Note also that I already have asked this in sci.math a few months ago. –  porton Feb 18 '10 at 20:44
    
A Google Groups search on "Paseman filter" brings it up quickly. The advice there was (essentially) to study the finite case. –  Gerhard Paseman Feb 18 '10 at 23:05
3  
The reason it is hard to find... The "From" line is not "Gerhard Paseman" but "Ask me about System Design". Dated December 30, 2009. –  Gerald Edgar Feb 19 '10 at 14:55
add comment

I wrote more detailed proof based on the proof by Joel David Hamkins in this online article.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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