Inclusion-exclusion-like fractional sum is positive?

Question

Let $A_1,A_2,\ldots,A_n$ be finite nonempty sets. Is it true that $$\sum_{i=1}^n\frac{1}{|A_i|}-\sum_{1\leq i<j\leq n}\frac{1}{|A_i\cup A_j|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|A_i\cup A_j\cup A_k|}-\cdots+\frac{(-1)^{n-1}}{|A_1\cup\cdots\cup A_n|}$$ is always positive?

For $n=1$ this is obvious. For $n=2$ it is true because $\frac{1}{|A_1|}\geq\frac{1}{|A_1\cup A_2|}$ and $\frac{1}{|A_2|}>0.$

For $n=3$ it is true because $\frac{1}{|A_1|}\geq\frac{1}{|A_1\cup A_2|}$, $\frac{1}{|A_2|}\geq\frac{1}{|A_2\cup A_3|}$, $\frac{1}{|A_3|}\geq\frac{1}{|A_3\cup A_1|}$, and $\frac{1}{|A_1\cup A_2\cup A_3|}>0$.

But for $n=4$ this reasoning ceases to hold.

Answer 1

Here is an analytic proof inspired by the one in the answer to question #1343375 (thanks to kubek789 for the link!).

We fix a positive integer $n$. We let $\left[ n\right] $ denote the set $\left\{ 1,2,\ldots,n\right\} $.

We first show an auxiliary result:

Theorem 1. Let $A_{1},A_{2},\ldots,A_{n}$ be $n$ finite nonempty sets. Let $x\in\left( 0,1\right) $. Then, \begin{equation} 0<\sum\limits_{I\subseteq\left[ n\right] }\left( -1\right) ^{\left\vert I\right\vert }x^{\left\vert \bigcup_{i\in I}A_{i}\right\vert }<1 . \end{equation}

Proof of Theorem 1. Let $A$ be the set $A_{1}\cup A_{2}\cup\cdots\cup A_{n} $. Let $X$ be the set of all maps $A\rightarrow\left\{ 0,1\right\} $. We make $X$ into a probability space by assigning to a map $f:A\rightarrow \left\{ 0,1\right\} $ the probability $x^{\left\vert f^{-1}\left( 1\right) \right\vert }\left( 1-x\right) ^{\left\vert f^{-1}\left( 0\right) \right\vert }$. This probability space $X$ is precisely the $\left\vert A\right\vert $-th Cartesian power of the probability space $\left\{ 0,1\right\} $ where $1$ has probability $x$ and $0$ has probability $1-x$. In simpler terms, randomly sampling a point in $X$ is tantamount to constructing a map $A\rightarrow\left\{ 0,1\right\} $ by flipping an $x$-coin for every $a\in A$ (independently), and letting the map $A\rightarrow\left\{ 0,1\right\} $ send $a$ to $1$ if the $x$-coin has brought up heads and to $0$ if it has brought up tails. Here, an "$x$-coin" means a biased coin which brings up heads with probability $x$.

Now, let $Y\subseteq X$ be the set of all maps $f:A\rightarrow\left\{ 0,1\right\} $ such that every $i\in\left\{ 1,2,\ldots,n\right\} $ satisfies $0\in f\left( A_{i}\right) $. Then, $Y$ is the set of all maps $f:A\rightarrow\left\{ 0,1\right\} $ such that no $i\in\left\{ 1,2,\ldots,n\right\} $ satisfies $A_{i}\subseteq f^{-1}\left( 1\right) $. Thus, the probability of $Y$ (as an event in the probability space $X$) can be computed by the principle of inclusion and exclusion to be $\sum\limits _{I\subseteq\left[ n\right] }\left( -1\right) ^{\left\vert I\right\vert }x^{\left\vert \bigcup_{i\in I}A_{i}\right\vert }$. But this probability is $>0$ (since the "constant-$0$" map belongs to $Y$ and has nonzero probability) and $<1$ (since the "constant-$1$" map does not belong to $Y$, and still has nonzero probability). Thus, Theorem 1 follows.

(Please correct all stochastics terminology that I have butchered. I have not used probability spaces since I passed probability 101 some 9 years ago.)

Theorem 2. Let $A_{1},A_{2},\ldots,A_{n}$ be $n$ finite nonempty sets. Then, \begin{equation} \sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert }>0 . \end{equation}

Proof of Theorem 2. Theorem 1 shows that every $x\in\left( 0,1\right) $ satisfies

$1>\sum\limits_{I\subseteq\left[ n\right] }\left( -1\right) ^{\left\vert I\right\vert }x^{\left\vert \bigcup_{i\in I}A_{i}\right\vert }$

$=1+\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert }x^{\left\vert \bigcup_{i\in I} A_{i}\right\vert }$ (here, we have split the $I=\varnothing$ term out of the sum)

$=1-\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}x^{\left\vert \bigcup_{i\in I} A_{i}\right\vert }$.

In other words, every $x\in\left( 0,1\right) $ satisfies

$\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}x^{\left\vert \bigcup_{i\in I} A_{i}\right\vert }>0$.

