Fact-checked by Grok 2 weeks ago

Surjective function

A surjective function, also known as an onto function, is a mapping from a set A (the domain) to a set B (the codomain) such that every element in B is the image of at least one element in A; formally, for every b \in B, there exists some a \in A with f(a) = b.^[1]^[2] The concept of surjectivity, alongside injectivity and bijectivity, was formalized in modern set theory by the collective Nicolas Bourbaki in their 1954 treatise Théorie des ensembles, drawing from earlier notions of "onto" mappings in analysis and algebra.^[3] The term "surjective" derives from the French surjectif, where sur implies "onto" or "upon," reflecting the idea of covering the entire codomain.^[4] Prior to this standardization, equivalent ideas appeared in works on functions dating back to the early 20th century, but without the precise terminology. Surjective functions are distinguished from injective (one-to-one) functions, which map distinct elements of the domain to distinct elements of the codomain, though a function can be surjective without being injective—for instance, multiple domain elements may map to the same codomain element. A function that is both surjective and injective is bijective, establishing a one-to-one correspondence between sets, which is fundamental for proving equal cardinalities. Examples illustrate surjectivity clearly: the linear function f: \mathbb{R} \to \mathbb{R} given by f(x) = 2x + 1 is surjective, as for any real number y, solving $2x + 1 = y yields x = \frac{y-1}{2} \in \mathbb{R}.^[5] In contrast, g: \mathbb{R} \to \mathbb{R} defined by g(x) = x^2 is not surjective onto \mathbb{R} (since negative numbers lack preimages), but it is surjective onto [0, \infty).^[6] In applied contexts, surjectivity plays a key role in linear algebra, where a linear transformation T: V \to W between vector spaces is surjective if its image spans W, equivalent to the rank of its matrix representation equaling \dim(W); this ensures solvability of linear systems T(\mathbf{v}) = \mathbf{w} for all \mathbf{w} \in W.^[7] More broadly, surjective functions underpin existence theorems in analysis (e.g., the intermediate value theorem implies certain continuous functions are surjective onto intervals).

Fundamentals

Definition

In set theory, sets are well-determined collections of distinct objects, known as elements or members. A function f: A \to B between two sets A (the domain) and B (the codomain) is formally defined as a triple (A, B, G), where G \subseteq A \times B is a relation such that for every a \in A, there exists exactly one b \in B with (a, b) \in G, often denoted f(a) = b. The image of f, denoted f(A), is the subset of B consisting of all elements b \in B for which there exists at least one a \in A such that f(a) = b, i.e., f(A) = \{ f(a) \mid a \in A \}. A function f: A \to B is surjective if every element of the codomain B is mapped to by at least one element of the domain A. Formally, f is surjective if for every b \in B, there exists at least one a \in A such that f(a) = b. Equivalently, the image of f equals the entire codomain, i.e., f(A) = B. The term "surjective" was coined by the collective of mathematicians known as Nicolas Bourbaki in their 1954 treatise Théorie des ensembles to describe functions that map "onto" the codomain, distinguishing them from injective functions (which map elements distinctly) and bijective functions (which are both injective and surjective).

Notation and Terminology

In mathematics, a function f: A \to B is commonly denoted using the standard arrow \to to indicate the mapping from domain A to codomain B, with surjectivity explicitly stated in words such as "is surjective" or "is onto."^[1] Alternative notations for surjectivity include the two-headed arrow f: A \twoheadrightarrow B (Unicode U+21A0, rightwards two-headed arrow), emphasizing that every element in B is reached.^[8] The terminology "surjective function" is synonymous with "onto function," reflecting the property that the image equals the codomain.^[1] In some contexts, "total function" may appear but specifically denotes a function defined on its entire specified domain, contrasting with partial functions and unrelated to codomain coverage.^[9] The surjective arrow \twoheadrightarrow visually distinguishes surjectivity from the plain arrow \to by its two heads, symbolizing coverage of the target set without gaps.^[8] The word "surjective" derives from the French "surjectif," coined by the mathematician collective Nicolas Bourbaki in their 1954 work Théorie des ensembles, where the prefix "sur-" (meaning "upon" or "onto") evokes mapping elements onto the codomain, paralleling "injective" from "in-" (meaning "in").^[3]^[4]

