Prove f is a Bijection - Need Help

[jmazurek]

Need help... If f(f(x))=x then prove f is a bijection.

 

[homology]

Need help... If f(f(x))=x then prove f is a bijection.

Let's say that f maps some set S into itself. First prove surjectivity, so given any x in S show that there exists y such that f(y)=x, that's easy, y=f(x). So f is surjective. Next, prove injectivity:

let x not equal to y be elements of S. I'll use != for non-equality. So x!=y. but f(f(x))=x and f(f(y))=y so f(f(x))!=f(f(y)). which implies that f(x)!=f(y). Do you see why? if f(x)=f(y) then x and y are mapped to the same point but since f(f(x))!=f(f(y)) this means that this one point is mapped to two points in the image so f would not be a function at all.

Cheers,

Kevin

 

[Galileo]

A function is a bijection if and only if it has an inverse. f is equal to it's own inverse since f(f(x))=x, so f has an inverse and so it is bijective.

 

[Ethereal]

This is a different question from the above, but since I don't feel like starting a new topic, I'll post it here:

I read somewhere that the reals in the interval [0,1] can be put into a bijection with the \Re \geq 0 . The bijective function in question is \frac{x}{1-x}

How can it be proven that the function is bijective?

I (naively) thought of the following:

Suppose there exist a nonnegative real number r. Then
\frac{x}{1-x} = r which can be expressed in terms of r to be
x = \frac{r}{1+r}

Now it must be shown that 0 \leq \frac{r}{1+r} \leq 1

Suppose \frac{r}{1+r} < 0Then r < 0 which contradicts the definition of r. Suppose \frac{r}{1+r} > 1, then r > 1+r, which means 1 < 0, which is a contradiction. The function can be shown to be injective by noting that its derivative \frac{1}{(1-x)^2} is always positive for all values of x and hence the function is strictly increasing and hence injective.

But the limitations of my informal "proof" are that it does not show that the function is surjective. How can this be shown? If there is anything with the "proof" above, please point it out; I haven't studied maths formally yet.

 

[matt grime]

you mean the interval [0,1) and you appear to have shown surjectivity, or you would if you phrased it as: let r be any real number, r=>0, then there is an x in [0,1) such that \frac{x}{1-x}=r

 

[Ethereal]

you mean the interval [0,1) and you appear to have shown surjectivity, or you would if you phrased it as: let r be any real number, r=>0, then there is an x in [0,1) such that \frac{x}{1-x}=r

Oh, sorry I meant [0,1). Is there something lacking in the proof? And also, can the reals in [0,1) be put into 1 to 1 correspondence with the rest of the Reals?

 

[matt grime]

no, there is nothing lacking. you've shown it is a surjection, though you didn't realize, and yes, your proof it is injective is perfectly good.

the reals in any non-empty interval may be put in bijection with R, however the bijection has no need to be continuous, and in this case can't be, for high-faluting reasons that needn't worry us.

here are several tricks for doing this:

tan is a good function, it takes the interval (-pi/2,pi/2) bijectively to R

any two open intervals (a,b) (c,d) may be mapped bijectively between themselves simply by "stretching" (can't be bothered to type out the full function, but clearly if you have two intervals of the same length (b-a = d-c) then simply adding c-a to every number is a bijection between them, and (0,1) maps bijectively to (0,k) for all k by multiplication by k).

you can put the interval (0,1) in bijection with [0,1) too.

pick an infinite, increasing sequence in [0,1) starting with 0, say 0, 1/2, 2/3, 3/4, 4/5 etc, and define a map from [0,1) to (0,1) by x maps to x if x not in the sequence, and if x is in the sequence send it to the next element in the sequence.


EDIT: if you want to show there is a bijection between any two sets S and T it suffices to show there is an injection from S to T and an injection from T to S