Exposition: Complementive filters are complete lattice

November 2, 2009 by porton

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. In fact this is equivalent to our conjecture:

Proposition 4 Our main conjecture is equivalent to join-closedness of the sublattice {Z (D \mathcal{A})} of the lattice {\mathfrak{F}}.

Proof: The reverse implication is trivial. Let’s prove the direct implication: 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 X} 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 X}.

    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})} is equivalent to 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.

    • Tags:
    Posted in Filters, Open problems | Leave a Comment »

    Filter objects

    October 31, 2009 by porton

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

    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 a set 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}.)

    Formal definition of filter objects in the framework of ZF is given here. 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} with the above defined order is a complete lattice. (See this draft article for a proof.)

    Posted in Filters | 1 Comment »

    Principal filters are center – solved

    October 31, 2009 by porton

    I have proved this conjecture:

    Theorem 1 If {\mathfrak{F}} is the set of filter objects on a set {U} then {U} is the center of the lattice {\mathfrak{F}}. (Or equivalently: The set of principal filters on a set {U} is the center of the lattice of all filters on {U}.)

    Proof: I will denote {Z (\mathfrak{F})} the center of the lattice {\mathfrak{F}}. I will denote {\mathrm{atoms}^{\mathfrak{A}} a} the set of atoms of a lattice {\mathfrak{A}} under its element {a}.

    Let {\mathcal{X} \in Z (\mathfrak{F})}. Then exists {\mathcal{Y} \in Z (\mathfrak{F})} such that {\mathcal{X} \cap^{\mathfrak{F}} \mathcal{Y} = \emptyset} and {\mathcal{X} \cup^{\mathfrak{F}} \mathcal{Y} = U}. Consequently, there are {X \in \mathrm{up} \mathcal{X}} such that {X \cap^{\mathfrak{F}} \mathcal{Y} = \emptyset}; we have also {X \cup^{\mathfrak{F}} \mathcal{Y} = U}. Suppose {X \supset \mathcal{X}}. Then (because for {\mathfrak{F}} is true the disjunct propery of Wallman, see [1]) exists {a \in \mathrm{atoms}^{\mathfrak{F}} X} such that {a \notin \mathrm{atoms}^{\mathfrak{F}} \mathcal{X}}. We can conclude also {a \notin \mathrm{atoms}^{\mathfrak{F}} \mathcal{Y}}. Thus {a \notin \mathrm{atoms}^{\mathfrak{F}} ( \mathcal{X} \cup^{\mathfrak{F}} \mathcal{Y})} and consequently {\mathcal{X} \cup^{\mathfrak{F}} \mathcal{Y} \neq U} what is a contradiction. We have {\mathcal{X} = X \in \mathscr{P} U}.

    Let now {X \in \mathscr{P} U}. Then {X \cap (U \setminus X) = 0} and {X \cup (U \setminus X) = U}. Thus {X \cap^{\mathfrak{F}} (U \setminus X) = \bigcap^{\mathfrak{F}} \left\{ X \cap (U \setminus X) \right\} = \emptyset}; {X \cup^{\mathfrak{F}} (U \setminus X) = \bigcap^{\mathfrak{F}} (\mathrm{up} X \cap \mathrm{up} (U \setminus X)) = \bigcap^{\mathfrak{F}} \left\{ U \right\} = U} (used formulas from [1]). We have shown that {X \in Z (\mathfrak{F})}. \Box

    This theorem may be generalized for a wider class of filters on lattices than only filters on lattices of a subsets of some set.

    [1] Victor Porton. Funcoids and Reloids. http://www.mathematics21.org/binaries/set-filters.pdf

    Posted in Uncategorized | 1 Comment »

    Are principal filters the center of the lattice of filters?

    October 31, 2009 by porton

    This conjecture has a seemingly trivial case when \mathcal{A} is a principal filter. When I attempted to prove this seemingly trivial case I stumbled over a looking simple but yet unsolved problem:

    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. (I skip the proof that \mathscr{F} is a lattice).

    Conjecture The set of principal filters on a set U is the center of the lattice of all filters on U.

    Note that by center of a (distributive) lattice I mean the set of all its complemented elements.

    I did a little unsuccessful attempt to solve this problem before I’ve put it into this blog. I will think about this more. You may also attempt to solve this open problem for me.

    Posted in Filters, Open problems | 2 Comments »

    Collaborative math research – a real example

    October 25, 2009 by porton

    There were much talking about writing math research articles collaboratively but no real action. I present probably the first real example of a research manuscript ready to be written collaboratively.

    I wrote the draft Filters on Posets and Generalizations which I present to the online mathematical society to finish writing it as a collaborative project.

    Read the rest of this entry »

    Tags: , , , , , , , ,
    Posted in Filters | Leave a Comment »

    Complete lattice generated by a partitioning – finite meets

    October 20, 2009 by porton

    I conjectured certain formula for the complete lattice generated by a strong partitioning of an element of complete lattice. Now I have found a beautiful proof of a weaker statement than this conjecture. (Well, my proof works only in the case of distributive lattices, but the case of non-distributive lattices is outside of my research area.)

    Let’s denote R = \left\{ \bigcup{}^{\mathfrak{A}}X | X\in\mathscr{P}S \right\} where S is a strong partitioning an element of the complete lattice \mathfrak{A}. Our conjecture is trivially equivalent to the statement that R is closed under arbitrary meets and joins.

    That R is closed regarding any joins is obvious. To finish proving the conjecture we need to show that R is closed under arbitrary meets. In this post I prove weaker result that R is closed under finite meets.

    I hope this finite case may serve as a model for the general infinite case. However it seems that generalizing it to infinite case is non-trivial.

    Read the rest of this entry »

    Tags: ,
    Posted in Filters, Open problems | Leave a Comment »

    Complete lattice generated by a partitioning of a lattice element

    October 20, 2009 by porton

    In this post I defined strong partitioning of an element of a complete lattice. For me it was seeming obvious that the complete lattice generated by the set S where S is a strong partitioning is equal to \left\{ \bigcup{}^{\mathfrak{A}}X | X\in\mathscr{P}S \right\}. But when I actually tried to write down the proof of this statement I found that it is not obvious to prove. So I present this to you as a conjecture:

    Conjecture The complete lattice generated by a strong partitioning S of an element of a complete lattice \mathfrak{A} is equal to \left\{ \bigcup{}^{\mathfrak{A}}X | X\in\mathscr{P}S \right\}.
    Read the rest of this entry »

    Tags: , ,
    Posted in Filters, Open problems | 1 Comment »

    Partitioning elements of distributive and finite lattices

    October 18, 2009 by porton

    I proposed this open problem for the next polymath project. Now I will consider some its special simple cases. Read the rest of this entry »

    Posted in Filters, Open problems | Leave a Comment »

    Proposal: Partitioning a lattice element

    October 17, 2009 by porton

    I’ve given two different definitions for partitioning an element of a complete lattice (generalizing partitioning of a set). I called them weak partitioning and strong partitioning.

    The problem is whether these two definitions are equivalent for all complete lattices, or if are not then under which additional conditions these are equivalent. (I suspect these may be equivalent under the additional condition that our lattice is distributive.)

    I may seem greedy producing now already second or third (dependently on how to count) polymath proposal about my problems, but I just want to present all of my proposal for (hopefully) fair judges Terence Tao and Tim Gowers. The more the better.

    Tags:
    Posted in Open problems | 2 Comments »

    Partitioning of a lattice element: a conjecture

    October 17, 2009 by porton

    Let \mathfrak{A} is a complete lattice. Let a\in\mathfrak{A}.

    I will call weak partitioning of a a set S\in\mathscr{P}\mathfrak{A}\setminus\{0\} such that

    \bigcup{}^{\mathfrak{A}}S = a \text{ and } \forall x\in S: x\cap^{\mathfrak{A}}\bigcup{}^{\mathfrak{A}}(S\setminus\{x\}) = 0.

    I will call strong partitioning of a a set S\in\mathscr{P}\mathfrak{A}\setminus\{0\} such that

    \bigcup{}^{\mathfrak{A}}S = a \text{ and } \forall A,B\in\mathscr{P}S: (A\cap B=0\Rightarrow \bigcup{}^{\mathfrak{A}}A\cap{}^{\mathfrak{A}}\bigcup{}^{\mathfrak{A}}B = 0).

    Question: Do exist complete lattices for which weak partitioning and strong partitioning are not the same?

    If this conjecture (that it is the same for arbitrary complete lattices) is indeed false for arbitrary complete lattices, we must find the cases when it is true. (I strongly suspect that it is true for distributive complete lattices.)

    Tags:
    Posted in Open problems | 3 Comments »

    « Older Entries