Counting and Finiteness

The notion of counting

“Counting” is the act of finding the natural number which has a bijection with the set being counted.

Finite and Infinite sets

Ordinal Numbers

Ordinal numbers are used to identify the position of an entry in an ordered list.

We will use Von Neumann's definition of ordinals here. According to Von Neumann's definition, an ordinal is the the well-ordered set of all smaller ordinals. By this definition, the following are ordinals in sequence. \[ J_0 = \{\} \\ J_1 = \{0\} \\ J_2 = \{0,1\} \\ J_3 = \{0,1,2\} \\ J_4 = \{0,1,2,3\} \\ .. \]

Observe that by this definition the $n^{\rm th}$ ordinal is simply the natural number $n$, i.e. $J_n = n$. We note that the more common definition of ordinals is actually any isomorphism of $J_n$, but we will ignore this detail for the moment.

Finite Sets

A Finite set is any set that can be assigned a one-to-one correspondence, or “isomorphism” with any ordinal. For instance, the following sets are all finite:

• $\{1, 2, 3\}$. This has an isomorphism with $J_3$.
• $\{x | x \in \naturals$ AND $x = 2n+1$ for some $n \in \naturals$ AND $x \lt 100\}$. This set of all odd numbers less than 100 and is isomorphic with $J_{50}$.
• {all people in Pittsburgh at 3.00am on 1 Jan 2015}. This is isomorphic with $J_N$ for some $N \lt 10,000,0000$, although we may not know the actual value of $N$.

Infinite Sets

Any set which cannot be assigned an isomorphism with any $J_N$ is infinite.

Countability

Any set that is isomorphic with $\naturals$ is said to be Countable.

By this definition, $\naturals$ itself is countable.

Subsets of $\naturals$ can be countable

An interesting property of $\naturals$ is that it has subsets that have subsets that have one-to-one correspondences with the entire set. Here are some examples.

• $\{x | x \in \naturals ~~AND~~ x > 5\}$. This subset of $\naturals$ which skips the first 5 elements is also isomorphic with $\naturals$ as shown by the following figure.
  FIGURE
  
• $\naturals \setminus \{k\} = \{1, 2, \cdots, k-1, k+1, \cdots\}$, i.e. the set of natural numbers other that $k$. This is isomorphic with $\naturals$ as illustrated by the following figure. This can be formally proved by showing defining the bijection $\forall n \lt k~n \rightarrow n,~\forall n \gt k~n \rightarrow n+1$.
  FIGURE
  
• $\naturals \setminus S$, where $S$ is finite. Removing a finite number of elements from $\naturals$ also results in a set that is isomorphic with $\naturals$ itself, as shown in the following figure. In principle the existance of this map must be formally proved. The proof can follow the same lines used to prove that $\naturals$ is infinite, given below.
  FIGURE
  

We will list other, more curious examples of countable sets, but first we must discuss if $\naturals$ is finite.

Countabilite sets are Infinite

First we prove the following proposition.

Proposition: $\naturals$ is infinite

This may appear to be obvious, in fact it is not so, and must be proved. In order to prove that $\naturals$ is infinite, we must prove that it does not have a bijection with any $J_N$.

Proof:

We will use induction and proof by contradiction.

Base Case:

$\naturals$ does not have a bijection with $J_0 = \{\}$. This follows from the fact that $\naturals$ has at least one element in it, and hence cannot have a bijection with an empty set.

Inductive Case:

Assume that $\naturals$ is not infinite. It must therefore have a bijection with some $J_{n}$. Consider $n-1 \in J_n$. In the bijection be this must have some map within $\naturals$. Let the corresponding element in $\naturals$ be $k$. We can remove $n-1$ from $J_n$ and $k$ from $\naturals$ and the two resulting sets will still have a bijection, i.e. $\naturals \setminus \{k\} \longleftrightarrow J_n \setminus \{n-1\}$.

But $J_n \setminus \{n-1\} = J_{n-1}$. Also we know from the earlier examples that $\naturals$ has a bijection with $\naturals \setminus \{k\}$. So, this implies that $\naturals \longleftrightarrow J_{n-1}$, i.e., if $\naturals$ has a bijection with $J_n$, it must have a bijection with $J_{n-1}$.

Recurisvely, this means that $\naturals$ must have a bijection with $J_0$, which we know to be untrue from our base case.

Hence $\naturals$ cannot have a bijection with any $J_n$. $\naturals$ must be infinite.

Corollary: All countable sets are infinite

This follows directly from the fact that countable sets are isomorphic with $\naturals$, which is infinite.

You can delete a countable set from a countable set and still get a countable set

An interesting property of $\naturals$ is that you can remove an inifnite number of elements from it, and still get a set that has one-to-one correspondence with itself. Below are some examples. In fact, the property that you can remove an inifnite number of elements from a set and the result can be isomorphic with the original set is true of all infinite sets.

• $\{x | x \in \naturals$ AND $x$ is even$\}$. Although this set is only considering every second element of $\naturals$ it has a one-to-one correspondence with $\naturals$ itself as shown by the following figure.
  FIGURE
  
• $\{x | x$ is prime$\}$. The set of all prime numbers is also isomorphic with $\naturals$ itself, as shown in the following figure.
  FIGURE
  

$\ints$ are countable

$\rationals$ is countable