11
$\begingroup$

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 ?

$\endgroup$
  • $\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
4
$\begingroup$

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.

$\endgroup$
  • 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
11
$\begingroup$

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 \}$$

and

$$\{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$.

$\endgroup$
  • $\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
6
$\begingroup$

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.

$\endgroup$
  • 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
0
$\begingroup$

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).

$\endgroup$

Your Answer

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