Functions

Let A, B be sets. A function f : A → B is a rule that assigns to every element of A one and only one element of B i.e. ∀x ∈ A ∃!y ∈ B s.t. f(x) = y.
1. A = domain
2. B = codomain
3. f(A) = range
  1. f(A) = {y ∈ B | ∃x ∈ A s.t. f(x) = y}.
4. F : A → {T, F} = Boolean function
  1. assigns truth values to the elements of A
5. Γ(f) = graph
Composition of Functions
Inversion of Functions
1. Injective
  1. f(x) = f(y) ⇒ x = y
    1. never maps distinct domain elements to the same codomain element
  2. sin x : [0, π 2 ] → R is injective
  3. sin x : R → R is not injective because sin 0 = sin π = 0
2. Surjective
  1. ∀z ∈ B ∃x ∈ A s.t. f(x) = z
    1. every element in the codomain has an element in the domain that maps to it
3. Bijective
  1. every element in domain paired with exactly one element in codomain and vice versa
    1. all bijective functions, and only bijective functions, have inverses
FINITE SETS
1. Proposition: Let A, B be sets and let f : A → B be a function. Assume A is finite. Then f is injective ⇔ f(A) has the same number of elements as A.
  1. Proof
    1. A if finite so we can write it as A = {a1, a2, ..., ap} for some p.
      1. Then, f(A) = {f(a1), f(a2), ..., f(ap)} ⊆ B.
        A priori, some f(ai) might = f(aj).
        However, f is injective ⇔ f(ai) != f(aj) whenever i != j ⇔ f(A) has exactly p elements just like A.
  2. Corollary 1
    1. Let A, B be finite sets such that #(A) = #(B). Let f : A → B be a function. f is injective ⇔ f is bijective.
      1. ⇒
        Suppose f : A → B is injective. Since A is finite, by the previous proposition, f(A) has the same number of elements as A, but f(A) ⊆ B and B has the same number of elements as A ⇒ #(A) = #(f(A)) = #(B), which means f(A) = B, i.e. f is also surjective ⇒ f is bijective
      2. ⇐
        f is bijective ⇒ f is injective
  3. Corollary 2 (The Pigeonhole Principle)
    1. The name 'Pigeonhole principle' is due to Paul Erdös and Richard Rado. It was known previously as the Principle of the Drawers of Dirichlet. It has a simple statement, but it's a very powerful result in both mathematics and computer science.
    2. Since f(A) ⊆ B, and #(B) < (A), f(A) cannot have as many elements as A, so by the proposition, f cannot be injective, namely y ∃ a, a′ ∈ A with a != a ′ (i.e. distinct elements) s.t. f(a) = f(a′).
    3. Examples
      1. You have 8 friends. At least two of them were born the same day of the week. #(days of the week) = 7 < 8.
      2. A family of five gives each other presents for Christmas. There are 12 presents under the tree. We conclude that at least one person got three presents or more.
      3. In a list of 30 words in English, at least two will begin with the same letter. #(letter in the English alphabet) = 26 < 30
INFINITE SETS
1. Hilbert's Paradox of the Grand Hotel
  1. A fully occupied hotel with infinitely many rooms can always accommodate an additional guest as follows:
    1. The person in Room 1 moves to Room 2
      1. The person in Room 2 moves to Room 3, ad inf.
        If the rooms are x1, x2, x3, ..., define the function f(x1) = x2, f(x2) = x3, ..., f(xm) = xm+1.
  2. Claim
    1. As defined, f is injective but not surjective (therefore not bijective).
    2. Let H = {x1, x2, ... } be the hotel consisting of infinitely many rooms.
    3. f : H → H is given by f(xn) = f(xn+1). f(H) = H\{x1}
  3. Proposition
    1. A set A is finite ⇔ ∀f : A → A, an injective function, is also bijective.
  4. Proof
    1. ⇒
      1. If the set A is finite, then it follows immediately from Corollary 1 that every injective function f : A → A is bijective
    2. ⇐
      1. We prove the contrapositive
        Suppose that the set A is infinite
        We shall construct an injective function that is not bijective
        Since A is infinite, there exists some infinite sequence x1, x2, x3, ... consisting of distinct elements of A i.e. an element of A occurs at most once in this sequence.
        Then there exists a function f : A → A such that f (xn) = xn+1 for all integers n ≥ 1 and f(x) = x if x is an element of A that is not in the sequence x1, x2, x3, ....
        If x is not a member of the infinite sequence x1, x2, x3, ..., then the only element of A that gets mapped to x is the element x itself; if x = xn, where n > 1, then th eonly element of A that gets mapped to x is xn-1.
        It follows that the function f is injective. It is not surjective, however, since no element of A gets mapped to x1. This function f is thus an example of a function from the set A to itself, which is injective but not bijective.

Media attachments

Comp (binary/octet-stream)

Next up

Functions

Description

Resource summary

Media attachments

Similar

	Created by Luke Byrne over 6 years ago