I'm reading proof on Wikipedia that the existence of pseudorandom generators implies the existence of one-way functions.
My understanding is that pseudorandom generators are defined as
A function $G_l:\{0,1\}^l\to\{0,1\}^m$ is a pseudorandom generator if all of the following hold:
a. $l<m$
b. $G_l\in\mathbf P$
c. For any polynomially-sized circuit $C$, $$ \left|\Pr_{x\sim\text{Unif}\{0,1\}^l}[C(x)=1]-\Pr_{x\sim\text{Unif}(D)}[C(x)=1]\right|<\text{poly}(n), $$ where $D$ is the image of $G_l$.
and that one-way functions are defined as:
A function $f:\{0,1\}^n\to\{0,1\}^n$ is a one-way function if all of the following hold:
- $f$ is invertible
- $f\in\mathbf P$
- For any polynomially-sized circuit $C$,
$$ \Pr[f(C(f(x))=f(x)]<\text{poly}(n). $$
Question 1: Looking at definitions for one-way functions above, I assume that the notation $f:\{0,1\}^n\to\{0,1\}^n$ refers to a family of functions $\mathcal F=\{f_n\}_{n\in\mathbf N}$, where each $f_n$ is an invertible function $\{0,1\}^n\to\{0,1\}^n$. (And analogously for the defintion of pseudorandom generators.) Is this assumption correct?
The proof that pseudorandom generators implies one-way functions given on the Wikipedia page starts off with:
Consider a pseudorandom generator $G_l:\{0,1\}^l\to\{0,1\}^{2l}$. Let's create the following one-way function $f:\{0,1\}^n\to\{0,1\}^n$ that uses the first half of the output of $G_l$ as its output. Formally, $$ f(x,y)\to G_l(x) $$
Question 2: What exactly is this saying? It looks like $|x|+|y|=n$, so I'll assume for now that $|x|=l=n/2$, in which case $G_l(x)$ outputs a string of length $2l=n$. But if $G$ ignores $y$, how can $f$ be injective?
Thanks!