Saturday, 22 April 2017

Proof Verification (Set Theory)

Let S be a set with N elements and let A1,,A101 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×1000(1012)×200+(1013)×6



2) We know from property E that A1A2A3A4A5A6=




3) By associative law we have [A1A2A3][A4A5A6]=



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 (1013)×6



7) However (1013)×6 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 limhrightarrow0fracsin(ha)h

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