We denote the left hand side of this inequality by $f\left( x\right) $. Then, we thus have shown that every $x\in\left( 0,1\right) $ satisfies $f\left( x\right) >0$. Hence, $\int_{0}^{1}\dfrac{f\left( x\right) } {x}dx>0$. But the definition of $f$ (and the rule that $\int_{0}^{1} \dfrac{x^{m}}{x}dx=\dfrac{1}{m}$ for every $m\geq1$) yields $\int_{0} ^{1}\dfrac{f\left( x\right) }{x}dx=\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert }$. Hence, $\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert }>0$, and Theorem 2 is proven.

Answer 2

In my previous response to this topic, I've given a proof of the positivity using probabilities and integrals. Let me give a different proof now, which still uses a bit of analysis (limits), but otherwise is completely combinatorial; its main ingredients are the principle of inclusion and exclusion and the "tensor power trick" (in a really simple incarnation).

Strengthening the inequality I

We fix a positive integer $n$. We let $\left[ n\right] $ denote the set $\left\{ 1,2,\ldots,n\right\} $.

We must prove the following fact (I'm copying the numbering from my previous response):

Theorem 2. Let $A_{1},A_{2},\ldots,A_{n}$ be $n$ finite nonempty sets. Then, \begin{equation} \sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing }}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert }>0. \end{equation}

I shall prove the following stronger inequality:

Theorem 3. Let $A_{1},A_{2},\ldots,A_{n}$ be $n$ finite nonempty sets. Then, \begin{equation} \sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing }}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert }\geq\dfrac{1}{\left|A_1\right|}. \end{equation}

Clearly, Theorem 3 implies Theorem 2 (because $\dfrac{1}{\left|A_1\right|}>0$).

Two combinatorial lemmas

We will use the Principle of Inclusion and Exclusion in the following form (Theorem 3.42 in Darij Grinberg, Notes on the combinatorial fundamentals of algebra, version of 10 January 2019):

Theorem 4 (Principle of Inclusion and Exclusion). Let $G$ be a finite set. For each $i\in G$, let $A_i$ be a finite set. Then, \begin{equation} \left\vert \bigcup_{i\in G}A_{i}\right\vert = \sum_{\substack{I\subseteq G;\\I\neq\varnothing}} \left( -1\right) ^{\left\vert I\right\vert -1} \left\vert \bigcap_{i\in I}A_{i}\right\vert . \end{equation}

But I don't know how to derive Theorem 3 from Theorem 4 directly. Instead, I will take a detour through the following lemmas:

Lemma 5. Let $Q$ be a finite totally ordered set. Let $J$ be a subset of $Q$. Let $r\in J$. Let $S$ be the set of all permutations of $Q$. Then, \begin{equation} \left\vert \left\{ \sigma\in S\ \mid\ \sigma\left( r\right) >\sigma\left( j\right) \text{ for all }j\in J\setminus\left\{ r\right\} \right\} \right\vert =\dfrac{\left\vert S\right\vert }{\left\vert J\right\vert }. \end{equation}

Lemma 5 is more or less obvious if you have the right intuition: For a uniformly random permutation $\sigma\in S$, every element $r$ of $J$ is equally likely to be $\operatorname{argmax}\left\{ \sigma\left( j\right) \ \mid\ j\in J\right\} $ (which is tantamount to satisfying $\sigma\left( r\right) >\sigma\left( j\right) $ for all $j\in J\setminus\left\{ r\right\} $); thus, the probability for $r$ to be $\operatorname{argmax} \left\{ \sigma\left( j\right) \ \mid\ j\in J\right\} $ is $\dfrac {1}{\left\vert J\right\vert }$. Essentially, this is saying that the symmetric group $S$ is, well, symmetric. If you find this convincing, scroll forward to Lemma 6. But just in case, let me now give a fully rigorous combinatorial proof for the sake of completeness.

Proof of Lemma 5. The set $J$ is nonempty (since $r\in J$). Thus, for each permutation $\sigma\in S$, the set $\sigma\left( J\right) $ is nonempty, and therefore has a largest element. In other words, for each permutation $\sigma\in S$, there exists a $j\in J$ for which $\sigma\left( j\right) $ is maximum (among all $j\in J$). This $j$ is unique (since $\sigma$ is a permutation, and thus never takes the same value twice). We denote this $j$ by $m\left( \sigma\right) $. Thus, we have defined a map $m:S\rightarrow J$ that sends each permutation $\sigma\in S$ to $m\left( \sigma\right) \in J$.

Now, let us consider the fibers $m^{-1}\left( \left\{ j\right\} \right) $ of this map $m$ for $j\in J$. Fix two elements $u$ and $v$ of $J$. We claim that $\left\vert m^{-1}\left( \left\{ u\right\} \right) \right\vert =\left\vert m^{-1}\left( \left\{ v\right\} \right) \right\vert $.

