Question about the Proof of "Pseudorandom generators imply one-way functions" in "Foundations of Cryptography"

Question

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$?

Answer 1

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$.