Let A and B be sets. A function Φ : A → B assigns to each element of a (for each a ∈ A or ∀ a ∈ A) exactly one element of B (f(a) ∈ B).The sets A, B are called the domain and codomain of the function respectively. Functions are also called maps or mappings (1.a). A function is just a collection of ordered pairs of the form (a, b) where a ∈ A and b ∈ B that satisfies one condition: every element a in the domain A must be paired with exactly one element b in the codomain B.
A way of representing the set of ordered pairs which define a function is to use one of the notations {(x,y)| y = f(x), x ∈ X} or {(x, f(x))| x ∈ X}.
1.c’s diagram represents the set of pairs {(1, A), (2, B), (3, C), (3, D)}. It does not define a function because: (i) 3 is in more than one ordered pair, (3, C) and (3, D); (ii) 4 is not a first element (input) of any ordered pair.
A function is most often denoted by letters such as f, g, or h. A function takes an input element from the set A (X) and produces an output in the set B (Y). We can image it as some sort of black box, device, or machine that does this transformation (1.b). You put some object into its input funnel, then the function machine will process that object and turn it into some other object, which comes out as output.
Let’s see some examples:
The image or range of a function f: X → Y is simply the set of all possible values it may produce under the mapping or transformation given by f, that is, f(X) = {y | y = f(x), x ∈ X } ⊆ Y. The set of ordered pairs C={(x, y)| y = f(x), x ∈ X} is called the graph of the function and represents a curve in the x, y-plane giving a pictorial representation of the function.
An injective or one-to-one function is a function that maps distinct elements of its domain to distinct elements of its codomain, that is, whenever Φ(a_{a}) = Φ(a_{2}) then a_{1} = a_{2}. In other words, if we pick any element from the codomain, it is either connected to exactly one or no elements from the domain.
f, g: ℝ → ℝ, then f(x) = 2x, and g(x) = 2x+1 are both injective, but x^{2} is not, because f(-1) = 1 = f(1). A monotonic function is a function that is either always increasing or always decreasing on its domain. A strictly monotonic function is injective, since in this case x_{1} < x_{2} implies that f(x_{1}) < f(x_{2}) or f(x_{1}) > f(x_{2}).
A surjective or onto function is a function that for each element in the codomain there is at least one element in the domain that maps to it. Thus, if we choose any element from the codomain, we can find at least one element from the domain that it is connected to. It is one whose image is the entire codomain, that is, for every b ∈ B, there exists a ∈ A such that Φ(a) = b.
For any set X, the identity function id_{X}: X → X, id_{X}(x) = x, ∀ x ∈ X is surjective. f,g: ℝ → ℝ, f(x) = 2x +1 is surjective (∀ y∈ℝ, we have an x(^{y-1}⁄_{}2) such that f(x)=y), but g(x)=x^{2} is not. However, g: ℝ → ℝ^{+}, where ℝ^{+} = {x∈ℝ : x ≥ 0} and g(x)=x^{2} is surjective.
A bijective function is a relation that is both injective and surjective. It is a function that each element in the domain is mapped to exactly one element in the codomain and viceversa. Formally, if Φ(a_{1}) = Φ(a_{2}), then a_{1} = a_{2}, and for every b ∈ Y, there exists a ∈ A such that f(a) = b.
For any set X, the identity function id_{X}: X → X, id_{X}(x) = x, ∀ x ∈ X is bijective. Any lineal function over the reals, f: ℝ → ℝ, f(x) = ax + b, a ≠ 0 is a bijection. g: ℝ → (^{-Π}⁄_{2}, ^{Π}⁄_{2}), given by g(x) = arctan(x) is bijective.
Given two functions f : X → Y and g : Y → Z, the composition g ◦ f : X → Z is defined by (g ◦ f)(x) = g(f(x)) ∀ x ∈ X.
If Z = X, then we can define f ◦ g: Y → Y. However, in general f ◦ g ≠ f ◦ g. If X ≠ Y, that’s pretty obvious, these functions have different domains and codomains, but even in the case X = Y, f ◦ g and f ◦ g will generally not be the same, e.g., f, g: ℝ → ℝ, f(x)=x^{2}, and g(x)=2x+1, f ◦ g = (2x+1)^{2}, g ◦ f = 2x^{2}+1.
If a subset of X x Y is a bijection f, then each x ∈ X appears as the first member of exactly one ordered pair in f and also each y ∈ Y appears as the second member of exactly one ordered pair in f. Therefore, we can interchange the first and second members of all ordered pairs in f to obtain a set of ordered pairs (y, x), and get a new function, aka the inverse function f^{-1}. f^{-1} is also a bijection function, that is, a one-to-one function mapping Y onto X.
Given functions α: A → B, β: B → C, γ: C → D. Then, the following statements hold true:
Definition. The empty set ∅ is finite and has cardinality |∅| = 0. A non-empty set S is called finite and have cardinality |S| = n ∈ N if and only if there exists a bijection from S to {1, 2, . . . n}. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements.
Proof. A function f: X → Y can only be injective if |Y| ≥ |X| since the number of elements in the image f(X) is equal to the number of elements in the domain and f(X)⊆Y.
A function f: X → Y can only be surjective if |Y| ≤ |X|. Therefore, if if is bijective then |Y| = |X|.
However, it will be important to know whether two infinite sets have the same cardinality. Two sets X and Y have the same cardinality if there exists a bijective if and only if there exist a bijection between them, e.g., ℤ (that is, whole numbers, positive, negative, and zeros), and ℤ^{+} (the set of positive members of ℤ) have the same cardinality: 1 ↔ 0, 2 ↔ 1, 3 ↔ -1, 4 ↔ 2, 5 ↔ -2, 6 ↔ 3, 7 ↔ -3, etc. Therefore, |ℤ| = |ℤ^{+}| = χ_{0}. Observe that a proper subset of an infinite set could have the same number of elements as the whole set. Incredible enough, |ℚ| = χ_{0}. If you imagine the fractions to be glued to a string, and pulling it to the left, the string straightens out and all elements of ℚ appear on it in an infinite row as 0, 1/2, -1/2, 1, -1, 3/2, 2/3… (Figure 1.a.)
|ℝ| = χ_{0}? No. Suppose that we’ve created a bijection, producing a list containing every single real number between 0 and 1 in some order. There is a “new” number between 0 and 1 that cannot possible be in the list.
Take the first decimal place of our first number on our list and adds 1 to it (if it was 9, you need to change it to a zero), and use the result as the first decimal place of the new number. Then, take the second decimal place of our second number on our list and adds 1 to it, using the result as the second decimal place of the new number. This process continues infinitely, and the new number won’t be on the list (Figure 1.b.)
Theorem. A function is bijective if and only if has an inverse.
Proof. Let f : A → B be bijective. We will define a function f^{−1}: B → A as follows. Let b ∈ B. Since f is surjective, there exists a ∈ A such that f(a) = b. Let f^{−1}(b) = a.
Since f is injective, this a is unique, so f^{-1} is well-defined.
Now we much check that f^{-1} is the inverse of f. First we will show that f^{-1} ◦ f = Id_{A}.
Let a ∈ A. Let b = f(a). Then, by definition, f^{-1}(b) = a. Then f^{-1} ◦ f(a) = f^{-1}(f(a)) = f^{-1}(b) = a.
Now we will show that f ◦ f^{-1} = Id_{B}. Let b ∈ B. Let a = f^{-1}(b). Then, by definition, f(a) = b. Then f ◦ f^{-1}(b) = f(f^{-1}(b)) = f(a) = b.
Let f : A → B have an inverse. is it bijective?