Indeed, there is clearly a permutation $\gamma\in S$ of $Q$ that satisfies $\gamma\left( v\right) =u$ and $\gamma\left( J\right) =J$. (Indeed, such a $\gamma$ can be constructed as follows: Pick some permutation of $J$ that sends $v$ to $u$; then, extend this permutation to the whole $Q$ in an arbitrary way.) Consider such a $\gamma$.

Now, let $\tau\in m^{-1}\left( \left\{ u\right\} \right) $. Thus, $\tau\in S$ is a permutation such that $m\left( \tau\right) =u$. From $m\left( \tau\right) =u$, we conclude that $\tau\left( u\right) $ is the maximum value among all the $\tau\left( j\right) $ with $j\in J$ (by the definition of $m$). In other words, $\tau\left( u\right) =\max\left\{ \tau\left( j\right) \ \mid\ j\in J\right\} $. Since $\left\{ \tau\left( j\right) \ \mid\ j\in J\right\} =\tau\left( J\right) $, this rewrites as $\tau\left( u\right) =\max\left( \tau\left( J\right) \right) $. Now, \begin{align*} \left( \tau\circ\gamma\right) \left( v\right) & =\tau\left( \underbrace{\gamma\left( v\right) }_{=u}\right) =\tau\left( u\right) =\max\left( \tau\left( \underbrace{J}_{=\gamma\left( J\right) }\right) \right) =\max\left( \underbrace{\tau\left( \gamma\left( J\right) \right) }_{\substack{=\left( \tau\circ\gamma\right) \left( J\right) \\=\left\{ \left( \tau\circ\gamma\right) \left( j\right) \ \mid\ j\in J\right\} }}\right) \\ & =\max\left\{ \left( \tau\circ\gamma\right) \left( j\right) \ \mid\ j\in J\right\} . \end{align*} In other words, $\left( \tau\circ\gamma\right) \left( v\right) $ is the maximum value among all the $\left( \tau\circ\gamma\right) \left( j\right) $ with $j\in J$. In other words, $m\left( \tau\circ\gamma\right) =v$ (by the definition of $m$). Thus, the permutation $\tau\circ\gamma\in S$ belongs to the fiber $m^{-1}\left( \left\{ v\right\} \right) $. In other words, $\tau\circ\gamma\in m^{-1}\left( \left\{ v\right\} \right) $.

Now, forget that we fixed $\tau$. We thus have proven that $\tau\circ\gamma\in m^{-1}\left( \left\{ v\right\} \right) $ for each $\tau\in m^{-1}\left( \left\{ u\right\} \right) $. Hence, the map \begin{align*} m^{-1}\left( \left\{ u\right\} \right) & \rightarrow m^{-1}\left( \left\{ v\right\} \right) ,\\ \tau & \mapsto\tau\circ\gamma \end{align*} is well-defined. This map is furthermore injective (because if two elements $\tau_{1}$ and $\tau_{2}$ of $m^{-1}\left( \left\{ u\right\} \right) $ satisfy $\tau_{1}\circ\gamma=\tau_{2}\circ\gamma$, then clearly $\tau_{1} =\tau_{2}$, since $\gamma$ is invertible). Hence, we have constructed an injective map $m^{-1}\left( \left\{ u\right\} \right) \rightarrow m^{-1}\left( \left\{ v\right\} \right) $. Hence, $\left\vert m^{-1}\left( \left\{ u\right\} \right) \right\vert \leq\left\vert m^{-1}\left( \left\{ v\right\} \right) \right\vert $. The same argument (with the roles of $u$ and $v$ interchanged) yields $\left\vert m^{-1}\left( \left\{ v\right\} \right) \right\vert \leq\left\vert m^{-1}\left( \left\{ u\right\} \right) \right\vert $. Combining this with $\left\vert m^{-1}\left( \left\{ u\right\} \right) \right\vert \leq\left\vert m^{-1}\left( \left\{ v\right\} \right) \right\vert $, we find $\left\vert m^{-1}\left( \left\{ u\right\} \right) \right\vert =\left\vert m^{-1}\left( \left\{ v\right\} \right) \right\vert $.

Now, forget that we fixed $u$ and $v$. We thus have shown that $\left\vert m^{-1}\left( \left\{ u\right\} \right) \right\vert =\left\vert m^{-1}\left( \left\{ v\right\} \right) \right\vert $ for any two elements $u$ and $v$ of $J$. Applying this to $v=r$, we thus conclude that \begin{equation} \left\vert m^{-1}\left( \left\{ u\right\} \right) \right\vert =\left\vert m^{-1}\left( \left\{ r\right\} \right) \right\vert \qquad\text{for each }u\in J. \label{pf.l5.1} \tag{1} \end{equation}

