1. ## Injective, Surjective, Bijective

Ok I'm up to the next step in set theory and am having trouble determining if set relations are injective, sirjective or bijective.

Say we are matching the members of a set "A" to a set "B"

Injective means that every member of "A" has a unique matching member in "B". You won't get two "A"s pointing to one "B", but you could have a "B" without a matching "A"

Surjective means that every "B" has at least one matching "A" (maybe more than one).

Bijective means both. So we have a perfect 1-1 relationship

Let
A = {1,2,3,4,5}and B = {0,6,7,8,9}
(a) How many functions f: A =>B are there?
(b) How many injective functions f : A => B are there?
(c) How many surjective functions f : A =>B are there?
(d) How many bijective functions f : A =>B such that f(3) = 6 are there?

2. Have you tried any of these?
This is a nice set of problems.
Are you simply asking us for the answers? Or do you need help?
If you need help, show us what you don’t understand. We can deal with that.
But, I hope that none of us simply gives out the answers to prove we can do them

3. Sorry that was rude of me. I will post up my thoughts (I don't really have answers) later tonight. Sorry again.

4. Originally Posted by TTim
Let
A = {1,2,3,4,5}and B = {0,6,7,8,9}

(a) How many functions f: A =>B are there?
(b) How many injective functions f : A => B are there?
(c) How many surjective functions f : A =>B are there?
(d) How many bijective functions f : A =>B such that f(3) = 6 are there?

OK I have looked at this and have no clue how to do it. The functions
f(A) = 0, f(A) = 6, f(A) = 7 etc is all I can come up with.

Are there any procedural ways to find these functions? Any hints, tips appreciated.

5. Part a) is asking, "how many ways can we define $f:A \mapsto B$"?
How many different values can $f(1)$ have?
How many different values can $f(2)$ have?
How many different values can $f(3)$ have?
etc.

6. Originally Posted by Plato
Part a) is asking, "how many ways can we define $f:A \mapsto B$"?
How many different values can $f(1)$ have?
How many different values can $f(2)$ have?
How many different values can $f(3)$ have?
etc.
5? for f(1) to map to B it needs to equal 0,6,7,8or 9? Same with the rest...

Do I have to have every element A map to some element B? I.e. I can't have an A map to something that isn't in B?

7. Originally Posted by TTim
5? for f(1) to map to B it needs to equal 0,6,7,8or 9? Same with the rest...?
Yes. So the answer to a) is $5^5.$
Now, what is different about b)?

8. Originally Posted by Plato
Yes. So the answer to a) is $5^5.$
Now, what is different about b)?
I'm lost already. How is it 5^5? Are you saying
f(1) --> 0
f(2) --> 6
f(3) --> 7
f(4) --> 8
f(5) --> 9

would be a function as would

f(1) --> 0
f(2) --> 6
f(3) --> 7
f(4) --> 9
f(5) --> 8

as well as

f(1) --> 6
f(2) --> 6
f(3) --> 6
f(4) --> 6
f(5) --> 6

as wells as

f(1) --> 6
f(2) --> 6
f(3) --> 6
f(4) --> 6
f(5) --> 0

All of these are mapping from A to B but how can you confirm if a function actually exists that exhibits this mapping property?

9. Originally Posted by TTim
I'm lost already. How is it 5^5? Are you saying
f(1) --> 0
f(2) --> 6
f(3) --> 7
f(4) --> 8
f(5) --> 9

would be a function as would

f(1) --> 0
f(2) --> 6
f(3) --> 7
f(4) --> 9
f(5) --> 8

as well as

f(1) --> 6
f(2) --> 6
f(3) --> 6
f(4) --> 6
f(5) --> 6

as wells as

f(1) --> 6
f(2) --> 6
f(3) --> 6
f(4) --> 6
f(5) --> 0

All of these are mapping from A to B but how can you confirm if a function actually exists that exhibits this mapping property?
it is 5^5 since you have 5 elements in the domain, each of which can map to any of the 5 elements in the codomain. thus, you have 5 choices for each of the 5 inputs, so in all you have 5*5*5*5*5 = 5^5 choices of mappings.

10. Suppose that set A has j elements and set B has k elements.
How many functions are there from A to B? ANSWER $k^j$.
Reason: for each one of the j elements in A we have k choices for its image in B.

How many functions are there from B to A? ANSWER $j^k$.
How many functions are there from A to A? ANSWER $j^j$.
How many functions are there from B to B? ANSWER $k^k$.

11. Originally Posted by Plato
Suppose that set A has j elements and set B has k elements.
How many functions are there from A to B? ANSWER $k^j$.
Reason: for each one of the j elements in A we have k choices for its image in B.

How many functions are there from B to A? ANSWER $j^k$.
How many functions are there from A to A? ANSWER $j^j$.
How many functions are there from B to B? ANSWER $k^k$.
Alright cool, if asked to provide one of the 3125 functions would it be possible to determine that function?

So we have 5^5 functions. Injective and surjective functions will obviously form different subsets of the wholse set of the functions.

Injective functions - Each A will need to have a unique B. Seeing as both sets are the same cardinality for a function to be surjective it must be injective and vice versa?

There will be 5(5x4x3x2x1) = 600 bijective functions? (Clutching at straws here)

12. Originally Posted by TTim
Alright cool, if asked to provide one of the 3125 functions would it be possible to determine that function?
So we have 5^5 functions. Injective and surjective functions will obviously form different subsets of the wholse set of the functions.

Injective functions - Each A will need to have a unique B. Seeing as both sets are the same cardinality for a function to be surjective it must be injective and vice versa?

There will be 5(5x4x3x2x1) = 600 bijective functions? (Clutching at straws here)
NO NO NO
Not all function are surjections, injections or bijections.

In your question the answer to part b is $(5)(4)(3)(2)(1)=120$

13. Originally Posted by Plato
NO NO NO
Not all function are surjections, injections or bijections.

In your question the answer to part b is $(5)(4)(3)(2)(1)=120$
I understand that not all the functions are surjections, injections or bijections. But I fell as if there is something weird happening because both sets have the same number of elements.

Ok...

I'll make some statements about what I think.

1. A and B have the same cardinalty.
2. Because of 1 any function that is injective is surjective. I.e. seeing as every A has a unique matching B this means that every B is mapped onto by one A?
3. surjectivity does not imply injectivity

14. Originally Posted by TTim
1. A and B have the same cardinalty.
2. Because of 1 any function that is injective is surjective. I.e. seeing as every A has a unique matching B this means that every B is mapped onto by one A?
3. surjectivity does not imply injectivity
Those statemants are correct. Let |A| stand for the cardinality of set A.
Then if |A|=|B|=k then there are (k!) bijections from A to B. [That is k factorial].

15. So, to sum up for cardinality:
for a function $f:A \rightarrow B$

if the function is injective then:
the codomain is atleast as big as the domain. $\mid A \mid \leq \mid B \mid$
and the number of possible functions is $\frac{\mid B \mid !}{(\mid B \mid-\mid A \mid)!}$

if the function is surjective then:
the domain is at least as big as the codomain. The opposite of above. $\mid A \mid \geq \mid B \mid$
This means that every element b in the codomain B is an image of at least one element a in the domain A.
and the number of possible functions is $\frac{\mid A \mid !}{(\mid A \mid-\mid B \mid)!}$

and bijective is $\mid A \mid = \mid B \mid$

Something wrong with my probability?

Page 1 of 2 12 Last

,

,

,

,

,

,

,

,

,

,

,

,

,

,

# how many bijective functions are possible between two sets

Click on a term to search for related topics.