Solution to A function f is said to be one-to-one, or an injection, if and only if … - Sikademy
Author Image

Archangel Macsika

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)\leftrightarrow(f:A->B is onto)

((f:A->B is one to one)\leftrightarrow(f:A->B is onto)) = ((f:A->B is one to one)\to(f:A->B is onto))\land((f:A->B is onto)\to(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)\to(f:A->B is onto))

2) ((f:A->B is onto)\to(f:A->B is one to one))


Letter b means b \in B, other letters \isin A

1) Let's suppose that (f:A->B is one to one)\land(f:A->B is not onto) \implies(f(a)\not=f(c)\leftrightarrow a\not=c)\land(\exists b\forall a(f(a) \not=b))\to |A| < |B|. 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)\land(f:A->B is not one to one) \implies(∀b∃a( f(a) = b)\land(\exists a,c:(f(a)=f(c))\land(a \not=b))\to |A| > |B|. 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

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-987-qpid-842