Functions - 4CCSAMAI Lecture 3 PDF

Functions Given sets A and B, a function from A to B is a rule f that associates with each element of A exactly one element of B. f A  r  ◀ ...

Functions Given sets A and B, a function from A to B is a rule f that associates with each element of A exactly one element of B. f A  r  ◀  B r -r r  1 rX   r XX r XXXX zr XX   If f associates x ∈ A with y ∈ B, then we write f (x) = y and say “f of x is y”, or “f maps x to y”, or the “value of f at x is y”. If f is function from A to B, then we write: f :A→B. We call A the domain of f , and B the codomain of f. every element of the domain has to be mapped somewhere in the codomain (but not everything in the codomain has to be a value of a domain element) one element cannot be mapped to 2 different places (but it can happen that 2 different elements are mapped to the same place) ©A. Kurucz, King’s College London 94  Functions and not functions Let H be the set of all humans, alive or dead. Let’s make some H → H associations and discuss whether each is a H → H function or not. f (x) is a parent of x This f is NOT a function, because people have two parents. f (x) is the mother of x This f is a H → H function, because each person has exactly one mother. f (x) is the oldest child of x This f is NOT a H → H function, because some person has no children. f (x) is the set of all children of x Though this f is a function, it is NOT a H → H function, because each person is associated with a set of people rather than one person. (This f is a H → P (H) function.) ©A. Kurucz, King’s College London 95  Different ways of describing functions F OR EXAMPLE : Let A = {a, b, c} and B = {1, 2, 3}. We can describe a function f : A → B by listing all its associations: f (a) = 1, f (b) = 1, f (c) = 2. We can describe the same f by drawing points and arrows: A B ar -r : 1   b r  :r   2   c r  r3  We can describe the same f by drawing its ‘graph’: B 3 2 s 1 s s A a b c ©A. Kurucz, King’s College London 96  More examples of f : A → B functions A function is a rule. Sometimes we can describe this rule by a single formula: Let A = B = Z. For every x ∈ Z, let f (x) = 6x + 28 Then, for example, f (2) = 6 · 2 + 28 = 40, f (0) = 28, f (−113) = −650,... Sometimes the rule can only be described by case distinction: Let A = B = N. For every n ∈ N, let 2n ,  if n is odd, g(n) = 3n2 + n + 1, if n is even Then, for example, g(4) = 3 · 42 + 4 + 1 = 53, g(3) = 23 = 8,... And the rule does not have to be described by a formula at all: Let A = {E | E is a healthy African elephant} and B = {e | e is an elephant ear}. For every E ∈ A, let ℓ(E) = E’s left ear ©A. Kurucz, King’s College London 97  Some useful functions The floor function ⌊ ⌋ : R → Z assigns to any real number x the largest integer that is less than or equal to x. F OR EXAMPLE : ⌊ 21 ⌋ = 0, ⌊− 32 ⌋ = −2, ⌊3.2⌋ = 3, ⌊9⌋ = 9. The ceiling function ⌈ ⌉ : R → Z assigns to any real number x the smallest integer that is greater than or equal to x. F OR EXAMPLE : ⌈ 31 ⌉ = 1, ⌈− 54 ⌉ = −1, ⌈5.3⌉ = 6, ⌈7⌉ = 7. x − 1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x + 1 ⌊−x⌋ = −⌈x⌉ ⌈−x⌉ = −⌊x⌋ ©A. Kurucz, King’s College London 98  Functions with multiple arguments If the domain of a function f is a Cartesian product A1 ×· · ·×An , we say that f has arity n, or f is an n-ary function, or f has n arguments. In this case, for each n-tuple (x1 ,... , xn ) ∈ A1 ×· · ·×An , f (x1 ,... , xn ) denotes the value of f at (x1 ,... , xn ). x1 - x2 - p f - f (x ,... , x ) p 1 n p xn - A function f with two arguments is also called a binary function. For binary functions, we have the option of writing f (x, y) = z in the form xf y = z (such as, 4 + 5 = 9 instead of +(4, 5) = 9 ). ©A. Kurucz, King’s College London 99  Tuples and sequences are functions A tuple can be thought of as a function. F OR EXAMPLE : The 5-tuple (22, 14, 55, 1, 700) can be thought of as a listing of the values of the function f : {0, 1, 2, 3, 4} → N defined by f (0) = 22, f (1) = 14, f (2) = 55, f (3) = 1, f (4) = 700. Similarly, an infinite sequence of objects can also be thought of as a function. F OR EXAMPLE : Suppose that (b0 , b1 ,... , bn ,... ) is an infinite sequence of objects from a set S. Then this sequence can be thought of as a listing of the values of the function f : N → S defined by f (n) = bn. ©A. Kurucz, King’s College London 100  Functions are special binary relations A function f : A → B can be considered as a relation from A to B : {(a, b) ∈ A×B | f (a) = b} Relations that are also functions have two special properties: for every a ∈ A there is some b ∈ B with (a, b) being in the relation (every element of the domain has to be mapped somewhere in the codomain) and no two ordered pairs in the relation have the same first element (one element cannot be mapped to 2 different places) F OR EXAMPLE : W HY ? {(x, y) ∈ N×N | y = x − 1} is NOT a function. 0 is not mapped {(x, y) ∈ Z×Z | y = x − 1} is a function. f (n) = n − 1 {(x, y) ∈ N×R | x = y 2 } is NOT a function. (25, 5) and (25, −5) are both in {(x, y) ∈ N×N | x = y 2 } is NOT a function. 2 is not mapped {(x, y) ∈ N×N | y = x2 } is a function. f (n) = n2 ©A. Kurucz, King’s College London 101  Properties of functions A function f : A → B is called one-to-one (or injective) if it maps distinct elements of A to distinct elements of B. Another way to say this: f is one-to-one if for all elements x, y in A, if x ̸= y then f (x) ̸= f (y). A function f : A → B is called onto (or surjective) if every element b in B can be obtained as b = f (a) for some a in A. In general, this might not be the case. If f is an A → B function, this just means that for every a ∈ A, we have f (a) ∈ B. But the range of f range(f ) = {f (a) ∈ B | a ∈ A} can be a proper subset of B. A function is called a bijection if it is both one-to-one and onto. ©A. Kurucz, King’s College London 102  Examples ' $ ' $ one-to-one, onto, not onto not one-to-one s1 as Q  Q a sP s2 b s Q Q- s1 PPP Q Q b sP q s3 c sP s2 PP s Q P PP PP  1  PP  P  PPP c s q s4 PP ds  q s3 & % & % ' $ ' $ neither one-to-one, bijection nor onto as 1 s1 a sP s1   P  1 @  P  P b s @ s2 b s  s2  PP q P @ 3    1 @   c s @ - s 3  c s  s3  1   @   d s Rs @ 4 d s  s4 & % & % ©A. Kurucz, King’s College London 103  Bijections and inverses Bijections always come in pairs. If f : A → B is a bijection, then there is a function f −1 : B → A , called the inverse of f defined by f  ◀  q q A  B q@ q q @  q f −1 (b) = a whenever f (a) = b  @ q @ q ▶ f −1 Then f −1 is also a bijection, and we have f −1 f (a) = a, f f −1 (b) = b, for every b ∈ B.

