Surjective function

In mathematics, a surjective function is a specific way to connect two sets. A function maps elements from a starting set, called the domain, to a target set, called the codomain. A function is surjective if every single element in the codomain is paired with at least one element from the domain. This means the image, or the actual set of values reached by the function, is exactly equal to the codomain.

In other words, no part of the target set is left empty or untouched by the mapping.

To understand the mechanism, imagine the function as a process of covering a space. If you have a domain $X$ and a codomain $Y$, the function $f$ is surjective if for every $y$ in $Y$, there is at least one $x$ in $X$ such that $f(x) = y$. It is important to note that the mapping does not have to be unique. Multiple different elements in the domain can point to the same single element in the codomain. The defining requirement is simply that the entire codomain is "covered" by the image of the domain.

Surjective functions have several distinct mathematical properties and types. A function is called bijective if it is both surjective and injective. An injective function is one where every input has a unique output, meaning no two inputs share the same target. While a surjection must cover the whole codomain, it does not care if it hits the same spot twice. However, if a function is surjective, it possesses a right inverse. This is a function $g$ such that $f(g(y)) = y$ for every $y$ in the codomain. This means the function $f$ can "undo" the action of $g$, even if $g$ cannot perfectly undo $f$.

History shows that these terms were formalized by a specific group of thinkers. The terms surjective, injective, and bijective were introduced by Nicolas Bourbaki. This was not one person, but a pseudonym for a group of mainly French mathematicians. They began publishing a series of books in 1935 to present modern advanced mathematics. The name "surjective" comes from the French word "sur," meaning "over" or "above." This describes how the image of the domain spreads over and completely covers the codomain.

There are many notable examples of surjection across different fields of math. For instance, the function $f(x) = 2x + 1$ is surjective over the set of real numbers. For any real number $y$ you choose, you can find an $x$ by calculating $(y - 1)/2$. In contrast, the function $g(x) = x^2$ is not surjective if the codomain is all real numbers. This is because no real number squared will ever result in a negative value, like $-1$. However, if you restrict the codomain to only non-negative real numbers, the function becomes surjective.

Another example is found in 3D video games. Computers use surjective functions to project 3D vectors onto a 2D flat screen.

Surjections also reveal important truths about the size of sets, known as cardinality. If a surjective function exists from set $X$ to set $Y$, then the cardinality of $X$ must be greater than or equal to the cardinality of $Y$. Essentially, you must have at least as many elements in your starting group as you have in your target group to ensure every target is hit. If both sets are finite and have the exact same number of elements, then a surjection is automatically an injection as well. This relationship helps mathematicians compare the sizes of different infinite sets.

Finally, surjections connect to broader algebraic structures and categories. In the study of categories, surjective functions are known as epimorphisms in the category of sets. An epimorphism is a mapping that is "right-cancellative." This means if you have two functions $g$ and $h$ that, when composed with $f$, produce the same result, then $g$ and $h$ must be equal. Furthermore, any function can be decomposed into two simpler parts: a surjection followed by an injection. This allows mathematicians to break down complex mappings into these fundamental building blocks.