Injective functions

11 Key excerpts on "Injective functions"

• 

  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)

  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. E XAMPLE 5.8. Let p :  ∗ →  ∗ be the function that appends a 1 to the end of any given string. As examples, p(1101) = 11011 and p(ε) = 1. To prove that this function is injective, let ω 1 and ω 2 be two strings in  ∗ . If p(ω 1 ) = p(ω 2 ), then the string ω 1 1 and the string ω 2 1 are identical. This means that ω 1 and ω 2 are identical strings as well. Exercise 5.6 Determine whether the following functions are injective. (a) f : R + → R + given by f (x) = √ x, where R + is the set of positive real numbers. (b) g : R \ {0} → R \ {0} given by g(x) = 1/x. (c) h : R \ {0} → R \ {0} given by h(x) = 1/x 2 . (d) m :  ∗ → Z[x] given by m(ω) = ω 0 + x ω . As an example, m(10011) = 2 + x 5 . 2 The notation g(a, b) is technically incorrect; the input element is the ordered pair (a, b), so the output should be denoted g((a, b)), as we did in the previous sentence with f . But, in fact, notation like g(a, b) is quite standard, to reduce the number of parentheses in a context where the meaning is clear. 116 5. Functions D EFINITION 5.9. A function f : X → Y is surjective if for each y ∈ Y there exists an x ∈ X such that f (x) = y. 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.

  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 - ePub

  Introduction to Differential Calculus

  Systematic Studies with Engineering Applications for Beginners

  • Ulrich L. Rohde, G. C. Jain, Ajay K. Poddar, A. K. Ghosh(Authors)
  • 2012(Publication Date)
  • Wiley

    (Publisher)

  onto function as discussed below in (A) and (C), respectively.

  A. One–One Function : A function is one-one provided distinct elements of the domain are related to distinct element of the codomain . In other words, a function f : A → B is defined to be one-one if the images of distinct element of A under f are distinct, that is, for every a 1 , a 2 A , f (a 1 ) = f (a 2 ) ⇒ a 1 = a 2 . [It also means that, f (a 1 ) ≠ f (a 2 ) ⇒ a 1 ≠ a 2 .] A one–one function is also called injective function (Figure 2.7a and b ).

  Figure 2.7

  Note: If there is at least one pair of distinct elements, a 1 , a 2 A , such that

  then, such a function is called many–one . We define many-one function as follows:

  B. Many–One Function : If the codomain of the function has at least one element, which is the image for two or more elements of the domain, then the function is said to be many–one function (Figure 2.8a and b ).

  Figure 2.8

  A constant function is a special case of many–one function (Figure 2.9 ).

  C. Onto Function : A function f : A → B is called an onto function if each element of the codomain is involved in the relation .

  Figure 2.9

  Figure 2.10

  Figure 2.11

  (Here, range of f = codomain B .)

  In other words, a function f : A → B is said to be onto if every element of B is the image of some element of A , under f , that is, for every b B , there exist an element a A such that f (a ) = b (Figure 2.10a and b ). Onto function is also called surjective function .

  The most important functions are those which are both one–one and onto . In a function that is one–one and onto, each image corresponds to exactly one element of the domain

  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 - ePub

  Mathematical Foundations of Computer Science

  • Bhavanari Satyanarayana, T.V. Pradeep Kumar, Shaik Mohiddin Shaw(Authors)
  • 2019(Publication Date)
  • CRC Press

    (Publisher)

  (6.1) , we get that

  f

  (

  x + 3

  )

   = 

  (

  x + 3

  )

  2

  − 3

  (

  x + 3

  )

  + 2

   = 

  x 2

  + 6 x + 9 − 3 x − 9 + 2

   = 

  x 2

  + 3 x + 2

  6.2    Types of Functions (including Bijective Functions)

  Definition

  (i)   f : S → T is said to be one-one function (or injective function) if it satisfies the following condition:

  f

  (

  s 1

  )

   =  f

  (

  s 2

  )

   ⇒ 

  s 1

   = 

  s 2

  .

  (ii)   f: S → T is said to be onto function (or surjective function) if it satisfies the following condition:

  t ∈ T ⇒ there corresponds an element s in S such that f(s) = t.

  (iii)   A function is said to be a bijection if it is both one-one and onto.

  Example 6.6

  (i)   f: R → R such that f(x) = 3x + 2 is an one-to-one and onto function.

  (ii)   f: N →{0, 1} such that

  f

  ( x )

   = 

  {

  1 ,

  if   x   is   odd

  0 ,

  if   x   is   even

  is an onto function but not an one-one function.

  (iii)   f: N → N defined by f(x) = x2 + 2. It is an one-one function not an onto function, since there is no x ∈ N such that f(x) = 1.

  (iv)   f: R → R be such that f(x) = | x | where | x | is the absolute value of x. Then f is neither one-one nor onto.

  Theorem 1

  Let X and Y be two finite set with same number of elements. A function f: X → Y is one-to-one if and may is it is onto.

  Proof: Let X = {x1 , x2 , …, xn } and Y = {y1 , y2 , …, yn }. If f is one-to-one then {f(x1 ), f(x2 ), …, f(xn )} is a set of n distinct elements of Y and hence f is onto.

  If f is onto then {f(x1 ), f(x2 ),…, f(xn )} form the entire set Y, so must all be different. Hence f is one-to-one.

  6.2.1    Observation

  From the above theorem, we can understand that if we have a bijection between two finite sets, then the two sets must have same number of elements.

  Example 6.7

  The function σ : Z+ → Z+

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  An Introduction to Proofs with Set Theory

  • Daniel Ashlock, Colin Lee(Authors)
  • 2022(Publication Date)
  • Springer

    (Publisher)

  In general, we prefer to use range to refer to the co-domain, the set the arrow points to in a formal definition of a function (for example the set T when f W S ! T is the function in question). Definition 7.8 Let X; Y; and Z be sets. The composition of two functions f W X ! Y and g W Y ! Z is a function h W X ! Z for which h.x/ D g.f .x// for all x 2 X . We write g ı f for the composition of g with f . The definition of the composition of two functions requires a little checking to make sure it makes sense. Since every point must appear as a first coordinate of an ordered pair in a function, every result of applying f to an element of X is an element of Y to which g can be applied. This means that h is a well-defined set of ordered pairs. Notice that the order of composition is important—if the sets X , Y , and Z are distinct there is only one order in which composition even makes sense. Example 7.9 Suppose that f W N ! N is given by f .n/ D 2n while g W N ! N is given by g.n/ D n C 4. Then .g ı f /.n/ D 2n C 4 while .f ı g/.n/ D 2.n C 4/ D 2n C 8 7.1. MATHEMATICAL FUNCTIONS 89 We now start a series of definitions that divide functions into a number of classes. We will arrive at a point where we can determine if the mapping of a function is reversible, if there is a function that exactly reverses the action of a given function. Definition 7.10 A function f W S ! T is injective or one-to-one if no element of T (no second coordinate) appears in more than one ordered pair. Such a function is called an injection. Example 7.11 X f e Y a b c d 2 1 3 4 5 Shown here is an example of a drawing of an injective function from the set X D f1; 2; 3; 4; 5g to the set Y D fa; b; c; d; e; f g. If we let f W X ! Y be the function shown in the diagram then in the ordered pair notation f D f.1; c/; .2; a/; .3; e/; .4; d/; .5; f /g. As f is an injective function no element in Y appears more than once as the second element in an ordered pair.

  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
• 

  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 - ePub

  A Bridge to Higher Mathematics

  • Valentin Deaconu, Donald C. Pfaff(Authors)
  • 2016(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  4    

  Functions

   

  Many times we deal with quantities which depend on other quantities: the volume depends on the size, the heat index depends on the humidity, the force depends on the mass. These illustrate the idea of a function. In mathematics, a function is a certain rule which associates to any element in a set A , called the domain, a unique element in a set B , called the codomain. You already met real functions of real variables in calculus, like f (x ) = x 2 , g (x ) = ln x or h (x ) = tan x . The domain and the set of values for these functions are subsets of ℝ, and a function is defined as a formula (or algorithm) which associates to each input in the domain a precise output. The domain of f is ℝ and the set of values is [0, ∞). The domain of g is (0, ∞) and the set of values is ℝ. The domain of h is

  R \ {

  ( 2 k + 1 )

  π 2

  : k ∈ Z

  }

  and the set of values is ℝ. We will need to work with more general functions among all kinds of sets, not just subsets of the real numbers.

  Even though a function is a particular case of a relation, we study functions first and define relations in the next chapter. After giving the precise definition of a function using its graph, we introduce operations and give several examples of functions. A given function determines two new functions, called the direct image and the inverse image, where the inputs and the outputs are sets. Sometimes it is necessary to shrink or enlarge the domain of a function, giving rise to restrictions and extensions. We also discuss one-to-one and onto functions, composition, and inverse functions. We conclude with families of sets and the axiom of choice, necessary in many proofs.

  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