I'm aware that there's a simple proof by contradiction for this, mainly:

Assume $x_1 \neq x_2$. If $f(x_1)=f(x_2)$, then $g(f(x_1))=g(f(x_2))$ which, since $g \circ f$ is injective, implies $x_1=x_2$. By contradiction, $f$ is injective.

I wanted to see if the method of direct proof I used is valid. Could someone just skim over it and alert me if there's any gaps? Here's the proof I came up with:

$$\exists ! x \in D(g \circ f) = A (\forall w \in R(g \circ f) \subseteq C)$$ $$\implies \exists ! y \in R(f) \subseteq B (\forall w \in R(g \circ f) \subseteq C)$$ $$\implies \exists ! x \in D(g \circ f)=D(f)=A (\forall y \in R(f) \subseteq B)$$ $$\implies \exists ! x \in A (\forall y \in R(f) \subseteq B)$$

Hence, $f$ is injective.

Rewritten in words:

Because $f$ is injective, there's a unique $x$ for each $g(f(x))\in C$. Since $g \circ f$ is a function from $R(f)$ onto $C$, this implies there's a unique $y\in R(f)$ for each $g(f(x))\in C$. Since there exists a unique $x$ and unique $y$ for each $g(f(x))\in C$, then there must exist a unique $x$ for each $y \in R(f)$, hence making $f$ injective.

To me, I believe the second implication I made, assuming there exits a unique $x$ for every $y$ just because there existed a unique $y$ for each $w$, seems like a large step -- so I'm really doubting if that's a valid move.

  • $\begingroup$ This might be a duplicate of math.stackexchange.com/questions/1274914/… $\endgroup$ – jibounet Jan 8 '17 at 14:38
  • $\begingroup$ Can you tell me in words the meaning of $\exists ! x \in D(g \circ f) = A (\forall w \in R(g \circ f) \subseteq C)$? I have a hard time making sense of it. $\endgroup$ – Momo Jan 8 '17 at 15:18
  • $\begingroup$ @Momo I was trying to express how $g \circ f$ was injective by stating that there's only one $x \in A$ such that $g(f(x))=w$ (I think I should have it the other way around actually, that is, $\forall w \dots \exists ! x \dots$), and I mentioned that $R(g \circ f) \subseteq C$ because $g \circ f$ isn't surjective, so it's not necessarily the case that $R(g \circ f) = C$. $\endgroup$ – Drew Jan 8 '17 at 16:37
  • $\begingroup$ @Momo I just edited the original post hopefully clarifying everything $\endgroup$ – Drew Jan 8 '17 at 16:51
  • $\begingroup$ From what I understand, I believe that what you intend to write for the definition of injectivity of $g\circ f$ is $$\forall w\in R(g\circ f)\subseteq C \ \exists! x\in D(g\circ f)=A \text{ such that } g\circ f(x)=w$$ which is quite different from what you actually wrote. $\endgroup$ – Momo Jan 8 '17 at 18:32

For the direct proof, why not just:

$$f(x)=f(y)\Longrightarrow g(f(x))=g(f(y))\Longrightarrow g\circ f(x)=g\circ f(y)\Longrightarrow x=y$$

So $f$ is injective.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.