Proof Verification (Set Theory)

Question

Let $S$ be a set with $N$ elements and let $A_1,\dots ,A_{101}$ be $101$ (possibly non disjoint) subsets of $S$ with the following properties:

a) each element of $S$ belongs to at least one of these subsets

b) each subset contains exactly $1000$ elements of $S$

c) the intersection of any pair of subsets contains exactly $200$ elements

d) the intersection of any three subsets contains exactly $6$ elements

e) the intersection of any $4$ or more distinct subsets is empty

Prove this set cannot exist

My Proof

1) We know from inclusion-exclusion we can compute the cardinality by $101\times1000 - \binom{101}{2}\times200 + \binom{101}{3}\times6$

2) We know from property E that $A_1\cap A_2 \cap A_3 \cap A_4 \cap A_5 \cap A_6 = \emptyset$

3) By associative law we have $[A_1\cap A_2 \cap A_3] \cap [A_4 \cap A_5 \cap A_6] = \emptyset$

4) We can do this with any distinct intersection of 3 subsets. Therefore, all our intersections with 3 sets are disjoint from each other.

5) Since they are all disjoint, we can write the cardinality as the sum of all intersections of 3 distinct sets

6) The sum of all distinct intersections of 3 sets can be written as $\binom{101}{3}\times6$

7) However $\binom{101}{3}\times6$ does not equal our computation in step 1. So, the set is a contradiction. Valid ways of counting compute different cardinalities for it.

My Question

I want to know if the proof is sensible, readable and most importantly correct.

Answer 1

Your step $(4)$ doesn’t quite work. You know that if $A_{i_1},A_{i_2},A_{i_3},A_{i_4},A_{i_5}$, and $A_{i_6}$ are distinct sets in the family, then $A_{i_1}\cap A_{i_2}\cap A_{i_3}$ and $A_{i_4}\cap A_{i_5}\cap A_{i_6}$ are disjoint but clearly $A_{i_1}\cap A_{i_2}\cap A_{i_3}$ and $A_{i_1}\cap A_{i_2}\cap A_{i_4}$, say, are not disjoint. Thus, you don’t have $\binom{101}3$ pairwise disjoint intersections of triplets of sets. (In fact, you can get at most $33$, since $34\cdot3=102>101$.) You also don’t know that every element of $S$ belongs to $3$ or more of the subsets, so even if all $\binom{101}3$ intersections of triplets were pairwise disjoint, there’s still no guarantee that their union is all of $S$.

You know from your inclusion-exclusion calculation that $N=90900$. Another inclusion-exclusion calculation will tell you what $|A_{i_1}\cup A_{i_2}\cup A_{i_3}|$ is for each set of distinct $i_1,i_2,i_3\in\{1,\ldots,101\}$. You can make a similar calculation for pairs of subsets. Then observe that

$$|S|\le\sum_{k=1}^{33}|A_{3k-2}\cup A_{3k-1}\cup A_{3k}|+|A_{100}\cup A_{101}|\;,$$

and get a contradiction.