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