Growth function-Number of hypothesis

Question

I am trying to prove that $m_{h}(n)\leq min(M,2^{n})$ where M is the number of the hypotheses and $m_{h}(n)$ is the growth function. The only thing I know is that $m_{h}(n)\leq2^{n}$ from definition of growth function but I can found a relation between M and $2^n$ in order to prove this inequality. Any help will be appreciated.

Answer 1

The growth function is the number of decidable dichotomies of $n$ points right? Then, for each dichotomy, a hypothesis may or may not decide it. Now, a single hypothesis cannot decide two different dichotomies, as that would mean that such a hypothesis would evaluate to two different values at a point. Therefore, the number of dichotomies that can be decided is at most the number of hypothesis. Because, if this is not true, then the number of decided dichotomies is more than the number of hypothesis, and therefore at least two dichotomies are decided by the same hypothesis. This is impossible as discussed above. Thus, $m_H(n) \le M$.

Then, as you stated, $m_H(n) \le 2^n$. Now, since both inequalities are true, $$m_H(n) \le \min(M, 2^n)$$