Bijective Functions

11 Key excerpts on "Bijective Functions"

• 

  eBook - PDF

  Introduction to Mathematics

  • 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 () = .

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  CounterExamples

  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 ).

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Exploring Mathematics

  An Engaging Introduction to Proof

  • John Meier, Derek Smith(Authors)
  • 2017(Publication Date)
  • Cambridge University Press

    (Publisher)

  You can also use complements to construct another map from A to P (A): let g : A → P (A) with g(a) = A − {a}. As an example, consider the set A = {Ole, Lena, Sven}. Then f (Lena) = {Lena} and g(Lena) = {Ole, Sven}. The range of f is {{Ole}, {Lena}, {Sven}} , while the range of g is {{Ole, Lena}, {Lena, Sven}, {Sven, Ole}} . 5.3 Injective, Surjective, and Bijective 115 (e) The function f : A × B → A with f ((a, b)) = a is often called a projection, in this case a projection onto the first coordinate. The function g(a, b) = b is the projection onto the second coordinate; 2 its range is B. (f) The function f : A → A × A with f (a) = (a, a) is often called a diagonal. To see why this name is appropriate, set A = [0, 1] and sketch the points in the subset {(a, a) | a ∈ [0, 1]} of the plane R 2 . Exercise 5.5 Determine which of the following are functions with the given domains and codomains. (a) f : Z → N with f (x) = |x|. (b) f : Z → N with f (x) = |x| + 1. (c) f : R → R with f (x) = √ x 2 − x + 1. (d) f : Z → R with f (x) = √ x 2 − x + 1. (e) f : Z → Z with f (x) = x 2 − x + 1. (f) f : Z → N with f (x) = x 2 − x + 1. (g) f : R → R + with f (x) = x 2 − x + 1, where R + is the set of positive real numbers. 5.3. Injective, Surjective, and Bijective The core vocabulary of functions includes the adjectives injective, surjective, and bijective. D EFINITION 5.6. A function f : X → Y is injective if for all x 1 , x 2 ∈ X, f (x 1 ) = f (x 2 ) implies x 1 = x 2 . Put another way, f is injective if no two distinct xs have the same image. An injective function is also called one-to-one. The claim that a function is injective is sometimes encoded by the symbol  →, as in f : X  → Y and X f  → Y . E XAMPLE 5.7. The function f : Z → Z given by f (x) = 3x is injective for the following reason: for any x 1 , x 2 ∈ Z, having f (x 1 ) = f (x 2 ) means that 3x 1 = 3x 2 , which gives x 1 = x 2 upon dividing both sides by 3.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Discrete Mathematics

  Proofs, Structures and Applications, Third Edition

  • Rowan Garnier, John Taylor(Authors)
  • 2009(Publication Date)
  • CRC Press

    (Publisher)

  We have already seen in example 5.7.1 that f : R → R , x 7 → x 2 , is neither injective nor surjective. Thus the properties of a function depend crucially on its domain and codomain as well as the ‘rule of association’. In particular, the statement ‘the function f ( x ) = x 2 is bijective’ is ambiguous at best and meaningless at worst. 3. Let E + = { 2 n : n ∈ Z + } denote the set of even positive integers and consider the function f : Z + → E + defined by f ( n ) = 2 n . Now f ( n ) = f ( n 0 ) ⇒ 2 n = 2 n 0 ⇒ n = n 0 , so f is injective, and if m ∈ E + then n = m/ 2 ∈ Z + and f ( n ) = m , so f is surjective. Therefore f is a bijection. 4. Let f be the function R 2 → R 2 defined by f ( x, y ) = (2 x -3 y, x -2 y ) . Show that f ◦ f = id R 2 and deduce that f is a bijection. Solution Let ( x, y ) ∈ R 2 . Then ( f ◦ f )( x, y ) = f (2 x -3 y, x -2 y ) = (2(2 x -3 y ) -3( x -2 y ) , (2 x -3 y ) -2( x -2 y )) = ( x, y ) . Therefore f ◦ f = id R 2 . We can use this property to prove that f is both injective and surjective. Let ( x, y ) , ( x 0 , y 0 ) ∈ R 2 . Then: f ( x, y ) = f ( x 0 , y 0 ) f ( f ( x, y )) = f ( f ( x 0 , y 0 )) ⇒ ( f ◦ f )( x, y ) = ( f ◦ f )( x 0 , y 0 ) ⇒ ( x, y ) = ( x 0 , y 0 ) ⇒ so f is injective. To show that f is surjective, let ( a, b ) ∈ R 2 and define ( x, y ) = f ( a, b ) . Then f ( x, y ) = f ( f ( a, b )) = ( f ◦ f )( a, b ) = ( a, b ) so f is surjective. The properties of injections and surjections given in theorems 5.2, 5.3 and 5.5 immediately imply the following results. 262 Functions Theorem 5.6 Let f : A → B be a function where A and B are subsets of R . Then f is bijective if and only if every horizontal line through a point of B meets the graph of f exactly once. Theorem 5.7 (i) The composite of two bijections is a bijection. (ii) If f : A → B is a bijection, where A and B are finite sets, then | A | = | B | .

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  A Bridge to Higher Mathematics

  • 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 ).

  Sign up to read

  Learn more about book
