Maths – Functions (part 1)
September 10, 2009 Leave a comment
In Discrete Maths, ‘Functions’ have 3 features:
- Source (S) , or more commonly known as the Domain
- Target (T), or more commonly known as the CoDomain
- Behaviour, which is what the function does as it transforms the source (input) into the target (output)
Note: the source and the target are both sets.
Functions can have 3 different layouts, the first, and most common layout is:
f(x) = x+2
where x+2 is the behaviour of the function, f(x) is the target (codomain) and x is the source (domain).
The other 2 layouts are:
f: A —–> B
and
f
A —–> B
x |—–> x+2
The final layout is a little more complicated, with A being the source, B being the target. However, the other elements are: f which is the ‘name’ of the function, such as f(x) or here: g(x) with g as the name.
x |—–> x+2 is the behaviour of the function, so the right-hand-side of f(x). All together it can be transformed to:
- f(x)=x+2 which looks a lot better 🙂 note: x = A and f(x) = x+2 = B
the X is the domain or ‘source’, and the Y is the codomain – target.
The arrows represent the behaviour of the function. Since each the source and target are both sets, we can show that: X = { 1, 2, 3, 4 } Y = { A, B, C, D } |
Equality
Two functions:
f1: S1 ——> T1 f2: S2 ——> T2
are equal, if and only if (iff):
- They have the same source > S1 = S2
- They have the same target > T1 = T2
- They have the same behaviour > f1(x) = f2(x)
Identity Function
For an set S, there is a function S —–> S which sends each element x back to itself, for example f(x)=x. This is called the Identity Function, and is usually denoted by:
ids
Injective / Surjective and Bijective
A function
f
S ——-> T
is: (E = …is an element of…)
- Injective –> if for each y E T there is atmost one x E S with f(x)=y >>>>> not all elements in the target get hit from elements in the source.
- Surjective –> if for each y E T there is atleast one x E S with f(x)=y >>>>> all elements in the target must get hit from elements in the source at least once.
- Bijective –> if for each y E T there is precisely one x E S with f(x)=y >>>>> all elements in the target must get hit from elements in the source exactly once.
Note: notice how a function is only Bijective if it is exactly Injective and Surjective.
Examples of Injective Functions are:
- f(x)=x+2
- f(x)=2x
- f(x)=ln(x) and f(x)=exp(x)
The element C in the target does not get hit from any of the elements in the source
Example of Surjective Functions are:
- f(x)=x2
- f(x)=1+x2
All the elements in the target get hit at least once, even C that gets hit twice. this is a many-to-one relation.
Examples of Bijective Functions are:
- f(x)=2x+1
- f(x)=x
All elements get hit exactly once, with no elements in the target have none, or more sources. This is a one-to-onerelation.
Note: that a bijective function is usually the Identity Function. (But not always!)