On ADS (Part 4)February 10, 2012 at 14:40 | Posted in Uncategorized | Leave a comment
So what does it mean when we say “almost works”? We’ll start with a lemma:
Lemma 1 For a fixed , the set contains at most one element from each set , and hence is at most countable.
Proof: Suppose by way of contradiction what and are distinct members of for which
and this contradicts the fact that is a transversal for .
Now given , we are going to define to be those for which has failed to work, that is,
Lemma 2 The set is at most countable.
Proof: If not, find for which the set is uncountable, and set
Then for each , we have
which contradicts the preceding lemma.
So for a given , the function will “disjointify” from all but countably many with : the function “almost works”.
Notice that if and only if , so that we can define a graph on by connecting and if and only if . By the preceding lemma, every vertex of the graph has at most countably many edges coming out of it. An easy argument tells us that the connected components of our graph are at most countable as well.
Now if and are members of different connected components of then will disjointify and . But each connected component of can be disjointified easily (by induction) as it is at most countable.
Thus, it is straightforward now to “correct” to a function which will work everywhere.