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

Really I should first ask this question here on MathOverflow and only then post it as an open problem in Open Problem Garden and propose it as a polymath problem. Indeed I did the reverse and now hope that for somebody my "open problem" may be simple.

Let $U$ is a set. A filter (on $U$) $\mathcal{F}$ is by definition a non-empty set of subsets of $U$ such that $A,B\in\mathcal{F} \Leftrightarrow A\cap B\in\mathcal{F}$. Note that unlike some other authors I do not require $\varnothing\notin\mathcal{F}$. I will denote $\mathscr{F}$ the lattice of all filters (on $U$) ordered by set inclusion.

Let $\mathcal{A}\in\mathscr{F}$ is some (fixed) filter. Let $D= \{ \mathcal{X}\in\mathscr{F} | \mathcal{X}\supseteq \mathcal{A} \}$. Obviously $D$ is a bounded lattice.

I will call complementive such filters $\mathcal{C}$ that:

  1. $\mathcal{C}\in D$;
  2. $\mathcal{C}$ is a complemented element of the lattice $D$.

Conjecture The set of complementive filters ordered by inclusion is a complete lattice.

Read also my current progress on this problem.

share|improve this question
1  
You haven't included the requirement that filters are closed upwards under superset. –  Joel David Hamkins Nov 11 '10 at 0:22
    
Perhaps add the lattice tag? –  Joel David Hamkins Nov 11 '10 at 0:39
    
Does "complementive" or "complemented" here mean closed under taking complements as subsets of $U$? If so, then these "complementive filters" as you are calling them sound like the same things as Boolean subalgebras of the power set of $U$ (although I wouldn't call them filters unless you mean to include upward closure, which it sounds like you don't want to do). –  Todd Trimble Nov 11 '10 at 1:42
2  
@Joel and Todd: Upward closure follows from Porton's assumption about intersections, because he has a biconditional there, not just the left-to-right implication. –  Andreas Blass Nov 11 '10 at 2:07
    
Yes, Andreas. Also, I disagree with the votes to close---this is an interesting question. –  Joel David Hamkins Nov 11 '10 at 2:16
show 1 more comment

1 Answer

up vote 8 down vote accepted

The complementive filters ordered by inclusion form a lattice isomorphic to the quotient of the power set of $U$ modulo the filter $\mathcal A$. So, for example, if $U=\omega$ and if $\mathcal A$ is the filter of cofinite sets, then the lattice of complementive filters would not be complete.

To establish the isomorphism, consider a complementive filter $\mathcal C$ and its complement $\mathcal C'$ in $D$. The filter generated by $\mathcal C\cup\mathcal C'$ is the join in $D$, so it must be the top element, the improper filter of all subsets of $U$. So there must be a set $Q\in\mathcal C$ whose complement $U-Q$ is in $\mathcal C'$.

I claim that $\mathcal A\cup\{Q\}$ generates $\mathcal C$. To see this, suppose not, and consider some $Z\in\mathcal C$ that is not in the filter generated by $\mathcal A\cup\{Q\}$. Then $Z\cup(U-Q)$ cannot be in $\mathcal A$ (because, if it were, then its intersection with $Q$ would be in the filter generated by $\mathcal A\cup\{Q\}$, but this intersection is included in $Z$, which is not in that filter). But, since $Z\in\mathcal C$ and $U-Q\in\mathcal C'$, the union $Z\cup(U-Q)$ is in the intersection of these two filters, which is $\mathcal A$ (because they're complements in $D$). This contradiction establishes the claim.

Thus, each complementive $\mathcal C$ in $D$ is generated by the fixed $\mathcal A$ plus one more set $Q$. It is easy to check that the filter generated by $\mathcal A\cup\{Q\}$ and the filter generated by $\mathcal A\cup\{R\}$ are equal if and only if $Q$ and $R$ represent the same element in the quotient Boolean algebra $\mathcal P(U)/\mathcal A$. Better, the filter generated by $\mathcal A\cup\{Q\}$ is included in the one generated by $\mathcal A\cup\{R\}$ if and only if the element of $\mathcal P(U)/\mathcal A$ represented by $R$ is below (in the Boolean algebra) the one represented by $Q$. Thus, the correspondence between $\mathcal C$ and ($Q$ modulo $\mathcal A$) is an order-reversing bijection between the lattice of complementive filters and the Boolean algebra $\mathcal P(U)/\mathcal A$.

Since a Boolean algebra and its dual order are isomorphic, this proves my description of the structure of the lattice of complementive filters.

share|improve this answer
    
What you mean by "modulo filter"? I don't know such a term. –  porton Nov 11 '10 at 13:32
1  
The quotient of a Boolean algebra $B$ modulo a filter $F$ is obtained from $B$ by identifying two elements $x$ and $y$ iff there is $a\in F$ such that $x\wedge a=y\wedge a$. This relation between $x$ and $y$ is a congruence relation (in the sense of universal algebra), so the quotient inherits from $B$ a Boolean algebra structure. –  Andreas Blass Nov 11 '10 at 13:45
    
Why $\omega$ modulo filter of co-finite sets is not complete? –  porton Nov 11 '10 at 14:13
1  
Partition $\omega$ into infinitely many infinite sets $A_n$; their images $[A_n]$ in the quotient have no supremum, for the following reason. Given any upper bound $[X]$ (so, for each $n$, $X$ contains all but finitely many elements of $A_n$), choose, for each $n$, one element $z_n$ in $X\cap A_n$, and let $Y=X-\{z_n:n\in\omega\}$. Then $[Y]$ is also an upper bound for the $[A_n]$'s and it is strictly below $[X]$ because $X-Y$ is infinite. –  Andreas Blass Nov 11 '10 at 14:31
    
@Andreas: It is expected that I will greatly simplify your proof using terminology which I define in mathematics21.org/binaries/filters.pdf Indeed do you want me to acknowledge you in my publication? –  porton Nov 11 '10 at 22:50
show 4 more comments

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.