1
$\begingroup$

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}$ be 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.

$\endgroup$
6
  • 1
    $\begingroup$ You haven't included the requirement that filters are closed upwards under superset. $\endgroup$ Nov 11, 2010 at 0:22
  • $\begingroup$ Perhaps add the lattice tag? $\endgroup$ Nov 11, 2010 at 0:39
  • $\begingroup$ 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). $\endgroup$
    – Todd Trimble
    Nov 11, 2010 at 1:42
  • 2
    $\begingroup$ @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. $\endgroup$ Nov 11, 2010 at 2:07
  • $\begingroup$ Yes, Andreas. Also, I disagree with the votes to close---this is an interesting question. $\endgroup$ Nov 11, 2010 at 2:16

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ What you mean by "modulo filter"? I don't know such a term. $\endgroup$
    – porton
    Nov 11, 2010 at 13:32
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 11, 2010 at 13:45
  • $\begingroup$ Why $\omega$ modulo filter of co-finite sets is not complete? $\endgroup$
    – porton
    Nov 11, 2010 at 14:13
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 11, 2010 at 14:31
  • $\begingroup$ @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? $\endgroup$
    – porton
    Nov 11, 2010 at 22:50

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.