The inverse of a one – to – one function f

Let ~ be an equivalence relations on A , and let a ? A . The set of all elements in A which are equivalent to a is called the EQUIVALENCE CLASS of a under ~ and is denoted by [ a ] :
[ a ] = { b ?A? b ~ a } .
2
Theorem 1-1.
Let ~ be an equivalence relation in the set A . Then,
1)for each a ? A , [ a ] ? ? ,
2) if b ? [ a ] , then [ a ] = [ b ] ,
3) for any a , b ? A , with [a ] ? [ b ] , [ a ] ? [ b ] =? ,
4) U { [ a ] | a ? A } = A .
Proof .
~ is equivalence relation , so it is reflexive .
a ~ a , then a ? [ a].
Hence [a] ? ?
Let b? [a],
Hence b ~ a .
Since ~ is symmetric , then a ~ b.
Suppose that x ? [a], then x~a .
Since ~ is transitive , then x ~ b.
Hence x ? [b] .
So [a] ? [b].
Similarly [b] ? [a]
suppose that [a] ? [b] ? ?,
So there exist c ? [a] ? [b].
By 2 [a] = [c] = [b] , which is contradiction .
So [a] ? [b] = ?.
Since [a] ? A , then U {[a]|a ? A } ? A.
Since for each a ? A, then a ? [a].
Hence A ? U{[a] | a? A }.
So U{[a] |a? A } = A
Definition 1 - 7 .

A partition of a set A is a family {Ai} of nonempty subsets of A with the properties
If Ai ? Aj , then Ai ? Aj = ? (pairwise disjoint),
U Ai = A.
Example
If Zeis the set of even integers,
andZo is the set of odd integers,
thenZeU Zo = Z,
andZe ? Zo = ?.
Hence {Ze ,Zo} is partition of Z.
Example.
If A = { 0 ,1, 2 , . . . , 24 } , n= 5 , then
{ [ 0 ] , [ 1 ] , [ 2 ] , [ 3 ] , [ 4 ] } is partition of A.

Theorem 1-2 .
If {Ai} is a partition of the set A, then there is an equivalence . relation in A whose equivalence classes are precisely the . sets Ai.

Definition 1 – 8 .
A function f is a set of ordered pairs such that no two . distinct pairs have the same first component, and denoted by
( x , y ) ? f or y = f ( x ) .

Definition 1 – 9 .
A function f is said to be one – to one if and only if
x1 , x2 ?Df , with x1 ? x2 , implies f (x1) ? f (x2)
4
Definition 1 – 10 .
The inverse of a one – to – one function f is denoted by
f -1, it is the set of ordered pairs,
f – 1 = { (y , x )| (x , y ) ?f } .
Notes :
( f – 1o f ) (x ) = x for x ? Df .
2)( f o f -1 ) ( y ) = y for y ?Rf .

Definition 1 – 11 .

If f is a function from X into , and A ?X , then the direct image of A is the subset of Y , and denoted by f ( A) ,
f ( A ) = { f (x ) | x ?A } ,
and if B ? Y, then the inverse image of B is the subset
of X denoted by f -1(B )
f -1(B) = { x | f(x) ?B}.

Theorem 1 – 3.

For each subset B? Y,
f (f -1(B))? B.
Proof.
If b? f ( f – 1 (B )) ,
then b = f (a) for some a in f – 1 (B) .
Hence f (a )?B ,
so b? B,
Then f ( f– 1 ( B )) ? B .

Corollary .

If f is function onto the set Y , then
f ( f – 1 ( B ) = B .


5

Proof .
From 1 – 14 f ( f -1 ( B)) ? B.
Let b ?B , then b = f ( a ) ? for some a in X .
Since a? f – 1( B) ,
f (a ) ? f ( f – 1 ( B),
So b ? f ( f – 1 (B)).
Hence B ? f ( f– 1 ( B )).
So f ( f – 1 ( B )) = B .
Theorem 1- 4
For each subset A ? x,
A ? f -1 (f (A)).
Proof .
H.W.
Collorary
If f is a one to one function, then
A = f -1(f(A)).
Proof .
H.W.
Division Algorithm