Now, $\sum_{s\in S}1=\left\vert S\right\vert \cdot1=\left\vert S\right\vert $, so that \begin{align*} \left\vert S\right\vert & =\sum_{s\in S}1=\sum_{u\in J}\underbrace{\sum _{\substack{s\in S;\\m\left( s\right) =u}}1}_{\substack{=\left\vert \left\{ s\in S\ \mid\ m\left( s\right) =u\right\} \right\vert \cdot1\\=\left\vert \left\{ s\in S\ \mid\ m\left( s\right) =u\right\} \right\vert } }=\sum_{u\in J}\left\vert \underbrace{\left\{ s\in S\ \mid\ m\left( s\right) =u\right\} }_{=m^{-1}\left( \left\{ u\right\} \right) }\right\vert =\sum_{u\in J}\underbrace{\left\vert m^{-1}\left( \left\{ u\right\} \right) \right\vert }_{\substack{=\left\vert m^{-1}\left( \left\{ r\right\} \right) \right\vert \\\text{(by \eqref{pf.l5.1})}}}\\ & =\sum_{u\in J}\left\vert m^{-1}\left( \left\{ r\right\} \right) \right\vert =\left\vert J\right\vert \cdot\left\vert m^{-1}\left( \left\{ r\right\} \right) \right\vert , \end{align*} and thus $\left\vert m^{-1}\left( \left\{ r\right\} \right) \right\vert =\dfrac{\left\vert S\right\vert }{\left\vert J\right\vert }$.

But if $\sigma\in S$ is an arbitrary permutation, then we have the following equivalences: \begin{align*} & \ \left( m\left( \sigma\right) =r\right) \\ & \Longleftrightarrow\ \left( r\text{ is the unique }j\in J\text{ for which }\sigma\left( j\right) \text{ is maximum}\right) \\ & \qquad\left( \text{by the definition of }m\left( \sigma\right) \right) \\ & \Longleftrightarrow\ \left( \begin{array} [c]{c} \sigma\left( r\right) \text{ is the largest value among all }\sigma\left( j\right) \text{ with }j\in J\text{,}\\ \text{and is only attained for }j=r \end{array} \right) \\ & \Longleftrightarrow\ \left( \sigma\left( r\right) >\sigma\left( j\right) \text{ for all }j\in J\setminus\left\{ r\right\} \right) . \end{align*} Hence, \begin{align*} \left\{ \sigma\in S\ \mid\ m\left( \sigma\right) =r\right\} & =\left\{ \sigma\in S\ \mid\ \sigma\left( r\right) >\sigma\left( j\right) \text{ for all }j\in J\setminus\left\{ r\right\} \right\} . \end{align*} Thus, \begin{align*} & \left\{ \sigma\in S\ \mid\ \sigma\left( r\right) >\sigma\left( j\right) \text{ for all }j\in J\setminus\left\{ r\right\} \right\} \\ & =\left\{ \sigma\in S\ \mid\ m\left( \sigma\right) =r\right\} =m^{-1}\left( \left\{ r\right\} \right) . \end{align*} Hence, \begin{align*} & \left\vert \left\{ \sigma\in S\ \mid\ \sigma\left( r\right) >\sigma\left( j\right) \text{ for all }j\in J\setminus\left\{ r\right\} \right\} \right\vert \\ & =\left\vert m^{-1}\left( \left\{ r\right\} \right) \right\vert =\dfrac{\left\vert S\right\vert }{\left\vert J\right\vert }. \end{align*} This proves Lemma 5. $\blacksquare$

Auxiliary inequalities

Time to get to the interesting parts. The following lemma can be viewed as a particular case of Theorem 3 (applied to $A_i = B_i \cup\left\{ q\right\} $ for some extra element $q$), but we will rather use it as a stepping stone in our proof of Theorem 3:

Lemma 6. Let $B_{1},B_{2},\ldots,B_{n}$ be $n$ finite sets. Then, \begin{equation} \sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing }}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}B_{i}\right\vert +1}\geq\dfrac{1}{\left|B_1\right|+1}. \end{equation}

Proof of Lemma 6. Let $N=\left\vert \bigcup_{i=1}^{n}B_{i}\right\vert $. Thus, we can WLOG assume that $\bigcup_{i=1}^{n}B_{i}$ is the set $\left\{ 1,2,\ldots,N\right\} $ (indeed, we can achieve this by relabeling the elements of $\bigcup_{i=1}^{n}B_{i}$). Assume this. Thus, $B_{i} \subseteq\left\{ 1,2,\ldots,N\right\} $ for all $i\in\left[ n\right] $.

Notice that $0\notin B_{i}$ for all $i\in\left[ n\right] $ (since $B_{i}\subseteq\left\{ 1,2,\ldots,N\right\} $). Hence, $0\notin\bigcup_{i\in I}B_{i}$ for any subset $I$ of $\left[ n\right] $.

Let $S$ be the set of all permutations of the $\left( N+1\right) $-element set $\left\{ 0,1,\ldots,N\right\} $. Clearly, $\left\vert S\right\vert =\left( N+1\right) !$.

For each $i\in\left[ n\right] $, we define a subset $A_{i}$ of $S$ by \begin{equation} A_{i}=\left\{ \sigma\in S\ \mid\ \sigma\left( 0\right) >\sigma\left( j\right) \text{ for all }j\in B_{i}\right\} . \end{equation}

