Mappings

    Mappings and functions are synonyms; that is, mappings assign every element in one set a unique value in another set. Mappings are one of the most fundamental concepts in all of mathematics and can be used not only to define groups in an abstract manner, but also to clarify the meaning of statements such as "two groups have essentially the same structure".

The set notations for the following commonly used sets are:

    (i) is the set of natural numbers  
    
    (ii) is the set of integers
    
    (iii) is the set of rational numbers  
    
    (iv) is the set of real numbers.
    
    (v) is the set of complex numbers.

We will often use capitals letters such as to denote sets and lowercase letters to denote elements of sets, but with this said, it's still very important to write all theorems, definitions, exercises, ... as formal statements.

Definition (Cartesian Products and Relations) Let and be sets. Then the set is called the Cartesian product of and further the subsets of are called relations.

    Undoubtedly you should have seen this definition when for example is a function from defined by sending and the graph of namely is a relation of However, the definitions of Cartesian Product and Relation hold for arbitrary sets, and not just sets of real numbers. This is an example of how "abstract" an abstract algebra course can be. Many of the definitions and theorems will be statements for the most general case as possible, given that this is an introductory level abstract algebra.  
    By now you are aware of linear functions, quadratic functions, polynomial functions, exponential functions, trigonometric function and on and on. And in calculus you study how to take limits, derivatives, and integrals of functions. So it is fair to say that in precalculus and calculus, the main objects of investigation were functions of real numbers. Recall a function is a relation with a special property: for every ordered pair of real numbers (an input) there corresponds a unique real number (output). The important part of this definition is of course the quantifiers: "for every" and "there corresponds a unique". Now we would like to make this definition more abstract by defining a function using arbitrary sets. However since we are going to be in a more abstract setting (not just sets of real numbers) we will use the term mappings instead of functions.

Introducing Mappings

Definition (Mappings) A mapping is a set , a set , and a subset of such that

    (i) if then there is an element such that
    
    (ii) if and then
    
In other words, is a mapping (or correspondence) from to if it satisfies conditions and (ii) (and is denoted by ); namely, assigns to every element of a unique element of The set is the domain, the set is the codomain, and the subset of is the graph of the mapping. Two mappings and are equal if they have the same domain, same codomain, and the same graph. In particular, a mapping from a set to itself with the property is the identity mapping on .  

Example (Types of Mappings) The following are not mappings:
    
    


and the following are mappings:
    

Definition (Types of Mappings) If is a mapping, then

    (i) if then is the image of under   
    
    (ii) if then the set is the pre-image of under
    
    (iii) if then there is an element such that , then is surjective (or onto);
    
    (iv) if for all then is injective  (one-to-one); and
    
    (v) if is both injective and surjective, then is bijective.
    
    

Example (Types of Mappings) The mapping defined by is one-to-one but not onto. The mapping defined by is onto but not one-to-one.

Proposition (Mappings of Sets) If and and are subsets of then

    (i)
    
    (ii) and
    
    (iii) is one-to-one if and only if
    
    Proof. (i): By definitions of image of a subset, and union of sets:
    

such that
or   such that
such that or such that

            
    (ii): If then there exists such that So and and therefore, and By definition of intersection and subset,
    (iii): Suppose is one-to-one. By (ii), it suffices to show that If then there exists an such that and there exists an such that Since is one-to-one, and thus Whence, Conversely, assume for any subsets and of In particular, if in , , and then is empty and thus so is So there is no element such that Therefore, and so is one-to-one.

Mappings on Finite and Infinite Sets

