Given two functions f : X → Y and g : Y → Z, the composition of both of them is a new function that is formed by applying one function to the output of the other function (kind of “chain reaction”) 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 function, e.g., f, g: ℝ → ℝ, f(x)=x^{2}, and g(x)=2x+1, f ◦ g = (2x+1)^{2} = 4x^{2} + 4x + 1 ≠ 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.
We say that f is invertible if there exists a function f^{-1}: Y → X, called the inverse of f, such that f^{-1}∘f = id_{X} and f∘f_{-1} = id_{Y}. When inverse functions exist, they are unique. A bijective function is always invertible.
Examples: f: ℝ → ℝ, defined by f(x) = x^{3} and g: ℝ → (0, ∞), defined by g(x) = e^{x} are both invertible, real-valued functions, and their inverse functions are f^{-1}: ℝ → ℝ, f^{-1}(x)=$\sqrt[3]{x}$ and g^{-1}: (0, ∞) → ℝ, g^{-1}(x) = ln(x) respectively. On the other hand, x^{2} and cos(x) are not invertible.
f·f^{-1}(x)=$(\sqrt[3]{x})^3=x=id$
Given functions f: A → B, g: B → C, h: C → D. Then, the following statements hold true:
Proof
Let a ∈ A, [(h·g)·f] (a) = (h·g)(f(a)) = h(g(f(a))) = h((g·f)(a)) = [h·(g·f)] (a)∎
Proof.
Let c ∈ C ⇒ [g is onto] ∃b ∈ B: g(b) = c ⇒ [f is onto] ∃a ∈ A: f(a) = b. Therefore, ∃a ∈ A: (g·f)(a) = g(f(a)) = g(b) = c ∎
Proof.
Suppose (g.f)(a) = (g·f)(b) ⇒ g(f(a)) = g(f(b)) ⇒ [g is one-to-one] f(a) = f(b) ⇒ [f is one-to-one] a = b∎
Proof. If f and g are both bijective, then they are both one-to-one and onto ⇒ g.f is both one-to-one and onto ⇒ g is bijective.
Proof. Let A, B and C be sets such that g: A → B and f: B → C.
If f·g expresses the process or idea of putting one’s socks (g), then putting on one’s shoes (f), (f·g)^{-1}=g^{-1}·f^{-1} refers to the reverse process of undressing, which is taking off one’s shoes (f^{-1}), immediately followed by taking off one’s socks (g^{-1}).
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 obviously f(X)⊆Y.
A function f: X → Y can only be surjective if (By definition, a function is a collection of ordered pairs of the form (a, b) that satisfies one condition: every element a in the domain A must be paired with exactly one element b in the codomain B. ) |Y| ≤ |X|. Therefore, if f 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 and only if there exist a bijection between them, e.g., ℤ (that is, whole numbers, positive, negative, and zeros), and ℤ^{+} (the set of positive elements of ℤ) have the same cardinality: 1 ↔ 0, 2 ↔ 1, 3 ↔ -1, 4 ↔ 2, 5 ↔ -2, 6 ↔ 3, 7 ↔ -3, etc. Therefore, |ℤ| = |ℤ^{+}| = χ_{0}.
For any sets A, B, and B, the following statements are true: |A| = |A| (f: A → A, f(x) = x is bijective, that is, f = Id_{A}). If |A| = |B|, then |B| = |A| (if f: A → B is a bijection ⇒ f^{-1}: B → A is a bijection, too). If |A| = |B| and |B| = |C|, then |A| = |C| (if f: A → B and g: B → C are bijections, then g∘f: A → C is a bijection, too.)
X has cardinality less than or equal to the cardinality of Y, |X| ≤ |Y| if there exists an injective function from X into Y. X has cardinality strictly less than the cardinality of Y, |X| < |Y|, if there is an injective function, but no bijective function, from X to Y.
For any sets A, B, and C: |A| ≤ |A| (f: A → A, f(x) = x is bijective, that is, f = Id_{A}). If |A| ≤ |B| and |B| ≤ |C|, then |A| ≤ |C| (if f: A → B and g: B → C are injections, then g∘f: A → C is an injection, too.) Either |A| ≤ |B| or |B| ≤ |A| (it is not trivial). Cantor - Bernstein - Schroeder. If A and B are sets where |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|.
Cantor’s Theorem. Let A be a set, and P(A) be its power set. Then. |A| < |$\mathbb{P(A)}$|. Recall that for any set A, the power set of A, written $\mathbb{P(A)}$, is the collection of all subsets of A.
Proof. If A is a finite set, it is enough to recall that |P(A)| = 2^{|A|}.
Let A be an arbitrary, possible infinite, set. We can define an injection f: A → P(A), f(a) = {a}, and therefore |A| ≤ |$\mathbb{P(A)}$|.
For the sake of contradiction, let f: A → P(A) be a bijection. Let D = {a ∈ A: a ∉ f(a)}. Of course, D ⊆ A ⇒ [f is a bijection (we only really need that f is a surjection)] ∃y ∈ A: f(y) = D. The big fat ugly question: is y ∈ D?
Therefore, no such bijection is possible ⇒ |A| < |$\mathbb{P(A)}$|∎
Observe that a proper subset of an infinite set could have the same number of elements as the whole set. Maybe it is hard to believe but, |ℚ| = χ_{0}. If you imagine the fractions to be glued or stuck to a cord or a string, and pulling it to the left, the string straightens out and all rational elements appear on it in as an infinite row as 0, 1/2, -1/2, 1, -1, 3/2, 2/3… (Figure 1.a.)
Theorem. There exists no bijection f: ℕ → ℝ, and therefore |ℕ| ≠ |ℝ|. This is a first indication of how there are different kinds of infinite.
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, because of how we have constructed it (e.g., 0.25904···), won’t be on the list (Figure 1.b.)
Exercises:
$f(n) = \begin{cases} \frac{n}{2}, &n~ mod~ 2 = 0 \\ -\frac{n+1}{2}, &n~ mod~ 2 ≠ 0 \end{cases}$
We need to show that there is a bijective function f: (0, ∞) → (0, 1).
Consider the interval (0, ∞) as the positive x-axis and the interval (0, 1) on the y-axis of ℝ^{2}, so they are both perpendicular to each other as illustrated in Figure 1.a.
Let’s define geometrically f(x) to be the point on the interval (0, 1) where the line from the point P(-1, 1) to x ∈ (0, ∞) intersects the y -axis. By similar triangles formulas (Recall: two triangles are similar if their corresponding angles are equal and their corresponding sides are in the same ratio), we have $\frac{1}{x+1}=\frac{f(x)}{x}↭f(x)=\frac{x}{x+1}$. It is left to the reader to demonstrate that f is bijective.
Definition. Let A be an arbitrary set. Then, A is said to be countable infinite if |ℕ| = |A|, that is, if there exists a bijection f: ℕ → A. A is said to be uncountable if A is infinite and |ℕ| ≠ |A|, that is, if there exists no bijection f: ℕ → A.
If A is countable infinite, there exists a bijection f: ℕ → A, it allows us to list out the set A as an infinite list f(1), f(2), f(3), ···, i.e., the set A’s elements can be arranged in an infinite list a_{1}, a_{2}, a_{3}, ···
Theorem. If A and B are both countable infinite, then so is A x B and A ∪ B. More generally, given n countable infinite A_{1}, A_{2}, ···, A_{n}, the Cartesian product A_{1} x A_{2} x ··· x A_{n} is also countable infinite.
Proof.
Suppose A and B are both countable infinite, we can rewrite A and B in list form as follows, A = {a_{1}, a_{2}, a_{3}, ···} and B = {b_{1}, b_{2}, b_{3}, ···}. Figure 1.b shows how to form an infinite path passing through all elements of the Cartesian product A x B.
We can mix or shuffle A and B into a single infinite list for A ∪ B as follows, A ∪ B = {a_{1}, b_{1}, a_{2}, b_{2}, a_{3}, b_{3}, ···} considering that we do not list an element twice if it belongs to both A and B.
The proof is provided by induction on n. For the basis step, n = 2, notice that it has already been demonstrated, A_{1} x A_{2} is countably infinite.
Let’s assume that the statement holds for k = n, i.e., A_{1} x A_{2} x ··· x A_{n} is countably infinite, and consider k = n+1, i.e., the Cartesian product A_{1} x A_{2} x ··· x A_{n+1}.
Let’s define the function f: A_{1} x A_{2} x ··· x A_{n+1} → (A_{1} x A_{2} x ··· A_{n}) x A_{n+1}, as follows f(x_{1}, x_{2}, ···, x_{n+1}) = ((x_{1}, x_{2}, ···, x_{n}), x_{n+1}).
It is pretty obvious that f is bijective, and therefore |A_{1} x A_{2} x ··· x A_{n+1}| = |(A_{1} x A_{2} x ··· x A_{n}) x A_{n+1}|. By the induction hypothesis, A_{1} x A_{2} x ··· x A_{n} is countable infinite, and by assumption A_{n+1} is countable infinite. Futhermore, the Cartesian product of two countable infinite sets (n = 2, Case base) is countable infinite, too, and we have shown that A_{1} x A_{2} x ··· x A_{n+1} has the same cardinality of this Cartesian product, and therefore it is countable infinite∎
Theorem. A function is bijective if and only if has an inverse.
Proof.
⇒) Suppose f: A → B be bijective.
⇐) Suppose f has an inverse.