>>11109848Proof of the contrapositive:
Suppose A is infinite.
Lemma: If we remove an element from A, the result is still infinite.
Proof of Lemma: Suppose we remove an element from A and the result is finite. Then when we add it back in, we add 1 to the cardinality, so A is finite. End proof.
Now, A is infinite, so we may remove an element of A. Call it a_1, and call the resulting set A_1. Then A_1 is infinite, and we can remove an element from A_1, call it a_2 and the remaining set A_2.
Induction: a_1 is defined, and if we suppose A_(n-1) and a_(n-1) are defined, then we may define a_n by choosing some element in A_(n-1) ane A_n as the resulting set.
By induction, a_n is defined for all n. It has no repeats, again by definition. Define f : N to A by f(n) = a_n. This is an injection from N to A. Thus |N| <= |A|.
By contrapositive, if |A| < |N|, then A is finite.
