Chapter IV · Limits of functions of a positive integral variable

Finite and infinite classes

§52 20 min

An infinite class is simply one that is not finite; for sets of positive integers this means having no largest member.

Why this matters

Every definition in the rest of this chapter rests on two words, finite and infinite. “Only finitely many terms lie outside the band” is the whole content of a limit, and the difference between “all but finitely many nn” and “infinitely many nn” is the difference between converging and not. §52 pauses to say what these words mean, and in particular that “an infinite number” is not a number.

The idea

A class (today: a set) is the collection of all things with some property: British subjects, members of Parliament, positive integers, real numbers. A class is finite if it has some definite number of members, 0,1,2,…0, 1, 2, \dots, even if nobody knows that number. Hardy’s example is the class of all British subjects, past, present and future: finite, though we cannot say how many.

The positive integers are different. Name any number nn, however large (a thousand, a million), and there are more than nn positive integers: 1,2,…,n+11, 2, \dots, n+1 already are. That is all “infinite” means. Try the challenge: name a number, and see whether each class can beat it.

Explore Name a number; can the class beat it?

Try this. Choose a class and raise nn. Try the divisors of 360360 with n=23n = 23 and then n=24n = 24. Then choose the primes, and read Euclid's witness for a few values of nn.

The class {2,3,5,7,… }\{2, 3, 5, 7, \dots\}
Here are 11 different members, more than n=10n = 10: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Euclid: no finite list of primes can be complete (see below).
Euclid’s witness. Multiply the first 10 primes (2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 · 29) and add 1: P=6469693231P = 6469693231. Dividing PP by any of those primes leaves remainder 1, so its smallest prime factor, 331331, is a prime missing from the list.
What to notice

The infinite classes answer every nn with n+1n + 1 members. The finite ones run out at a definite point and stay out. The primes are the interesting case: we can list n+1n + 1 of them only because Euclid's argument guarantees that no finite list of primes is complete; the witness shows a new prime, built from the old ones, every time.

So “there are an infinite number of primes” is shorthand for “the class of primes is not finite”. It does not say that the primes are counted by some enormous number called “infinity”. The same caution returns in §55, where the symbol ∞\infty appears for the first time.

Precise statements

Definition Finite and infinite classes Hardy: §52

A class is finite if, for some whole number N≥0N \ge 0, its members can be listed as a1,a2,…,aNa_1, a_2, \dots, a_N (with N=0N = 0 for the empty class). It is infinite if it is not finite. Equivalently, a class is infinite if, for every positive integer nn, it has more than nn members.

For classes of positive integers, which are the only ones the next lessons need, there is a sharper and very practical test.

Theorem Finite sets of positive integers

A class EE of positive integers is finite if and only if either EE is empty or EE has a largest member. Equivalently, EE is infinite if and only if, for every n0n_0, EE contains some n>n0n > n_0.

Theorem There are infinitely many primes Hardy: Euclid; Examples XXIII, 2

The class of prime numbers is infinite.

Proofs

Proof Finite sets of positive integers
Strategy

A finite list has a largest entry; conversely, a set of positive integers with a largest member MM sits inside 1,2,…,M1, 2, \dots, M, which is finite.

Finite and non-empty implies a largest member

List the members as a1,…,aNa_1, \dots, a_N with N≥1N \ge 1. The larger of two numbers exists, and repeating this N−1N - 1 times gives the largest of a1,…,aNa_1, \dots, a_N.

A largest member implies finite

If MM is the largest member, every member is one of 1,2,…,M1, 2, \dots, M. So EE has at most MM members, and listing those of 1,…,M1, \dots, M that lie in EE gives a finite list.

Restate for infinite sets

Take negations. EE is infinite exactly when it is non-empty with no largest member, that is, when every member n0n_0 (and hence every number n0n_0 at all) is exceeded by some member of EE.

The theorem turns “finitely many exceptions” into “no exceptions beyond some point”. That translation is the whole of the next lesson.

Proof There are infinitely many primes
Strategy

Show that no finite list of primes can contain them all: from the list, build a number whose prime factors are all missing from it.

Take any finite list of primes

Let p1,p2,…,pNp_1, p_2, \dots, p_N be any primes (for instance the first NN).

Form P=p1p2⋯pN+1P = p_1 p_2 \cdots p_N + 1

Then P≥2P \ge 2, so PP has at least one prime factor: its smallest factor greater than 11 is prime, since any factor of that factor would be a smaller factor of PP.

No pkp_k divides PP

Dividing PP by pkp_k leaves remainder 11, because pkp_k divides the product p1⋯pNp_1 \cdots p_N. So every prime factor of PP is a prime not on the list.

Conclude

Every finite list of primes misses some prime, so the class of primes is not finite. In the language of the definition: for every nn there are more than nn primes.

Notice that PP itself need not be prime: 2⋅3⋅5⋅7⋅11⋅13+1=30031=59⋅5092 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509. The argument only needs some prime factor of PP to be new.