Proposition (Mappings on Finite and Infinite Sets)

    (i) If and are finite sets with the same number of elements, then every mapping is one-to-one if and only if it is onto.
    
    (ii) There exists a mapping from a set to itself that is one-to-one but not onto if and only if there is a mapping from the set to itself that is onto but not one-to-one (such a set is defined as an infinite set).
    
    Proof. (i): Assume that is any mapping that is one-to-one,   and consider the subset Since is one-to-one, the elements are all distinct and so contains elements. Thus showing that is onto.
    Conversely, assume that is any mapping that is onto, and assume for a contradiction that is not one-to-one. In other words, and being onto along with the assumption that at least one element of maps to two or more elements of means there are more than elements in which is a contradiction. More technically, if and for some in and some with Since is onto, for each with there exists an element such that Consider the subset The elements are distinct since is a mapping. Thus has elements which is a contradiction. Therefore, if and then and so is one-to-one.
    (ii): Let be any non-empty set. Suppose that is not onto but is one-to-one, then define a mapping that is not one-to-one but is onto. Since is not onto we will define on the set by using and the complement. Define by
    

                    
Notice is well defined because is one-to-one. To see this suppose If then there exists a unique such that Therefore,   By definition of pre-image and that is a mapping, is onto. Since is not onto there exists a such that Therefore, But since there must exist such that or equivalently Whence, is not one-to-one.
    Suppose that is onto and not one-to-one, then define a mapping that is one-to-one but is not onto. For each choose a  unique such that and let be the collection of all such Since is onto (and by the Axiom of Choice) this process defines a mapping     by By construction β is one-to-one. If β were onto then would be one-to-one. Thus, is not onto.
    

  

Composition of Mappings

Definition (Composition of Mappings) If and then the composition (denoted by ), is a mapping from to and is defined by for each

Proposition (Properties of Composition) Assume and
    (i) If and are onto, then is onto.
    (ii) If is onto, then is onto.
    (iii) If and are one-to-one, then is one-to-one.
    (iv) If is one-to-one, then is one-to-one.
    
    Proof.  (i): Assume that and are onto and Because is onto, there exists such that Since is onto there exists such that So which means there exists such that and so is onto.
    (ii): Assume that is onto and Then there exists such that But then with Hence is onto.
    (iii): Assume that both and are one-to-one and Then because is one-to-one; and because is one-to-one. Therefore, is one-to-one.
    (iv): Assume that is one-to-one, and then Since is one-to-one, and thus is one-to-one.  

Invertible Mappings

Definition (Invertible Mappings) A mapping is an inverse of if both and A mapping is said to be invertible if it has an inverse.

Proposition (Invertible Mappings)    

    (i) A mapping is invertible if and only if it is both one-to-one and onto.
    
    (ii) An inverse of an invertible mapping is invertible.
    
    Proof. (i): Assume that is invertible with inverse Then being the identity mapping on is one-to-one; therefore, must be one-to-one. Also, being the identity mapping on is onto; whence is onto. Therefore, if is invertible it is also one-to-one and onto. Conversely, assume that is onto and one-to-one and Since is onto there exists such that But is also one-to-one, so this element must be unique. Using this , define This can be done for each element in and in this way a mapping is constructed such that and Thus is invertible.
    (ii):  Assume that is invertible with inverse Then being the identity mapping on is onto; therefore, must be onto. Also, being the identity mapping on is one-to-one; whence is one-to-one. Therefore β is invertible by part (i).  

Proposition (Composition-Invertible) Assume and

    (i) If and are invertible, then is invertible.
    
    (ii) If is invertible, then is onto and is one-to-one.
    
    Proof. (i): If and are invertible then and are one-to-one and onto. So is one-to-one and onto; whence is invertible.
    (ii): If is invertible, then is onto and one-to-one. Thus, is onto and is one-to-one.  

Properties of Mappings

Proposition (Properties of Mappings) Let

    (i) Then, is onto if and only if there exists a mapping such that
    
    (ii) Then, is one-to-one if and only if for every set and all mappings and if then
    
    (iii) Then, is onto if and only if there exists a mapping such that
    
    (iv) Then, is one-to-one if and only if for every set and all mappings and if then
    
    Proof. (i): Assume that is onto and let For each there exists such that (Axiom of Choice). For each pick one such that and let be the set of all such chosen pairs Then each is the first component of one ordered pair in so is a mapping. Let if and only if Then and so Conversely, assume that and there is a mapping with Given let Then so is onto.
    (ii): Assume that is onto and let Then there exists with If then Since for all it follow Assume that is not onto and let such that Define by for all and define by for all and Then since On the other hand and since Since and have the same domain and same codomain,
    (iii): Assume that is one-to-one and let Pick (Axiom of Choice) Let Since is one-to-one, each element of is the first entry in one and only one ordered pair in Hence, is a mapping. Let be where Then and since has domain and codomain we have Conversely, assume that for there exists with and that Then, if then and so is one-to-one.
    (iv): Assume that is one-to-one, and Then and so Since is one-to-one, Since for all and and have the same domain and same codomain, Conversely, assume that is not one-to-one. Then there exists in with Let and define by and define by and Then but since and   

