# MAT246H1 Lecture Notes - Surjective Function, Natural Number, Bijection

69 views3 pages MAT246 Lecture8 (2012-11-07)
Size of infinite sets
Definition 10.1.1. A set means any collection of things. The things are called elements of the set. If S is a
set, a subset of S is a set all of whose elements are elements of the set S. The empty set is the set
that has no elements at all. The empty set is a subset of every set. The union of a collection of sets is the
set consisting of all elements that occur in any of the given sets. The intersection of a collection of sets is
the set containing all elements that are in every set in the given collection. If the intersection of two sets
is the empty set, the sets are said to be disjoint.
Definition 10.1.3. The set S and T are said to have the same cardinality if their elements can be paired
with each other’s.
Definition 10.1.4. The notation   is used to denote a function taking the set into the set
; that is, a mapping of each element of to an element of . The set is called the domain of the
function. The range is the set of all its values; that is, the range of   is   .
Definition 10.1.5. A function   is said to be one-to-one/injective if    whenever
 . That is, a function is one-to-one if it does not set two different elements to the same element.
Definition 10.1.6. A function   is onto/surjective if for every   there is an    such
that  ; that is, the range of is all of .
Definition 10.1.7. The sets and have the same cardinality if there is a bijective function  
that is one-to-one and is also onto all of . Denoted as .
Ex1. The sets of even natural numbers and odd natural numbers have the same cardinality.
Proof:
Let be the set of even natural numbers; be the set of odd natural numbers.
If     ;    , then define a function taking    by letting
     for each  .
        , thus is injective.
The range of is all of , thus is surjective.
That is, and have the same cardinality.
Ex2. The set of even natural numbers has the same cardinality as the set of all natural numbers.
Proof:
Let be the set of even natural numbers; be the set of all natural numbers.
Define a function   by letting  
Part1.      
Thus, is injective.
Part2. If        
Thus, is surjective.
That is, and have the same cardinality.
Unlock document

This preview shows page 1 of the document.
Unlock all 3 pages and 3 million more documents.