Examples

Basic Examples

A simple example of a surjective function is the mapping f: \{1,2\} \to \{a\} defined by f(1) = a and f(2) = a. Here, the codomain \{a\} has only one element, which is the image of both elements in the domain, ensuring every codomain element is attained./07:_Functions/7.02:_Properties_of_Functions) Constant functions provide another basic illustration of surjectivity. Any constant function from a non-empty domain to a singleton codomain is surjective, as the single codomain element is mapped to by every domain element; for instance, the function g: \{x,y,z\} \to \{c\} where g(x) = g(y) = g(z) = c hits the entire codomain \{c\}./08:_New_Page/8.02:_New_Page) The identity function on any set offers a straightforward case of surjectivity. For a set X, the identity map \mathrm{id}_X: X \to X defined by \mathrm{id}_X(x) = x for all x \in X is surjective, since each element in the codomain X is precisely the image of itself from the domain./06:_Functions/6.04:_Onto_Functions) These examples can be visualized using arrow diagrams, where domain elements are points on one side and codomain elements on the other, connected by arrows representing the function values. Surjectivity appears when every codomain point receives at least one incoming arrow, as in the case of multiple arrows converging on the single point a for the finite set example above. Such diagrams concretize the condition that the function's image equals the codomain./07:_Functions/7.02:_Properties_of_Functions)

Function-Specific Examples

In analysis, the exponential function \exp: \mathbb{R} \to (0, \infty), defined by \exp(x) = e^x, provides a classic example of surjectivity. For every positive real number y > 0, there exists an x \in \mathbb{R} such that \exp(x) = y, namely x = \ln y, ensuring the image covers the entire codomain of positive reals.^[10] A related illustration arises with quadratic functions. The map f: \mathbb{R} \to \mathbb{R} given by f(x) = x^2 fails to be surjective, as its image consists solely of non-negative reals, missing all negative values in the codomain. However, restricting the codomain appropriately yields surjectivity: the function g: \mathbb{R} \to [0, \infty) defined by g(x) = x^2 is surjective, since for any y \geq 0, the preimage includes \sqrt{y} and -\sqrt{y}.^[7] In linear algebra, projection functions exemplify surjectivity in vector spaces. Consider the projection \pi: \mathbb{R}^2 \to \mathbb{R} defined by \pi(x, y) = x. This map is surjective because for every real number r \in \mathbb{R}, the point (r, 0) \in \mathbb{R}^2 satisfies \pi(r, 0) = r, covering the entire codomain./03%3A_Linear_Transformations_and_Matrix_Algebra/3.02%3A_One-to-one_and_Onto_Transformations) In number theory and abstract algebra, the canonical projection in modular arithmetic demonstrates surjectivity as a group homomorphism. The function f: \mathbb{Z} \to \mathbb{Z}/n\mathbb{Z} given by f(k) = k \mod n is surjective for any positive integer n, as every residue class in the codomain is attained by the integers from 0 to n-1.^[11]

Properties

Right Invertibility

A function f: A \to B between sets is surjective if and only if there exists a function g: B \to A such that f \circ g = \mathrm{id}_B, where \mathrm{id}_B denotes the identity function on B.^[12] To see this, suppose f is surjective. Then for each b \in B, the preimage f^{-1}(\{b\}) is nonempty. Using the axiom of choice, select one element g(b) \in f^{-1}(\{b\}) for every b \in B; this defines g such that f(g(b)) = b for all b. Conversely, if such a g exists, then for every b \in B, b = f(g(b)), so b lies in the image of f, proving surjectivity.^[12] In general, right inverses are not unique. When f is surjective but not injective, some preimages contain multiple elements, permitting different selections for g(b) and thus multiple possible right inverses. Uniqueness holds if and only if f is also injective, in which case f is bijective and g is the unique two-sided inverse.^[13] The statement that every surjective function admits a right inverse is equivalent to the axiom of choice. For finite sets A and B, however, a right inverse exists and can be constructed explicitly without the axiom of choice, as the finiteness ensures a direct, choice-free selection from nonempty finite preimages.