• 

  Available until 7 Feb |Learn more

  Abstract 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 ).

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Discrete Mathematics

  Proof Techniques and Mathematical Structures

  • R C Penner(Author)
  • 1999(Publication Date)
  • WSPC

    (Publisher)

  (b) Describe an extension of the function / : IN -> {0,1} defined by f(n) = 0 if n is even and f(n) = 1 if n is odd to the superset H D IN of the domain. 3. Prove that if A' C A is proper, then the restriction of the identity map 1A : A -> A to A' is not the identity map 1,4'. 4. Suppose that A' C A, let i : A' — > A denote the inclusion map, and suppose that / : A — > B is a function. Prove that / | A' = / ° *• 5. Suppose that B C B' y let j : B -> £?' denote the inclusion map, and suppose that / : A — ) ► £ is a function. Prove that the function obtained from / by extending the codomain to B' is j o f. 6.4 INJECTIVITY, SURJECTIVITY, AND BIJECTIVITY This section is dedicated to the study of certain special conditions on functions of truly basic importance, as follows: If / : A -» B is a function, then we say that 6.4 Injectivity, Surjectivity, and Bijectivity 279 / is surjective or onto if for each b G B, there is some a G A so that f(a) — b. Dually, we say that / is injective or one-to-one or monic if whenever a,a f G A satisfy a ^ a', then we have f(a) ^ /(a'). In other words, / is injective if and only if Va, a' G A[f(a) = f(a f ) =$> a = a f ]. Furthermore, if / is both surjective and injective, then we say that / is bijective. A surjective function is called simply a surjection or an epimorphism, an injective function is called simply an injection or a monomorphism, and a bijective function is called simply a bijection or a one-to-one correspondence. Let G be the digraph associated with the function / : A —► B as before consisting of disjoint copies of vertices corresponding to elements of A and B together with one arrow starting at a and ending at b for each ordered pair (a, b) G / . 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.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Introduction to Analysis

  • 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.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Algebra and Number Theory

  An Integrated Approach

  • Martyn R. Dixon, Leonid A. Kurdachenko, Igor Ya Subbotin(Authors)
  • 2011(Publication Date)
  • Wiley

    (Publisher)

  Generally we will only consider situations when both of the sets A and B are nonempty. 1.2.6. Definition. The mappings f : A — > B and g : C — > D are said to be equal if A = C, B = D and f(a) = g (a) for each element a e A. We emphasize that if the mappings / and g have different codomains, they are not equal even if their domains are equal and f(a) = g (a) for each element a G A. 1.2.7. Definition. Let f : A — > B be a mapping. (i) A mapping f is said to be injective (or one-to-one) if every pair of distinct elements of A have distinct images. (ii) A mapping f is said to be surjective (or onto) iflmf = B. (iii) A mapping f is said to be bijective if it is injective and surjective. In this case f is a one-to-one correspondence. The following assertion is quite easy to deduce from the definitions and its proof is left to the reader. 1.2.8. Proposition. Let f : A — > B be a mapping. Then (i) / is injective if and only if every element of B has at most one preimage; 12 ALGEBRA AND NUMBER THEORY: AN INTEGRATED APPROACH (ii) / is surjective if and only if every element of B has at least one preimage; (iii) / is bijective if and only if every element of B has exactly one preimage. To say that / : A — > B is injective means that if x, y e A and x y then f(x) f(y). Equivalently, to show that / is injective we need to show that if f(x) = f(y) then x — y. To show that / is surjective we need to show that if b e B is arbitrary then there exists a e A such that f{a) — b. More formally now, we say that a set A is finite if there is a positive integer n, for which there exists a bijective mapping A — > {1, 2 , . . . , n}. In this case the positive integer n is called the order of the set A and we will write this as A = n or Card A = n. By convention, the empty set is finite and we put |0| = 0 . Of course, a set that is not finite is called infinite. 1.2.9. Corollary. Let A and B be finite sets and let f : A — > B be a mapping.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Journey into Discrete Mathematics

  • 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).

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Discrete Mathematics with Applications, Metric Edition

  • Susanna Epp(Author)
  • 2019(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  452 CHAPTER 7 PROPERTIES OF FUNCTIONS Definition A one-to-one correspondence (or bijection ) from a set X to a set Y is a function F : X S Y that is both one-to-one and onto. A Function from a Power Set to a Set of Strings Let 3 ({ a , b }) be the set of all subsets of { a , b } and let S be the set of all strings of length 2 made up of 0’s and 1’s. Then 3 ({ a , b }) 5 { [ , { a }, { b }, { a , b }} and S 5 {00, 01, 10, 11}. Define a function h from 3 ({ a , b }) to S as follows: Given any subset A of { a , b }, a is either in A or not in A , and b is either in A or not in A . If a is in A , write a 1 in the first position of the string h ( A ); otherwise write a 0 there. Similarly, if b is in A , write a 1 in the second position of the string h ( A ); otherwise write a 0 there. This definition is summarized in the following table. h Subset A of { a , b } Status of a in A Status of b in A String h ( A ) in S [ not in not in 00 { a } in not in 10 { b } not in in 01 { a , b } in in 11 Is h a one-to-one correspondence? Solution The arrow diagram shown in Figure 7.2.6 shows clearly that h is a one-to-one correspondence. It is onto because each element of S has an arrow pointing to it. It is one-to-one because each element of S has no more than one arrow pointing to it. { a } { b } { a , b } 00 10 01 11 S h ({ a , b }) FIGURE 7.2.6 ■ A String-Reversing Function Let T be the set of all finite strings of x ’s and y ’s. Define g : T S T by the following rule: For each string s [ T , g ( s ) 5 the string obtained by writing the characters of s in reverse order. Is g a one-to-one correspondence from T to itself? Solution The answer is yes. To show that g is a one-to-one correspondence, it is neces-sary to show that g is one-to-one and onto. To see that g is one-to-one, suppose that for some strings s 1 and s 2 in T , g ( s 1 ) 5 g ( s 2 ). [We must show that s 1 5 s 2 . ] Now to say that g ( s 1 ) 5 g ( s 2 ) is the same as saying that the string Example 7.2.8 Example 7.2.9 Copyright 2020 Cengage Learning.

  Sign up to read

  Learn more about book