Theorem: Bijections & Axiom of Choice

[laminatedevildoll]

If f X---> Y is a function and if there is exactly one function g:Y---> X so that
f o g = id_y, the f is a bijection and g=f^-1. Do I need to use the axiom of choice to prove this theorem?

 

[Hurkyl]

My gut says no. Why do you think so?

 

[laminatedevildoll]

I am not sure. But, is it possible to solve it thru the axiom of choice?

 

[Hurkyl]

Anything you can do without invoking the axiom of choice, you can do with invoking the axiom of choice. I give no guarantees that trying to invoke the axiom of choice would be any easier.

 

[laminatedevildoll]

If I were to prove this theorem without the axiom of choice, then it would just be something like this...?

Theorem: If f X---> Y is a function and if there is exactly one function g:Y---> X so that f o g = id_y, the f is a bijection and g=f^-1

g(x1)=g(x2)
f(g(x1)=f(g(x2)
id_y(x1)=id_y(x2) because f o g = id_y
x1=x2
let x=h(y)
f(x)=f(h(y))=id_y=y, then f^-1 exists

g=g(f o f^-1)
= (g o f) * f^-1 = f^-1

h=(f^-1 o f) = f^-1 * (h o f) = f^-1

 

[Hurkyl]

I can't tell -- your presentation is lacking in detail.

For example, your first four lines could have been:

Suppose x1 and x2 are elements of Y such that g(x1) = g(x2). Then,
f(g(x1)) = f(g(x2))
id_y(x1) = id_y(x2) (since fog = id_y)
x1 = x2
Therefore, g(x1) = g(x2) implies x1 = x2, and g is injective.

It still contains all of the same rigor, but it actually let's people know what you're trying to do! It says what types x1 and x2 have, it states your hypotheses, and states your conclusion.


Because your presentation is lacking those details, I can't even figure out what the rest of your proof is trying to do. What is h? How did you prove f^-1 exists? I -think- I have an idea what the last 2 or 3 lines are doing, but if I'm right, you're proving the converse of what you're supposed to prove!

 

[laminatedevildoll]

Maybe h was not supposed to be there. I was trying to prove something in an earlier proof that g=h=f^-1.

In any case, in those last lines, I was trying to prove the converse of what I am supposed to prove, but I get mixed up. I am not sure if this is correct. Do you have any advice of proving inverse functions properly?

To prove that f is onto. For every value of y, we have to find a value of x so that y=f(x)

Define x=g(y)

To prove that y=f(x)

f(x)=f(g(y))= (f o g)(y) = id_y(y)=y

To prove that g=f^-1

g = g o id_y
= g o (f o f^-1)
= (g o f ) o f^-1
= id_x o f^-1
= f^-1

 

[Hurkyl]

g = g o id_y
= g o (f o f^-1)

Can't do that -- you don't know that f^-1 exists yet! You've only shown that f is surjective, you haven't shown it to be injective (and thus bijective).

The uniqueness of g will probably come into play in that step, since you haven't used it yet!

 

[laminatedevildoll]

f is injective.
f(x1)=f(x2)
x1=x2
This function is one-to-one and on-to so it must be bijective. Therefore f^-1 is a function.

How do I prove that f^-1 exist?

y=f(x) if x=f^-1(y)
Hence f(f^-1(y))=f(x)=y and f^-1(f(x))=f^-1(y) = x

 

[matt grime]

Here's a proof without the AC, on the assumption that there is at least one right inverse to f.

Let us show that f not bijective implies that f does not have exactly one right inverse.

Obivously if f fails to be surjective then there are no right inverses, contradicting the assumption that there was at least one, hence f is surjective.

Now suppose that f fails to be injective, then there are two elements u and v in X such that f(u)=f(v) - but we are only taking two elements and thus not invoking the axioms of choice. Given g a right inverse (ie the one we know must exist) we know that f(u) is an element of Y and is thus in the domain of g, thus we may replace u with gf(u) and assume that u is in the range of g. (Note the sidestep of any axiom of choice issue since we are stating explicitly what u is to be replaced by).

Thus we have elements u,v in X and w in Y such that f(u)=f(v)=y and g(y)=u.

Define h by h(t)=g(t) for t=/=y , and h(y)=v. Then h=/=g, but fg=fh=Id_Y.

I don't see that I've made any *infinite* set of choices without proper definition. Which is reasonable since it is only to do with injections. If it were surjections and left inverses then it may be a whole different matter.

Thus not injective implies more than one inverse. Or injective implies at most one inverse, and we are done as then exactly one inverse implies bijective.