Define and let be the set of all proper subsets of . (A proper subset is a subset that is not the set itself.) How many ordered pairs of proper subsets of are there such that (a) is not a proper subset of and is not a proper subset of ; and (b) for any sets and is not a proper subset of and is not a proper subset of ?
Solution
For ease of notation, we let . Then both and are proper subsets of . We consider the following cases: Case 1. If , then is a proper subset of any set except the empty set, so we must have . Case 2. If , then cannot be empty, nor can it contain either 1 or 2, so we must have . This also implies that if contains another element, then there would be no choice of because would be a proper subset. Case 3. If , then cannot contain 0, and cannot contain both 1 and 2 (or it becomes a proper superset of ), so it can only be or , and both work. The similar apply when . Case 4. If , then since cannot contain 0, it must contain both 1 and 2 (or it becomes a proper subset of , so . Hence, all the possibilities are for 7 possible pairs in total.