Functions and relations


Relation

A (binary) relation R:X→Y is a sub-set of the Cartesian product X × Y.

ie, R ⊆ (X × Y)

A set of ordered pairs.

n-ary relation: a sub-set of a Cartesian product A₁ × A₂ × … × Aₙ

Equivalence relation

A relation R that is:

Eg: Arithmetic equality.

Equivalence class

Given an equivalence relation R defined on a set A, if a ∈ A, equivalence class of a is

[a] = {x∈A | aRx}

Set of all equivalence classes with regard to an equivalence relation R defined on a set A is

[A]= {[a] | a ∈ A}

which is also written as A/R (read as A modulo R). This is the quotient set of A by R.

Operation

Not the same as relation.

A binary relation is not necessarily a function

R ⊆ (X × X)

but a binary operation is a function like

R : (X × X) → X

Preorder

A relation that is

Partial order

A relation that is

ie, a partial order is an anti-symmetric preorder.

Partially ordered set (poset)

Combination of a set and a partially ordered relation on that set.

Eg: the relation <= on the set of integers.

a<=a                      ie, reflexive.
a<=b and b<=a means a==b. ie, anti-symmetric
a<=b and b<=c means a<=c. ie, transitive

Totally/linearly ordered set (full order)

A poset where for any two elements a and b of the set, aRb or bRa.

Eg: <= over the set of integers is a total ordering. But < over integers isn't. Because if a=b, neither a<b nor b<a holds.

Function

A special type of relations.

A relation R:X→Y is a function iff every elemment of X has only one image in Y.

Every element in X must have exactly one image in Y.

Also denoted as

y = f(x)

Functions are useful to represent how one quantity changes with respect to changes in another quantity.

Like the value of a sinsuoidal wave (of the form A.sin(ωt + Φ)) being dependent on time (t).

A relation is not a function if one of the following is true:

Image and preimage

If for y = f(x),

Domain

The domain of a relation R:X→Y is the set X.

Range

The range of a relation R:X→Y is the set Y.

Codomain

The set of values of the range set to which the values of the function are restricted to.

Codomain ⊆ Range

Eg: In a function f:X→Y where X = {1, 2}, Y = {10, 20, 30} and f:X→Y = {(1,10), (2,20)},

Inverse of a function

The inverse of a function f:X→Y is f⁻¹:Y→X where (x, y) ∈ f mean (y, x) ∈ f⁻¹.

ie, g is inverse of f if f composed with g gives the identity function.

There may be left inverse and right inverse (function here, not element).

g∘f = id  (g is left inverse of f)
f∘g = id  (g is right inverse of f)

Function composition

When the domain of a function g and the codomain of another function f are the same, we can compose f and g.

f:A->B
g:B->C

then

g∘f = A -> C

(Notice that the order in which function are written look as if it is in 'reverse order').

One-to-one (Injection)

Each element in the codomain has only one pre-image in the domain.

Whenever f(a1) = f(a2), a1 = a2.

If a is the set of husbands and b is the set of wives, if R is an injective function, then there is no polyandry. 🥱

Onto (Surjection)

Every element in the codomain has at least one pre-image in the domain.

∀b∈B, ∃a∈A, f(a) = b

If a is the set of men and b is the set of women, if R is a surjective function (indicative of marriage), then every woman is married.

One-to-one and onto (Bijection)

A function that is both one-to-one and onto.

An bijective function is invertible.

A function can have an inverse iff it is a bijection (since it sort of needs to go somewhere and come back).

If f:A→B, then f⁻¹:B→A.

Partial function (partial ordering)

A partial function is a function that is defined only on part of its domain. ³

Total function (total ordering)

This is what we usually mean when we say 'function'.

Some functions

Identity function

f: ℝ → ℝ such that ∀x, f(x) = x.

Its graph is a straight line passing through the origin at 45°.

Constant function

f: ℝ → ℝ such that ∀x, f(x) = c where c is a constant.

Its graph is a straight line parallel to the X axis, intercepting the Y axis at y=c.

Polynomial function

f: ℝ → ℝ such that f(x) = a₀ + xa₁ + x²a₂ + .... + xⁿaₙ where n is a non-negative integer and all aᵢ ∈ ℝ.

Examples:

Whereas 2x¾ + 4x⁴ is not a polynomial function since the power x is not a whole number.

Quadratic function

A restricted form of polynomial function.

Has the form f(x) = ax² + bx + c where

Degree of term with highest degree is 2.

A bivariate version (ie, 2 variables) would be f(x,y) = ax² + by² + cxy + dx + ey + f.

Rational functions

Functions of the form f(x)/g(x) where

Coefficients of the polynomial terms needn't be rational??

Eg: (x³ - x²) / x³

Modulus function

A function f:ℝ→ℝ

f(x) = { x, if x ≥ 0
        -x, otherwise}

Graph is V-shaped, with point of the base of the 'V' being at the origin and the arms of the 'V' being at 45° with the origin.

         |         
         |         
         |         
   \     |     /   
    \    |    /    
     \   |   /     
      \  |  /      
       \ | /       
        \|/        
---------+---------
         O                          

Signum function

A function f:ℝ→ℝ

f(x) = { 1, if x>0,
         0, if x==0,
        -1, if x<0

Graph looks like a step.

            ┃             
            ┃             
           1┃------------ 
            ┃             
            ┃             
━━━━━━━━━━━━⊙━━━━━━━━━━━━━
           0┃             
            ┃             
  ----------┃ -1          
            ┃             
            ┃             

Though range is ℝ, co-domain = {1, 0, -1}

Sigmoid function

           1            eˣ
f(x) = ---------  =  --------
        1 + e⁻ˣ       eˣ + 1

Graph is a S-shaped curve, with one end 'tending' to 0 and the other 'tending' to 1.

Sigmoid function has an interesting property:

f(x) = 1 - f(-x)

Greatest integer function

A function f:ℝ→ℝ (or f:ℝ→ℤ maybe?)

Denoted by [x].

f(x) = [x]

Value is the biggest integer ≥ x.

Examples:

Limit of a function

lim f(x)
x→k

is the limit of the function f at a point k, which lies in the domain of f.

f is said to have a limit at k if the left and right limits of f at k exists and are the same:

lim f(x) =  lim f(x) = lim f(x) = L
x→k         x→k⁻       x→k⁺       

References