Year 12s: what will be the first way you research your future options? >>

Amalgamation of proof techniques for bijectivity

To prove bijectivity, you usually prove that the function is injective and surjective, so I was wondering if the combined experience on TSR here could share a few different techniques for proving injectivity and surjectivity and whether they only work in special cases or not. For starters, I'm familiar with:

Injectivity:

1. The graphical method of sketching the graph of the function and using the horizontal line test to determine whether or not it's injective. Only suitable for some of the more simple functions and might be time consuming. But it's generally a reliable method. Not very suitable for functions of the form

f(x,y)

though.

2. Showing that the function

f(x)

is either strictly decreasing or increasing over its domain, that is

f'(x) < 0, \forall x \in \mathbb{D}

f'(x) > 0, \forall x \in \mathbb{D}

where

\mathbb{D}

is the domain of the function

f(x)

. Not really suitable for functions of the form

f(x,y)

either. Or at least, in my experience.

3. Proving that

f(x) = f(y) \iff x=y

, this works nicely with functions of the form

f(x,y)

as you can generally form simultaneous equations and show the implication. Can be a little time-consuming depending on the functions, sometimes using the derivative to show it's strictly increasing or decreasing works faster for single-variable functions, although that's usually based on the domain of the function.

4. I've run out, does anybody else have any other techniques to share?

Surjectivity:

I actually have no clue as to how to go about doing this, does anybody have any explanations? :smile:

Reply 1

President Snow

To prove surjectivity, you wish to show that for any arbitrary b, there exists a such that f(a)=b.

So, to show that some function is NOT surjective, find some b member of codomain for which there does not exist an a member of codomain such that f(a)=b. For example, given f(x)=x^2, there does not exist an a such that f(x)=-1, therefore f is not surjective.

To show that something is surjective, you need to find an arbitrary a within the domain which gives an arbitrary b within the codomain.

Consider g : R --> R, g(x)=4x.

Consider arbitrary b is a member of R [codomain]. Then there exists a=(1/4)b is a member of R [domain] such that g(a)=b for all b member of codomain. Thus g is surjective. Note that g would not be surjective if we let g : Z --> R or g : Z --> Z. Can you see why?

Also, since a function f has a left inverse if and only if f is injective, and f has a right inverse if and only if f is surjective, then it is equivalent to prove for injectivity that a left inverse exists for f, and for surjectivity that a right inverse exists for a. Not that the inverses may not be unique, all that matters is whether or not one exists.

If both exist, and the function f has both a left and right inverse, then f is bijective [and if it's bijective then it has both a left and right inverse - once again it's an iff relation]. Further, this pair of left and right inverses will happen to always be equal, and will also be unique. We call this "the" inverse, often denoted f^-1.

In order to prove the existence of such inverses, find function g, left or right compose it as necessary with the original map f, and show you get the identity map.

Now one particular special case. When both the domain and codomain of a function f are both equal and finite, f is either bijective, or neither injective nor surjective [draw out some little pictures to figure out why]. Therefore, in such a scenario, if you can prove either injectivity, or surjectivity, then the function must be bijective. Alternatively, if you can prove that the function is not either of injective or surjective, then it is not the other one either. But only when the domain and codomain are equal AND finite.

(edited 9 years ago)

Reply 2

Zacken

So considering g: R -> R, g(x) = 4x.

There exists an arbitrary

b \in \mathbb{R}

such that for some

a \in \mathbb{R}

, we have that

4a = b \Rightarrow a = \frac{b}{4}

.

The codomain of g is

\mathbb{R}

and since

b = 4a, \forall a \in \mathbb{R}

we can see that

b \in \mathbb{R}

and hence the range and the codomain will be equal to each other, implying surjectivity?

However, if we let the domain of g be

\mathbb{Z}

then the values that b will take (its range) is

4k, \forall k \in \mathbb{Z}

whereas its codomain will be R, that is, there will be some values in the codomain that won't be 'hit' by the function? Example, 4.5 is part of the codomain of g (R) but not in the range of g, since b will never equal 4.5 if a can only take on integer values? :smile: