# Question about the Proof of “Pseudorandom generators imply one-way functions” in “Foundations of Cryptography”

In "Foundations of Cryptography, Volume 1" by Oded Goldreich, chapter 3.3.6 states the following theorem:

Let $$G$$ be a pseudorandom generator with expansion factor $$l(n) = 2n$$. Then the function $$f\colon \{0,1\}^* \to \{0,1\}^*$$ defined by letting $$f(x,y) \stackrel{\text{def}}= G(x)$$, for every $$|x| = |y|$$ is a strongly one-way function.

The theorem is proved by reduction, with given an inverter $$A$$ construct the following distinguisher $$D$$: $$D(\alpha) = 1 \quad\text{iff}\quad f(A(\alpha)) = \alpha$$ (where $$D$$ distinguishes between $$U_{2n}$$ and $$G(U_n)$$). There is one part of the proof I do not understand:

[...] by $$f$$'s construction, at most $$2^n$$ different $$2n$$-bit-long strings (i.e., those in the support of $$G(U_n)$$) have pre-images under $$f$$. Hence $$\Pr[D(U_{2n}) = 1] = \Pr[f(A(U_{2n})) = U_{2n}] \leq 2^{-n}$$.

Why don't all $$2^{2n}$$ possible $$2n$$-bit-long strings have preimages under $$f$$?

Let $$n\in \mathbb{N}$$, and fix $$x,y \in \{0,1\}^n$$, $$f(x,y)=G(x) \in \{0,1\}^{2n}$$. By $$f$$'s definition, $$\forall x,y_1,y_2 \in \{0,1\}^n,\;f(x,y_1)=f(x,y_2).$$ Hence, if we define the function $$f'\colon\{0,1\}^n\to \{0,1\}^{2n}$$ by $$f'(x)=f(x,0^n)$$ we get that $$\operatorname{Im}(f)=\operatorname{Im}(f')$$ and $$\lvert\operatorname{Im}(f')\rvert\le \lvert\{0,1\}^n\rvert=2^n$$.