Countable & uncountable sets

Definition: Countable set.: A countable set is a set that is bijective to . Definition: Infinite set: Infinite sets that are not countable are called uncountable sets.

• Note that we do NOT consider finite sets to be countable.

Cardinality

Definition: Cardinality. is a set. The cardinality of is the number of elements contained in . For example, if ,

• The cardinality of ,
  • This shows that there are infinities that are bigger and smaller than
• Let be two non-empty sets.
  • If , then there exists an injection
  • if , then there exists a surjection

Power sets

Definition: Power sets. Let be a non-empty set. The power set of denoted or is the collection of all subsets of . For example: Let . Then, . , .

• For any finite set with elements

Infinite countable sets

• is the smallest infinite set
  • The next largest infinite set is which is bijective to
  • The next is
  • The continuum hypothesis asks if there are infinite sets that are not countable and has cardinality smaller than

Infinite uncountable sets

• There are also sets that are infinite but not countable
  • This means that they cannot be defined as bijective to
• This is shown through Georg Cantor’s diagonal argument