Characterizing Finiteness

Definition 46   A set S is finite if for every $f:S\to S$ and every $s\in S$ the sequence defined inductively by s₀=s, s_n+1=f(s_n) is eventually periodic; that is, there are natural numbers k and $p\neq 0$ such that s_k=s_p+k.

Proposition 6.12   The empty set $\emptyset$ is finite.

Theorem 6.13   If a set S is infinite, then it is not finite.

Definition 47   The the cardinal set $[n]=\{k\in Naturals\vert k<n\}$. Note that [n] has exactly n elements.

Proposition 6.14   The cardinal [n] is finite.

Proposition 6.15   If A is finite and $B\subseteq A$ then B is finite.

Proposition 6.16   If A is finite and $f:A\to B$ is onto, then B is finite.

Proposition 6.17   A subset $S\subseteq \ensuremath{\mathbb{N} }$ is finite if and only if there is an $n\in \ensuremath{\mathbb{N} }$ with $S\subseteq [n]$.

Proposition 6.18   If A and B are finite then so are $A\times B$, A+B, and $A\cup B$.

Theorem 6.19   A set S is finite if and only if it is not infinite.