Maths – Functions (part 1)


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

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

>> Adapted from COMP10020 Discrete Maths Lecture Notes, Copyright 2009 Graham Gough
Advertisements

About Badgerati
Computer Scientist, Games Developer, and DevOps Engineer. Fantasy and Sci-fi book lover, also founder of Cadaeic Studios.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: