Suppose $P(n)$ is certain statement. I hear all the time that my teachers say

$$ P(n) \; \; \text{occurs for infinitely many} \; \; \;n $$

$$ P(n) \; \; \text{for all but finitely many} \; \; n $$

MY question: What are the precise definitions of this statements ?

  • $\begingroup$ e.g. all naturals that are a power of $2$ vs all primes that are odd. $\endgroup$ – Yves Daoust Dec 30 '14 at 14:39
  • $\begingroup$ To be explicit, "all but finitely many" implies "occurs for infinitely many". $\endgroup$ – jII Nov 22 '18 at 18:01

The first statement ($P(n) \; \; \text{occurs for infinitely many} \; \; \;n$) means that there is an infinite number of ways to satisfy the proposition $P(n)$. Just like Michael says, in $\mathbb(n)$ let $P(n)$ : n is even, then there is an infinite number of $n \in\mathbb N$ that satisfies $P(n)$ (because there are infinitely many even numbers).

The second statement ($P(n) \; \; \text{for all but finitely many} \; \; n$) means that, although there is an infinite number of ways of satisfying a condition $P(n)$, there is a finite number of exceptions. For example, in $\mathbb N$ let $P(n)$ : n > 5. There is a inifinite number of $n \in\mathbb N$ that satisfies $P(n)$ (there are infinitely many natural numbers greater than 5), but there is a finite number of exceptions, in our case, the numbers: 0, 1, 2, 3, 4 and 5 are those exceptions.

  • 1
    $\begingroup$ It seems $5$ is also an exception. $\endgroup$ – GEdgar Dec 30 '14 at 15:08
  • $\begingroup$ Edited! Thanks :) $\endgroup$ – Felipe Gavilan Dec 30 '14 at 15:14

We say $P(n)$ occurs for infinitely many $n$ if $\{n \mid P(n)\ \text{is true}\}$ contains infinitely many elements.

We say $P(n)$ occurs for all but finitely many $n$ if $\{n \mid P(n)\ \text{is not true}\}$ contains only finitely many elements.

Example: For the set $\mathbb{N}$, consider $P(n):$ $n$ is even. We have

$$\{n \mid P(n)\ \text{is true}\} = \{2, 4, 6, \dots \}$$


$$\{n \mid P(n)\ \text{is not true}\} = \{1, 3, 5, \dots \}.$$

As $\{n \mid P(n)\ \text{is true}\}$ contains infinitely many elements, we can say that $P(n)$ occurs for infinitely many $n$.

As $\{n \mid P(n)\ \text{is not true}\}$ contains infinitely many elements, we cannot say that $P(n)$ occurs for all but finitely many $n$.

  • $\begingroup$ So, do you mean that $\{ n : P(n) true \}$ contains infinitely many elements in the sense that this set is uncountable ? $\endgroup$ – user203867 Dec 30 '14 at 7:34
  • $\begingroup$ @WillieRosario No, it can be countable. For example, the set of natural numbers is countable (but infinite). $\endgroup$ – 5xum Dec 30 '14 at 7:36
  • $\begingroup$ so what is the definition of infinite then? maybe I am confused with terminology $\endgroup$ – user203867 Dec 30 '14 at 7:37
  • 4
    $\begingroup$ Infinite literally means not finite. $\endgroup$ – Michael Albanese Dec 30 '14 at 7:42
  • 6
    $\begingroup$ @WillieRosario Then your problem has little to do with the phrases you mentioned, and everything to do with you not knowing the definitions for finite and infinite. I suggest going back to that part of the text and class notes. $\endgroup$ – zibadawa timmy Dec 30 '14 at 7:49

I am assuming that $n \in \mathbb{N}$ in the following:

The first statement corresponds to $\forall n$ $\exists k\ge n$ such that $p(k)$ is true.

The second statement corresponds to $\exists n$ such that $\forall k \ge n$ $p(k)$ is true.

  • 1
    $\begingroup$ You seem to be assuming that $n$ is a natural number, which is not specified. If $n$ is, for example, an integer, and $P(k)$ means "$k>0$", then $P(n)$ occurs for infinitely many $n$, but your first statement is false. Similarly, if $n\in\Bbb{Z}^-$, and $P(k)$ means $k\ne -1$, then $P(n)$ for all but finitely many $n$, but your second statement is false. And what if $n$ is not in a totally ordered set? $\endgroup$ – KSmarts Dec 30 '14 at 15:18
  • 1
    $\begingroup$ This is true, but the OP is trying to understand what the expressions mean so it seems prudent to work with a straightforward, concrete example. Plus, of course, the symbol $n$ means it must be a natural number :-). $\endgroup$ – copper.hat Dec 30 '14 at 15:33

Some concrete examples.

For $P(n)$ = "$P$ is prime", $P(n)$ and $\neg P(n)$ both occur for infinitely many $n$: there is no last prime, nor a last non-prime (composite).

For $P(n)$ = "$P$ is a McNugget Number", P(n) is true for all except finitely many $n$: there's only 22 different McNugget counts that cannot be created (using boxes of 6, 9, and 20).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy