November 2, 2009 / porton

Exposition: Complementive filters are complete lattice

(In a past version of this article I erroneously concluded that our main conjecture follows from join-closedness of ${Z (D \mathcal{A})}$ .)

Let ${U}$ is a set. A filter ${\mathcal{F}}$ (on ${U}$ ) is 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 ${\emptyset \notin \mathcal{F}}$ . I will denote ${\mathfrak{f}}$ the lattice of all filters (on ${U}$ ) ordered by set inclusion.

Conjecture 1 Let ${\mathcal{A} \in \mathfrak{f}}$ is some (fixed) filter. Let ${D = \left\{ \mathcal{X} \in \mathfrak{f} \hspace{1em} | \hspace{1em} \mathcal{X} \supseteq \mathcal{A} \right\}}$ . (Obviously ${D}$ is a bounded lattice.) Then the set of complemented elements of the lattice ${D}$ (ordered by set inclusion) is a complete lattice.

This conjecture was first formulated in this blog post and suggested as a polymath project in this blog post.

1. Filter objects

(Borrowed from this blog post)

For greater clarity I will use {filter objects} instead of filters. Below I will describe the properties of filter objects without exact definition and the proofs. You can look here for the formalistic behind.

I will denote the set of all filters objects on ${U}$ as ${\mathfrak{F}}$ . Filter objects are bijectively related with filters by the bijection “ ${\mathrm{up}}$ ” from the set of filter objects to the set of filters. A filter object corresponding to principal filter generated by a set ${A}$ is equal to ${A}$ . (Thus the set of subsets of ${U}$ is a subset of ${\mathfrak{F}}$ .)

For formal definition of filter objects in the framework of ZF see here. Below we will not need the exact definition of filter objects, but only the facts that “ ${\mathrm{up}}$ ” is a bijection from filter objects to filters and that a filter object corresponding to principal filter generated by a set ${A}$ is equal to ${A}$ .

I will define the order on the set of filter objects by the formula ${\mathcal{A} \subseteq \mathcal{B} \Leftrightarrow \mathrm{up} \mathcal{A} \supseteq \mathrm{up} \mathcal{B}}$ for every filter objects ${\mathcal{A}}$ and ${\mathcal{B}}$ . This order well-agrees with the order of sets on ${U}$ .

${\mathfrak{F}}$ is a complete lattice. (See here for a proof.)

2. Second definition

Let ${\mathfrak{A}}$ is a bounded distributive lattice. Let ${a \in \mathfrak{A}}$ . I will denote ${D a = \left\{ x \in \mathfrak{A} \hspace{1em} | \hspace{1em} x \subseteq a \right\}}$ . Obviously ${D a}$ is a bounded lattice.

The center of a bounded distributive lattice ${\mathfrak{A}}$ is by definition the set ${Z (\mathfrak{A})}$ of all complemented elements of ${\mathfrak{A}}$ . It is a well known fact that the center is a boolean lattice.

I will call ${Z (D \mathcal{A})}$ the elements {complementive} to ${\mathcal{A}}$ .

Now our conjecture can be equivalently reformulated:

Conjecture 2 ${Z (D \mathcal{A})}$ is a complete lattice whenever ${\mathcal{A}}$ is an element of the lattice ${\mathfrak{F}}$ .

If the conjecture is true it may be generalized for the case of ${\mathfrak{F}}$ being the set of filter objects on some lattice instead of our less general case of filters on a set.

3. Special case of ${\mathcal{A}}$ being a set

I almost believe that our conjecture is true in general, because it is true in the special case when ${\mathcal{A}}$ is a set. Trueness of this special case of our conjecture trivially follows from the following theorem:

Theorem 3 ${Z (D A) = \mathscr{P} A}$ if ${A \in \mathscr{P} U}$ .

Proof: It follows from this theorem. $\Box$

4. Ways to attack our conjecture

4.1. Calculating meets and joins

To prove that a lattice is complete is enough to prove one of the following two statements: 1. it has all joins; or 2. it has all meets.