For any subset $I$ of $\left[n\right]$, we have \begin{align*} \bigcap_{i\in I}A_{i} & =\bigcap_{i\in I}\left\{ \sigma\in S\ \mid \ \sigma\left( 0\right) >\sigma\left( j\right) \text{ for all }j\in B_{i}\right\} \\ & \qquad\left( \text{by the definition of }A_{i}\right) \\ & =\left\{ \sigma\in S\ \mid\ \sigma\left( 0\right) >\sigma\left( j\right) \text{ for all }j\in\underbrace{\bigcup_{i\in I}B_{i}} _{\substack{=\left( \left\{ 0\right\} \cup\bigcup_{i\in I}B_{i}\right) \setminus\left\{ 0\right\} \\\text{(since }0\notin\bigcup_{i\in I} B_{i}\text{)}}}\right\} \\ & =\left\{ \sigma\in S\ \mid\ \sigma\left( 0\right) >\sigma\left( j\right) \text{ for all }j\in\left( \left\{ 0\right\} \cup\bigcup_{i\in I}B_{i}\right) \setminus\left\{ 0\right\} \right\} \end{align*} and thus \begin{align*} \left\vert \bigcap_{i\in I}A_{i}\right\vert & =\left\vert \left\{ \sigma\in S\ \mid\ \sigma\left( 0\right) >\sigma\left( j\right) \text{ for all } j\in\left( \left\{ 0\right\} \cup\bigcup_{i\in I}B_{i}\right) \setminus\left\{ 0\right\} \right\} \right\vert \\ & =\dfrac{\left\vert S\right\vert }{\left\vert \left\{ 0\right\} \cup\bigcup_{i\in I}B_{i}\right\vert } \end{align*} (by Lemma 5, applied to $Q=\left\{ 0,1,\ldots,N\right\} $, $J=\left\{ 0\right\} \cup\bigcup_{i\in I}B_{i}$ and $r=0$). Hence, for any subset $I$ of $\left[ n \right]$, we have \begin{equation} \left\vert \bigcap_{i\in I}A_{i}\right\vert =\dfrac{\left\vert S\right\vert }{\left\vert \left\{ 0\right\} \cup\bigcup_{i\in I}B_{i}\right\vert } =\dfrac{\left\vert S\right\vert }{\left\vert \bigcup_{i\in I}B_{i}\right\vert +1} \label{pf.l6.4} \tag{2} \end{equation} (since $\left\vert \left\{ 0\right\} \cup\bigcup_{i\in I}B_{i}\right\vert =\left\vert \bigcup_{i\in I}B_{i}\right\vert +1$ (because $0\notin \bigcup_{i\in I}B_{i}$)).

Also, $\bigcup_{i\in\left[ n\right] }A_{i}\supseteq A_1 = \bigcap_{i\in\left\{ 1\right\} }A_{i}$ and thus \begin{align*} \left\vert \bigcup_{i\in\left[ n\right] }A_{i}\right\vert & \geq\left\vert \bigcap_{i\in \left\{1\right\} }A_{i}\right\vert =\dfrac{\left\vert S\right\vert }{\left\vert \bigcup_{i\in \left\{1\right\}}B_{i}\right\vert +1}\\ & \qquad\left( \text{by \eqref{pf.l6.4} (applied to }I=\left\{1\right\} \text{)}\right) \\ & =\dfrac{\left\vert S\right\vert }{\left|B_1\right|+1} \end{align*} (since $\bigcup_{i\in \left\{1\right\} }B_{i} = B_1$).

Now, Theorem 4 (applied to $G=\left[ n\right] $) yields \begin{equation} \left\vert \bigcup_{i\in\left[ n\right] }A_{i}\right\vert =\sum _{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\underbrace{\left\vert \bigcap_{i\in I}A_{i}\right\vert }_{\substack{=\dfrac{\left\vert S\right\vert }{\left\vert \bigcup_{i\in I}B_{i}\right\vert +1}\\\text{(by \eqref{pf.l6.4})}} }=\sum_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{\left\vert S\right\vert }{\left\vert \bigcup_{i\in I}B_{i}\right\vert +1}, \end{equation} so that \begin{equation} \sum_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{\left\vert S\right\vert }{\left\vert \bigcup_{i\in I}B_{i}\right\vert +1}=\left\vert \bigcup _{i\in\left[ n\right] }A_{i}\right\vert \geq\dfrac{\left\vert S\right\vert }{\left|B_1\right|+1}. \end{equation} Cancelling $\left\vert S\right\vert $ from this inequality (this is allowed since $\left\vert S\right\vert >0$), we obtain \begin{equation} \sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing }}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}B_{i}\right\vert +1}\geq\dfrac{1}{\left|B_1\right|+1}. \end{equation} This proves Lemma 6. $\blacksquare$

Lemma 7. Let $A_{1},A_{2},\ldots,A_{n}$ be $n$ finite sets. Let $m$ be a positive integer. Then, \begin{equation} \sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing }}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert +1/m}\geq\dfrac{1}{\left|A_1\right|+1/m}. \end{equation}

