Prove: A mapping f:S->T is bijective if and only if it has an inverse?

1. Jun 18, 2004

mruncleramos

Can a mapping from f:S->T associate an element of s into several elements of T? Also, how do you prove: A mapping f:S->T is bijective if and only if it has an inverse?

2. Jun 18, 2004

HallsofIvy

Staff Emeritus
No. "mapping" is another word for "function". Part of the definition of function is that f(x) be a single value.

f:S-> T is bijective iplies f has an inverse:

Let y be any member of T. Since f is bijective it is both one-to-one (injective) and onto (surjective). Since f is surjective, there exist at least one member of S, x, such that f(x)= y. Since f is injective, there is only one such. Define g: T->S by g(y)= x.
Now show that that is a function and is the inverse of f.

f has an inverse implies f is bijective.

i) for any y in T, let x= f-1(y). Then, by definition of inverse, f(x)= y so f is surjective.

ii) suppose f(x1)= f(x2). Applying f-1 to both sides of the equation f-1(f(x1)= f-1(x2)
x1= x2
so f is injective.

Since f is both injective and surjective, it is bijective.

3. Jun 19, 2004

kioria

To take things into an account, I remember in discrete maths - a bit like computational mathematics or rather, it is computational mathematics - we define set |R| = |{1,1,1,1}| as 4. As there are four items in the set. Now, in the other extreme, let S = {1}, then |S| = |{1}| = 1. So in effect the sets R and S have different properties.

One other thing is that, once again, in computer science, R = {1,1,1,1} and S = {1} are two totally different sets. Lets map (+2) to both sides and find the total sum of all the elements in the sets, i.e., {sum (map (+2) R)} and {sum (map (+2) S)}.

sum (map (+2) R) = sum {3,3,3,3} = 12
sum (map (+2) S) = sum {1} = 1 /= 12 = sum (map (+2) R)
and as function applied two both sets are equal, R and S are not equal.

However, answering your question, even in computer science the values of each element after mapping only takes 1 value from the image. i.e., notice that (map (+2) R) = {3,3,3,3}. So 1 -> 3 by mapping. And each element valued 1, goes to exactly one value in the image of f, that is 3.

But as I said, this is in computer science and most of the computer applications - although duplicates are considered nasty in some cases.

Last edited: Jun 19, 2004
4. Jun 19, 2004

matt grime

The set {1,1,1,1} contains only one element. you aren't allowed to repeat elements in a set.

5. Jun 21, 2004

kioria

I meant cardinalities... yes my wordings were pretty poor.