As a clarification, what is the property P(n)?
Hello
Given
, > 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.
Could someone please help?
Thanks in advance
Kardash
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
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?
Thanks for replying.
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
, > 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
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.
Thank you for your reply. You are an expert and I was not able to understand your statement fully. Kindly help me understand.
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?
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
Not really.
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.
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.