MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $U$ is a complete lattice with least element 0.

Weak partitioning is a collection $S$ of nonempty subsets of $U$ such that $\forall x\in S: x\cap\bigcup(S\setminus\{x\})=0$.

Strong partitioning is a collection $S$ of nonempty subsets of $U$ such that $\forall A,B\in PS:(A\cap B=\emptyset \Rightarrow \bigcup A\cap\bigcup B=0)$.

Easy to show that every strong partitioning is weak partitioning.

Is weak and strong partitioning the same?

If not, under which additional conditions these are the same?

share|cite|improve this question
Is U a complete lattice or a complete lattice of sets? (In the former case, changing your cups and caps with vees and wedges where appropriate would make the question easier to parse.) The answer to your question hinges on the validity of some distributive laws, these do hold in lattices of sets but not necessarily in general lattices. – François G. Dorais Feb 18 '10 at 21:08
Why would anyone decide to give this question a bounty??? – Joseph Van Name Jun 27 '13 at 0:15
up vote 6 down vote accepted

If the lattice $U$ satisfies the meet distributive law $$x \wedge \bigvee_{i \in I} y_i = \bigvee_{i \in I} x \wedge y_i$$ where $(y_i)_{i \in I}$ is an arbitrary collection of elements of $U$, then "weak partitioning" implies "strong partitioning." More precisely, you only need the above to hold when the right hand side is $0$.

An example of a complete lattice where weak and strong partitioning are inequivalent is the lattice $U$ consisting of all closed subsets of $\{1,\frac12,\frac13,\ldots,0\}$ (as a subspace of $\mathbb{R}$) and the collection $S = \{\{\frac1n\}: n \geq 1\}$. The weak-partitioning property is easily verified since the points $\frac1n$ are isolated. The strong partitioning property fails for the two sets $A = \{\{\frac1{2n}\}: n \geq 1\}$ and $B = \{\{\frac1{2n+1}\} : n \geq 0\}$, for example, since $\bigvee A = \overline{\bigcup A}$ and $\bigvee B = \overline{\bigcup B}$ both contain the point $0$.

PS: In your formulation of weak and strong partitioning, I interpret $S$ as a collection of nonzero elements of $U$, since "nonempty subsets" doesn't make much sense in context.

share|cite|improve this answer
I probably should have mentioned that complete lattices which satisfy the meet distributive law mentioned above are called frames or complete Heyting algebras. – François G. Dorais Feb 18 '10 at 23:54
Sorry, I misunderstand something. First: all elements of $U$ except $S$ are subsets of $\mathbb{R}$ but $S$ is not a subset of $\mathbb{R}$. How this may be? Second: What are infimuma and suprema, are these infimuma and suprema on the induced order? Are infima and suprema opposite to these defined by the induced order? – porton Feb 19 '10 at 18:19
S is a subset of U. (Please see the PS and correct your question to reflect what you wanted to say.) Thes infs and sups of the second paragraph are computed in the complete lattice of closed subsets of the given subspace of R. – François G. Dorais Feb 19 '10 at 18:26
I again don't understand. Why we introduce $S$? Elements $\frac1n$ of $S$ are anyway closed subsets of $\{1,\frac12,\frac13,\ldots,0\}$ and so we have them in $U$. Why we need $S$? – porton Feb 19 '10 at 19:04
The set S is in your question. – François G. Dorais Feb 19 '10 at 19:23

I wrote more detailed proof based on the counterexample by François G. Dorais in this online article.

share|cite|improve this answer

Your Answer


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.