Epimorphisms

In category theory, a morphism f: A \to B in a category \mathcal{C} is an epimorphism, or epi, if for every object C in \mathcal{C} and every pair of parallel morphisms g, h: B \to C, the equality g \circ f = h \circ f implies g = h.^[14] This definition captures a form of right-cancellability for the morphism f.^[15] In the category \mathbf{Set} of sets (with functions as morphisms), epimorphisms coincide exactly with surjective functions.^[15] To outline why surjectivity implies the epimorphism property, suppose f: A \to B is surjective and g, h: B \to C satisfy g \circ f = h \circ f. For any b \in B, there exists a \in A such that f(a) = b, so g(b) = g(f(a)) = h(f(a)) = h(b); hence g = h.^[16] Conversely, if f is an epimorphism but not surjective, let b_0 \in B \setminus f(A) and consider C = \{0, 1\} with discrete functions as morphisms. Define g: B \to C to be the constant map sending everything to $0, and h: B \to Cbyh(b) = 0ifb \in f(A)andh(b_0) = 1

(and &#36;0

elsewhere if needed). Then g \circ f = h \circ f (both constant $0onA), but g \neq h, contradicting that fis epi; thusf$ must be surjective.^[16] This equivalence in \mathbf{Set} highlights how surjections behave categorically, generalizing their right invertibility in the concrete setting of sets (as discussed in the prior section on right invertibility). However, the situation differs in other categories, where epimorphisms need not be surjective. For instance, in the category of commutative rings (with ring homomorphisms as morphisms), the inclusion \mathbb{[Z](/page/Z)} \hookrightarrow \mathbb{[Q](/page/Q)} is an epimorphism despite not being surjective.^[14] To verify this, note that any two ring homomorphisms \phi, \psi: \mathbb{[Q](/page/Q)} \to R (for a commutative ring R) agreeing on \mathbb{[Z](/page/Z)} must agree on \mathbb{[Q](/page/Q)}, since \mathbb{[Q](/page/Q)} is the localization of \mathbb{[Z](/page/Z)} at the nonzero integers and homomorphisms preserve localizations; thus the inclusion right-cancels.^[17]

Binary Relations Perspective

In set theory, a binary relation between sets A and B is defined as a subset R \subseteq A \times B./01%3A_Proofs/04%3A_Mathematical_Data_Types/4.04%3A_Binary_Relations) A function f: A \to B corresponds to a binary relation f \subseteq A \times B that is total on the domain—meaning every element a \in A relates to exactly one b \in B—and single-valued, ensuring no two elements in B relate to the same a \in A.^[18] From this relational viewpoint, surjectivity of f requires that for every b \in B, there exists at least one a \in A such that (a, b) \in f.^[19] This condition characterizes surjective functions as right-total binary relations, where the relation covers the entire codomain B without leaving any element unmatched.^[18] In contrast to general functions, which may leave some codomain elements unrelated, surjectivity imposes totality on the codomain side, ensuring the relational structure has no "dangling" or unused elements in B./01%3A_Proofs/04%3A_Mathematical_Data_Types/4.04%3A_Binary_Relations) Such right-total relations are sometimes termed surjective relations in broader relational theory, highlighting their coverage property independent of the functional restriction.^[18] When represented graphically, a surjective function manifests as a directed bipartite graph with vertices partitioned into A and B, where each vertex in A has out-degree exactly 1 and each vertex in B has in-degree at least 1./01%3A_Proofs/04%3A_Mathematical_Data_Types/4.04%3A_Binary_Relations) This graph-theoretic perspective, often called the functional graph of the relation, underscores surjectivity by guaranteeing positive in-degree for all codomain nodes, preventing isolated vertices in B./01%3A_Proofs/04%3A_Mathematical_Data_Types/4.04%3A_Binary_Relations)

Domain Cardinality Constraints

