Abstract Algebra/Functions

Definition

edit

A function   is a triplet   such that:

  •   is a set, called the domain of  
  •   is a set, called the codomain of  
  •   is a subset of  , called the graph of  

In addition the following two properties hold:

  1.  .
  2.  .

  we write   for the unique   such that  .

We say that   is a function from   to  , which we write:

 

Example

edit

Let's consider the function from the reals to the reals which squares its argument. We could define it like this:

 
 

Remark

edit

As you see in the definition of a function above, the domain and codomain are an integral part of the definition. In other words, even if the values of   don't change, changing the domain or codomain changes the function.

Let's look at the following four functions.

The function:

 
 

is neither injective nor surjective (these terms will be defined later).

The function:

 
 

is not injective but surjective.

The function:

 
 

is injective but not surjective.

The function:

 
 

is injective and surjective

As you see, all four functions have the same mapping but all four are different. That's why just giving the mapping is insufficient; a function is only defined if its domain and codomain are known.

Image and preimage

edit

For a set  , we write   for the set of subsets of  .

Let  . We will now define two related functions.

The image function:

 

The preimage function:

 

Note that the image and preimage are written respectively like   and its inverse (if it exists). There is however no ambiguity because the domains are different. Note also that the image and preimage are not necessarily inverse of one another. (See the section on bijective functions below).

We define  , which we call the image of  .

For any  , we call   the support of  .

Proposition: Let  . Then

  1.  
  2.  

Example

edit

Let's take again the function:

 
 

Let's consider the following examples:

 
 
 

Further definitions

edit

Let   and  . We define   by  , which we call the composition of   and  .

Let   be a set. We define the identity function on A as

 

Properties

edit

Definition: A function   is injective if

 

Lemma: Consider a function   and suppose  . Then   is injective if and only if there exists a function   with  .
Proof:
 :
Suppose   is injective. As   let's define   as an arbitrary element of  . We can then define a suitable function   as follows:

 

It is now easy to verify that  .
 :
Suppose there is a function   with  . Then  .   is thus injective.
Q.E.D.

Definition: A function   is surjective if

 

Lemma: Consider a function  . Then   is surjective if and only if there exists a function   with  .
Proof:
 :
Suppose   is surjective. We can define a suitable function   as follows:

 

It is now easy to verify that  .
 :
Suppose there is a function   with  . Then  . Then  .   is thus surjective.
Q.E.D.

Definition: A function   is bijective if it is both injective and surjective.

Lemma: A function   is bijective if and only if there exists a function   with   and  . Furthermore it can be shown that such a   is unique. We write it   and call it the inverse of  .
Proof:
Left as an exercise.

Proposition: Consider a function  . Then

  1.   is injective iff  
  2.   is surjective iff  
  3.   is bijective iff the image and preimage of   are inverse of each other

Example: If   and   are sets such that  , there exists an obviously injective function  , called the inclusion  , such that   for all  .

Example: If   is an equivalence relation on a set  , there is an obviously surjective function  , called the canonical projection onto  , such that   for all  .

Theorem: Define the equivalence relation   on   such that   if and only if  . Then, if   is any function,   decomposes into the composition

 

where   is the canonical projection,   is the inclusion  , and   is the bijection   for all  .

Proof: The definition of   immediately implies that  , so we only have to prove that   is well defined and a bijection. Let  . Then  . This shows that the value of   is independent of the representative chosen from  , and so it is well-defined.

For injectivity, we have  , so   is injective.

For surjectivity, let  . Then there exists an   such that  , and so   by definition of  . Since   is arbitrary in  , this proves that   is surjective.

Q.E.D.

Definition: Given a function  ,   is a

(i) Monomorphism if given any two functions   such that  , then  .

(ii) Epimorphism if given any two functions   such that  , then  .

Theorem: A function between sets is

(i) a monomorphism if and only if it is injective.

(ii) an epimorphism if and only if it is surjective.

Proof: (i) Let   be a monomorphism. Then, for any two functions  ,   for all  . This is the definition if injectivity. For the converse, if   is injective, it has a left inverse  . Thus, if   for all  , compose with   on the left side to obtain  , such that   is a monomorphism.

(ii) Let   be an epimorphism. Then, for any two functions  ,   for all   and  . Assume  , that is, that   is not surjective. Then there exists at least one   not in  . For this   choose two functions   which coincide on   but disagree on  . However, we still have   for all  . This violates our assumption that   is an epimorphism. Consequentally,   is surjective. For the converse, assume   is surjective. Then the epimorphism property immediately follows.

Q.E.D.

Remark: The equivalence between monomorphism and injectivity, and between epimorphism and surjectivity is a special property of functions between sets. This not the case in general, and we will see examples of this when discussing structure-preserving functions between groups or rings in later sections.

Example: Given any two sets   and  , we have the canonical projections   sending   to  , and   sending   to  . These maps are obviously surjective.

In addition, we have the natural inclusions   and   which are obviously injective as stated above.

Universal properties

edit

The projections and inclusions described above are special, in that they satisfy what are called universal properties. We will give the theorem below. The proof is left to the reader.

Theorem: Let   be any sets.

(i) Let   and  . Then there exists a unique function   such that   and   are simultaneously satisfied.   is sometimes denoted  .

(ii) Let   and  . Then there exists a unique function   such that   and   are simultaneously satifsied.

The canonical projections onto quotients also satisfy a universal property.

Theorem: Define the equivalence relation   on   and let   be any function such that   for all  . Then there exists a unique function   such that  , where   is the canonical projection.