The following are some notes taken during a lecture.
Basic Definitions
Definition: Let A and B be nonempty sets. A function f from A to B, denoted f: A → B is an assignment of each element of A to exactly one element of B. We write f(a) = b if b is the unique element of B assigned by the function f to the element a of A.
Functions are sometimes called mappings or transformations.
A function f: A → B can also be defined as a subset of A×B (a relation). This subset is restricted to be a relation where no two elements of the relation have the same first element.
Specifically, a function f from A to B contains one, and only one ordered pair (a, b) for every element a∈ A.
Basic Definitions
- Given a function f: A → B:
- We say f maps A to B or f is a mapping from A to B
- A is called the domain of f
- B is called the codomain of f
- If f(a) = b, then b is called the image of a under f. a is called the preimage of b.
- The range of f is the set of all images of points in A under f. We denote it by f(A).
- Two functions are equal when they have the same domain, the same codomain and map each element of the domain to the same element of the codomain.
Representing Functions
- Functions may be specified in different ways:
- An explicit statement of the assignment.
- Students and grades, for example.
- A formula.
- f(x) = x + 1
- A computer program.
- A Java program that when given an integer n, produces the nth Fibonacci Number.
- An explicit statement of the assignment.
Examples
Injections
Definition: A function f is said to be one-to-one , or injective, if and only if f(a) = f(b) implies that a = b for all a and b in the domain of f. A function is said to be an injection if it is one-to-one.
Surjection
Definition: A function f from A to B is called onto or surjective, if and only if for every element there is an element with. A function f is called a surjection if it is onto.
Bijection
Definition: A function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto (surjective and injective).
Showing that a Function is One-to-One or Onto
Showing that a Set is One-to-One or Onto
Example 1: Let f be the function from {a,b,c,d} to {1,2,3} defined by f(a) = 3, f(b) = 2, f(c) = 1, and f(d) = 3. Is f an onto function?
Solution: Yes, f is onto since all three elements of the codomain are images of elements in the domain. If the codomain were changed to {1,2,3,4}, f would not be onto.
Example 2: Is the function f(x) = x2 from the set of integers to the set of integers onto?
Solution: No, f is not onto because there is no integer x with x2 = −1, for example.
Inverse Functions
Definition: Let f be a bijection from A to B. Then the inverse of f, denoted , is the function from B to A defined as No inverse exists unless f is a bijection. Why?
Examples
Example 1: Let f be the function from {a,b,c} to {1,2,3} such that f(a) = 2, f(b) = 3, and f(c) = 1. Is f invertible and if so what is its inverse?
Solution: The function f is invertible because it is a one-to-one correspondence. The inverse function f-1 reverses the correspondence given by f, so f–1 (1) = c, f–1 (2) = a, and f–1 (3) = b.
Example 2: Let f: Z 🡪 Z be such that f(x) = x + 1. Is f invertible, and if so, what is its inverse?
Solution: The function f is invertible because it is a one-to-one correspondence. The inverse function f-1 reverses the correspondence so f–1 (y) = y – 1.
Example 3: Let f: R → R be such that . Is f invertible, and if so, what is its inverse?
Solution: The function f is not invertible because it is not one-to-one .
Composition of Functions
Definition: Let f: B → C, g: A → B. The composition of f with g, denoted is the function from A to C defined by
Example 2: Let g be the function from the set {a,b,c} to itself such that g(a) = b, g(b) = c, and g(c) = a. Let f be the function from the set {a,b,c} to the set {1,2,3} such that f(a) = 3, f(b) = 2, and f(c) = 1.
What is the composition of f and g, and what is the composition of g and f.
Solution: The composition f∘g is defined by
- 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.
Note that g∘f is not defined, because the range of f is not a subset of the domain of g.
Example 2: Let f and g be functions from the set of integers to the set of integers defined by f(x) = 2x + 3 and g(x) = 3x + 2.
What is the composition of f and g, and also the composition of g and f ?
Solution:
- 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
Graphs of Functions
Some Important Functions
Floor Function
Floor and Ceiling Function
Proving Properties of Functions
Factorial Functions
Definition: f: N → Z+ , denoted by f(n) = n! is the product of the first n positive integers when n is a nonnegative integer.
f(n) = 1 ∙ 2 ∙∙∙ (n – 1) ∙ n, f(0) = 0! = 1
Examples:
f(1) = 1! = 1
f(2) = 2! = 1 ∙ 2 = 2
f(6) = 6! = 1 ∙ 2 ∙ 3∙ 4∙ 5 ∙ 6 = 720
f(20) = 2,432,902,008,176,640,000.
eof