A function f is said to be one-to-one, or an injection, if and only if f(a) = f(b) implies that a = b for all a and b in the domain of f. Note that a function f is one-to-one if and only if f(a) ≠ f(b) whenever a ≠ b. This way of expressing that f is one-to-one is obtained by taking the contrapositive of the implication in the definition. A function f from A to B is called onto, or a surjection, if and only if for every element b ∈ B there is an element a ∈ A with f(a) = b. A function f is onto if ∀y∃x( f(x) = y), where the domain for x is the domain of the function and the domain for y is the codomain of the function Now consider that f is a function from A to B, where A and B are finite sets with |A| = |B|. Show that f is one-to-one if and only if it is onto.
The Answer to the Question
is below this banner.
Can't find a solution anywhere?
NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?
Get the Answers Now!You will get a detailed answer to your question or assignment in the shortest time possible.
Here's the Solution to this Question
We have next statement: for finite sets A and B such that |A| = |B| (f:A->B is one to one)(f:A->B is onto)
((f:A->B is one to one)(f:A->B is onto)) = ((f:A->B is one to one)(f:A->B is onto))((f:A->B is onto)(f:A->B is one to one))
So, to prove the given statement we will prove two statements:
1) ((f:A->B is one to one)(f:A->B is onto))
2) ((f:A->B is onto)(f:A->B is one to one))
Letter b means b B, other letters A
1) Let's suppose that (f:A->B is one to one)(f:A->B is not onto) (. But |A| = |B|, so we came to the contradiction, which means our assumption is false, so (f:A->B is onto). The first statement is proven
2) Let's suppose that (f:A->B is onto)(f:A->B is not one to one) (. But |A| = |B|, so we came to the contradiction, which means our assumption is false, so (f:A->B is one to one). The second statement is proven
The statement has been proven