View Single Post
  #2  
Old 01-03-2013, 03:02 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Growth Function division into S1 and S2

A full dichotomy on all N points can have a "twin" dichotomy (also on all N points) that is identical to it except for the last bit, where it differs so one dichotomy ends with +1 and the other ends with -1. It is those "twin" dichotomies that end up in the set S_2 (both of them); the one ending with +1 goes to S_2^+ and the one ending with -1 goes to S_2^-. Each of S_2^+ and S_2^- has \beta elements, hence S_2 which is their union has 2\beta elements.

The dichotomies that do not have a "twin" are the ones that end up in S_1 and there are \alpha of them. Each dichotomy goes to one, and only one, of the sets S_1, S_2^+, S_2^-. I hope this clarifies the matter. Please feel free to ask further questions.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote