Composition of functions

[UOAMCBURGER]

Homework Statement

Let A, B, C be finite sets such that A and B have the same number of elements, that is, |A| = |B|. Let f : A → B and g : B → C be functions.
(a) Suppose f is one-to-one. Show that f is onto.
(b) Suppose g ◦ f is one-to-one. Show that g is one-to-one.

Homework Equations

The Attempt at a Solution

We can let n = |A| = |B|
Since f is injective, we know that for all b ∈ B there exists at most ONE a ∈ A, such that f(a)=b right? that is, given x,y ∈ A f(x) != f(y) => x != y right? I can just see this from the definition, not sure how useful it is or where to go from here.

 

[fresh_42]

Homework Statement

Let A, B, C be finite sets such that A and B have the same number of elements, that is, |A| = |B|. Let f : A → B and g : B → C be functions.
(a) Suppose f is one-to-one. Show that f is onto.
(b) Suppose g ◦ f is one-to-one. Show that g is one-to-one.

Homework Equations

The Attempt at a Solution

We can let n = |A| = |B|
Since f is injective, we know that for all b ∈ B there exists at most ONE a ∈ A, such that f(a)=b right?

Yes.

... that is, given x,y ∈ A f(x) != f(y) => x != y right?

No. It means $x\neq y \Rightarrow f(x) \neq f(y)$ or $f(x)=f(y) \Rightarrow x=y$

... I can just see this from the definition, not sure how useful it is or where to go from here.

You have to use the finiteness of your sets. Injective means that all elements of $A$ are sent to different elements in $B$. Now you have to show, that you get all of them.

 

[UOAMCBURGER]

Yes.No. It means $x\neq y \Rightarrow f(x) \neq f(y)$ or $f(x)=f(y) \Rightarrow x=y$
You have to use the finiteness of your sets. Injective means that all elements of $A$ are sent to different elements in $B$. Now you have to show, that you get all of them.

I think my definition was correct, I meant given two elements in the domain (hence x,y ∈ A) then f(x) != f(y) (meaning that no two elements in A can map to the same element in the codomain, B) .. the definition of injective functions. the x !=y just means that the two elements in the domain can't be equal, otherwise it is possible to have f(x) = f(y). sorry if i wasnt clear about that.

 

[fresh_42]

I think my definition was correct,

No, it was not.

... I meant given two elements in the domain (hence x,y ∈ A)...

They are only different if you add $x\neq y$

then f(x) != f(y) (meaning that no two elements in A can map to the same element in the codomain, B)

Yes, but that is not what you wrote. No two elements map onto the same element means: If two elements ($x, y$) happen to map to the same element ($f(x)=f(y)$), then they are equal ($x=y$):
$$
f \text{ is injective } \Longleftrightarrow (f(x)=f(y) \Longrightarrow x=y) \Longleftrightarrow (x \neq y \Longrightarrow f(x)\neq f(y))
$$
However, you wrote

that is, given x,y ∈ A f(x) != f(y) => x != y right?

which is the wrong direction and means that $f$ is well-defined: Different image points cannot result from one origin.

.. the definition of injective functions. the x !=y just means that the two elements in the domain can't be equal, otherwise it is possible to have f(x) = f(y). sorry if i wasnt clear about that.

I like the following mnemonic: Put your arms in front of you and let the hands be $f$. Now make them touch at the wrist. This is not allowed for any function to be well-defined. Let them touch at the finger tips instead, then this is not allowed for injectivity.