Proof of Lemma 7. For each $i\in\left[ n\right] $, we define a finite set $B_{i}$ by $B_{i}=A_{i}\times\left\{ 1,2,\ldots,m\right\} $. Then, for each subset $I$ of $\left[ n\right] $, we have \begin{equation} \bigcup_{i\in I}\underbrace{B_{i}}_{=A_{i}\times\left\{ 1,2,\ldots,m\right\} }=\bigcup_{i\in I}\left( A_{i}\times\left\{ 1,2,\ldots,m\right\} \right) =\left( \bigcup_{i\in I}A_{i}\right) \times\left\{ 1,2,\ldots,m\right\} \end{equation} and thus \begin{align} \left\vert \bigcup_{i\in I}B_{i}\right\vert & =\left\vert \left( \bigcup_{i\in I}A_{i}\right) \times\left\{ 1,2,\ldots,m\right\} \right\vert =\left\vert \bigcup_{i\in I}A_{i}\right\vert \cdot\underbrace{\left\vert \left\{ 1,2,\ldots,m\right\} \right\vert }_{=m}\nonumber\\ & =\left\vert \bigcup_{i\in I}A_{i}\right\vert \cdot m.\label{pf.l7.2} \tag{3} \end{align} Also, the definition of $B_1$ yields $B_1 = A_1 \times \left\{1,2,\ldots,m\right\}$, so that \begin{align} \left|B_1\right| = \left| A_1 \times \left\{1,2,\ldots,m\right\}\right| = \left|A_1\right| \cdot \underbrace{\left\vert \left\{ 1,2,\ldots,m\right\} \right\vert }_{=m} & = \left|A_1\right| \cdot m . \label{pf.l7.3} \tag{4} \end{align}

But Lemma 6 yields \begin{equation} \sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing }}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}B_{i}\right\vert +1}\geq\dfrac{1}{\left|B_1\right|+1}. \end{equation} In view of \eqref{pf.l7.2} and \eqref{pf.l7.3}, this rewrites as \begin{equation} \sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing }}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert \cdot m+1}\geq\dfrac{1}{\left|A_1\right| \cdot m+1}. \end{equation} Multiplying both sides of this inequality by $m$, we find \begin{equation} \sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing }}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert +1/m}\geq\dfrac{1}{\left|A_1\right|+1/m} \end{equation} (since $m\cdot\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert \cdot m+1}=\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert +1/m}$ for each $I\subseteq\left[ n\right] $, and since $m\cdot\dfrac{1}{\left|A_1\right| \cdot m+1}=\dfrac {1}{\left|A_1\right|+1/m}$). This proves Lemma 7. $\blacksquare$

We can now prove Theorem 3:

Proof of Theorem 3. Consider a positive integer $m$ going to infinity. Then, $\lim\limits_{m\rightarrow\infty}\dfrac{1}{q+1/m}=\dfrac{1}{q}$ for every positive real $q$. Thus, \begin{align*} & \lim\limits_{m\rightarrow\infty}\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert +1/m}\\ & =\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing }}\left( -1\right) ^{\left\vert I\right\vert -1}\underbrace{\lim \limits_{m\rightarrow\infty}\dfrac{1}{\left\vert \bigcup_{i\in I} A_{i}\right\vert +1/m}}_{=\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i} \right\vert }}=\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac {1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert }, \end{align*} so that \begin{align*} \sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing }}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert } & =\lim\limits_{m\rightarrow\infty }\underbrace{\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq \varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac {1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert +1/m}}_{\substack{\geq \dfrac{1}{\left|A_1\right|+1/m}\\\text{(by Lemma 7)}}}\\ & \geq\lim\limits_{m\rightarrow\infty}\dfrac{1}{\left|A_1\right|+1/m}=\dfrac{1}{\left|A_1\right|}. \end{align*} This proves Theorem 3. $\blacksquare$

Strengthening the inequality II

But wait... We can prove better inequalities. Let us extend Lemma 6 as follows:

