almost all
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000: Often mathematicians use expressions such as "almost every positive integer is composite" or "almost all real numbers are irrational." In each case almost every or almost all means all but a "negligible" fraction, but how we define that fraction (and negligible) depends on the underlying set.

In the positive integers (the usual case in this glossary):

Let P(n) be a predicate (a statement about the integer n such as "n is prime"). Let #P(N) be the number of positive integers n less than N which satisfy P(n). For example, if P(n) = "n is even," then #P(N) is floor(N/2).

If the ratio #P(N)/N gets arbitrarily close to 1 as N gets big (that is, lim #P(N)/N = 1 as N approaches infinity), then we say "for almost every n, P(n)."

For example, if P(n) is "n is composite," then #P(N) is about (1 - 1/log N) N (by the prime number theorem), so #P(N)/N is about 1-1/log N. This clearly gets close to 1 as N gets large; so, almost every positive integer is composite.

In other sets:
In other sets the concept "almost every" is defined in different ways. For example, in the real numbers a common way to define "almost every" is to specify all but a set of measure zero (usually using the Lesbegue measure). These ideas are beyond the scope of this glossary.




Chris K. Caldwell © 1999-2017 (all rights reserved)