Directly calculating meets and joins for the lattice ${Z (D \mathcal{A})}$ seems a complicated problem.

It could be simplified if meets or joins on ${Z (D \mathcal{A})}$ coincide with meets or joins on ${\mathcal{\mathfrak{F}}}$ .

For meets it is not the case. (A counter-example is simple to find in the case ${\mathcal{A} = U}$ when ${U}$ is any infinite set.)

For joins it seems true that joins on ${Z (D \mathcal{A})}$ coincide with joins on ${\mathcal{\mathfrak{F}}}$ . However I failed to prove it.

Proposition 4 If our main conjecture is true, then the sublattice ${Z (D \mathcal{A})}$ of the lattice ${\mathfrak{F}}$ is join-closed.

Proof: Let ${S \in \mathscr{P} Z (D \mathcal{A})}$ . Let our main conjecture is true and thus ${\bigcup^{Z (D \mathcal{A})} S}$ exists. We need to prove that ${\bigcup^{Z (D \mathcal{A})} S = \bigcup^{\mathfrak{F}} S}$ . Because ${Z (D \mathcal{A})}$ is a sublattice of ${\mathfrak{F}}$ it’s enough to prove that for any ${\mathcal{F} \in D \mathcal{A}}$

$\displaystyle \forall K \in S : K \subseteq \mathcal{F} \Rightarrow \mathcal{F} \supseteq \bigcup {\nobreak}^{Z (D \mathcal{A})} S.$

Really: Let ${C \in \mathrm{up}^{D \mathcal{A}} \mathcal{F}}$ and ${\forall K \in S : K \subseteq \mathcal{F}}$ . Then ${C \supseteq \mathcal{F}}$ ; ${C \supseteq \bigcup {\nobreak}^{Z (D \mathcal{A})} S}$ ; ${C \in \mathrm{up}^{D \mathcal{A}} \bigcup {\nobreak}^{Z (D \mathcal{A})} S}$ . Thus ${\mathcal{F} \supseteq \bigcup {\nobreak}^{Z (D \mathcal{A})} S}$ . $\Box$

4.2. Intersection with a set

An other way to characterize elements of ${Z (D \mathcal{A})}$ is:

Theorem 5 ${\mathcal{X} \in Z (D \mathcal{A}) \Leftrightarrow \exists X \in \mathscr{P} U : \mathcal{X} = X \cap^{\mathfrak{F}} \mathcal{A}}$ for every ${\mathcal{X} \in \mathfrak{F}}$ .

Proof:

Reverse implication Let ${\mathcal{X} = X \cap^{\mathfrak{F}} \mathcal{A}}$ . Let also ${\mathcal{Y} = (U \setminus X) \cap^{\mathfrak{F}} \mathcal{A}}$ . Then ${\mathcal{X} \cap^{\mathfrak{F}} \mathcal{Y} = \emptyset}$ and ${\mathcal{X} \cup^{\mathfrak{F}} \mathcal{Y} = (X \cup (U \setminus X)) \cap^{\mathfrak{F}} \mathcal{A} = U \cap^{\mathfrak{F}} \mathcal{A} = \mathcal{A}}$ . So ${\mathcal{X} \in Z (D \mathcal{A})}$ .

Direct implication Let ${\mathcal{X} \in Z (D \mathcal{A})}$ . Then exists ${\mathcal{Y} \in Z (D \mathcal{A})}$ such that ${\mathcal{X} \cap^{\mathfrak{F}} \mathcal{Y} = \emptyset}$ and ${\mathcal{X} \cup^{\mathfrak{F}} \mathcal{Y} = \mathcal{A}}$ . Then exists ${X \in \mathscr{P} U}$ such that ${X \in \mathrm{up} \mathcal{X}}$ and ${X \cap^{\mathfrak{F}} \mathcal{Y} = \emptyset}$ . Obviously ${( \mathcal{X} \cup^{\mathfrak{F}} \mathcal{Y}) \cap^{\mathfrak{F}} X = X \cap^{\mathfrak{F}} \mathcal{A}}$ ; ${\mathcal{X} \cup^{\mathfrak{F}} (X \cap^{\mathfrak{F}} \mathcal{Y}) = X \cap^{\mathfrak{F}} \mathcal{A}}$ ; ${\mathcal{X} = X \cap^{\mathfrak{F}} \mathcal{A}}$ . $\Box$

