I'm faced with this sentence in a solution of a problem:
The negation of "$P(n)$ for infinitely many $n$" is "$\lnot p(n)$ for large enough $n$".
What is the difference between infinitely many and large enough $n$?
Asked
Active
Viewed 2,949 times
11
Asaf Karagila
- 393,674
Fatemeh Karimi
- 402
- 5
- 13
-
https://math.stackexchange.com/questions/301318/meaning-of-infinitely-many-is-it-same-as-forall/ – Asaf Karagila Jul 16 '17 at 08:11
-
@AsafKaragila I read this question and I didn't understand!! hence, I asked my own question – Fatemeh Karimi Jul 16 '17 at 11:53
-
11For future reference, in a situation like this you should include a link to the question and try to explain what was unclear about the answers. – Asaf Karagila Jul 16 '17 at 12:36
-
1When we say "for large enough $n$," we mean (assuming that $n$ is intended to denote a natural number) "for all but finitely-many $n$." – Cameron Buie Jul 16 '17 at 19:17
5 Answers
27
It is true that infinitely many integers are even.
But it is not true that all large enough integers are even, because no matter how big an integer you pick, I can always find an odd integer which is bigger.
Ted
- 33,788
16
Perhaps these definitions will clarify the issue:
- We say that $P(n)$ holds for infinitely many $n$ if for any $N$ there is $n>N$ so that $P(n)$ is true.1
- We say that $P(n)$ holds for large enough (or sufficiently large) $n$ if there is $N$ so that $P(n)$ is true for all $n>N$.
With these definitions, can you see why "$P(n)$ for infinitely many $n$" and "$\lnot P(n)$ for large enough $n$" are negations of each other?
It might be that the source you are using has different definitions. If that is the case, it is best to include the definitions in your question to make sure every speaks exactly the same language. The definitions I gave above are not the only possible way to define these concepts.
1 Mind you, this is true if we are working over $\mathbb N$, but not in general. For something less context-dependent, you could say that the set $\{n\in\mathbb N;P(n)\}$ is infinite. The reason I chose not to go this way is to make the comparison clearer.
Joonas Ilmavirta
- 25,809
6
When something is true for infinitely many $n$, it doesn't have to be true always even when $n$ gets massive. For example, $P(n)$ might be "$n$ is a prime". This statement is true for infinitely many $n$, but it's not the case that as soon as $n>n_0$ for some number $n_0$, every $n$ is an prime number.
On the other hand, if something is true when $n$ is large enough, then it's true for infinitely many $n$. This is because there are infinitely many numbers.
1
We can convert one statement to the other by simple manipulations:
Negation of "Property P(n) for infinitely many n" ==
Negation of "Infinitely many n have the Property P(n)" ==
"Only Finitely many n have the Property P(n)"
We have only a finite set of elements where Property P(n) is true.
Now, every finite set has a maximal element M; hence Property P(n) is false for all n>M.
We do not wish to find M, but it must be some finite "sufficiently large" number.
Hence "Only Finitely many n have the Property P(n)" ==
"Property ¬P(n) for n>M" ==
"Property ¬P(n) for large enough n".
Prem
- 9,669
1
Formally speaking, when we talk about infinitely many $n$'s we are essentially saying: $$\forall m\exists n(m<n\land\varphi(n)),$$ namely, there is always a larger $n$ which satisfies some property.
When we say "for all large enough $n$", we mean that from some point onwards, something happens, so $$\exists m\forall n(m<n\rightarrow\varphi(n)),$$ namely, there is some $m$ such that any larger $n$ will satisfy the property.
Clearly, "for all large enough $n$" implies "there are infinitely many $n$", but not the other way around. Some examples are easy to give such as "There are infinitely many prime numbers", but it is not the case that "Every large enough $n$ is a prime number".
Asaf Karagila
- 393,674