Question

Use the pigeon hole principle to prove that initial segments of the counting numbers are finite

Answer 1

Initial segment determined by n, a natural number, is defined as the set = {1,2,...,n-1}. Now suppose for some n, the set is infinite then since the set contains elements less than n, hence by pigeon hole principle, there are infinitely many elements in equal to a particular . But this means that for every such such that , the set contains just one element namely k. This happens for every k<n. Thus contains all k<n and moreover every such k appears once which makes the set finite.