Lemma 8. Let $B_{1},B_{2},\ldots,B_{n}$ be $n$ finite sets. Let $G$ be a subset of $\left[ n\right] $. Then, \begin{equation} \sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing }}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}B_{i}\right\vert +1}\geq\sum\limits_{\substack{I\subseteq G;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1} \dfrac{1}{\left\vert \bigcup_{i\in I}B_{i}\right\vert +1}. \end{equation}

Note that Lemma 8 turns into Lemma 6 if you set $G=\left\{ 1\right\} $.

Proof of Lemma 8. Let us use the same notations as in the proof of Lemma 6. Let us also WLOG assume that $\bigcup_{i=1}^{n}B_{i}$ is the set $\left\{ 1,2,\ldots,N\right\} $ (as in the proof of Lemma 6).

From $G\subseteq\left[ n\right] $, we obtain $\bigcup_{i\in G}A_{i} \subseteq\bigcup_{i\in\left[ n\right] }A_{i}$, and thus \begin{equation} \left\vert \bigcup_{i\in G}A_{i}\right\vert \leq\left\vert \bigcup _{i\in\left[ n\right] }A_{i}\right\vert =\sum_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{\left\vert S\right\vert }{\left\vert \bigcup_{i\in I}B_{i} \right\vert +1} \end{equation} (this is proven as in the proof of Lemma 6). Thus, \begin{align*} & \sum_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{\left\vert S\right\vert }{\left\vert \bigcup_{i\in I}B_{i}\right\vert +1}\\ & \geq\left\vert \bigcup_{i\in G}A_{i}\right\vert =\sum_{\substack{I\subseteq G;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\underbrace{\left\vert \bigcap_{i\in I}A_{i}\right\vert } _{\substack{=\dfrac{\left\vert S\right\vert }{\left\vert \bigcup_{i\in I} B_{i}\right\vert +1}\\\text{(by \eqref{pf.l6.4})}}}\\ & \qquad\left( \text{by Theorem 4}\right) \\ & =\sum_{\substack{I\subseteq G;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{\left\vert S\right\vert }{\left\vert \bigcup_{i\in I}B_{i}\right\vert +1}. \end{align*} Cancelling $\left\vert S\right\vert $ from this inequality (this is allowed since $\left\vert S\right\vert >0$), we obtain \begin{equation} \sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing }}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}B_{i}\right\vert +1}\geq\sum\limits_{\substack{I\subseteq G;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1} \dfrac{1}{\left\vert \bigcup_{i\in I}B_{i}\right\vert +1}. \end{equation} This proves Lemma 8. $\blacksquare$

Next, we generalize Lemma 7 as follows:

Lemma 9. Let $A_{1},A_{2},\ldots,A_{n}$ be $n$ finite sets. Let $G$ be a subset of $\left[ n\right] $. Let $m$ be a positive integer. Then, \begin{equation} \sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing }}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert +1/m}\geq\sum\limits_{\substack{I\subseteq G;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1} \dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert +1/m}. \end{equation}

Proof of Lemma 9. Lemma 9 can be derived from Lemma 8 in the same way as Lemma 7 was derived from Lemma 6. $\blacksquare$

We can now generalize Theorem 3:

Theorem 10. Let $A_{1},A_{2},\ldots,A_{n}$ be $n$ finite nonempty sets. Let $G$ be a subset of $\left[ n\right] $. Then, \begin{equation} \sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing }}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert }\geq\sum\limits_{\substack{I\subseteq G;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1} \dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert }. \end{equation}

Proof of Theorem 10. Theorem 10 can be derived from Lemma 9 in the same way as Theorem 3 was derived from Lemma 7. $\blacksquare$

One interesting feature of Theorem 10 is that (unlike our above proof of Theorem 3) it allows us to determine when equality holds in Theorem 3. Namely, we have the following:

Proposition 11. Equality holds in Theorem 3 if and only if each $j\in\left[ n\right] $ satisfies $A_{1}\subseteq A_{j}$.

Proof of Proposition 11 (sketched). I leave it to the reader to check that if each $j\in\left[ n\right] $ satisfies $A_{1}\subseteq A_{j}$, then equality holds in Theorem 3 (hint: all addends on the left hand side cancel each other in pairs, except for the addend $\dfrac{1}{\left\vert A_{1}\right\vert }$). Let me prove the converse:

Assume that equality holds in Theorem 3. We must show that each $j\in\left[ n\right] $ satisfies $A_{1}\subseteq A_{j}$.

Indeed, assume the contrary. Thus, there exists some $j\in\left[ n\right] $ such that $A_{1}\not \subseteq A_{j}$. Consider this $j$. From $A_{1} \not \subseteq A_{j}$, we conclude that $A_{j}$ is a proper subset of $A_{1}\cup A_{j}$. Hence, $\left\vert A_{j}\right\vert <\left\vert A_{1}\cup A_{j}\right\vert $, so that $\dfrac{1}{\left\vert A_{j}\right\vert }>\dfrac {1}{\left\vert A_{1}\cup A_{j}\right\vert }$.

Also, $A_{1}\neq A_{j}$ (since $A_{1}\not \subseteq A_{j}$), so that $1\neq j$. Now, Theorem 10 (applied to $G=\left\{ 1,j\right\} $) yields \begin{align*} \sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing }}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert } & \geq\sum\limits_{\substack{I\subseteq \left\{ 1,j\right\} ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert }\\ & =\dfrac{1}{\left\vert A_{1}\right\vert }+\underbrace{\dfrac{1}{\left\vert A_{j}\right\vert }-\dfrac{1}{\left\vert A_{1}\cup A_{j}\right\vert } }_{\substack{>0\\\text{(since }\dfrac{1}{\left\vert A_{j}\right\vert } >\dfrac{1}{\left\vert A_{1}\cup A_{j}\right\vert }\text{)}}}\qquad\left( \text{since }1\neq j\right) \\ & >\dfrac{1}{\left\vert A_{1}\right\vert }. \end{align*} This contradicts our assumption that equality holds in Theorem 3. This contradiction shows that our assumption was wrong. Hence, Proposition 11 is proven. $\blacksquare$

Answer 3

I don't understand your justification for why this is true even for $n=2$ (more strongly, I think it's false). It's certainly the case that $\left|A_1\right|^{-1} \ge \left|A_1 \cup A_2\right|^{-1}$, but there are more terms in the sum over pairs of sets than in the sum over sets, so comparing individual terms doesn't guarantee anything about the sign of the outcome. For instance, let $A_1=\{1,2,3\}$, $A_2=\{1,2,4\}$, $A_3=\{1,3,4\}$, and $A_4=\{2,3,4\}$. Then every $\left|A_i\right|=3$, and every $\left|A_i\cup A_j\right|=4$, so $$ \sum_{i=1}^{4}\frac{1}{\left|A_i\right|} - \sum_{1\le i<j\le 4}\frac{1}{\left|A_i\cup A_j\right|}=4\times\frac{1}{3}-6\times\frac{1}{4}=-\frac{1}{6} < 0.$$ Am I missing something?

