13

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 ?

psmears
  • 767

4 Answers4

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

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

Michael Albanese
  • 99,526
  • So, do you mean that ${ n : P(n) true }$ contains infinitely many elements in the sense that this set is uncountable ? –  Dec 30 '14 at 07:34
  • @WillieRosario No, it can be countable. For example, the set of natural numbers is countable (but infinite). – 5xum Dec 30 '14 at 07:36
  • so what is the definition of infinite then? maybe I am confused with terminology –  Dec 30 '14 at 07:37
  • 4
    Infinite literally means not finite. – Michael Albanese Dec 30 '14 at 07:42
  • im confused now. –  Dec 30 '14 at 07:44
  • A set is infinite if it is not finite. An infinite set that is in one-to-one correspondence with $\mathbb{N}$ is called countable; examples include $\mathbb{N}$, $\mathbb{Z}$, and $\mathbb{Q}$. An infinite set which is not in one-to-one correspondence with $\mathbb{N}$ is called uncountable; examples include $\mathbb{R}$ and $\mathbb{C}$. – Michael Albanese Dec 30 '14 at 07:47
  • 6
    @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. – zibadawa timmy Dec 30 '14 at 07:49
6

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.

copper.hat
  • 172,524
  • 1
    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? – KSmarts Dec 30 '14 at 15:18
  • 1
    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 :-). – copper.hat Dec 30 '14 at 15:33
4

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.

Felipe Gavilan
  • 643
0

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

Dan Uznanski
  • 11,025