For finite sets A and B, a necessary condition for the existence of a surjective function f: A \to B is that the cardinality of the domain satisfies |A| \geq |B|./04%3A_Mathematical_Data_Types/4.05%3A_Finite_Cardinality) This follows from the pigeonhole principle: if |A| < |B|, then at least one element in B cannot be mapped to from A, preventing surjectivity. Conversely, if |A| \geq |B|, a surjection exists; for example, partition A into |B| subsets (possibly of unequal size) and map each subset constantly to a distinct element of B. When |A| = |B|, any surjection is also a bijection./04%3A_Mathematical_Data_Types/4.05%3A_Finite_Cardinality) In the infinite case, the cardinality condition remains |A| \geq |B| for a surjection f: A \to B to exist, meaning no surjection is possible if |A| < |B|.^[20] This holds under the axiom of choice, which equates the existence of a surjection from A to B with the existence of an injection from B to A (defining |A| \geq |B|). Without the axiom of choice, the implication from surjection to injection may fail, but the condition is standard in ZFC set theory.^[20] In general, for arbitrary sets A and B, there exists a surjective function f: A \to B if and only if |A| \geq |B|.^[20] The sufficiency direction follows from constructing a surjection when an injection B \to A exists: embed B into A and map the complement of the image to a fixed element of B (assuming B nonempty). The necessity relies on the axiom of choice to select preimages, yielding an injection B \to A.^[20] This cardinality comparison aligns with the Schröder–Bernstein theorem, which states that injections A \to B and B \to A imply a bijection (so |A| = |B|); surjections provide the injection B \to A via choice, enabling such equipotency arguments when combined with the converse injection.

Composition Properties

A key property of surjective functions under composition is that if g \circ f: X \to Z is surjective, where f: X \to Y and g: Y \to Z, then the right factor g must be surjective.^[21] To prove this, consider any z \in Z. Since g \circ f is surjective, there exists x \in X such that g(f(x)) = z. Setting y = f(x) \in Y, it follows that g(y) = z, showing that every element of Z is in the image of g. Thus, g is surjective.^[21] The converse does not hold: surjectivity of g alone does not imply surjectivity of g \circ f. For g \circ f to be surjective, the image of f must cover the entire domain Y of g, meaning f must also be surjective.^[21] An example illustrates this failure: let X = \{1\}, Y = \{a, b\}, Z = \{c, d\}, with f(1) = a (so f is not surjective) and g(a) = c, g(b) = d (so g is surjective). Then g \circ f(1) = c, and the image is \{c\}, which is not all of Z, so g \circ f is not surjective.^[21] In contrast, if both f and g are surjective, then g \circ f is surjective.^[22] This rightward propagation of surjectivity extends to longer chains of compositions. If h \circ g \circ f is surjective, then both h \circ g and g are surjective by repeated application of the theorem, illustrating how surjectivity must hold for all functions to the right of the first in the chain.^[21] Any function f: X \to Y can be decomposed as a composition of a surjection followed by an injection: f = i \circ s, where s: X \to f(X) is the canonical surjection onto the image f(X) \subseteq Y, and i: f(X) \to Y is the inclusion map, which is injective.^[23] This factorization highlights the structural role of surjections in representing the "onto" aspect of arbitrary mappings. Surjectivity in compositions also connects to right invertibility: if g \circ f admits a right inverse, then f has a right inverse, though the details depend on the specific invertibility conditions.^[22]

Induced Maps

