Mathematics
Surjective functions
Surjective functions, also known as onto functions, are functions where every element in the range is mapped to by at least one element in the domain. In other words, every output value has at least one input value that produces it. Surjective functions are important in many areas of mathematics, including algebra, topology, and analysis.
Written by Perlego with AI-assistance
Related key terms
1 of 5
10 Key excerpts on "Surjective functions"
eBook - PDFExploring Mathematics
An Engaging Introduction to Proof
- John Meier, Derek Smith(Authors)
- 2017(Publication Date)
- Cambridge University Press(Publisher)
Put another way, f is surjective if each element in Y is hit by some element in X. A sur- jective function is also called onto. The claim that a function is surjective is sometimes encoded by the symbol , as in f : X Y and X f Y . Sven Lena Ole Alice Bob Cecelia Figure 2. A function between two finite sets. In Figure 2 we illustrate a function going from the set {Ole, Lena, Sven} to the set {Alice, Bob, Cecelia}, where each person in the first set is sent to his or her favorite partner when playing games. This function is not injective, as Lena and Sven both like playing with Bob. It is also not surjective: Cecelia is lonely, not being the preferred partner of anyone in the first set. E XAMPLE 5.10. The following three examples provide some insight into how you prove that a given function is or is not surjective. (a) The function f : Z → Z given by f (x) = 3x is not surjective for the following reason: 1 is an element of (the codomain) Z, but the equation f (x) = 3x = 1 is not satisfied by any element of (the domain) Z. (b) The function p : ∗ → ∗ given by appending a 1 to the end of any string is also not surjective. To prove this you could first note that the process of appending a 1 increases the length of any string ω by 1. Since ε has length 0, p(ω) = ε is not satisfied by any ω ∈ ∗ . (c) Let g : ∗ → Z be defined by g(ω) = ω 0 − ω 1 . This function is surjective; we can also say that it is “onto Z.” To prove this, we need to show that the range of g is all of Z, which we do by considering three cases: (i) Because g(ε) = 0, we know 0 is in the range of g. (ii) If n > 0, define ω n to be the string consisting of n 0s. Then g(ω n ) = n, and thus all positive integers are in the range of g. (iii) If n < 0, define ω n to be the string consisting of |n| 1s. Then g( ω n ) = n, and thus all negative integers are in the range of g. Exercise 5.7 Prove the following claims: (a) The function in Example 5.5 (a) is both surjective and injective for any set A.
eBook - PDFDiscrete Mathematics
Proofs, Structures and Applications, Third Edition
- Rowan Garnier, John Taylor(Authors)
- 2009(Publication Date)
- CRC Press(Publisher)
† Some authors use the term ‘one-to-one function’ for an injective function and ‘onto function’ for a surjective function. 248 Functions Written less formally, a function f is injective if, for all a, a 0 ∈ A , if a 6 = a 0 then f ( a ) 6 = f ( a 0 ) . However, to prove that a given function is injective it is generally easier to use the equivalent contrapositive statement. That is, for all a, a 0 ∈ A , if f ( a ) = f ( a 0 ) then a = a 0 . Of course, to show a function is not injective we need to find a counter-example to the general condition. In other words, we need to find two different elements a and a 0 of A which have the same image, f ( a ) = f ( a 0 ) . The second part of the definition can be rephrased simply to say that f : A → B is surjective if its image set equals its codomain, i.e. im ( f ) = B . Examples 5.7 1. We have seen that f : R → R , x 7 → x 2 , is neither injective nor surjective. 2. Let f : { 1 , 2 , 3 , 4 , 5 } → { 1 , 2 , 3 , 4 , 5 , 6 } , be defined by 1 7 → 4 , 2 7 → 6 , 3 7 → 1 , 4 7 → 3 , 5 7 → 5 , and let g : { 2 , 4 , 6 , 8 , 10 , 12 } → { 2 , 3 , 5 , 7 , 11 } , be defined by 2 7 → 11 , 4 7 → 2 , 6 7 → 5 , 8 7 → 3 , 10 7 → 5 , 12 7 → 7 . Injections and Surjections 249 The function f is injective because each element of the domain has a different image. In other words, the following situation does not occur in the arrow diagram of f . The element 2 in the codomain is not the image of any element of the domain, 2 / ∈ im ( f ) . Therefore f is not surjective. Now consider g . There do exist two different elements of the domain with the same image, g (6) = 5 = g (10) , so g is not injective. Since each element of the codomain is ‘hit by an arrow’— 2 = g (4) , 3 = g (8) , 5 = g (6) , 7 = g (12) and 11 = g (2) —it follows that g is surjective. 3. Consider f : R → R defined by f ( x ) = 3 x -7 . Show that f is both injective and surjective.
eBook - PDFCounterExamples
From Elementary Calculus to the Beginnings of Analysis
- Andrei Bourchtein, Ludmila Bourchtein(Authors)
- 2014(Publication Date)
- Chapman and Hall/CRC(Publisher)
Another common name is injective mapping (or injective function) . One-to-one correspondence . If f ( x ) is a one-to-one mapping of X 3 4 Counterexamples: From Calculus to the Beginnings of Analysis onto Y , then f ( x ) is said to be a one-to-one correspondence between X and Y . Another common name is bijective mapping (or bijective function) . Remark . Frequently the term one-to-one function is used for one-to-one correspondence. Composition of functions . Let f ( x ) maps X into Y , and g ( y ) maps Y into Z . Then the composition of f and g is the function h with domain X and codomain Z defined by the formula h ( x ) = g ( f ( x )), ∀ x ∈ X . The standard notation is h ( x ) = g ( f ( x )) or h ( x ) = g ◦ f ( x ). Inverse function . Let f ( x ) be a one-to-one function with domain X and image Y . In this case, it is possible to define the inverse function f − 1 ( y ), with domain Y and image X , that assigns to each y ∈ Y the only element x ∈ X such that f ( x ) = y . Equivalent sets . Two sets are called equivalent if there exists a one-to-one correspondence between them. Finite/infinite sets . A set is called finite if it has a finite number of elements. Otherwise a set is infinite . The empty set is considered to be finite. Countable/uncountable set . A set is countable if it is equivalent to N . A set is uncountable if it is neither finite nor countable . Elementary properties Bounded function . A function f ( x ) is bounded above (below) on a set S if there exists a real number M ( m ) such that f ( x ) ≤ M ( f ( x ) ≥ m ) for all x ∈ S . A function is bounded if it is bounded above and below. Otherwise, a function is unbounded . Even function . A function f ( x ) defined on X is called even if for any x ∈ X it holds that f ( − x ) = f ( x ). Odd function . A function f ( x ) defined on X is called odd if for any x ∈ X it holds that f ( − x ) = − f ( x ).
eBook - PDF- Scott A. Taylor(Author)
- 2023(Publication Date)
- American Mathematical Society(Publisher)
8.7.1. Injective/surjective/bijective. Two important properties that a function may or may not have are the properties of being injective (also known as one-to-one) and surjective (also known as onto). 12 Definition 8.54 (Injective/surjective/bijective). Suppose that ∶ → is a function. It is: • injective (or one-to-one) if for all , ∈ , if () = (), then = . • surjective (or onto) if for every ∈ , there exists ∈ such that () = . • bijective if ∶ → is both injective and surjective. If ∶ → is injective, we will often write ∶ ↪ . If ∶ → is sur- jective, we will often write ∶ ↠ . To denote a bijection ∶ → , we could combine the symbols ↪ and ↠ and use ↪→. We call injective functions in- jections; Surjective functions surjections, and bijective functions bijections. Some people use the term “one-to-one correspondence” to mean “bijective”, but this is easily confused with “one-to-one” and so we will avoid it. For ∶ → to be a function, it must have the property that, for all , ∈ , if = , then () = (). To be injective, it must have the property that, for all , ∈ , if () = (), then = . That the property of having a unique output for each input and the property of being injective are converses is no accident—we’ll see why when we discuss inverse functions! Here are equivalent formulations of the three terms. Observe that surjectivity is related to a claim about existence and injectivity is related to a claim about uniqueness. Theorem 8.55 (Equivalent formulations). Suppose that ∶ → is a func- tion. Then: (1) ∶ → is injective if and only if for every ∈ there is at most one ∈ with () = . (2) ∶ → is surjective if and only if range = . (3) ∶ → is surjective if and only if for every ∈ there is at least one ∈ with () = . (4) ∶ → is bijective if and only if for every ∈ there is a unique ∈ with () = .
Available until 7 Feb |Learn moreAbstract Algebra
An Inquiry Based Approach
- Jonathan K. Hodge, Steven Schlicker, Ted Sundstrom(Authors)
- 2013(Publication Date)
- Chapman and Hall/CRC(Publisher)
Appendix A Functions Focus Questions By the end of this investigation, you should be able to give precise and thorough answers to the questions listed below. You may want to keep these questions in mind to focus your thoughts as you complete the investigation. • What is a function? • What does it mean to say that a function is an injection? How can we prove that a function is (or is not) an injection? • What does it mean to say that a function is a surjection? How can we prove that a function is (or is not) a surjection? • What is a bijection? • What is the composition of two functions, and what is a composite function? What are some important theorems about composite functions? • What is the inverse of a function? Under what conditions is the inverse of a func-tion f : A → B a function from B to A ? • What are some important theorems about functions and their inverses? Functions are frequently used in mathematics to define and describe certain relationships be-tween sets and other mathematical objects. In this appendix, we will first study special types of functions known as injections and surjections. Before defining these types of functions, we will review the definition of a function and explore certain functions with finite domains. Definition A.1. A function f from a set A to a set B is a collection of ordered pairs { ( a,b ) : a ∈ A and b ∈ B } such that for each element a in A , there is one and only one element in B such that ( a,b ) is in f . There is a special notation, called functional notation , that is commonly used to describe func-tions and the way they act on sets. In particular, if ( a,b ) is in the function f , we write f ( a ) = b (read as “ f of a equals b ”). It is important to note the dual use of the symbol f here; we use f to represent a collection of ordered pairs and also to describe an action (pairing a with b in f ( a ) = b ).
eBook - PDF- Valentin Deaconu, Donald C. Pfaff(Authors)
- 2016(Publication Date)
- Chapman and Hall/CRC(Publisher)
The operation of composition of functions preserves injectivity and surjec- tivity: Theorem 4.45. Let f : Y → Z and let g : X → Y . If f and g are one-to-one functions, then so is f ◦ g : X → Z . If f and g are onto, then f ◦ g : X → Z is also onto. Proof. Assume (f ◦ g)(x) = (f ◦ g)(x ′ ), so f (g(x)) = f (g(x ′ )) for x, x ′ ∈ X . Since f is one-to-one, we get g(x) = g(x ′ ). Since g is one-to-one, we get x = x ′ , hence f ◦ g is one-to-one. Assume now that z ∈ Z . Since f is onto, we can find y ∈ Y with f (y) = z . Since g is onto, there is x ∈ X with g(x) = y. We conclude that (f ◦ g)(x) = z , hence f ◦ g is onto. Exercise 4.46. Prove by counterexample that the converse of each statement of the above theorem is false. Definition 4.47. A function f : X → Y is called bijective if it is one-to-one and onto. Example 4.48. Prove that the function f : R → R, f (x) = x 3 is bijective. Proof. To show that f is one-to-one, assume x 3 = x ′3 for some x, x ′ ∈ R. By taking cubic roots, we get x = x ′ . To show that f is onto, let y ∈ R be arbitrary. Then f ( 3 √ y) = ( 3 √ y) 3 = y, so we found x = 3 √ y ∈ R with f (x) = y. Definition 4.49. We say that a function f : X → Y is invertible (or has an inverse) if there is g : Y → X such that g ◦ f = id X and f ◦ g = id Y . The inverse of f is unique, is denoted f −1 and satisfies f −1 (y) = x ⇔ f (x) = y. Recall that we already used the notation f −1 = f −1 P : P (Y ) → P (X ) for any function f : X → Y and we called it the inverse image function. If f is a bijection, we have f −1 ({y}) = f −1 (y). You must be careful to distinguish from the context between the two meanings of f −1 . We have the following characterization of invertible functions: Theorem 4.50. A function f : X → Y is invertible if and only if it is bijective. 64 A bridge to higher mathematics Proof. If f : X → Y is invertible, let g : Y → X be its inverse. To prove that f is one-to-one, assume f (x 1 ) = f (x 2 ).
eBook - PDF- Corey M. Dunn(Author)
- 2017(Publication Date)
- CRC Press(Publisher)
1 for x ∈ ( −∞ , 0] Both are considered to be extensions of the same function f . squaresolid 1.4.4 Types of functions Although there are many different types of functions within all of mathemat-ics, we focus on three very important types: injective (or one to one), surjective (or onto), and bijective functions. Definition 1.33. Let f : X Y . → 1. The function f is injective (or one-to-one ) if f ( x 1 ) = f ( x 2 ), then x 1 = x 2 . 2. The function f is surjective (or onto ) if for every y ∈ Y there exists an x ∈ X with f ( x ) = y . 3. The function f is bijective if it is both one to one and onto. Here are a couple practice questions illustrating these properties. Practice 1.34. Let f : R R be defined as f ( x ) = x 2 . → (a) Is f ( x ) injective? (b) Is f ( x ) surjective? (c) Find a restriction of the domain of f so that the resulting func-tion is injective. (d) Find a restriction of the range of f so that the resulting function is surjective. Methodology. For Part (a), since there are two different inputs that map to the same output, the function is not injective according to Definition 1.33 – we will need to exhibit such inputs. Since there are outputs that are not targeted by any input, this function is not surjective according to Definition 1.33 –we will have to exhibit such an output and demonstrate that no input is mapped to it by f . There are lots of answers to Part (c) since there are many different restrictions we could choose, although for this particular function, negative numbers are mapped to the same place as their positive counterpart, and so removing the negative numbers from the domain should work. For Part (d), 35 Sets, Functions, and Proofs we observe that any non-negative number has a square root in R , whereas no negative numbers do. So, no negative numbers are targeted by this function and removing them from the range should produce the desired effect. Solution. (a) This function is not injective, since f ( − 2) = f (2) = 4, but 2 = � − 2.
eBook - PDFDiscrete Mathematics
Proof Techniques and Mathematical Structures
- R C Penner(Author)
- 1999(Publication Date)
- WSPC(Publisher)
According to the definitions, / is surjective if for each element of JB, there is some arrow of G terminating at 6, and / is injective if no two distinct arrows of G terminate at a common vertex. The following digraphs of functions illustrate the various possibilities. surjective not injective injective not surjective not surjective not injective surjective injective We next give several examples illustrating these definitions. ■ Example 6.4.1 The function / : {1,2,3} -> {1,2,3} given by / = {(!, 2), (2,2), (3,1)} is not surjective since / does not attain the value 3 for any argument, and it is not injective since /(l) = 2 = /(2). Example 6.4.2 The function / : IN -> IN defined by f(n) = Zn is not 280 Chapter 6 Functions surjective since for instance it does not attain the value 1 for any argument, but it is injective since if /(rii) = /(ri2), then 3ni = 3n 2 , so dividing by 3, we find ni = n>2* ■ Example 6.4.3 Given a < b E I t , let [a, b] denote the closed interval [a, b] = {t € R : a < t < 6} and define the function /:[a,6]->[0,l] t — a t ^ -. b — a The function / is surjective since if x € [0,1], then f(t) = x where t = a + (b — a)x and t € [a, 6] since x G [0,1]. The function / is also injective since if /(£i) = / f o ) , then (ti — a)/(b — a) = (£2 — a )/(& ~~ a )> s o multiplying by b — a and adding a, we find that t = £2. Since / is both injective and surjective, / is a bijection by definition. It is worth saying explicitly here that on a certain level if there is a bijection / : A —>-B, then one imagines the two sets A^B as being the same size, and we shall make this comment precise in the next chapter. For finite sets A and B, if there is a bijection from i to B, then A and B clearly have the same number of elements. Indeed, one may think of a bijection from A to B as simply a relabeling of the the elements B by the elements in A.
eBook - PDF- Owen D. Byer, Deirdre L. Smeltzer, Kenneth L. Wantz(Authors)
- 2018(Publication Date)
- American Mathematical Society(Publisher)
Additionally, since each element in ? is the image of some element of ? , that is , ∀? ∈ ?, ∃? ∈ ?, 𝜙(?) = ?, 𝜙 is surjective. Since 𝜙 is both injective and surjective, 𝜙 is a bijection. (2) In order to see whether ? is injective, we check the definition. Does ? 1 ≠ ? 2 imply sin(? 1 ) ≠ sin(? 2 ) for all ? 1 , ? 2 ∈ ℝ ? Of course not: for example, 0 ≠ 𝜋 , but sin 0 = sin 𝜋 . Hence, ? is not injective. On the other hand, for any ? ∈ [−1, 1] , there exists an ? ∈ ℝ such that sin ? = ? . (We assume this trigonometric fact is well known.) Therefore, by definition, ? is surjective. (3) Suppose ? 1 , ? 2 ∈ ℝ and ?(? 1 ) = ?(? 2 ) . Then 2? 1 − 3 = 2? 2 − 3 , from which it follows that ? 1 = ? 2 . Thus, ? is injective. Given any ? ∈ ℝ , let ? = (? + 3)/2 ∈ ℝ . Then ?(?) = 2((? + 3)/2)) − 3 = ? . Thus, ? is surjective. 116 Chapter 5 Relations and Functions Since ? is both injective and surjective, ? is a bijection. This can be seen in Fig-ure 5.6(a): since the graph passes a “horizontal line test”, ? is injective, and since the projection of the graph onto the ? -axis is all of ℝ , ? is surjective. (4) Suppose ℎ(? 1 ) = ℎ(? 2 ) for some ? 1 , ? 2 ∈ ℝ . As before, we wish to show that this condition forces ? 1 = ? 2 . Because ℎ is piecewise defined, we need to consider several cases. Suppose that one of the values (say, ? 1 ) is negative while the other is nonnegative; then ℎ(? 1 ) = ℎ(? 2 ) means that ? 1 = ? 2 +1 , which is an impossibility. If both ? 1 and ? 2 are negative, then ℎ(? 1 ) = ℎ(? 2 ) means that ? 1 = ? 2 . If both ? 1 and ? 2 are nonnegative, then ℎ(? 1 ) = ℎ(? 2 ) means that ? 1 + 1 = ? 2 + 1 , which again implies that ? 1 = ? 2 . Thus, ℎ is injective. However, note that if ? ∈ (0, 1) , there is no ? ∈ ℝ such that ℎ(?) = ? . Therefore, ℎ is not surjective, since Range(ℎ) contains no elements from the interval (0, 1).
- Susanna Epp(Author)
- 2019(Publication Date)
- Cengage Learning EMEA(Publisher)
Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 7.3 COMPOSITION OF FUNCTIONS 465 You can see from the diagram that f is one-to-one and onto. Thus f 2 1 exists and is found by tracing the arrows backwards, as shown below. Y X f –1 a b c x y z Now f 2 1 + f is found by following the arrows from X to Y by f and back to X by f 2 1 . If you do this, you will see that ( f 2 1 + f )( a ) 5 f 2 1 ( f ( a )) 5 f 2 1 ( z ) 5 a ( f 2 1 + f )( b ) 5 f 2 1 ( f ( b )) 5 f 2 1 ( x ) 5 b and ( f 2 1 + f )( c ) 5 f 2 1 ( f ( c )) 5 f 2 1 ( y ) 5 c . Thus the composition of f and f 2 1 sends each element to itself. So by definition of the identity function, f 2 1 + f 5 I X . In a similar way, you can see that f + f 2 1 5 I Y . ■ More generally, the composition of any function with its inverse (if it has one) is an identity function. Intuitively, the function sends an element in its domain to an element in its co-domain and the inverse function sends it back again, so the composition of the two sends each element to itself. This reasoning is formalized in Theorem 7.3.2. Theorem 7.3.2 Composition of a Function with Its Inverse If f : X S Y is a one-to-one and onto function with inverse function f 2 1 : Y S X , then (a) f 2 1 + f 5 I X and (b) f + f 2 1 5 I Y . Proof: Part ( a ) : Suppose f : X S Y is a one-to-one and onto function with inverse function f 2 1 : Y S X . [To show that f 2 1 + f 5 I X , we must show that for each x [ X , ( f 2 1 + f )( x ) 5 x . ] Let x be any element in X . Then, by definition of composition of functions, ( f 2 1 + f )( x ) 5 f 2 1 ( f ( x )) Let z 5 f 2 1 ( f ( x )). By definition of inverse function, f ( z ) 5 f ( x ) , (continued on page 466) Note Recall that if b is any element of Y , then f 2 1 ( b ) 5 that element a of X such that f ( a ) 5 x .
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