for every a ∈ A, F OR EXAMPLE : Let Odd and Even be the sets of odd and even natural numbers, respectively. Define a function f : Odd → Even by f (n) = n − 1. Then f is a bijection and its inverse f −1 : Even → Odd is defined by f −1 (n) = n + 1. ©A. Kurucz, King’s College London 104  Some important functions For every set A, its identity function idA : A → A is defined by, for all a ∈ A, idA (a) = a Then idA is a bijection and its inverse is itself. Let S be a set. For every subset A ⊆ S, its characteristic function fA : S → {0, 1} is defined by, for all x ∈ S,  1, if x ∈ A, fA (x) = 0, if x ∈ /A Say, if A ⊆ N then fA : N → {0, 1} can be represented by an infinite 0-1 sequence. ©A. Kurucz, King’s College London 105  Describing N → N functions by recursion The factorial function: Basis step: f (0) = 1 and f (1) = 1. Recursive step: If n > 1 then f (n) = f (n − 1) · n. We used to write n! for f (n). The Fibonacci function: Leonardo Fibonacci asked in 1202: Let’s start with a pair of rabbits that needs one month to mature, and assume that every month each pair produces a new pair that becomes productive after one month. How many new pairs are produced each month? Basis step: f (0) = 0 and f (1) = 1. Recursive step: If n > 1 then f (n) = f (n − 2) + f (n − 1). 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,... ©A. Kurucz, King’s College London 106  Combining functions: composition Let g : A → B and f : B → C be functions. The composition of f and g is the function (f ◦ g) : A → C defined by
(f ◦ g)(a) = f g(a) for each a ∈ A. g f A   ◀   ◀  C B    ◀  f ◦g We only define the composition f ◦ g when “codomain of g” = “domain of f ” ! ©A. Kurucz, King’s College London 107  Composition of functions: examples Let X = {a, b, c} and Y = {1, 2, 3}. Let function g : X → X be defined by g(a) = b, g(b) = c, g(c) = a, and function f : X → Y be defined by f (a) = 3, f (b) = 2, f (c) = 1. Then:
(f ◦ g)(a) = f g(a) = f (b) = 2,
(f ◦ g)(b) = f g(b) = f (c) = 1,
(f ◦ g)(c) = f g(c) = f (a) = 3.
(g ◦ g)(a) = g g(a) = g(b) = c,
(g ◦ g)(b) = g g(b) = g(c) = a,
(g ◦ g)(c) = g g(c) = g(a) = b. Watch out: f ◦ f and g ◦ f are not defined! ©A. Kurucz, King’s College London 108  Properties of composition Even if both are defined, f ◦ g and g ◦ f can be different: Let f and g be both Z → Z functions, defined by f (x) = 2x + 3 and g(x) = 3x + 2. Then:
(f ◦ g)(x) = f g(x) = f (3x + 2) = 2(3x + 2) + 3 = 6x + 7,
(g ◦ f )(x) = g f (x) = g(2x + 3) = 3(2x + 3) + 2 = 6x + 11. ◦ is associative: f ◦ (g ◦ h) = (f ◦ g) ◦ h If f : A → B is a bijection then f −1 ◦ f = idA and f ◦ f −1 = idB For any function f : A → B, f ◦ idA = idB ◦ f = f ©A. Kurucz, King’s College London 109  Comparing finite sets It is not hard to compare the sizes of finite sets: we simply count the number of elements in each. If finite sets have the same number of elements, then there is always a bijection between them. '$ '$ '$ a s - s - s⋆ 1 b s - s - s◁ 2 c s - s - s+ 3 d s - s - s2 4 e s - s - s3 &% &5 % &% ©A. Kurucz, King’s College London 110  And infinite sets? Idea: Two infinite sets have the same size if there is bijection between them. We call a set A countable if it is either finite or there is a bijection between A and N. F OR EXAMPLE : As idN : N → N is a bijection, N is countable. Let Odd be the set of odd natural numbers. Strangely enough, even if Odd ⊂ N, it has the same size as N: The function f : N → Odd defined by f (x) = 2x + 1 is a bijection. ©A. Kurucz, King’s College London 111  N×N is countable We need to describe a bijection between N×N and N. We arrange the ordered pairs in N×N in such a way that they can be easily counted: (0, 0) ←→ 0, (0, 1), (1, 0), ←→ 1, 2, (0, 2), (1, 1), (2, 0), ←→ 3, 4, 5, (0, 3), (1, 2), (2, 1), (3, 0), ←→ 6, 7, 8, 9,...... We can describe this N×N → N bijection by
(m, n) ←→ 1 + 2 + · · · + (m + n) + m. ©A. Kurucz, King’s College London 112  But not all sets are countable The power set P (N) of N is NOT countable: There is NO bijection between N and P (N) In other words, there are more subsets of numbers than numbers. W HY ? We show that for any function f , if f : N → P (N) then f is not onto: So let f : N → P (N) be an arbitrary function. Then, for every n ∈ N, we have f (n) ∈ P (N), so f (n) is a subset of N. Now take the following subset Df of N: Df = {n ∈ N | n ∈ / f (n)} We show that Df is not in the range of f , that is, for every n ∈ N, Df ̸= f (n) : Take an arbitrary n ∈ N. Then there are two cases, either n ∈ Df or n ∈ / Df. If n ∈ Df , then n should have the property describing Df , so n ∈ / f (n) ; Df ̸⊆ f (n) If n ∈ / Df , then the property describing Df does not hold for n, so n ∈ f (n) ; f (n) ̸⊆ Df ©A. Kurucz, King’s College London 113