Pac learnable when changing distribution
I think the definitions in that book are unclear. If you note, the realisability assumption is not stated as an assumption on anything, nor as a standalone definition, so that already is a bit confusing. I have struggled to find one anywhere that is clear actually.

It appears to me that The Realisability Assumption is also dependent on the distribution  $D$ and the labelling function $f$. That is the trio ($H, D, f$) can be realisable. $H$ in and of itself cannot be realisable.

It took me some sleuthing to come to this conclusion, and I hope it is the right one. I think you are nearly on the right lines of thinking. Here is my thinking:

As you say, if we choose a distribution that causes problems then perhaps we can prove that $L(h) = Err(h) &gt; 0$. If you assume $H$ is finite, and $f$ is not in $H$, then we can find problematic points $x$s and put positive probabilities on them. Then for every $h$ in $H$, $L(h) &gt; 0$; i.e. $H$ is not actually realisable with respect to any distribution.

We have made an assumption that $H$ is finite, but given that the book later on goes on demonstrate results with realisability, and finite $H$, I think we should assume that realisability and finite $H$ together are a valid consideration, and therefore, we cannot assume that realisability holds across any distribution over the domain set $X$. I think therefore we should assume that that is what they meant when defining realisability.

Similarly for the labelling function $f$. If $H$ and $D$ are realisable, independently of $f$, then in the case where $H$ is finite and contains only one hypothesis $h$, we can choose an $f$ that is different to h on the whole domain, which would result in $Err(h) = 1$.

So here's how I would state the Realisability Assumption:


  Definition (The Realisability Assumption) Given a learning problem with distribution $D$ over the domain set, and labelling function $f$, then a set of hypotheses, $H$, is Realisable if there exists $h* \in H$ s.t.
  $L_{(D,f)}(h*) = 0$.


Note that you do not need to know what $D$ and $f$ are to assume that $H$ is realisable with respect to them. We can just assume that $H$ is realisable with respect to them, whatever they may be.

So, assuming realisability in PAC Learnability also restricts $D$ and $f$ to be those which are realisable w.r.t. $H$.