Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

If it helps anything, please assume that everything below is finite.

Let $\mathcal A$ be a family of subsets of a set $X$. I want to consider the following independence condition (C) on $\mathcal A$.

(C). The function $\bigcup: 2^\mathcal A\to2^X$ is an injection.

In other words, (C) says that each subfamily of $\mathcal A$ has a different union.

Every pairwise disjoint family $\mathcal A$ satisfies this condition. If I put together pairwise disjoint pieces, I can recognize them in the union.

But there are other examples. For $|\mathcal A|=1,$ (C) simply says that $\mathcal A\neq \{\varnothing\}$ because

  • if $\mathcal A=\{\varnothing\},$ then $\varnothing,\{\varnothing\}\subseteq\mathcal A,$ and $\bigcup\varnothing=\bigcup\{\varnothing\}=\varnothing,$ but $\varnothing\neq\{\varnothing\},$ so $\bigcup$ is not injective;
  • if $\mathcal A = \{Y\},$ $Y\neq\varnothing,$ then the only subfamilies of $\mathcal A$ are $\varnothing$ and $\{Y\}$, and they have different unions.

For $|\mathcal A|=2$, $\mathcal A=\{Y,Z\},$ (C) says that $Y\setminus Z\neq\varnothing\neq Z\setminus Y.$ (In other words, neither of the sets is a subset of the other.) Indeed,

  • if $Y\setminus Z=\varnothing,$ then $\bigcup\{Y,Z\}=\bigcup\{Z\}$ (and the same for $Z\setminus Y=\varnothing$);
  • otherwise, the unions of $\varnothing,\{Y\},\{Z\},\{Y,Z\}$ are all different.

For $|\mathcal A|=3,$ I already don't see a simple condition equivalent to (C). Is there one in the general case? (C) is of course a simple condition in terms of formulation, but it is quite a complex one in terms of the "little conditions" it comprises. I'm not certain that a condition I'm asking for exists, but perhaps it does, and someone here can help me see it?

share|cite|improve this question
"Every pairwise disjoint family $\mathcal A$ satisfies this condition" - No, we must not have $\emptyset$ itself in the family. – Hagen von Eitzen May 21 '13 at 15:59
up vote 2 down vote accepted

The condition that $$\tag1 A\not\subseteq\bigcup(\mathcal A\setminus\{A\})\qquad\text{for all }A\in \mathcal A$$ is necessary to distinguish $\mathcal A$ from $\mathcal A\setminus\{A\}$ and sufficient as it implies that $A\in \mathcal B\subseteq \mathcal A$ iff $A\subseteq \bigcup\mathcal B$.

For each $A\in \mathcal A$, $(1)$ allows us to select an element $a(A)\in A\setminus \bigcup(\mathcal A\setminus\{A\})$ that works as a "sensor" for $A$. That is, we can restrict everything from $X$ to $\{a(A)\mid A\in\mathcal A\}$ and by that end up in the simple case of disjoint singleton sets. In other words, an equivalent condition is:

There exists a subset $X'\subseteq X$ such that $A\cap X'$ is a singleton for every $A\in\mathcal A$ and $A_1\ne A_2$ implies $A_1\cap X'\ne A_2\cap X'$.

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.