Scribd
Upload
40 views1 page

Study Notes - Cardinality: Let F

The document defines cardinality and countable sets. A set is countable if its elements can be listed as a1, a2, a3 and so on. It provides examples of countable and uncountable sets like natural numbers and real numbers on the interval [0,1].

Uploaded by

Yoni Mac
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
40 views1 page

Study Notes - Cardinality: Let F

The document defines cardinality and countable sets. A set is countable if its elements can be listed as a1, a2, a3 and so on. It provides examples of countable and uncountable sets like natural numbers and real numbers on the interval [0,1].

Uploaded by

Yoni Mac
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Study Notes | Cardinality

DEFINITION: (The cardinality of a set). Two sets A and B have the same cardinal number if there exist a
one to one function from A onto B. (i.e. a bijective function) If so, they are said to be equinumerous. The
cardinality of A is represented by A .

DEFINITION: A set A is finite if either A is the empty set (which has a cardinal number 0) or there is an
n in N such that A is equinumerous to {1, 2,3,..., n} . (In which case A has cardinal number n ).

DEFINITION: A set A is a countable set if it is finite or if A = N . The cardinal number of N is also


denoted ℵ0 . This is the first letter of the Hebrew alphabet, aleph, with subscript zero. It is pronounced aleph
nought. An infinite set that is not countable is called an uncountable set. Notice that two uncountable sets
could have different cardinalities.

Actually, a set A is countable if the elements of A are finite or may be listed as a1, a2, a3, a4, … The
list itself determines a bijection from N to A . Also, countable sets are the smallest infinite sets.

DEFINITION: A set is infinite if it can be placed in a 1-1 correspondence with a proper subset of itself.
_______________________________________________________________________________________

Example: Consider the natural numbers.

{1,2,3,4, 5,..., n,...}


↓↓↓↓↓ ↓
{2,4,6,8,10,..,2n,...}
We have a bijective function and these two sets have the same cardinality. Therefore, we have a 1-1
correspondence with a proper subset of the natural numbers.

Example: Do the integers and natural numbers have the same number of elements? (i.e. can we place
them into a 1-1 correspondence with each other)

{1, 2, 3, 4, 5, 6, 7,..., 2n, 2n + 1,... }


↓↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
{0,1, −1,2, − 2,3, − 3,..., n, − n,...} Therefore yes !

Example: Show that S = [ 0,1] and T = [0,1) are equinumerious by finding a bijection between the sets.

Let f ( x ) = 1/( n +1) if there exist a


x otherwise
1/ n 
n∈ N such that x =

 

You should spend some time with this function to thoroughly understand what is taking place here!!

You might also like