# Theorem: Bijections & Axiom of Choice

• laminatedevildoll
In summary, 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.
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?

My gut says no. Why do you think so?

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

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.

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

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!

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

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!

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

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.

Last edited:

## What is a bijection?

A bijection is a mathematical function that establishes a one-to-one correspondence between the elements of two sets. This means that every element in one set is paired with exactly one element in the other set, and vice versa. In other words, there are no repeated or missing elements in either set.

## What is the Axiom of Choice?

The Axiom of Choice is a fundamental principle in set theory that asserts the existence of a choice function for any collection of non-empty sets. This means that given a set of sets, there exists a function that can select one element from each set in the collection. It is often used in proofs involving infinite sets.

## How are bijections and the Axiom of Choice related?

Bijections and the Axiom of Choice are closely related because the Axiom of Choice can be used to prove the existence of a bijection between two sets. This is because the Axiom of Choice allows us to select one element from each set, which is necessary for establishing a one-to-one correspondence between the two sets.

## What is the importance of bijections and the Axiom of Choice in mathematics?

Bijections and the Axiom of Choice are important concepts in mathematics because they allow us to compare and establish relationships between different sets. Bijections help us understand the size and structure of sets, while the Axiom of Choice provides a powerful tool for proving the existence of certain mathematical objects.

## Are there any controversies surrounding the Axiom of Choice?

Yes, there have been some controversies surrounding the Axiom of Choice in mathematics. Some mathematicians argue that the Axiom of Choice can lead to counterintuitive results and paradoxes, while others believe that it is a necessary and useful tool in mathematical reasoning. The debate is ongoing and has led to the development of alternative set theories, such as constructive and intuitionistic mathematics.

• Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
5
Views
681
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
6
Views
972
• Calculus and Beyond Homework Help
Replies
5
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
411
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K