FACTOID # 30: If Alaska were its own country, it would be the 26th largest in total area, slightly larger than Iran.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
RELATED ARTICLES
People who viewed "Surjection" also viewed:
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Surjection
A surjective function.
Enlarge
A surjective function.
Another surjective function.
Another surjective function.
An non-surjective function.
Enlarge
An non-surjective function.

In mathematics, a function f is said to be surjective if and only if its values span its whole codomain; that is, for every y in the codomain, there is at least one x in the domain such that f(x) = y. Image File history File links A diagram illustrating a function that is not injective but is surjective. ... Image File history File links A diagram illustrating a function that is not injective but is surjective. ... A bijection. ... A bijection. ... Image File history File links Diagram to illustrate a function that is an injection but not a surjection. ... Image File history File links Diagram to illustrate a function that is an injection but not a surjection. ... Mathematics is often defined as the study of topics such as quantity, structure, space, and change. ... Partial plot of a function f. ... ↔ ⇔ ≡ logical symbols representing iff. ... A codomain in mathematics is the set of output values associated with (or mapped to) the domain of inputs in a function. ... Domain has several meanings: // General some kind of territory, such as (for example) a demesne or a realm synonymous with a metaphorical field, e. ...


Said another way, a function fX → Y is surjective if and only if its range f(X) is equal to its codomain Y. A surjective function is called a surjection, and said to be onto.

Contents


Examples and counterexamples

  • For any set X, the identity function idX on X is surjective.
  • The function fR → R defined by f(x) = 2x + 1 is surjective, because for every real number y we have f(x) = y where x is (y - 1)/2.
  • The natural logarithm function ln: (0..+∞) → R is surjective.
  • The function gR → R defined by g(x) = x² is not surjective, because (for example) there is no real number x such that x² = −1. However, if the codomain is defined as [0,+∞), then g is surjective.
  • The function fZ → {0,1,2,3} defined by f(x) = x mod 4 is surjective.

The natural logarithm, invented by John Napier, is the logarithm to the base e, where e is equal to 2. ... Modular arithmetic is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ...

Properties

  • A function fX → Y is surjective if and only if there exists a function gY → X such that f o g equals the identity function on Y. (This statement is equivalent to the axiom of choice.)
  • If f and g are both surjective, then f o g is surjective.
Surjective composition: the first function need not be surjective.
Surjective composition: the first function need not be surjective.
  • If f o g is surjective, then f is surjective (but g maynot be).
  • fX → Y is surjective if and only if, given any functions g,h:Y → Z, whenever g o f = h o f, then g = h. In other words, surjective functions are precisely the epimorphisms in the category Set of sets.
  • If fX → Y is surjective and B is a subset of Y, then f(f −1(B)) = B. Thus, B can be recovered from its preimage f −1(B).
  • Every function hX → Z can be decomposed as h = g o f for a suitable surjection f and injective function g. This decomposition is unique up to isomorphism, and f may be thought of as a function with the same values as h but with its codomain restricted to the range h(W) of h, which is only a subset of the codomain Z of h.
  • By collapsing all arguments mapping to a given fixed image, every surjection induces a bijection defined on a quotient of its domain. More precisely, every surjection f : AB can be factored as a projection followed by a bijection as follows. Let A/~ be the equivalence classes of A under the following equivalence relation: x ~ y if and only if f(x) = f(y). Equivalently, A/~ is the set of all preimages under f. Let P(~) : AA/~ be the projection map which sends each x in A to its equivalence class [x]~, and let fP : A/~ → B be the well-defined function given by fP([x]~) = f(x). Then f = fP o P(~).
  • If fX → Y is a surjective function, then X has at least as many elements as Y, in the sense of cardinal numbers.
  • If both X and Y are finite with the same number of elements, then f : X → Y is surjective if and only if f is injective.

↔ ⇔ ≡ logical symbols representing iff. ... An identity function f is a function which doesnt have any effect: it always returns the same value that was used as its argument. ... In mathematics, the axiom of choice, or AC, is an axiom of set theory. ... Image File history File links An illustration of two functions/mappings: the left is neither injective nor surjective and the right is non-injective and surjective. ... Image File history File links An illustration of two functions/mappings: the left is neither injective nor surjective and the right is non-injective and surjective. ... In the context of abstract algebra or universal algebra, an epimorphism is simply a homomorphism onto or surjective homomorphism. ... Category theory is a mathematical theory that deals in an abstract way with mathematical structures and relationships between them. ... In mathematics, the category of sets is the category whose objects are all sets and whose morphisms are all functions. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, a set A is a subset of a set B, if A is contained inside B. Every set is a subset of itself. ... In mathematics, the image of an element x in a set X under the function f : X → Y, denoted by f(x), is the unique y in Y that is associated with x. ... In mathematics, an injective function (or one-to-one function or injection) is a function which maps distinct input values to distinct output values. ... In mathematics, the term up to xxxx is used to describe a situation in which members of an equivalence class can be regarded as a single entity for some purpose. ... In linguistics, cardinal numbers is the name given to number words that are used for quantity (one, two, three), as opposed to ordinal numbers, words that are used for order (first, second, third). ... In mathematics, a set is called finite if and only if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ... In mathematics, an injective function (or one-to-one function or injection) is a function which maps distinct input values to distinct output values. ...

See also

In mathematics and related technical fields, the term map or mapping is often a synonym for function. ... In the context of abstract algebra or universal algebra, an epimorphism is simply a homomorphism onto or surjective homomorphism. ... In mathematics, an injective function (or one-to-one function or injection) is a function which maps distinct input values to distinct output values. ...

Category theory view

In the language of category theory, surjective functions are precisely the epimorphisms in the category of sets. Category theory is a mathematical theory that deals in an abstract way with mathematical structures and relationships between them. ... In the context of abstract algebra or universal algebra, an epimorphism is simply a homomorphism onto or surjective homomorphism. ... In mathematics, the category of sets is the category whose objects are all sets and whose morphisms are all functions. ...


  Results from FactBites:
 
Surjection - Wikipedia, the free encyclopedia (522 words)
In mathematics, a function f is said to be surjective if and only if its values span its whole codomain; that is, for every y in the codomain, there is at least one x in the domain such that f(x) = y.
This decomposition is unique up to isomorphism, and f may be thought of as a function with the same values as h but with its codomain restricted to the range h(W) of h, which is only a subset of the codomain Z of h.
In the language of category theory, surjective functions are precisely the epimorphisms in the category of sets.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m