Empirical Risk and True Risk - Generalization Error Proof
This answer (as, I presume, the question) uses the notation of the book Understanding Machine Learning: From Theory to Algorithms by Shai Shalev-Shwartz and Shai Ben-David.
Suppose our domain set is $\mathbb N$ and we are interested in binary classification. We want to show that there exists a distribution $P$ on $\mathbb N$ and a learning algorithm $A$ such that the difference between the empirical error $L_S(A(S))$ of the hypothesis $A(S)$ produced by $A$ given the finite sample set $S$ and the true error $L_P(A(S))$ is large, i.e. the hypothesis $A(S)$ performs well on the training data but does not generalize.
So to prove the statement, let $m \geq 0$ and $\varepsilon &gt; 0$ and consider a binary classification scenario over the domain set $\mathbb N$.
We define a learner $A$ as follows: Given a set $S \subset \mathbb N \times \{0, 1\}$ of $m$ samples, $A$ outputs the hypothesis
$$ h_S(x) = 
\begin{cases}
y, &amp; \text{if } (x, y) \in S \\
0, &amp; \text{otherwise}.
\end{cases} $$
Clearly, the empirical error of the hypothesis produced by $A$ will be $0$ for any training set $S$ as we defined the output of $A$ specifically to be correct for all samples in $S$.
It remains to construct a probability distribution over $\mathbb N$ such that the true error of the hypothesis $A(S)$ is at least $1 - \varepsilon$ for any choice of $S$.
Recall that the true error of a hypothesis $h$ w.r.t. a distribution $P$ is defined as
$$L_P(h) = \Pr_{(x, y) \sim P}[h(x) \neq y].$$
We now fix the labels in our distribution to always be 1 to ensure that $A(S)$ errs on all inputs not contained in the sample set $S$.
Hence the task now reduces to assigning probabilities to each $n \in \mathbb N$ such that the combined probability of any $m$ points forming such a sample set is bounded by $\varepsilon$.
To achieve this, consider the distribution $P \colon \mathbb N \to [0, 1]$ with
$$
P(n) = 
\begin{cases}
\varepsilon / m, &amp; \text{if } n \leq m - 1 \\
\varepsilon / (m \cdot 2^{n - m + 1}), &amp; \text{otherwise}.
\end{cases}
$$
If we consider any sample set $S \subset \mathbb N$ of size $m$, we find that
$$ \Pr_{x \sim P}[x \in S] =  \sum_{n \in S} P(n) \leq \sum_{n \in S} \frac{\varepsilon}{m} = \varepsilon.$$
Hence, using the learner $A$ on a sample set $S$ of size $m$ drawn using the distribution $P$ yields a hypothesis $h_S$ with
$$
\begin{align}
L_P(A(S)) 
&amp;= \Pr_{x \sim P}[h_S(x) \neq 1] \\
&amp;= \Pr_{x \sim P}[x \notin S] \\
&amp;= 1 - \Pr_{x \sim P}[x \in S] \\
&amp;\geq 1 - \varepsilon.
\end{align}
$$
To finish everything off, recall that we defined $A$ such that $L_S(A(S) = 0$, yielding
$$|L_S(A(S) - L_P(A(S))| \geq 1 - \varepsilon.$$