This assertion is so basic that I’d expect it to have been put forward with someone’s name attached 100 years ago. But, I can’t find any reference to it searching the web. Of course, the other possibility is that my analysis is not correct.
Can anyone advise ?
Theorem. For a non-empty family of non-empty sets $S = \{S_i\}$ with union $S_0 = \large\cup_{s \in S} s$
- There is a partition of $S_0$ formed by defining $s_1$ and $s_2$ in $S_0$ to be “neighbours” if they are elements of exactly the same sets in $S$.
- The sets in $S$ can each be reformed by union of some or all of the sets in this partition.
Illustration.
Its trivial to prove for two sets $A$ and $B$ that $\{ \{A ∩ B\}, A\setminus\{A ∩ B\}, B\setminus\{A ∩ B\}\}$ is a partition of $A \cup B$. One notes that $\{A ∩ B\}$ might be empty, and it depends which definition of partition you prefer whether this is allowable or whether the empty set must be removed in such a case (Bourbaki allows it).
In a Venn diagram we believe that the whole can be formed from the “smallest bits” and that each set which is represented can be formed from some of these “bits”
Formalisation and Proof.
The sets may be infinite. The use of subscripts does not imply countability, just identifies different members of a set.
Define $s_i$ and $s_j$ in $S_0$ to be neighbours if $\forall S_k \in S$ either $s_i$ and $s_j \in S_k$ or $s_i$ and $s_j \not\in S_k$.
Then being neighbours is an equivalence relation (easily seen to be symmetric, reflexive and transitive). Consequently, this defines a partition of $S_0$ and we’ll call the equivalence classes neighbourhoods: for brevity, $N = \{N_i\}$
To show that the sets in $S$ can be formed from a selection of the neighbourhoods, consider $s_i \in S_j$. Since $N$ is a partition then $s_i \in N_k$ for some $N_k \in N$ and since it’s a neighbourhood all other elements of $N_k$ are also elements of $S_j$. Therefore $N_k \subset S_j$. Therefore we can find elements of $N$ which will include each element of $S_j$ and their union will be $S_j$.