Relation and Functions

Function
f(A) --> B
each element of A is mapped to exactly one element in B
A is domain and B is codomain, or B is image and A is pre image of B

Type of functions
one to one or injective :
if f(x) = f(y) then x=y for all x and y in the domain of f
that is no two values in the domain have same value in the range
f(x**2) is not function because x and -x both will have same value
or we can say f(x)!= f(y) when f!= y helpful in proving
there may be unmapped elements in one to one we have not restricted that till now

onto or surjective
if for every element in image B there is a corresponding element in A
by definition of function there should be image for all A and from onto we have constrained all B to have preimage

one to one correspondence or bijection
if it is both one to one and onto


Inverse or Invertible  and composition of function
If function is one to one and onto we can define inverse of function as f^-1(b) = a when f(a) = b
If it is not bijection then inverse would not be function at all

Let g be function from A to B and f be function from set B to set C  and range of g be subset of domain of f
The composition of function defined by
(f o g)(a) = f(g(a))
not commutative that is  (g o f)(a) != (f o g)(a)
Composition of funtion and its inverse forms identity element in either order
f^-1 o f (a) =  a and     f  o  f^-1 (a) =  a


Relation
set of ordered pair are called binary relation its subset of AxB

Number of relation on a set
if A has n elements then number of relation on A is subset of AxA since AxA has n^2 elements x and number of subsets of m elements is 2^m so there are 2^(n^2) relations on set A

Reflexive relation
A relation R on set A is reflexive if for every element a in A there is (a,a) in R
Symmetric
A relation R on set A is symmetric if (b,a) is any pair in R then we have (a,b) also in R
Antisymmetric
if there is (a,b) and (b,a) then a=b
that is it cannot have distinct a and b with this property
Transitive
if (a,b) and (b,c) then (a,c) should be in relation

Counting Relations
number of distinct reflexive relations on a set of n elements
we count reflexive relation on AxA that has n^2 elements
since all (a,a) pairs should be present for each n elements This has to be in the relation R and remaining pairs we can form from n^2-n elements So total number of relation is 2^n(n-1)
number of distinct irreflexive relations on set of n elements
its same as reflexive because  selection of diagonal elements is fixed that is they should not be selected and remaining n^2 - n elements for 2^n(n-1) number of relations

number of distinct symmetric relations
we have to count each pair (a,b) and (b,a) once since that is for each selection (a,b), (b,a) will be selected
for first element a we can select another element in n ways including the (a,a) pair
for second element b we select another element in n-1 ways  excluding the selection of a
so there are total n + n-1 + ...1 number of elements  = n(n+1)/2
or we can look at the matrix form to see that we need to select element on or above the diagonal which is n(n+1)/2
So total number of relations is 2^(n(n+1)/2)

number of antisymmetric relations
we can have a,b or b,a or none for two distinct elements
number of two distinct element subsets - C(n 2) = n(n-1)/2
and for each subset we have 3 choices therefore 3^n(n-1)/2
we can also select diagonal elements that is (a,a) so, those gives 2^n choices
Total number of relation 3^n(n-1) /2 * 2^n

Number of relations both reflexive and antisymmetric
diagonal element all has to included so single way to select them and rest we calculated above for antisymmetric that is 3^n(n-1) /2

Number of relations both irreflexive and symmetric
we can have all elements above the diagonal but not on the diagonal since we calculated for symmetric number of pairs as n(n+1)/2 we can deduct diagonal elements from this to get n(n-1)/2
so total number of relations = 2^n(n-1)/2

Combining relations
composition SoR is defined as all ordered pair where second element in R agrees with first element in S
example if R has ordered pair 2,3 and S has ordered pair 3,5 then SoR = 2,5
Power of relation is defined as
R^n = R^n-1 o R

Relation R on set A is transitive if and only if R^n is subset of R for n=1,2,3..

Closure of relation
reflexive closure is R U all diagonal elements (a,a)
symmetric closure is R U R^-1  where R^-1 is b,a whenever a,b
Transitive closure  Transitive closure of R equals connectivity relation R^*
There is pah from a to b of length n if and only if a,b is element of R^n


Transitive closure of n elements in 0-1 matrix is R* = R^1 U R^2 U ...R^n
all called union of boolean powers each boolean power takes n^2 * 2n-1 bit operations 
that is find the composite relation R o R and take union of all such
composite relation can be found by  same way we perform the matrix multiplication but
multiplication will be AND and addition will be OR


Warshalls algorithm to compute transitive closure
requires 2n^3 bit operations unlike boolean multiplication method that requires 2n^3* (n-1) bit operations
 based on construction of zero-one matrix



Congruence
a=b mod n
1)if a-b is integer multiple of n
a-b = kn or
2)a-b divides n that is a-b/n = k or
3)a mod n = b mod n that is both have the same remainder when divided by n

congruent class modulo m
a = b mod m
we find all a for which equivalent to b mod n that is a-b is integral multiple of n

