11
$\begingroup$

I derived this definition by searching for a representation of a family of sets. I am quite sure that someone should have thought to this before, because it seems to be quite straightforward given a family of sets. However, I did not find anything suitable on google or on wikipedia.

Let a family of sets, say $A_1, \ldots, A_n$, be given. To avoid misunderstanding I will call them modules. This family induces a unique partition on the union set $A = \bigcup_{i=1}^{n} A_i$ in the following way: I call building block a maximal subset $B$ of $A$ such that do not exist 2 different modules $A_i$ and $A_j$ with:

$B \cap A_i \not= \emptyset$,

$B \cap A_j \not= \emptyset$ and

$B\not\subseteq A_i \cap A_j$.

For example, if my family consists of 2 different overlapping modules $A_1$ and $A_2$, I can partition the set $A = A_1 \cup A_2$ as:

(elements in $A_1 \cap A_2$);

(elements in $A_1$ but not in $A_2$);

(elements in $A_2$ but not in $A_1$).

I know that in logic there is something similar, but I am searching for something in set theory. Moreover, I want to underline the dependency of this uniquely derived partition from the family of sets I am given.

See also http://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Mathematics#Given_a_family_of_sets.2C_I_can_generate_a_partition_of_their_union_set.2C_by_looking_at_their_overlapping...

Thanks to all!

A newcomer

$\endgroup$

1 Answer 1

19
$\begingroup$

Your building blocks are known as the atoms in the Boolean algebra or field of sets generated by the $A_i$. Each building block will consist of points that have the same pattern of answers for membership in the various $A_i$. To see this, observe first that by maximality any building block will respect this equivalence and therefore be a union of such atoms. Conversely, if a set has points with two different patterns of answers, then it will contain points from two $A_i$ without being contained in their intersection. (Specifically, if $x,y\in B$ and $x\in A_i$ but $y\notin A_i$, then pick $j$ such that $y\in A_j$, and observe that $B$ meets both $A_i$ and $A_j$, buit is not contained in $A_i\cap A_j$.) So the building blocks are the atoms.

If your family is finite as you indicated, then the Boolean algebra generated by the $A_i$ consists precisely of the unions of blocks. This is the representation theorem showing that every finite Boolean algebra is isomorphic to a finite power set---the power set of the atoms.

In the infinite case, however, the Boolean algebra generated by the $A_i$ may be atomless---it may have no atoms at all, and this is a fascinating case. Nevertheless, your blocks still form a partition, and are precisely the atoms in the infinitary-generated field of sets, still determined by my argument above by the patttern-of-answers to membership in the $A_i$.

$\endgroup$
6
  • $\begingroup$ Thank you! I have to look closer at it, but it seems to be potentially inspiring! Anyway, I do not have a Boolean algebra, because the family is not closed under union and intersection - for example, with my notation, the union of a module is not in general a module, but possibly I have to add some other building blocks. Does something like this already exists? I would be really interested in properties that such a "structure" have! (Otherwise I have to figure out by myself if there are any...) $\endgroup$
    – klaraspina
    Jun 18, 2010 at 10:06
  • $\begingroup$ My proposal was that you should close your modules under intersection, union and complement---this would be the generated Boolean algebra---but that after doing so, you will have the same building blocks, and these are the atoms of that Boolean algebra. $\endgroup$ Jun 18, 2010 at 11:03
  • 1
    $\begingroup$ You could also think in terms of the Venn diagram (en.wikipedia.org/wiki/Venn_diagram). Your buiilding blocks are the smallest spaces appearing in the appropriate Venn diagram of your modules. $\endgroup$ Jun 18, 2010 at 11:06
  • $\begingroup$ Closing the algebra is not a good thing for me. First of all because I want to keep in memory which are the given modules. Second, because if I close I have an exponential blowup of sets, and since I want to apply this representation in computer science, it would not be a good thing to do... $\endgroup$
    – klaraspina
    Jun 18, 2010 at 11:07
  • 1
    $\begingroup$ It isn't necessary to actually calculate and represent the whole Boolean algebra. You can describe and index each building block by the in-out membership pattern of points in the modules. $\endgroup$ Jun 18, 2010 at 11:16

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.