COMP10020 – Maths — Functions (part 1)

>>Want more notes on Functions? try here: Mindez

In Discrete Maths, ‘Functions’ have 3 features:

1. Source (S) , or more commonly known as the Domain
2. Target (T), or more commonly known as the CoDomain
3. 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-one relation.

Note: that a bijective function is usually the Identity Function. (But not always!)

Functions – Part 2