We may attempt to attack our conjecture by proving that meets or joins of filter objects of the form ${K \cap^{\mathfrak{F}} \mathcal{A}}$ are also of the form ${K \cap^{\mathfrak{F}} \mathcal{A}}$ .

Let ${S \in \mathscr{P} Z (D \mathcal{A})}$ . Then ${S = \left\{ X \cap^{\mathfrak{F}} \mathcal{A} \hspace{1em} | \hspace{1em} X \in T \right\}}$ where ${T \in \mathscr{P} \mathscr{P} U}$ .

How to calculate ${\bigcup^{Z (D \mathcal{A})} \left\{ X \cap^{\mathfrak{F}} \mathcal{A} \hspace{1em} | \hspace{1em} X \in T \right\}}$ and ${\bigcap^{Z (D \mathcal{A})} \left\{ X \cap^{\mathfrak{F}} \mathcal{A} \hspace{1em} | \hspace{1em} X \in T \right\}}$ ?

I conjecture:

${\bigcup^{Z (D \mathcal{A})} \left\{ X \cap^{\mathfrak{F}} \mathcal{A} \hspace{1em} | \hspace{1em} X \in T \right\} = \mathcal{A} \cap^{\mathfrak{F}} \bigcup T}$ and ${\bigcap^{Z (D \mathcal{A})} \left\{ X \cap^{\mathfrak{F}} \mathcal{A} \hspace{1em} | \hspace{1em} X \in T \right\} = \mathcal{A} \cap^{\mathfrak{F}} \bigcap T}$ .

It probably may be helpful if we would calculate ${\bigcup^{\mathfrak{F}} S}$ or ${\bigcap^{\mathfrak{F}} S}$ . (However it simple to show that in general ${\bigcap^{\mathfrak{F}} S \neq \bigcap^{Z (D \mathcal{A})} S}$ .)

${\bigcup^{\mathfrak{F}} S = \bigcup^{\mathfrak{F}} \left\{ X \cap^{\mathfrak{F}} \mathcal{A} \hspace{1em} | \hspace{1em} X \in T \right\}}$ . Sadly there are no distributive law we could apply here.

${\bigcap^{\mathfrak{F}} S = \bigcap^{\mathfrak{F}} \left\{ X \cap^{\mathfrak{F}} \mathcal{A} \hspace{1em} | \hspace{1em} X \in T \right\} = \mathcal{A} \cap^{\mathfrak{F}} \bigcap^{\mathfrak{F}} T}$ . Sadly ${\bigcap^{\mathfrak{F}} T}$ is not necessarily a set.

5. Consequences of our conjecture

5.1. Closedness of joins on ${Z (D \mathcal{A})}$

Above it was proved that closedness of joins of ${Z (D \mathcal{A})}$ follows from our main conjecture.

5.2. Coinciding pseudodifference and second pseudodifference

It seems that using our conjecture we can prove that quasidifference and second quasidifference coincide for the lattice of filter objects.

See this and this wiki pages for details about the current state of the problem about coinciding quasidifference and second quasidifference.

About these ads

← Filter objects

Open problem: Pseudodifference of filters →

One Comment

Trackbacks

“Filters on Posets and Generalizations” updated « Victor Porton's Math Blog

Exposition: Complementive filters are complete lattice

One Comment

Trackbacks

Leave a Reply Cancel reply

Follow Blog via Email

Recent Posts

Search

Categories

Archives

Follow “Victor Porton's Math Blog”

Exposition: Complementive filters are complete lattice

Share this:

One Comment

Trackbacks

Leave a Reply Cancel reply

Follow Blog via Email

Recent Posts

Search

Categories

Archives

Follow “Victor Porton's Math Blog”