Proving the existence of a bijection.

In summary, a property has been brought up where, given two sets X and Y and functions f and g mapping X into Y, with f being injective and g being surjective, there exists a bijection from X into Y. This is believed to be true due to the fact that bijections create an equivalence relation with respect to cardinality and injections and surjections imply that X and Y have equal cardinality. However, a formal proof for this proposition is currently unavailable.
  • #1
shoescreen
15
0
Hello all,

I've recently used a property that seems perfectly valid, yet upon further scrutiny I could not come up with a way to prove it. Here is what I would like some help on.

Given two sets X and Y and functions f and g mapping X into Y, with the property that f is injective and g is surjective, prove there exists a bijection from X into Y.

I believe this has to be true for the following reason. Since bijections create an equivalence relation wrt cardinality, we can think of injections as saying Y is no smaller than X, and surjections as saying that Y is no bigger than X. Together we have that Y is is the same size as X, and hence they are equal cardinality. Therefore there exists a bijection between the two.

However, this heuristic argument aside, I can not think of a proof of this proposition.
 
Physics news on Phys.org

FAQ: Proving the existence of a bijection.

How can you prove the existence of a bijection?

To prove the existence of a bijection, you need to show that there is a one-to-one and onto mapping between two sets. This means that every element in the first set is paired with exactly one element in the second set, and every element in the second set has at least one pairing in the first set.

What is the importance of proving the existence of a bijection?

Proving the existence of a bijection is important because it guarantees that there is a perfect correspondence between the elements of two sets. This is useful in various mathematical and scientific fields, such as graph theory, topology, and cryptography.

What are the common methods used to prove the existence of a bijection?

There are several methods that can be used to prove the existence of a bijection, such as the pigeonhole principle, constructing a specific function that satisfies the bijection criteria, and using mathematical induction.

Can the existence of a bijection be proven for infinite sets?

Yes, the existence of a bijection can be proven for infinite sets. In fact, proving the existence of a bijection for infinite sets can be more complex and may require the use of advanced mathematical concepts, such as cardinality and transfinite numbers.

What is the difference between a bijection and a one-to-one correspondence?

A bijection is a type of one-to-one correspondence, but not all one-to-one correspondences are bijections. A one-to-one correspondence simply means that there is a unique pairing between elements of two sets, while a bijection also requires that every element has a pairing in the other set. In other words, a bijection is a stricter form of one-to-one correspondence.

Similar threads

I Negation of statement involving cardinalities
Replies
10
Views
632
I Is √9x a Bijection from N to R?
Replies
7
Views
1K
MHB Proving Set Equivalence with Set Differences?
Replies
9
Views
2K
Does there exist a surjection from the natural numbers to the reals?
Replies
4
Views
3K
MHB How can we show that the inverse is bijective?
Replies
14
Views
3K
I Does the definition of cardinality assume distinguishability?
Replies
9
Views
1K
MHB Prove that the operations are well-defined
Replies
1
Views
2K
MHB Show that there exists a bijection
Replies
8
Views
2K
MHB Prove |X| = |Y| When X\Y and Y\X are Equipotent Sets
Replies
3
Views
3K
MHB Show $\bigcup A$ is Finite When $A$ is a Finite Set of Finite Sets
Replies
6
Views
2K

Hot Threads

Recent Insights

Back
Top