# Set theory and functions

(1) Prove or disprove: For any sets $X,Y,Z$ and any maps $f:X \to Y$ and $g:Y \to Z$, if $f$ is injective and $g$ is surjective, then $g \circ f$ is surjective.

So i proved previously that $f$ is injective if $g \circ f$ is injective, but then i also proved that if $g \circ f$ is surjective then $g$ is surjective. then this question appears, so how do i prove it that it is true or false? I'm saying it's true, because $g \circ f$ is bijective, so how do i go around proving it? Or my idea is already wrong? I need some help thanks.

(2) Show that (it is true in general that) for any sets $A,B$, one has $P(A) \cup P(B) \subseteq P(A \cup B)$.

I know that power set has exactly all the subsets of $A$ for $P(A)$. but I dont know how to start.

• hints: for (1) what if $f$ is not surjective? Sep 6, 2015 at 16:55
• what do u mean? Sep 6, 2015 at 16:57
• take $Y=Z$ and $g$ equals identity function. what would happen if $f$ is not surjective Sep 6, 2015 at 16:59
• For a counterexample see the second example here Sep 6, 2015 at 16:59
• if g is injective and f is not surjective, then gof will be injective? Sep 6, 2015 at 17:00

As you said in your question we have indeed:

• $g\circ f$ injective implies that $f$ is injective.
• $g\circ f$ surjective implies that $g$ is surjective.

Then under the condition that $f$ is injective and $g$ is surjective you seem to conclude that $g\circ f$ is bijective ("I'm saying it's true, because $g \circ f$ is bijective...").

From where do you get this? It seems to me that you turned aroung the two statements above. From injectivity of $f$ you are not allowed to conclude that $g\circ f$ injective. And from surjectivity of $g$ you are not allowed to conclude that $g\circ f$ surjective.

A (repetition of a) counterexample:

let $g:\{0,1,2\}\rightarrow\{0,1\}$ be prescribed by $0\mapsto0$, $1\mapsto1$, $2\mapsto1$ and let $f:\{0,1\}\rightarrow\{0,1,2\}$ be prescribed by $0\mapsto1$, $1\mapsto2$.

Then $f$ is injective and $g$ is surjective.

However $g\circ f:\{0,1\}\rightarrow\{0,1\}$ is constant (and prescribed by $0\mapsto1$ and $1\mapsto1$).

It is evidently not injective and is not surjective.