Injective & Surjective Functions

[tlkieu]

Just wondering if anyone could help me get in the right direction with these questions and/or point me to some material that will help me better understand how to approach these questions

In what follows I will denote the identity function; i.e. I(x) = x for all x ∈ R.
(a) Show that a function f is surjective if and only if there exists a function g such that f ◦ g = I.
(b) Show that a function f is injective if and only if there exists a function h such that h ◦ f = I.
(c) Suppose f ◦ g = I and h ◦ f = I. Show that g = h.

Okay so from what I understand for f ◦ g = I, this translates to f(g(x)) = I and for a function to be surjective it means that every element y in Y has element x in X for f(x). So would part (a) involve showing that f is a one-to-one function. I guess my weak point when it comes to these type of questions is setting out logical steps on how to prove, is there a certain system of steps that we follow? Any help would be greatly appreciated!

 

[nuuskur]

I think you mean part b involves showing some function is injective.

Injectivity, formally, means that for any elements $x,y$ in the domain: if $f(x) = f(y)$, then $x=y$. I'll address part b for now:
You need to prove two implications: from left to right and from right to left. [if that is ambiguous, let me know, but it should be elementary].
To be more precise, let $f: X\to Y$, where $X,Y\subseteq\mathbb{R}$, be injective. We must find $g:Y\to X$ such that for every $y\in Y$ we have $(fg)(y):=f(g(y)) = y$. How should we define $g(y)$ for a given $y$ and why can we do that?
For instance, if we look at $f(x) := x+1$, this is clearly injective. How do we define $g$ such that $f(g(x+1))=x+1$? Say, we defined $g(y) = y-1$, then you can verify this $g$ does what we want it to, but what allows us to define $g$ this way?

 

[tlkieu]

I think you mean part b involves showing some function is injective.

Injectivity, formally, means that for any elements $x,y$ in the domain: if $f(x) = f(y)$, then $x=y$. I'll address part b for now:
You need to prove two implications: from left to right and from right to left. [if that is ambiguous, let me know, but it should be elementary].
To be more precise, let $f: X\to Y$, where $X,Y\subseteq\mathbb{R}$, be injective. We must find $g:Y\to X$ such that for every $y\in Y$ we have $(fg)(y):=f(g(y)) = y$. How should we define $g(y)$ for a given $y$ and why can we do that?
For instance, if we look at $f(x) := x+1$, this is clearly injective. How do we define $g$ such that $f(g(x+1))=x+1$? Say, we defined $g(y) = y-1$, then you can verify this $g$ does what we want it to, but what allows us to define $g$ this way?

Hmm I think I kind of get the idea. Do you happen to know where I could potentially read more about this topic that uses examples like you've provided? I think I generally understand theories and proofs better when looking at a specific example then taking from that to understand the proof/theory itself.

 

[nuuskur]

Some googling and I found Karel Hrbacek & Thomas Jech, http://rads.stackoverflow.com/amzn/click/0824779150 [Broken]
which seems to be directed at undergraduate level studies. It is a rigorous text, so I'd recommend it.
What can tell you, though, is you need a solid understanding of propositional calculus and for introductory logic studies, I would definitely recommend P. Suppes Introduction to logic available legitimately free of charge. It does address set theory, which I'd totally forgotten about! heh :)

 

[tlkieu]

Any book that addresses elementary set theory. Unfortunately, I am not familiar with relevant literature in English.

Okay, thank you! Also in regards to (a) - would it be looking somewhat like this?

So if we suppose that f is a surjection. We define a function g : Y → X as follows.
Let y ∈ Y , and since f is a surjection, there exists x ∈ X (not necessarily unique) such that f(x) = y.
Now we choose one such x and call it xy and set g(y) = xy.
For any y ∈ Y , we have (f ◦ g)(y) = f(g(y)) = f(xy ) = y = IY (y). So we can conclude that f ◦ g = IY.

Suppose there exists g : Y → X such that f ◦ g = IY. If we let y ∈ Y, then g(y) ∈ X and f(g(y)) = (f ◦ g)(y) = IY (y) = y.
We conclude that f is a surjection.

Am I on the right track here? I've tried to make the steps logical, but not 100% if I'm heading in the right direction.

 

[nuuskur]

The first part is ok, at least it seems ok to me.

For the second part we need $f$ to be a surjection, therefore we need to show that for any $y\in Y$, there exists an $x\in X$ s.t $f(x)=y$. You can express this shortly by: $Y\subseteq f(X)$ (since the converse containment is trivial). Let $y\in Y$, then by assumption $y = (fg)(y)$ and $f(g(y)) = y$ i.e our $x$ is precisely $g(y)$. You did the same thing in the opposite direction, so yes, everything is A ok with part a :)

 

[tlkieu]

The first part is ok, at least it seems ok to me.

For the second part we need $f$ to be a surjection, therefore we need to show that for any $y\in Y$, there exists an $x\in X$ s.t $f(x)=y$. You can express this shortly by: $Y\subseteq f(X)$ (since the converse containment is trivial). Let $y\in Y$, then by assumption $y = (fg)(y)$ and $f(g(y)) = y$ i.e our $x$ is precisely $g(y)$. You did the same thing in the opposite direction, so yes, everything is A ok with part a :)

Thank you! I'm still trying to rap my head around everything, but will attempt part (b).

 

[PeroK]

So if we suppose that f is a surjection. We define a function g : Y → X as follows.
Let y ∈ Y , and since f is a surjection, there exists x ∈ X (not necessarily unique) such that f(x) = y.
Now we choose one such x and call it xy and set g(y) = xy.
For any y ∈ Y , we have (f ◦ g)(y) = f(g(y)) = f(xy ) = y = IY (y). So we can conclude that f ◦ g = IY.

Yes, this is correct.

Suppose there exists g : Y → X such that f ◦ g = IY. If we let y ∈ Y, then g(y) ∈ X and f(g(y)) = (f ◦ g)(y) = IY (y) = y.
We conclude that f is a surjection.

Good.

Am I on the right track here? I've tried to make the steps logical, but not 100% if I'm heading in the right direction.

Very much on the right track.

 

[tlkieu]

Yes, this is correct.



Good.



Very much on the right track.

Thank you! I'm a little stumped on part (b) and (c), so from what I understand injection means we have to show how it is a one-to-one function that is h(f(x)) has one value of x=X for every y=Y?

 

[PeroK]

Thank you! I'm a little stumped on part (b) and (c), so from what I understand injection means we have to show how it is a one-to-one function that is h(f(x)) has one value of x=X for every y=Y?

Part c) should be the simplest of the three. Why can't you even get started? You can always start by stating what you have to prove. For example, for part a) it was:

We need to show that:

1) if $f: X \rightarrow Y$ is surjective, then we can find $g: Y \rightarrow X$ such that $f \circ g = I_Y$
2) if there exists $g: Y \rightarrow X$ such that $f \circ g = I_Y$, then $f: X \rightarrow Y$ is surjective.

Then, you can write the definition of these things:

$f: X \rightarrow Y$ is surjective means that $\forall y \in Y, \ \exists x \in X$ such that $f(x) = y$

And:

$f \circ g = I_Y$ means that $\forall y \in Y, \ f(g(y)) = y$

Try doing this for b) and c) - c) should be easier.