Functions

Functions

1. 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.

   • A = domain
   • B = codomain
   • f(A) = range
     • f(A) = {y ∈ B | ∃x ∈ A s.t. f(x) = y}.
   • F : A → {T, F} = Boolean function
     • assigns truth values to the elements of A
   • Γ(f) = graph

2. Composition of Functions

3. Inversion of Functions

   • Injective
     • f(x) = f(y) ⇒ x = y
       • never maps distinct domain elements to the same codomain element
     • sin x : [0, π 2 ] → R is injective
     • sin x : R → R is not injective because sin 0 = sin π = 0
   • Surjective
     • ∀z ∈ B ∃x ∈ A s.t. f(x) = z
       • every element in the codomain has an element in the domain that maps to it
   • Bijective
     • every element in domain paired with exactly one element in codomain and vice versa
       • all bijective functions, and only bijective functions, have inverses

4. FINITE SETS

   • 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.
     • Proof
       • A if finite so we can write it as A = {a1, a2, ..., ap} for some p.
         • 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.
     • Corollary 1
       • Let A, B be finite sets such that #(A) = #(B). Let f : A → B be a function. f is injective ⇔ f is bijective.
         • ⇒
           • 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
         • ⇐
           • f is bijective ⇒ f is injective
     • Corollary 2 (The Pigeonhole Principle)
       • 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.
       • 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′).
       • Examples
         • You have 8 friends. At least two of them were born the same day of the week. #(days of the week) = 7 < 8.
         • 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.
         • In a list of 30 words in English, at least two will begin with the same letter. #(letter in the English alphabet) = 26 < 30

5. INFINITE SETS

   • Hilbert's Paradox of the Grand Hotel
     • A fully occupied hotel with infinitely many rooms can always accommodate an additional guest as follows:
       • The person in Room 1 moves to Room 2
         • 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.
     • Claim
       • As defined, f is injective but not surjective (therefore not bijective).
       • Let H = {x1, x2, ... } be the hotel consisting of infinitely many rooms.
       • f : H → H is given by f(xn) = f(xn+1). f(H) = H\{x1}
     • Proposition
       • A set A is finite ⇔ ∀f : A → A, an injective function, is also bijective.
     • Proof
       • ⇒
         • If the set A is finite, then it follows immediately from Corollary 1 that every injective function f : A → A is bijective
       • ⇐
         • 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.

Images and files in the map