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. MAT246 Lecture8 (2012-11-07)
Ex3. The set of natural numbers and the set of non-negative integers have the same cardinality.
Proof: let be the set of non-negative integers.
Define a function by letting
Part1.
Thus, is injective.
Part2. The range is all of
Thus, is surejective.
That is, and have the same cardinality.
Definiton 10.1.12

More
Less