Respuesta :
Answer with Step-by-step explanation:
We are given that a function
[tex]f:A\rightarrow B[/tex]
A and B are finite sets with
[tex]\mid A\mid=\mid B\mid [/tex]
We have to show that f is one- to- one if and only if it onto.
Let function is one -to -one
Cardinality of A=Cardinality of B
If cardinality of set A is greater than or equal to B then function is onto.
We have cardinality of A is equal to cardinality of set B.
Hence, function is onto.
Conversely,
Suppose function is onto
Cardinality of A =Cardinality of B
if cardinality of A is equal or less than cardinality of B then function is on-to-one.
We have cardinality of A =Cardinality of B
Hence, function is one-to-one.
You can use the fact that for proving "if and only if" type of statements, you have to prove that both side's implication to each other side.
The proof is given below and it is shown that given function f for given sets is one-to-one if and only if it is onto.
What are one-to-one functions?
Those relations in which one input is linked to one output and one output is linked to one input (input is value from domain and output is value from range), are called one-to-one functions.
What are onto functions?
If the given set B has all elements linked with the input set by the function f, then that function is called function from set A onto B (all elements occupied).
Thus,
[tex]\rm If \: y \in B; \exists \: x \in A : f(x) = y[/tex] (if f: A → B and onto)
Using above definitions and proving the statement given
We've to prove that if f: A → B and |A| = |B| = finite number (|A| means count of elements in A), then f is one-to-one if and only if f is onto.
For proving if and only if relationship, we have to prove it from both the sides
- Part 1: Let f is one-to-one, then proving that f is onto
f is one-to-one, thus each element of A is linked to unique element in output and that output cannot have two or more inputs linked to it. Thus, all n elements of A are linked with unique and different outputs. Thus, at least n different outputs should be available. Since |B| = n too, thus, all n elements of B are linked by inputs by the function f. Thus, f is onto function as it uses all elements of B.
- Part 2: Let f is onto, then proving that f is one-to-one
Since |A| = |B| = n (finite constant)
And f is a function, thus each input can map to at max only one output. Since f is onto, all n elements of B has to be used. Since there are n inputs and they can get all elements of B only if they link to different element of B than each other, otherwise, n elements input will link to n-1 or less outputs and f won't be declared onto(which it is as assumed).
Thus, if f is onto given, and |A| = |B| ,then f needs to be one-to-one.
Thus,
It is shown that the function is one-to-one if and only if f is onto.
Learn more about one-to-one and onto functions here:
https://brainly.com/question/12860292
