Saturday, 22 April 2017

Proof Verification (Set Theory)

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.

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...