when a=b we get 0/n which is divisible for a = b+m we get  (b+m - b)/m which is divisible so
[b]_m  ={b,b+m,b+2m...} U {b-m,b-2m,b-3m}

example for [13]_9 that is find a such that a=13 mod m
{13 13+9 13+2*9 ...} U {13-9 13-2*9 ....} = {13 22 31 ..}  U {4 -5 -14}

Modular exponential
find 103^45 mod 5
solution
1)we find that remainder increases  by going from  power of 1 to 2
2) we try to get to the 1 mod m
103 mod 5 = 3  mod 5  that is now we can put 3 at place of 103
103^2 mod 5 = (3)^2 mod 5 = 4 mod 5 //we can put 4 in place of 103^2
103^4 mod 5 =  (103^2)^2 mod 5 = 4^2 mod 5  = 1
now we can find 45 in terms of 4 that is 44+1
103^45 mod 5 =  (103 mod 5) (103^44 mod 5)
                       =  (3 mod 5) ((103^4)^11 mod 45) = 3

find 58^29 mod 11
58 mod 11 =3 mod 11
58^2 mod 11 = 9 mod 11
58^4
103^44 mod 5 = (103 ^ 4)^11 mod 5 =

property
1)if a = b mod m
b^n mod m = a^n  mod m

Methods for calculating modular exponention
1)calculate b^e and then find mod with that number
requires O(e) multiplications
operations takes lot of time
2)Memory efficient method
takes more number of operations but each operation takes less time making it faster
ensures that result always stays small
number of multiplications are O(e) only
but computation time decreases by O(e) from first because calculations involve much small number
3)right-to-left binary
reduces both operations and memory required
Total running time is O(log exponent)

Linear congruence theorem
ax = b mod m has solution if and only if b is divisible by gcd (a,m)
there will be exactly d solution in set {0 , 1, 2, ..n-1}
then use extended euclid algo to find all d solutions


Problem what is minimum number of ordered pair that should be chosen such that two pairs (a1,b1) and (a2,b2) in the chosen set has
a1= a2 mod 5 and b1 = b2 mod 3
Solution
we can rewrite the equation as a1 mod 5 = a2 mod 5 and b1 mod 3 = b2 mod 3
that is we need to find the ordered pair a1,b1 such that residue on mod 5 on first pair number is equal to residue from mod 5 on second pair number
number a1 will give residue {0 1 2 3 4} on mod 5 and number b1 will give residue {0 1 2} on mod 3
that is if we choose any pair like (7, 5) then residue is {2,2}
we have to find two pairs such that their residue in ordered pair is same that is if we got residue {2,3}  on first any ordered pair then there should be another set also with residue {2,3}
since there are 3*5 different pair of reside from pigeonhole principle we can deduce that there should be at least 16 pairs.



what in case of unordered pairs?


Equivalence relation
union of two equivalance relation is not equivalence relation
example R1 = congruence mod 3 and R2 = congruence mod 4 then
intersection of equivalence relation is equivalence relation
If R is transitive then R^2 =R

To prove relation is equivalence find the relation matrix
check if reflexive by diagonal elements
symmetric from symmetry of elements above and below
transitive by M^2 = M

Equivalence classes are found by finding all related elements like if relation (a,b)R(c,d) is equivalence relation if a+b = c+d
the we can find the equivalence class as
{1,2}  = {1,2} {2,1}
{1,3} = {1,3}{3,1} {2,2}
{1,4}={1,4}{4,1}{2,3}{3,2}

Partition
division non overlapping, non empty  that covers all elements
for equivalence relation, equivalence class forms partition

Number of partitions and Equivalence relation
the total number of partition of n element set is Bn Bell number
B(n+1) = {k=0 to n} C(n k)Bk

0  1    2    3    4    5    6     7
1  1    2    5   15  52  203

Partial order
reflexive
antisymmetric if aRb and bRa then a=b
transitive

called partially ordered set poset
if a and b are distinct element of partially ordered set and either a<=b or b<= a then they are comparable
if every two elements of poset are comparable it is called totally ordered
poset is called partial because some of the sets may be incomparable

well ordered set
if it is poset such that <= is total ordering and every non empty subset of S has a least element

Maximal and minimal elements of poset
Maximal if it is not less than any element of poset
greatest element is greater than every other element, its unique
element that is greater than all the elements in a subset A of poset then its called upper bound
least upper bound of subset A if x is upper bound that is less than every other upper bound of A


Lattice partially ordered set in which every element has both least upper bound and a greatest lower bound is called lattic


LCM GCD forms lattice that is each element at first level are primes like 2 3 5 and then elements above that are multiple of first level numbers like
2*2 , 2*3 , 2*5  3*2 ..
greatest upper bound gives GCD and lowest upper bound gives LCM

Problem
a)R =SxS
i)equivalence?
equivalence as reflexive symmetry and transitive fullfils
ii)poset
antisymmetry fails that is there are a,b and b,a both only if there is single element can it be partial ordered set
b)R={}
i)equivalence
not reflexive so not equivalence relation
can't be poset also