G is a PRG and takes in a seed s. Is G'(s) = [G(s)]' (i.e. the complement of G(s)) a PRG as well?
My proof by contradiction: Suppose G' is not a PRG, then G''(s) = [[G(s)]']' = G(s) is also not a PRG which is a contradiction, since our initial assumption is that G is a PRG.
Does this proof make sense? Can anyone point out any mistake(s) made?
This proof is wrong.
It's tried to prove the proposition "the complement of any function that is a PRG is a PRG" by contradiction. The contrary of that proposition is not "the complement of any function that is a PRG is a not a PRG", which is used in the attempted proof to justify the equation after "then".
The correct contrary is "there exists a function that is a PRG which complement is not a PRG", and a proof by contradiction must start from that (as the proposed proof does), and conclude a contradiction, without making unwarranted hypothesis. Hint: a correct proof will use the definition of "is a PRG".
Meta-argument that the question's proof is wrong (but not telling where): the argument used works just as well if we change "a PRG" into "identity" in the statement of the proposition to prove, and reaches the false conclusion that "the complement of any function that is identity is identity".
General hint: it's typically useful to write and use definition(s) involved in the statement of a proposition to prove or disprove.
