Find the number of nonempty sets of subsets of the set such that: (a) For any subsets . (b) If , and , then .
Solution
For a subset of , let be the set of all sets such that . It can be checked that the sets satisfy the conditions 1 and 2. We claim that the are the only sets of subsets of satisfying the conditions 1 and 2. (Thus, the answer is the number of subsets of , which is .) Suppose that satisfies the conditions 1 and 2, and let be the intersection of all the sets of . We claim that . First, by definition of , all elements are supersets of , so . On the other hand, by iterating condition 1, it follows that is an element of , so by condition 2 any set with is an element of . So . Thus .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.