Bijective Functions

7 Key excerpts on "Bijective Functions"

• 

  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)

  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 and each element of codomain is involved in the relation as shown in Figure 2.11 .

  Such a function is also called one-to-one correspondence or a bijective function.

  D. Bijective Function (or One-to-One Correspondence) :

  Definition (1): Consider a function f : A → B with “A ” as the domain of definition (i.e., the admissible set of the values of x ) and “B ” as the range (i.e., the set of corresponding values of y ).

  We say that the function y = f (x ) specifies a mapping of the set “A ” onto the set B: if two different points of the set A, there correspond different points of the set B , and the entire set B is the range of “f ”. Such a mapping is called one-to-one onto mapping.5

  Definition (2): Let A and B be two nonempty sets. A rule f , which, associates with each element “a ” of the set A, exactly one element “b ” of the set B, and under which, each element “b ” of set B corresponds to exactly one element “a ” of the set A , is called a one-to-one correspondence between the sets A and B .6

  Example (1): Consider the function y = f (x ) = x 3 . Here, for every value of x R , there corresponds a single value of y , and, conversely, to each y R , there corresponds a single value of x given by . Therefore, f specifies a one-to-one mapping, from R onto R .

  Example (2): Consider the function y = g (x ) = x 2 . Here, for every value of x R , there corresponds a single value of y (0, ∞). However, to every y > 0, there correspond two values of x : x = ± . Therefore, “g ” is not one-to-one correspondence .

  Example (3): Consider the exponential function y = f (x ) = ex . It can be shown that the function f (x ) = ex is one-to-one mapping from (−∞, ∞) onto (0, ∞). Note that for x 1 x 2 , we have , where x 1 , x 2 R , and R + . Consider ≠ 1 ⇒ ≠ 1 or ≠ e0 (since ) ⇒ x 1 − x 2 ≠ 0 ⇒ x 1 ≠ x 2 . In other words, ⇒ x 1 x 2 . Thus, x 1 ≠ x 2

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

  Understanding Real Analysis

  • Paul Zorn(Author)
  • 2017(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Functions come in many varieties. We will now define and illustrate, mainly using “toy” functions, some properties a given function may or may not have.

  Definition 1.8 (One‐to‐one functions). A function f : A → B is one ‐to ‐one (or injective ) if f (a 1 ) ≠ f (a ) whenever a 1 and a 2 are in A and a 1 ≠ a 2 . In equivalent words : f maps different inputs to different outputs. In equivalent symbols :

  Convince yourself of the equivalence.

  f

  (

  a 1

  )

  = f

  (

  a 2

  )

  ⇒

  a 1

  =

  a 2

  .

  The next two examples will help illustrate the meaning of—and how to prove or disprove—injectivity.

  EXAMPLE 3.

  The BIRTH MONTH function from Example 2 is not one‐to‐one, because BIRTH MONTH (Bob) = B IRTHMONTH (Carol) = December, even though

  Bob ≠ Carol. By contrast, MONTH NUMBER , which maps each month to its number in the year, is one‐to‐one. The inclusion” function i :

  Q → R

  with rule i (x ) = x is one‐to‐one, since outputs are inputs. The constant function c :

  R → R

  with rule c (x ) = 3 is at the opposite extreme—all inputs are mapped to the same output.

  Finding even one pair of inputs that give the same output is enough.

  The linear function L :

  R → R

  given by L (x ) = 3x + 5 is also one‐to‐one. To prove this, let’s check the equation in Definition 1.8, using some algebra:

  L

  (

  x 1

  )

  = L

  (

  x 2

  )

  ⇒ 3

  x 1

  + 5 = 3

  x 2

  + 5 ⇒ 3

  x 1

  = 3

  x 2

  ⇒

  x 1

  =

  x 2

  ,

  as desired.

  ♢

  Definition 1.9 (Onto functions). A function f : A → B is onto (or surjective ) if, for every b ∊ B , there is some a ∊ A with f (a ) = b . In equivalent words : Every element of the codomain is also in the range. In equivalent symbols :

  using “onto” as an adjective sounds ugly, but everybody does it.

  { f ( a ) | a ∈ A } = B .

  Example 4. The function BIRTH MONTH from Example 2 is not onto, because no member of P was born in (say) March. The function MONTH NUMBER : A → Finding even one such N 12 is onto, because the 12 months range in number from 1 to 12. The “inclusion” codomain member i s enough. i :

  Q → R

  with rule i (x ) = x

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Discrete Mathematics with Ducks

  • sarah-marie belcastro(Author)
  • 2018(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  in the target. (Every element of the domain lands on exactly one corresponding element of the target, so one can recover the domain by going backwards along the arrows.)

  Example 1.5 [of a function that is one-to-one but not onto] Let

  f : Z → Z

  be defined by

  f ( k ) = 2 k

  . Notice that f is not onto because

  3 ∈ Z

  is not the image of any

  k ∈ Z

  . (If there were such a k , then

  k =

  3 2

  ∉ Z

  .) On the other hand, f is one-to-one, and we’ll prove it: Let

  f

  (

  k 1

  )

  = f

  (

  k 2

  )

  . Using the definition of f , this becomes

  2

  k 1

  = 2

  k 2

  , and dividing through by 2 we obtain

  k 1

  =

  k 2

  as desired.

  Example 1.6 [of a function that is onto but not one-to-one] Let

  g : N ×

  Z 2

  → W

  be defined by

  g ( n , d ) = n · d

  . Notice that for any

  n ∈ N

  , the element (n , 0) maps to 0. Therefore, g is not at all one-to-one. However, it is onto: any element of

  W

  is either 0 or an element of

  N

  . We just saw that plenty of elements of

  N ×

  Z 2

  map to 0, so consider

  n ∈ N

  . Then

  g ( n , 1 ) = n

  , so given any

  w ∈ W

  , we have found an element (n , d ) of

  N ×

  Z 2

  such that

  g ( n , d ) = w

  .

  Example 1.7 [of a bijection] We will modify Example 3.2.5 to produce a bijection. Let

  f : Z → 2 Z

  be defined by

  f ( k ) = 2 k

  . Our proof of injectivity still holds, so we just have to prove that this map is surjective. Consider any

  z ∈ 2 Z

  . Then let

  k =

  z 2

  , so that

  f

  ( k )

  = f

  (

  z 2

  )

  = 2

  z 2

  = z

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Elementary Point-Set Topology

  A Transition to Advanced Mathematics

  • Andre L. Yandl, Adam Bowers, Adam Bowers(Authors)
  • 2016(Publication Date)
  • Dover Publications

    (Publisher)

  Y .

           Let f : X → Y be a function. If A ⊆ X is a subset of the domain of f, then the image of A is denoted f(A) and is defined to be the set

  If B ⊆ Y is a subset of the codomain of f, then the inverse image (or preimage) of B is denoted f–1 (B) and is defined to be the set

  It is important to note that the notation f–1 (B) does not imply that the inverse function f–1 is defined, because f may not be one-to-one.

           It is common in the literature to see other terms for functions that are onto or one-to-one. A function that is onto is sometimes called a surjection, a function that is one-to-one is also known as an injection, and a function that is both an injection and a surjection is called a bijection. Such functions are said to be surjective, injective, and bijective, respectively.

  Example 3.1.1. Let be the set of real numbers and define a function f : → by f(x) = x2 for x ∈ .

  (a)     Show that f is neither onto nor one-to-one.

  (b)     Find f ({−3, −1, 2, 4}), the image of the set {−3,−1, 2, 4}.

  (c)     Find the preimages: f–1 ([4, 9]), f–1 ([–1, 9]) and f–1 ([–4, –1])

  Solution. (a) The range of f is contained in the interval [0, ∞) because x2 ≥ 0 for all real numbers x. Since [0, ∞) is a proper subset of , the function f is not onto. To see that the range of f is [0, ∞), simply observe that if x ≥ 0, then and . Finally, note that f is not one-to-one because f(–2) = 4 = f(2), but –2 ≠ 2.

           (b)     By definition,

           (c)     We use the definition of the preimage:

  Notice that the last preimage is the empty set because x2 ≥ 0 for all x ∈ .

  Example 3.1.2. Let be the set of real numbers and define a function g : → by g(x) = 3x + 2 for x ∈ .

  (a)     Show that g is onto and one-to-one.

  (b)     Find a formula for g–1 (x).

  Solution. (a) Let c ∈ . Solve the equation 3x + 2 = c for x and get . Because

  it follows that g is onto. To see that g is one-to-one, observe that

           (b)     In (a), we showed g was one-to-one and onto. Consequently, the inverse function g–1 exists and for each x ∈ , we have g(g–1 (x)) = x

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Introduction to Abstract Algebra

  • Jonathan D. H. Smith(Author)
  • 2015(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  ∅ on the empty set. The absolute value function abs : ℤ → ℕ of (2.2) is surjective, while the absolute value function

  abs : Z → Z ; n ↦

  | n |

  (2.19)

  is not, since the equation

  | n | = − 5

  has no solution n . This shows why the codomain is an integral part of the specification of a function.

  PROPOSITION 2.15 (Sections of surjective functions.)

  Let f : X → Y be surjective. Then there is a function

  s : Y → X

  (2.20)

  such that

  f   ο   s =

  id Y

    .

  (2.21)

  PROOF    If X is empty, then so is Y , and f is just the identity function id∅ . In this case, s = id∅ makes (2.21) work. Now suppose that X is nonempty. For an element y of Y , there is an element x of X such that f (x ) = y . Choose the function value s(y) as one such element

  xy

  . Then a function s : Y → X is defined. For each element y of Y , we have

  f   ο   s

  ( y )

  = f

  ( s

  ( y )

  )

  = f

  (

  x y

  )

  = y =

  id Y

   

  ( y )

  ,

  verifying (2.21).

  DEFINITION 2.16 (Sections.)

  A function s : Y → X is called a section ofa function f : X → Y if f ο s = idy .

  PROPOSITION 2.17 (Functions with sections are surjective.)

  If a function f : X → Y has a section, then it is surjective.

  PROOF    Let s : Y → X be a section for f . Then

  f

  ( s

  ( y )

  )

  = f   ο   s

  ( y )

  =

  id Y

  ( y )

  = y

  for each element y of Y .

  Proposition 2.15 shows that each surjection has a section. Note that a surjection f might have many sections, because of the arbitrary choice of the elements x y in the proof of the existence of the section (Exercise 23 ).

  2.6   Isomorphisms

  DEFINITION 2.18 (Bijective function, isomorphism of sets.)

  A function f : X → Y is said to be bijective, or an isomorphism (of sets), or a bijection, if it is both injective and surjective.

  PROPOSITION 2.19 (Inverses of isomorphisms.)

  Let f : X → Y be a bijection. Then there is a function

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  A Bridge to Higher Mathematics

  • Valentin Deaconu(Author)
  • 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