A Primer on Functions
“The difference between the poet and the mathematician is that the poet tries to get his head into the heavens while the mathematician tries to get the heavens into his head.” G.K Chesterson
A function is a mathematical and magical (think mathemagical) black box concept. Used in programming, functions take an input, perform some operation on it and returns the output. A mathematical function works the same way.
Given an input a function must always return the same answer. For example, given f(A) = B then the function a must always return the value B.
In functional programming, this is what is known as a “functional function”.
A function cannot map one input to multiple outputs. However, outputs can have multiple inputs (2 inputs which give the same answer).
The above image represents a function because:
- Every element on the left hand side has an arrow coming out of it.
- Every element on the left hand side only has one arrow coming out of it
Suppose f: A → B.
A is called the domain, B is the co-domain and the range of f(A) is F(A) = {f(x) | x ∈ A}
In other words, the range is the set of all possible results from the function, the domain is the input and the codomain is the output.
Finding the domain of a function
It’s best to explain this using a function. Given f(x) = sqrt(2x-8) we can work out the range like so:
We know that the domain of a function is the set of all possible inputs into a function. We know that the above function is only defined when it's taking the square root of a non-negative number so it's only going to be defined when:
2x-8 ≥ 0.
Now this is a simple algebraic problem to find x.
2x ≥ 8
x ≥ 4So the domain here is the set of all real numbers ≥ 4.
Often times trying to find the domain of a function is the same as asking “is there any input that I can’t put into the function?”
Given the function f(x) = 2/x-3, let’s try find the range.
Is there anything that X CANNOT be?
Yes! If X is 0 it would cause an error as you cannot divide by 0!Mathematics is all about these beautiful little equations that interwine into what is mathematics. We took basic algebra and some knowledge we knew about square roots and we used it to deduce a mathematicla fact.
Finding the range of a function
It is best to use set theory notation to try and explain the range of a function. Since it is likely impossible to list every single element produced by a function. For example, the function f: R -> R, f(x) = 2 * x only receives real numbers. We know that the output is 2* a real number. So in set theory notation this is {x | x ∈ R and x*2}
Composition of Functions
Function composition is just applying the results of one function to the input of another function.
Given the functions f: X → Y and f: Y → Z then their composition is g º f which is just the function of X to Z. Function composition is denoted as ( g º f) (x) which is just g(f(x)).
Given another example, f(x) = 2x and g(x) = 3x. Then the composition is f º g means that you are inputting the output of f into g.
It may be more useful to look at only the co-domains and the domains, g º f x = X→Y →Z.
Matrix Composition
Sorry for the mess but I found this much easier to do on paper. It’s quite simple once you understand it. I reccomend you grab some paper and rewrite / redo what I’ve done.
Types of Functions
A function cannot have different outputs for a singular input. A function is called a general function (normal) if the same output can be achieved using 2 different inputs.
Injective Functions
A function is called injective if the codomain (output) is exactly the same as the range (set of all possible answers). In other words, one input always equals the same output but 2 inputs cannot equal the same output.
An injective function has a one to one relationship between the domain and the codomain.
Injective Functions on Infinite Sets
Suppose, f, is an injective function defined on an infinite set, X. By definition, f is one to one if and only if the following universal statement is true:
∀x1, x2 ∈ X, if f(x1) = f(x2) then x1 = x2.Thus to prove f is one-to-one you will need to use direct proof.
Suppose x1 and x2 are elements of X such that f(x1) = f(x2)
And show that x1 = x2.In other words, you need to show that if the input is x1 then the output of the function must always be x2.
Why should I give a damn about injective functions? (optional)
Image a set of student records each row containing an identifcation number and the students ID number. We need a way to locate a record if the ID number is known. Of course we could store each record in place n where n is the ID number, but ID numbers have 9 digits so the database will be 999999999 records big, even if there are as little as 2 students!
One of the ways we can improve this is by using hash functions. A hash functions takes a large input, does some maths (frequently using the modulus function) and outputs a much smaller number.
Suppose we are given the hash function:
Hash(n) = n mod 7
So given the ID number 201270456 into the funtion Hash we get the result “2”. From this, we can place it into the second position of the database with the ID number being 2.
This is where injective functionality comes into play. What if we already have a record in position 2 of the database? Does the student who is also in position 2 just die, murdered by their university because there is no physical way they can be in that position? Of course not!
A program will move the students ID number down every record, so it’ll check if 3 is avaible then 4. It will do this until it finds a position that is avaible to use!
Surjective functions
A function is called Surjective if every answer in the range has an input which results in that answer.
If you want to prove that a function is not surjective, find an element in the codomain that is not the image of something in the domain.
In other words, given 2 sets A = {1, 2, 3, 4, 5} and Y = {a, b, c, d} the function is surjective if every element in A maps to an element in Y. 2 elements in A can map to a single element in Y, so {4, 5} could equal {d}.
The important thing here is to understand that all elements in Y must map to every element in A, if it doesn’t then the function is called injective as well.
Prove h: Z → Z given by h(x) = 2x is not surjective, where Z is the set of all integers.
Answer: It is impossible to get the answer 3 so this is not surjective. Because the function takes an integer and returns an integer and if we assume it is surjective (contradiction) then the function must be able to return any integer given any integer. Becuase the function doubles the input by 2 it is impossible to get the number 3, for example.
Bijective Functions
A function is called bijective if it is both injective and surjective. For example, f: Q → Q given by f(x) = 2x is bijective. Bijective functions are reversible. You can find the inverse of a bijective function.
Inverse of Functions
The inverse of a function is a function whereby you insert the output of the original function and receive the original input.
A function can only have an inverse if it is a bijective function.
Cardinality of finite sets
The cardinality of a set is how many items are in a set. This is denoted as |a|. If a = {1, 2, 3} then |a| = 3.
Sets A and B have the same cadinality iff (if and only if) there is a bijection from A to B
If sets A and B are bijected then they have the same cardinality.
Powersets
The power set Pow(A) of a set A is the set of all subsets of A, in other words Pow(A) = {c | c ⊆ A}
If A is the set {1, 2, 3} then the powerset of A is the set that contains every subset of A. So Pow(A) = { {1}, {2}, {3}, {1,2}, {1,3}, {2, 3}, {1, 2, 3}, {Ø} }
The cardinality of a powerset is 2^n where n is the cardinality of A. In the above example, 2³ is 8 and there are 8 subsets in Pow(A).
Powerset and Bit Vectors
Turn the set into its bit vector representation and there will be 2^n bit vectors. Given the set {a, b, c} we can use bit vectors to work out the powerset of {a, b, c}
Infinite sets
Sets A and B have the same cardinality if there is a bijection from A to B, even if the sets are infinite.
Examples of infinite sets which have a bijection:
Take the sets of Integers and even integers
consider f(n) = 2nEven though the set of integers is infinite, it can be mapped to the second set of even integers perfectly, thus creating a bijection.
Uncountable sets
A set that is not countable is called uncountable.
The below video explains uncountable, infinite sets way better than I ever could so I highly suggest watching it.
The Pigeon Hole Principle
The Pigeon Hole Principle states that if |A| > |B| then at least one value of F occurs more than once.
In other words, if there are N holes and we have N+1 pigeons then 2 pigeons must occupy the same hole.
Example problem, I suggest going through this problem.
Suppose there are 15 people on a bus. show that at least 2 of them have a birthday in the same month.
For 12 people it might happen so that all their birthdays are in different months. once you have 12 + 1 (13) this persons birthday is in the same month as someomne else. Consider a set, A, of all people on the bus. and a set B of all the months (january, february) etc. the pigeon hole principle tells us that at least 2 people mapped to the same month meaning that as least 2 people are born in the same month.
The birthday paradox is a paradox of who shares a birthday. Given a room with 366 people, two of them must share a birthday according to the Pigeon hole principle. The birthday paradox is an amazing problem and this 5 minute video explains it pretty well
