1 Definitions and basic properties

A bijective map is a function that matches each element of its target set with exactly one element of its source set. In other words, it is both injective and surjective. Such maps are central in mathematics because they identify two sets as having the same size in a precise sense and allow information to be transferred back and forth without loss.

1.1 Function, domain, and codomain

A function assigns each element of a domain to a single element of a codomain. The domain is the set of inputs, while the codomain is the set in which outputs are considered to lie. A function may fail to hit some elements of the codomain, and it may also send different inputs to the same output.

1.2 Injective and surjective functions

An injective function, or one-to-one function, never assigns the same output to two different inputs. A surjective function, or onto function, reaches every element of the codomain at least once. These two properties address different kinds of completeness: injectivity prevents overlap, while surjectivity prevents omission.

1.3 Definition of bijection

A bijection is a function that is both injective and surjective. For each element of the codomain, there is exactly one corresponding element in the domain. This exact matching gives a bijection its defining feature: perfect pairing between the two sets.

1.4 One-to-one correspondence

A bijection is often described as a one-to-one correspondence. This phrase emphasizes that each object on one side is paired with precisely one object on the other side, with no leftovers in either set. Such correspondences are used to compare sets and to show that two collections can be matched element by element.

1.5 Inverse function

When a function is bijective, it has an inverse function. The inverse reverses the original assignment, sending each output back to its unique input. The existence of an inverse is one of the most important reasons bijections are so widely used, since it allows a mapping to be undone exactly.

2 Characterizations of bijective maps

Bijections can be recognized in several equivalent ways. Some descriptions use inverse maps, while others use algebraic properties of composition or counting arguments in finite settings. These viewpoints are often useful in different branches of mathematics.

2.1 Left and right inverses

A left inverse of a function undoes it when composed on the left, and a right inverse undoes it when composed on the right. For a bijection, these notions coincide and define the same inverse map. The presence of both a left and a right inverse is a strong signal that the function is bijective.

2.2 Composition with inverse maps

If a function is bijective, composing it with its inverse in either order gives the identity function on the appropriate set. This means the original function followed by the inverse does nothing overall, and the same is true in reverse. These identities provide a standard test for bijectivity.

2.3 Cardinality-based characterizations

Bijections are closely tied to the notion of equal cardinality. Two sets have the same cardinality if there exists a bijection between them. This idea is fundamental in set theory and provides a rigorous way to compare finite and infinite collections.

2.3.1 Finite sets

For finite sets, a function from a set to itself is bijective if and only if it is injective, and also if and only if it is surjective. This equivalence fails in general for infinite sets, but it is extremely useful in finite combinatorics and elementary algebra. In finite contexts, a bijection simply rearranges elements without duplicating or discarding any.

2.3.2 Infinite sets

For infinite sets, injectivity and surjectivity are no longer equivalent by themselves. Some maps can be injective without being surjective, while others can be surjective without being injective. A bijection remains the precise notion of perfect matching, even when the sets involved are infinite.

3 Examples

Examples help distinguish bijections from maps that only satisfy part of the definition. They also show how the concept appears in different mathematical settings.

3.1 Simple finite examples

A function from a three-element set to another three-element set can be bijective if it pairs the elements without repetition. For instance, a map that sends each item to a distinct target and uses every target exactly once is bijective. By contrast, a map that sends two inputs to the same output cannot be bijective.

3.2 Linear transformations

In linear algebra, a linear transformation between vector spaces may be bijective when it preserves structure and has an inverse linear transformation. Such maps are called linear isomorphisms. They identify vector spaces that are structurally the same, even if their elements are written differently.

3.3 Permutations

A permutation is a bijection from a set to itself. Permutations rearrange the elements of a set without changing the set as a whole. They are central in algebra and combinatorics because they represent reorderings and symmetries.

3.4 Common non-examples

A constant function is not bijective unless the domain contains only one element. The function sending integers to their squares is injective on the nonnegative integers but not surjective onto the integers. Likewise, a function can be surjective without being injective, such as certain maps from a larger set onto a smaller one.

4 Properties and consequences

Bijections preserve the essential information of a set or structure. Their reversibility gives them special algebraic and combinatorial power.

4.1 Preservation of structure under inverse

When a bijection respects additional structure, its inverse often preserves that structure as well. This is a key principle in algebra, where structure-preserving bijections are used to compare objects. The inverse therefore carries the same kind of information in the opposite direction.

4.2 Cancellation laws

Bijections support cancellation in compositions. If a bijection is composed with two functions and the results are equal, then one can often cancel the bijection to conclude that the original functions are equal. This property makes bijections especially useful in algebraic proofs.

4.3 Uniqueness of inverse

A bijection has exactly one inverse function. If another function also reversed the mapping, it would have to agree with the first inverse on every element. This uniqueness follows from the fact that each output corresponds to only one input.

4.4 Composition of bijections

The composition of two bijections is again a bijection. Likewise, the inverse of a bijection is a bijection. These closure properties mean that bijections form a stable class under the basic operations of composition and inversion.

5 Bijections in algebra

Bijections appear throughout algebra because they provide a formal way to say that two objects are equivalent in a structural sense. They often serve as the maps that connect two representations of the same underlying arrangement.

5.1 Set-theoretic viewpoint

In set theory, a bijection is the standard notion used to compare the size of sets. Two sets are considered equipotent if a bijection exists between them. This perspective does not depend on the nature of the elements, only on how they can be paired.

5.2 Group theory applications

In group theory, bijections are important when comparing groups and their elements. A group homomorphism that is also bijective identifies two groups in a way that respects the group operation. Such maps preserve the full algebraic structure and are therefore highly significant.

5.2.1 Isomorphisms as bijective homomorphisms

An isomorphism is a bijective homomorphism. It is the standard notion of sameness in group theory and many other algebraic systems. If two groups are isomorphic, they may look different on the surface, but they behave identically with respect to their operations.

5.3 Linear algebra applications

Linear algebra uses bijections to classify vector spaces and operators. A linear map that is bijective has a linear inverse, making it especially valuable for changing coordinates and comparing spaces.

5.3.1 Invertible matrices

An invertible matrix represents a bijective linear transformation in finite-dimensional settings. Its inverse matrix reverses the action of the original matrix. Invertibility is a central concept because it indicates that the transformation can be undone exactly.

5.3.2 Isomorphisms of vector spaces

A vector space isomorphism is a bijective linear map between vector spaces. Such a map shows that the spaces have the same linear structure, even if their elements are presented differently. This idea is essential in classification problems and in the study of coordinate changes.

Several related terms help place bijections within the broader language of functions and structure-preserving maps.

6.1 Injective map

An injective map sends distinct inputs to distinct outputs. It prevents collapse of information, but it may still miss elements of the codomain.

6.2 Surjective map

A surjective map reaches every element of the codomain. It ensures coverage, though multiple inputs may share the same output.

6.3 Permutation

A permutation is a bijection from a set to itself. It rearranges elements without changing the underlying collection.

6.4 Isomorphism

An isomorphism is a structure-preserving bijection. The term is used in algebra and related fields to mean that two objects are equivalent in form and behavior.

6.5 Invertible function

An invertible function is a function that has an inverse function. In standard mathematical usage, this is exactly the same as being bijective.