In set theory, a fundamental construction that induces surjective functions arises from equivalence relations on a set. Given a set A and an equivalence relation \sim on A, the quotient set A/{\sim} consists of the equivalence classes of \sim, and the canonical projection map \pi: A \to A/{\sim} defined by \pi(a) = , the equivalence class containing a, is surjective by construction, as every equivalence class is the image of its own elements under \pi. This surjection identifies elements that are equivalent, effectively collapsing the domain according to the relation. Surjective functions also induce additional surjections via their kernels. For a surjective function f: A \to B, the kernel equivalence relation \sim_f on A is defined by a \sim_f a' if and only if f(a) = f(a'), with equivalence classes corresponding to the fibers f^{-1}(b) for each b \in B. This relation partitions A into the preimages under f, and the canonical projection \pi: A \to A/{\sim_f} is surjective, while f itself induces a bijection \overline{f}: A/{\sim_f} \to B given by \overline{f}() = f(a), satisfying f = \overline{f} \circ \pi.^[24] The fibers of f thus provide the natural partition that underlies this induced structure. A key result in this context is the factorization theorem for functions between sets, which states that every function g: X \to Y factors uniquely (up to isomorphism) as g = i \circ s, where s: X \to Z is surjective and i: Z \to Y is injective, with Z taken as the image of g. When g itself is surjective, Z can be identified with the quotient X/{\sim_g} by the kernel of g, making i a bijection and yielding a unique factorization up to unique isomorphism of the intermediate set.^[24] This theorem highlights how surjections emerge canonically from partitions induced by the function's level sets. To construct an induced surjection explicitly from a partition of the domain, consider a set A = \{1, 2, 3, 4\} partitioned into \{\{1,2\}, \{3\}, \{4\}\}. The quotient set A/{\sim} is \{\{1,2\}, \{3\}, \{4\}\}, and the projection \pi: A \to A/{\sim} maps $1 and $2 to \{1,2\}, $3 to \{3\}, and $4 to \{4\}, which is surjective as each part is hit. This example illustrates how any partition of A defines an equivalence relation whose quotient map is inherently surjective, providing a direct method to generate such functions.^[25]

Surjections as Sets

The Set of All Surjections

The set of all surjective functions from a set A to a set B, commonly denoted \operatorname{Sur}(A, B), consists of all functions f: A \to B such that the image of f equals B, meaning every element of B is mapped to by at least one element of A. This collection is a proper subset of the full function space B^A, which comprises all possible functions from A to B.^[26] The set \operatorname{Sur}(A, B) is nonempty if and only if the cardinality of A is at least that of B, i.e., |A| \geq |B|. For finite sets, this condition ensures the existence of at least one surjection, as partitioning A into |B| nonempty subsets allows assigning each subset to a unique element of B.^[27] In the infinite case, the same cardinal inequality holds under the axiom of choice, guaranteeing a surjection by injecting B into A and extending to a cover.^[28] This nonempty condition underscores \operatorname{Sur}(A, B) as a foundational object in the study of function spaces, providing insights into mappings that fully utilize the codomain and serving as a building block for more advanced structures in set theory and category theory. When |A| = |B|, \operatorname{Sur}(A, B) contains the set of all bijections from A to B, as every bijection is inherently surjective by satisfying both injectivity and surjectivity.^[29] This inclusion highlights the role of surjections in equivalence relations and isomorphisms, where bijections represent the "perfect" matchings within the broader class of onto mappings. In topological contexts, equipping B with the discrete topology endows the function space B^A with the product topology, under which \operatorname{Sur}(A, B) inherits the subspace topology as a natural subcollection of continuous functions (all functions being continuous in this setup).^[30] This perspective facilitates analysis of convergence and compactness properties within surjective mappings.

Counting Surjections

The number of surjective functions from a finite set A with |A| = n elements to a finite set B with |B| = m elements, denoted |\mathrm{Sur}(A, B)|, is given by the formula m! \, S(n, m), where S(n, m) is the Stirling number of the second kind.^[31] The Stirling number of the second kind S(n, m) counts the number of ways to partition an n-element set into exactly m non-empty unlabeled subsets.^[32] Each such partition corresponds to a surjection by assigning the m subsets to the m elements of B via a bijection, which can be done in m! ways.^[32] This count can also be derived using the principle of inclusion-exclusion. The total number of functions from A to B is m^n. To exclude non-surjective functions, subtract the cases where at least one element of B is missed: there are \binom{m}{1} (m-1)^n such functions. Adding back the cases missing at least two elements gives \binom{m}{2} (m-2)^n, and so on, alternating signs.^[31] The resulting formula is

|\mathrm{Sur}(A, B)| = \sum_{k=0}^{m} (-1)^k \binom{m}{k} (m - k)^n.

