Equinumerous and Countability

Equinumerous Sets

Equinumerous

Let and be two sets. If there exists a bijection , then we say is equinumerous or equivalent to and write .

e.g. We have because the function defined by is a bijection.

Proposition

The equinumerous relation is an equivalence relation.

Proof The identity function is a bijection , thus it is reflexive. If , then there is a bijection . The inverse function is also a bijection. Thus , therefore it is symmetric. If and , then there exist bijection and . Since the composition is a bijection, we have , thus it is transitive.

Proposition

.

Proof Take a sequence with distinct elements in , say for . Define as follows: Clearly f is a bijection and thus .

Countability of Sets

Finite Set

A set is called finite if it is either empty or it is equinumerous to for some . If a set is not finite, then it is called infinite.

Denumerability & Countability

A set is called denumerable if it is equinumerous to . A set is called countable if it is either finite or denumerable. A set that is not countable is called uncountable.

Theorem

Any denumerable set is infinite.

Proof Assume a nonempty denumerable set is finite. Then for some we have . By definition of denumerability, we have . By transitivity, , yielding a contradiction.

Proposition

The difference between any infinite set and finite set is still infinite.

Proof Suppose set is infinite and set is finite. Assume is finite, and .

Theorem

Any infinite set contains a denumerable subset.

Proof Suppose is a infinite set. Then , and pick . Since is infinite, . Thus we can pick . We have and . We can repeat this procedure. If the procedure ended up in finite many steps, we would get a set for some such that which means , contradicting the assumption that is infinite. Therefore, the above procedure does not end up in finite many steps. It then produces an infinite sequence contained in with distinct elements.

Proposition

The set of real numbers is uncountable.

Proof Assume exists be some bijection. Then the range of is , which is