Mappings on Power Sets

Proposition (Mappings on Power Sets) Let and let and be the sets of all subsets of and respectively. Then

    (i) induces a mapping defined by for
    
    (ii) is one-to-one if and only if is one-to-one,
    
    (iii)   is onto if and only if is onto, and
    
    (iv) if and only if
    
    Proof. (i): Suppose that such that and So there exists such that and Clearly impossible. Therefore, for any
    (ii): Assume where W.L.O.G. there exists and Then because is one-to-one, but So and therefore, is onto-to-one. Conversely, let in Since is one-to-one, and so Therefore, is one-to-one.
    (iii): Let and and consider the subset Then and Further, since is onto Conversely, let Then, since is onto, there exists such that By definition of there exists such that and so is onto.
    (iv): If then and so   Conversely, if   then and so   If then for all and so for all Conversely, if then for all and so in particular, for all Therefore, for all as desired.

Abstract Algebra Books

Contemporary Abstract Algebra (student solution menual) Buy New: $38.00 New (10) Used (4) from $38.00 (more)

A First Course in Abstract Algebra, 7th Edition List Price: $124.00 Buy Used: $45.00 You Save: $79.00 (64%) New (21) Used (20) from $45.00This is an in-depth introduction to abstract algebra. Focused on groups, rings and fields, it should give students a firm foundation for more specialized work by emphasizing an understanding of the nature (more)

Elements of Abstract Algebra List Price: $12.95 Buy Used: $4.98 You Save: $7.97 (62%) New (19) Used (21) from $4.98Helpful illustrations and exercises included throughout this lucid coverage of group theory, Galois theory and classical ideal theory stressing proof of important theorems. Includes many historical notes. (more)

Abstract Algebra Buy New: $80.79 New (30) Used (21) from $80.79Widely acclaimed algebra text. This book is designed to give the reader insight into the power and beauty that accrues from a rich interplay between different areas of mathematics. The book carefully develops (more)

Abstract Algebra: An Introduction List Price: $195.95 Buy New: $72.72 You Save: $123.23 (63%) New (19) Used (22) from $68.50Abstract Algebra: An Introduction (more)

A Book of Abstract Algebra Buy New: $90.00 New (13) Used (6) from $81.13This text is aimed at the abstract or modern algebra course taken by junior and senior math majors and many secondary math education majors. A mid-level approach, this text features clear prose, an intuitive (more)

An Introduction to Abstract Algebra with Notes to the Future Teacher List Price: $125.00 Buy New: $65.99 You Save: $59.01 (47%) New (21) Used (9) from $65.99 This traditional treatment of abstract algebra is designed for the particular needs of the mathematics teacher. Readers must have access to a Computer Algebra System (C. A. S.) such as Maple, or at minimum (more)

A History of Abstract Algebra List Price: $49.95 Buy New: $35.22 You Save: $14.73 (29%) New (30) Used (9) from $35.22Prior to the nineteenth century, algebra meant the study of the solution of polynomial equations. By the twentieth century algebra came to encompass the study of abstract, axiomatic systems such as groups, (more)

Schaum's Outline of Modern Abstract Algebra (Schaum's) List Price: $18.95 Buy Used: $5.38 You Save: $13.57 (72%) New (23) Used (26) from $5.38Confusing Textbooks? Missed Lectures? Not Enough Time? Fortunately for you, there's Schaum's Outlines. More than 40 million students have trusted Schaum's to help them succeed in the classroom and on (more)

• print this page
• pages linking here
• related pages