Answer 4

Here is an extended comment:

It seems true for $n$ odd, for reasons similar to the ones given in the $n=3$ case. To see this, we first consider the first $n-1$ summands, and pair sum $i$, $1\leq i<n/2$, with sum $n-i$. Note that there are an equal number of terms these pairs, as $$ \binom{n}{i}=\binom{n}{n-i} $$ Now we pair up elements from each sum. Namely, we have to find a bijection taking $\{A_{j_1},\dots,A_{j_i}\}$ to a superset $\{A_{k_1},\dots,A_{k_{n-i}}\}$. If we can do this, then we know $$ \left|\cup_i A_{j_i}\right|\leq \left|\cup_i A_{k_i}\right|,\text{ or }\;\frac{1}{\left|\cup_i A_{j_i}\right|}\geq\frac{1}{\left|\cup_i A_{k_i}\right|} $$ and from this pairing it follows that the $i$th sum minus the $(n-i)$th sum is nonnegative. Adding on the final $n$th term, which is positive, will then ensure that the whole sum is positive.

(Hopefully the above argument makes sense. If it does not, feel free to leave a comment and I can expand on it, for now I will move on.)

So now it suffices to find such a bijection. I am unfortunately having trouble rigorously showing there is one, but heuristically it seems like there must be such a map. Hopefully that helps a bit, and I will keep thinking on it and see if I can finish it up.

Answer 5

Note: A remark in addition to the nice answer of @darijgrinberg.

He refers to a very elegant answer by @zeraouliarafik regarding the strongly related inequality question:

Let $x_1,\ldots,x_n> 0$. Does the following inequality hold? \begin{align*} \sum_{i=1}^n\frac{1}{x_i}-\sum_{i<j}\frac{1}{x_i+x_j}+\sum_{i<j<k}\frac{1}{x_i+x_j+x_k}-\cdots +(-1)^{n-1 }\frac{1}{x_1+\ldots+x_n}>0 \qquad\qquad \tag{1} \end{align*}

Observe, that OPs question is a generalisation of (1). In the following we consider two extreme cases:

Case 1: Sets $A_1,\ldots,A_n$ forming a partition

Let's assume the sets $A_i, 1\leq i \leq n$ form a partition of a set $X\neq \emptyset$.

Then OPs inequality becomes \begin{align*} \sum_{i=1}^n&\frac{1}{|A_i|}-\sum_{1\leq i<j\leq n}\frac{1}{|A_i\cup A_j|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|A_i\cup A_j\cup A_k|}-\cdots+\frac{(-1)^{n-1}}{|A_1\cup\cdots\cup A_n|}\\ &=\sum_{i=1}^n\frac{1}{|A_i|}-\sum_{1\leq i<j\leq n}\frac{1}{|A_i|+|A_j|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|A_i|+|A_j|+|A_k|}-\cdots+\frac{(-1)^{n-1}}{|A_1|+\ldots+|A_n|} > 0\tag{2}\\ \end{align*} which is exactly (1) and already proven by @zeraouliarafik in the referenced MSE inequality question.

On the other side we have the extreme case

Case 2: Identical sets $X=A_1=\ldots=A_n\neq \emptyset$

Then OPs inequality becomes

\begin{align*} \sum_{i=1}^n&\frac{1}{|A_i|}-\sum_{1\leq i<j\leq n}\frac{1}{|A_i\cup A_j|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|A_i\cup A_j\cup A_k|}-\cdots+\frac{(-1)^{n-1}}{|A_1\cup\cdots\cup A_n|}\\ &=\sum_{i=1}^n\frac{1}{|X|}-\sum_{1\leq i<j\leq n}\frac{1}{|X|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|X|}-\cdots+\frac{(-1)^{n-1}}{|X|}\\ &=\frac{1}{|X|}\left(\binom{n}{1}-\binom{n}{2}+\binom{n}{3}-\ldots+(-1)^{n-1}\binom{n}{n}\right)\\ &=\frac{1}{|X|}\left(1-(1-1)^n\right)\\ &=\frac{1}{|X|}>0\tag{3} \end{align*}

Other settings of $A_1,\ldots,A_n$ in between these extreme cases will give a result between the values of (2) and (3).

Question: It seems OPs expression could be some kind of measure of the scattering of $n$ subsets with $X=\bigcup_{i=1}^nA_i$. Maybe someone could point to related information?