# Mathematical proof for approximated equation basing on sets

Given $n$ sets i.e., $A_1, A_2,\dots, A_n$ where $|A_i|$ is the number of elements in the set $A_i$, let $U=A_1\cup A_2\cup\dots\cup A_n$. Can anyone prove that for sequences $|B_1|\ge|B_2|\ge\dots\ge|B_m|$ selected from the $A_i$ (so each $B_j=A_i$ for some $i$),

$$|B_1| + |B_2| +\dots+ |B_m|\approx\left(\frac{|B_1\cup B_2\cup\dots\cup B_m|}{|U|} + \frac{|(B_1\cup B_2\cup\dots\cup B_{m-1})\cap B_m|}{ 2|B_m|}\right)|U|.$$

This equation is holding good on a very huge data and proved to be be correctly approximating the closest value. But mathematical proof is needed to substantiate it. Can any one prove it mathematically?

• This was a fairly complicated TeXification, double check the formulas to make sure I did it right. – Mario Carneiro Jun 3 '15 at 5:14
• I think the equation needs some cleanup before it can even be analyzed for correctness. Several undeclared indexes ($i,j,k,m$) show up in the equation; what are these referring to? In the first paragraph it seems that there are $n$ sets but this apparently changes to $m$ in the equation and second paragraph. – Mario Carneiro Jun 3 '15 at 5:19
• @MarioCarneiro The indices $i,j,k,m$ are supposed to represent the relative order of $n(A_1),\ldots,n(A_m)$. It would have been much simpler to just assume that $n(A_1) \geq \dots \geq n(A_m)$. Also, perhaps more than two terms were intended in the sum, though granted only two appeared. – Yuval Filmus Jun 3 '15 at 5:32
• Please see the following example for better understanding. Lets take 6 sets. so n=6 i.e., A={1,2,3,4}, B={1,5,6,7,8,9,10}, C={1,2,3,4,10} D={4,5,6,7,10}, E={2,3,8,9} and F={3,8,9} then Universal set, U= Union(A,B,C,D,E,F)={1,2,3,4,5,6,7,8,9,10} thus |U|=10. Now say m=2 where I am considering B and C. then n(B) + n(C) ≈ [n(B ∪ C)/|U| +n((B) ∩C) /2n(C) ] * |U| That is 7+5 ≈ [10/10 + 2/(2*5)]* 10 that implies 12 ≈ (1+0.2)*10 that implies 12 ≈1.2 *10 that implies 12≈12.0 where n(B) = 7, n(C)= 5, n(B ∪ C)= 10, n((B) ∩C)= 2 – ksn Jun 3 '15 at 5:37
• It is okay to prove that the approximation deviates by a constant 'k' in cases. Say for example m=3 and say considering D,E,F from the above mentioned example. then n(D) +n(E) +n(F) ≈ [n(D ∪ E∪ F)/|U| +n(((D ∪ E) ∩F) /2n(F) ] * |U| that is 5+4+3 ≈ [9/10 + 3/(2*3)] * 10 that is 12 ≈ 1.4*10 that is 12 ≈14.0 .Here the deviation of approximation k= 14-12= 2. – ksn Jun 3 '15 at 6:04

Suppose that $A_m$ is disjoint from all other sets. Then your formula reads $$n(A_1) + \cdots + n(A_m) = n(A_1 \cup \cdots \cup A_m).$$ This is not true. For example, suppose that $n(A_m) = 1$ and $A_1=\cdots=A_{m-1}$, $n(A_1) = N$. The left-hand side is $N(m-1)+1$, while the right-hand side is $N+1$.
• Note that the original equation had an $\approx$, so perhaps it is not meant to be exactly true in all cases (not sure about what is meant, though...) – Mario Carneiro Jun 3 '15 at 5:15
• @MarioCarneiro Under what notion of approximation is $100m$ the same as $100$? – Yuval Filmus Jun 3 '15 at 5:33