Set theory and functions

Question

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

take $Y=Z$ and $g$ equals identity function. what would happen if $f$ is not surjective — user251257, Sep 06 '15 at 16:59
if g is injective and f is not surjective, then gof will be injective? — Joseph Lopez, Sep 06 '15 at 17:00
If $g$ is injective then $g(f(a))=g(f(b))\implies f(a)=f(b)$. But for $g\circ f$ to be injective we need more:$g(f(a))=g(f(b))\implies a=b$. — drhab, Sep 06 '15 at 17:04
The two questions are entirely distinct. Please don't post multiple unrelated questions in a single thread. Instead post two separate questions. — Asaf Karagila, Sep 06 '15 at 17:06

drhab · Answer 1 · 2015-09-06T17:51:35.263

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.

Set theory and functions

1 Answers1

Linked

Related