Mappings on Finite and Infinite Sets

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 If in and and then is empty and thus so is So there is no element such that Therefore, and so is one-to-one.

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 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 nonempty 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.
    

  

• print this page
• pages linking here
• related pages