1. ## proving infinite n

Hello

Given

$\forall n0$, $\exists n$> n0, P(n)

I am trying to prove that there are an infinite number of values n for which the
property
P(n) is true.

My initial thoughts are to assume only a limited n for which P(n) is true, for example only P(1), P(2) and P(3) are true and the rest is false. Then prove impossible, but I got stuck.

Kardash

2. ## Re: proving infinite n

As a clarification, what is the property P(n)?

3. ## Re: proving infinite n

Originally Posted by Ackbeet
As a clarification, what is the property P(n)?
Unfortunately, the question has not specified it. Is it possible to solve it without knowking P?

4. ## Re: proving infinite n

Originally Posted by kardash
Unfortunately, the question has not specified it. Is it possible to solve it without knowking P?
Come to think of it, I think the answer is yes. Last night I don't think I was thinking clearly. You are given the statement that

$(\forall n_{0})(\exists n)((n>n_{0})\land P(n)).$

I think your proof method is on the right track. If P(n) is not true for an infinite number of n's, then there is some maximum value N such that P(N) is true. Can you see how to set up a contradiction here?

5. ## Re: proving infinite n

This is what I am thinking about, but appreciate your help to formalize it and state it in proper math terms.

First I negated the sentence
$\exists n0$, $\forall n$> n0, P(n)

Then I assume P(n) is only true for P(1), P(2)

Then I assume n0=10

In this case P(n) does not hold.

Could you help to formalize this properly?

Kardash

6. ## Re: proving infinite n

Suppose there are only finitely many n such that P(n). If there are no n such that P(n), then given any m there is a k>m such that P(k), which contradicts that there are no n such that P(n). If there is an n such that P(n), then let m be the maximum such n, but then there is a k>m such that P(k), which contradicts that m is the maximum. It's that easy. The important lemma used is that any finite set of natural numbers has a maximum member.

7. ## Re: proving infinite n

Thank you for your reply. You are an expert and I was not able to understand your statement fully. Kindly help me understand.

Originally Posted by MoeBlee
Suppose there are only finitely many n such that P(n). If there are no n such that P(n), then given any m there is a k>m such that P(k), which contradicts that there are no n such that P(n).
We assume there is finite P(n), OK. Then what is meant by "If there are no n such that P(n)" ?? Could you give me an example?

Originally Posted by MoeBlee
If there is an n such that P(n), then let m be the maximum such n, but then there is a k>m such that P(k), which contradicts that m is the maximum. It's that easy. The important lemma used is that any finite set of natural numbers has a maximum member.
Could you explain by examples?

Was my initial thoughts correct? Or you have suggested a new approach?

My apologies but I was not able to understand. I am a beginner ....Thanks

8. ## Re: proving infinite n

Originally Posted by kardash
You are an expert
Not really.

Originally Posted by kardash
what is meant by "If there are no n such that P(n)" ?
It means: It is not the case that there exists a natural number n such that P(n) holds.

The expression "P(n)" stands for (in a manner of speaking) "n has the property P". To say "there is no (natural number) n such that P(n)" is to say that there is no natural number with the property P.

The argument is simple:

The assumption of the problem is that given any natural number m there is a natural number k greater than m that has property P. So let m be any natural number whatsoever. So there is a natural number k greater than m that has property k. So the set of natural numbers having property P is nonempty. Now, toward a contradiction suppose that the set of natural numbers having property P is a finite set. So the set of natural numbers that have property P is nonempty and finite. So there is a greatest natural number m having property P. But then, by the assumption of the problem, there is a natural number k greater than m such that k has property P. But that contradicts that m is the greatest natural number having property P. So the set of natural numbers having property P is not a finite set, i.e., the set of natural numbers having property P is an infinite set.

9. ## Re: proving infinite n

Thank you for clarifying that.

In this case, I guess there is no need for me to negate the sentence, right? Will it be sufficient to explain in words?

Thanks again

10. ## Re: proving infinite n

We assume the negation of "there are infinitely many n such that P9n)", then derive a contradiction, then conclude "there are infinitely many n such that P(n)".

As to what is sufficient for this proof, it depends on the context, whether the exercise is with regard to a certain mathematical system in a certain formula language, or just ordinary mathematics that mixes symbols and natural language, or whatever. In any case, the argument I gave is adequate as an ordinary mathematical argument.