Problem:
A cell of a 2-configuration of a set is a nonempty subset of such that
i. for any two distinct elements of , there exists a sequence of elements of with , and such that are all elements of the 2-configuration, and
ii. if is an element of and is an element of but not of , there does NOT exist a sequence of elements of with , and such that are all elements of the 2-configuration.
Also, we define a 2-configuration of to be barren if there is no subset of , with , such that and are all elements of the 2-configuration.
Show that, given any 2-configuration of a set , every element of belongs to exactly one cell.
Solution
Solution:
First, given , let be the set of all for which there exists a sequence as in the definition of a cell. Certainly (take ); we claim that is a cell. If , then there exist sequences and , so the sequence shows that the first condition is met.
For the second, suppose that there does exist a sequence with . Then, concatenating with our sequence from to , we get a sequence from to , contradicting the assumption . Thus, the second condition holds, and is a cell. So lies in at least one cell.
But now, note that if is a cell containing , then all for which such a sequence from to exists must lie in (or the second condition is violated), and if no such sequence exists, then cannot lie in (or the first condition is violated). Thus, the elements of are uniquely determined, so there is exactly one cell containing , and the proof is complete.