Worked examples and exercises

Exercise Finite or infinite? ●○○ Hardy: §52

Decide whether each class is finite or infinite: (a) the perfect squares; (b) the positive integers nn with n2<1000n^2 < 1000; (c) the multiples of 100100; (d) the real roots of x5−3x+1=0x^5 - 3x + 1 = 0; (e) the fractions in (0,1)(0, 1); (f) the leap years after 2000.

Hint
For each infinite class, show how to produce more than nn members for any nn. For each finite one, give a bound on the number of members.

Solution

(a) Infinite: 12,22,…,(n+1)21^2, 2^2, \dots, (n+1)^2 are n+1n + 1 different members. (b) Finite: n2<1000n^2 < 1000 forces n≤31n \le 31, so there are exactly 3131 members. (c) Infinite: 100,200,…,100(n+1)100, 200, \dots, 100(n+1). (d) Finite: a polynomial of degree 55 has at most 55 roots (in fact this one has 33 real roots). (e) Infinite: 12,13,…,1n+2\tfrac12, \tfrac13, \dots, \tfrac{1}{n+2}. (f) Infinite: every year 2000+400k2000 + 400k with k≥1k \ge 1 is a leap year under the Gregorian rules.

Exercise Combining classes ●○○ Hardy: §52

Show that (a) a subclass of a finite class is finite; (b) the union of two finite classes is finite; (c) a class containing an infinite subclass is infinite.

Solution

(a) If AA has NN members and B⊆AB \subseteq A, listing the members of AA and keeping those in BB lists BB with at most NN members. (b) If AA has MM members and BB has NN, listing AA and then BB lists every member of the union, with at most M+NM + N entries; remove repetitions. (c) If C⊇BC \supseteq B with BB infinite and CC were finite, then BB would be finite by (a), a contradiction.

Exercise Two complementary classes ●●○ Hardy: §52

Split the positive integers into two classes AA and BB, so that every positive integer is in exactly one of them. Show that at least one of AA, BB is infinite, and give examples in which (i) only AA is infinite, (ii) both are infinite.

Hint
Use part (b) of the previous exercise.

Solution

If both were finite, their union, the class of all positive integers, would be finite by (b), which it is not. Examples: (i) A={n:n≥10}A = \{n : n \ge 10\}, B={1,…,9}B = \{1, \dots, 9\}; (ii) AA the even numbers, BB the odd numbers. These are exactly the cases (a) and (c) that Hardy distinguishes in §53, with AA the nn that have some property and BB those that do not.

Exercise Euclid's numbers ●○○ Hardy: Examples XXIII, 2

Compute P=2⋅3⋅5⋅7+1P = 2 \cdot 3 \cdot 5 \cdot 7 + 1 and P′=2⋅3⋅5⋅7⋅11⋅13⋅17+1P' = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 + 1, and find a prime factor of each that is not among the primes used.

Solution

P=211P = 211, which is itself prime (it is not divisible by 2,3,5,7,112, 3, 5, 7, 11 or 1313, and 172>21117^2 > 211). P′=510511=19⋅26869P' = 510511 = 19 \cdot 26869; the prime 1919 is not among 2,…,172, \dots, 17. (The other factor, 26869=97⋅27726869 = 97 \cdot 277, is not prime, but we only need one new prime.)

Check yourself

Check yourself True or false?

“There are an infinite number of primes” means that the number of primes is a very large number called infinity.

Why

False. It means only that the class of primes is not finite: for every nn there are more than nn primes. There is no number “infinity” that counts them; the phrase is shorthand, as Hardy insists.

Check yourself Choose one

Hardy calls the class of all British subjects, past, present and future, finite. Why?

Why

Finiteness is a property of the class, not of our ability to count it. A class can be finite with an unknown number of members. Being “smaller” than the integers is not the definition (and some infinite classes, such as the even numbers, are part of the integers too).

Check yourself Choose one

A class EE of positive integers has the property that, for every n0n_0, some member of EE is greater than n0n_0. What can you conclude?

Why

A set of positive integers with members beyond every bound has no largest member, so by the theorem it is infinite. It need not contain all large integers: the even numbers have members beyond every bound but miss every odd number. That difference is exactly the topic of the next lesson.

Hardy’s language

But the reader must be careful always to remember that by saying this we mean simply that the class in question has not a finite number of members such as 1000, or 1,000,000.

— G. H. Hardy, §52

Summary

Summary
  • A class (set) is finite if it has some definite number NN of members, known or not; it is infinite if it is not finite.
  • Equivalently, infinite means: for every nn, there are more than nn members. “An infinite number” is shorthand, not a number.
  • A set of positive integers is finite exactly when it is empty or has a largest member; it is infinite exactly when it has members beyond every n0n_0.
  • Euclid: any finite list of primes misses a prime, so the primes form an infinite class.