^[31] Equivalence of the two expressions follows from the known relation S(n, m) = \frac{1}{m!} \sum_{k=0}^{m} (-1)^{m-k} \binom{m}{k} k^n.^[31] For fixed m and large n, the number of surjections approximates the total number of functions m^n, since the inclusion-exclusion terms beyond the leading one become negligible as (1 - k/m)^n \to 0 rapidly for k \geq 1.^[31] The exact count is provided by either formula above.

References

[1]
Surjection -- from Wolfram MathWorld
A surjection (or surjective map) is a function where for any b in B, there exists an a in A for which b=f(a). It is sometimes referred to as being 'onto'.Missing: definition | Show results with:definition
[2]
surjective - PlanetMath.org
Mar 22, 2013 · A function f:X→Y f : X → Y is called surjective or onto if, for every y∈Y y ∈ Y , there is an x∈X x ∈ X such that f(x)=y f ⁢ ( x ) = y .Missing: mathematics | Show results with:mathematics
[3]
History of the definition of Injective & Surjective Function
Jun 20, 2016 · The terms injective, surjective, and bijective were first introduced in Bourbaki's Théorie des ensembles, of 1954, page 80.
[4]
Injection and surjection - origin of words - Math Stack Exchange
Sep 25, 2012 · The French "injectif" is a natural choice, since we are injecting one set into another. The French word "sur" means "on" (as in "on top of"), making "surjectif ...What is a surjective function? - Mathematics Stack ExchangeUnderstanding the definition of surjective functionMore results from math.stackexchange.com
[5]
10.4 Injective and surjective functions
The terms injective , surjective and bijective were coined by Nicholas Bourbaki. ... We now prove that g is surjective using the square-root function. Given any ...
[6]
What is a surjective function? - Mathematics Stack Exchange
Sep 3, 2015 · A function is surjective if you can get any value you want by giving it the adequate argument. For example, y=f(x)=2x+1(x∈R) is surjective ...
[7]
Verifying if a function is surjective - Math Stack Exchange
Sep 11, 2024 · For example, f:R→R≥0 with f(x)=x2 is surjective since h:R≥0→R with h(x)=√x is its right-inverse. Obviously, you need to make an argument for the ...<|separator|>
[8]
[PDF] lecture 18: injective and surjective functions and transformations
Nov 18, 2016 · InJECtiVE And sURJECtiVE FUnCtions. There are two types of special properties of functions which are important in many different mathematical ...
[9]
What are usual notations for surjective, injective and bijective ...
Jun 21, 2011 · The usual notation is ↣ or ↪ for 1:1 functions and ↠ for onto functions. These arrows should be universally understood.Is f:P(A)→P(B), f(C)=C∩B injective or surjective?Proving Functions are Surjective - Mathematics Stack ExchangeMore results from math.stackexchange.com
[10]
Are there differences between total functions, epimorphic functions ...
Apr 7, 2014 · The term "total function" means exactly the same thing as "function". The term "total function" is used to imply a contrast with "partial ...What are use-cases of non-surjective total functions?Domain in a Surjective Function - Math Stack ExchangeMore results from math.stackexchange.com
[11]
4.6 Bijections and Inverse Functions
Example 4.6. 7 If we think of the exponential function ex as having domain R and codomain R>0 (the positive real numbers), and lnx as having domain R>0 and ...
[12]
[PDF] The Structure of (Z/nZ)
Apr 6, 2018 · ... Z → G defined by a 7→ ga is a surjective homomorphism. The proof of Lemma 6 shows that bc is also injective and is therefore an isomorphism.
[13]
[PDF] Functions and Inverses - CS@Cornell
Page 24. Right inverse ⇔ Surjective. ○ Theorem: A function is surjective (onto) iff it has a right inverse. ○ Proof (⇐): Assume f : A → B has right inverse h.
[14]
[PDF] TMA4145 – Linear Methods Franz Luef - NTNU
One the other hand if f : X → Y is right invertible such that f is surjective but not injective, then f will have many right inverses. Our study of linear ...
[15]
epimorphism in nLab
Dec 7, 2024 · In category theory, the concept of epimorphism is a generalization or strengthening of the concept of surjective functions between sets.
[16]
Epimorphism -- from Wolfram MathWorld
In the categories of sets, groups, modules, etc., an epimorphism is the same as a surjection, and is used synonymously with "surjection" outside of category ...
[17]
[PDF] Unique Lifting to a Functor
A morphism f : X → Y in Set is an epimorphism if and only if f is surjective. Proof. Suppose f is a surjection. Let g1, g2 : Y → Z be such that g1◦ f = g2◦ f.
[18]
Counterexamples in algebra? - MathOverflow
Jun 21, 2010 · 63 Answers. In the category of rings, epimorphisms do not have to be surjective: Z↪Q. I like Lance Small's example of a right but not left ...What do epimorphisms of (commutative) rings look like?Can we ascertain that there exist an epimorphism G→H?More results from mathoverflow.net
[19]
[PDF] Functions, Sets, and Relations
(Thus, a surjective function is a right-unique, right-total binary relation. A right-total binary relation is sometimes called a surjective relation.
[20]
Functions:Surjective - Department of Mathematics at UTSA
Nov 7, 2021 · The term surjective and the related terms injectiv and bijective were introduced by Nicolas Bourbaki, a group of mainly French 20th-century ...<|control11|><|separator|>
[21]
surjection and axiom of choice - PlanetMath
Mar 22, 2013 · Let f:A→B f : A → B be a surjection. Then the set C:={f−1(y)∣y∈B} C := { f - 1 ⁢ ( y ) ∣ y ∈ B } partitions A A . By the axiom of choice, ...
[22]
[PDF] Math 301: Introduction to Proofs Problem Set 4 due: October 2, 2019 ...
(iii) Prove that if g ∘ f is surjective then g is surjective. (iv) Find an example to show that it is possible for g and g ∘ f to be surjective ...
[23]
Injective, surjective and bijective functions - SIUE
A function f:A→B f : A → B is said to be surjective (or onto) if rng(f)=B. ... That is, for every b∈B b ∈ B there is some a∈A a ∈ A for which f(a)=b.
[24]
Properties of Functions - Department of Mathematics at UTSA
Jan 11, 2022 · of a surjection followed by an injection, where s is the canonical surjection of X onto f(X) and i is the canonical injection of f(X) into Y.<|control11|><|separator|>
[25]
[PDF] Fibers, Surjective Functions, and Quotient Groups
Nov 1, 2006 · Proposition 1 Let f : X −→ Y be a surjective function. Then there is a unique bijection F : X/f −→ Y which satisfies F◦π = f. 1 ...
[26]
[PDF] Math 190: Quotient Topology Supplement
Let X be any set and let. ∼ be any equivalence relation on X. We have a canonical surjective map π : X → X/ ∼ defined by π : x 7→ [x].
[27]
[PDF] Lecture 23: Sections 9.1 -9.3
The Set of All Functions from A to B. For nonempty sets A and B, the set of all functions from A to B is denoted by BA, i.e., BA = {f |f : A → B}. EX. List ...
[28]
[PDF] CS 173 Lecture 12: Functions (II)
Given finite sets A and B with B “ H, there exists a surjective function f : A Ñ B if an only if |B|ď|A|. Proof: To see the pðq implication, let A “ ta1,...,anu ...
[29]
[PDF] Cardinality
For infinite sets A and B, if there is an injective function f : A → B then there is a surjective function g : B → A. Thus, if there is an injective function f ...
[30]
[PDF] 2. Properties of Functions 2.1. Injections, Surjections, and Bijections ...
Thus to show a function is not surjective it is enough to find an element in the codomain that is not the image of any element of the domain.
[31]
[PDF] Function Spaces
These notes describe three topologies that can be placed on the set of all functions from a set X to a space Y : the product topology, the box topology, and the ...Missing: surjections | Show results with:surjections
[32]
[PDF] Enumerative Combinatorics 9: Möbius inversion
First, a formula for the Stirling numbers of the second kind. Theorem 9.3 The number of surjective functions from an m-set to an n-set is n. X i=0. (−1)i n i.
[33]
[PDF] combinatorial counting: special numbers - OSU Math
Stirling number of the second kind. We now define the Stirling numbers of the second kind: denote by P(n, k) the set of all partitions of an n-set into k ...