Composition of functions

  • #1

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.
 
Last edited by a moderator:

Answers and Replies

  • #2
14,386
11,699

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.
 
Last edited by a moderator:
  • #3
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 cant be equal, otherwise it is possible to have f(x) = f(y). sorry if i wasnt clear about that.
 
  • #4
14,386
11,699
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 cant 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.
 
Last edited:

Related Threads on Composition of functions

  • Last Post
Replies
3
Views
488
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
14
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
9
Views
787
  • Last Post
Replies
1
Views
3K
Top