Let X be a set of n points. Let P be a set of subsets of X, such that if A, B ∈ P, then X - A, A ∪ B, A ∩ B ∈ P. What are the possible values for the number of elements of P?
Solution
Answer: 2, 4, 8, ... , 2n.
Take 0 ≤ r < n. Let A1 = {1}, A2 = {2} , ... , Ar = {r}, Ar+1 = {r+1, r+2, ... , n}. Consider the collection of all unions of sets Ai. This collection has 2r+1 elements and satisfies the conditions. So this shows that we can achieve the values 2, 4, 8, ... , 2n.
To prove the converse we use induction on n. It is obviously true for n = 1. Suppose it is true for all n < N. Let X have N points and P be a set of subsets of X satisfying the condition. If |P| = 2, then there is nothing to prove. Otherwise we can find a member Y of P other than the empty set and X which has no non-trivial subsets in P. Now consider the collection Q of subsets of X - Y which are in P. It is easy to check that (1) P is just the collection of all A and A ∩ Y, where A is in Q, so that |P| = 2|Q|, and (2) Q satisfies the conditions, so |Q| is a power of 2 by induction.
© John Scholes
jscholes@kalva.demon.co.uk
15 Feb 2002