There exists versus for all but finitely many

[ki$$a]

"there exists" versus "for all but finitely many"

Hallo everybody!

Sorry for the stupid question but I have nobody else to ask
I am new in the field so please do not be very strict

Can anybody explain me the difference between "there exists" and "for all but finitely many"?

I deal with total and partial computable functions and finite/infinite sets... I have to prove some statements. Let's imagine that I proved that "there exists some x" which satisfies the task... So does this mean that I proved the same "for all but finitely many x" ? or it is not and I should prove something else?

Thank you in advance!

 

[HallsofIvy]

They both mean pretty much "what they say". If there exist something, a number, say, that satisfies a given property, then it might be that there is just one such number, or two, or three, or it might be that there exist a large number of numbers having that property, even infinite number of such numbers. Perhaps even all numbers have that property. The only thing "there exist a number such that ..." tells you is that it is NOT the property than NO numbers have that property.

Saying "all but finitely many" numbers have a property tells you immediately that there are an infinite set of numbers with that property. That is, that the set of all numbers that do NOT have the property is finite (perhaps even empty).

 

[SteveL27]

Saying "all but finitely many" numbers have a property tells you immediately that there are an infinite set of numbers with that property.

False. All but finitely many of the living population of Earth are female. But there are only finitely many females.

You can do the same thing with "numbers" if you take any finite set of numbers as your universe. All but finitely many of the natural numbers below 100 are even. Etc.

Trivial point, but no reason to further confuse the OP's question.

"Euclid alone has looked on beauty bare"

Agents of the U.S. Secret Service have been known to pay for the privilege :-)

 

[HallsofIvy]

False. All but finitely many of the living population of Earth are female. But there are only finitely many females.

Oh, dear! You are quite correct. of course, I was thinking of the 'set' as being "all real numbers" or "all integers" which are infinite to begin with. Thank you for the correction.

You can do the same thing with "numbers" if you take any finite set of numbers as your universe. All but finitely many of the natural numbers below 100 are even. Etc.

Trivial point, but no reason to further confuse the OP's question.



Agents of the U.S. Secret Service have been known to pay for the privilege :-)

Ouch!

 

[oleador]

I am also interested in the question, but the answer is not clear to me. So, is it correct that the quantifier "for all but finitely many" may relate to either finite or infinite amount of elements depending on whether the set of the elements is a finite or an infinite set? If so, does this mean that if the set is (in)finite, then "for all but finitely many" must relate to the (in)finite amount of elements?
Thank you.

 

[ki$$a]

False. All but finitely many of the living population of Earth are female. But there are only finitely many females.

Thanks, but the difference between "there exists" and "for all but finitely many" is still unclear :shy:
I can say like that: "There exists a person who is female" and the other way is "All but finitely many persons on Earth are female".

The question is: if I need to prove something "for all but finitely many x", do I need just prove it for only one x? if it is so, then "there exists" is equal to "all but finitely many". But now it seems to me that I also should prove that for some x my something will be wrong... If speak about above-mentioned example with population I mean that I should also prove that there is at least one men... Am I right ?

 

[SW VandeCarr]

Thanks, but the difference between "there exists" and "for all but finitely many" is still unclear :shy:
I can say like that: "There exists a person who is female" and the other way is "All but finitely many persons on Earth are female".

The question is: if I need to prove something "for all but finitely many x", do I need just prove it for only one x? if it is so, then "there exists" is equal to "all but finitely many". But now it seems to me that I also should prove that for some x my something will be wrong...

Prove that even numbers are half of the sequence of natural numbers beginning with 1 and ending with an even number for all but infinitely many natural numbers.

 

[SteveL27]

Thanks, but the difference between "there exists" and "for all but finitely many" is still unclear :shy:
I can say like that: "There exists a person who is female" and the other way is "All but finitely many persons on Earth are female".

The question is: if I need to prove something "for all but finitely many x", do I need just prove it for only one x? if it is so, then "there exists" is equal to "all but finitely many". But now it seems to me that I also should prove that for some x my something will be wrong... If speak about above-mentioned example with population I mean that I should also prove that there is at least one men... Am I right ?

If P is a proposition true for "all but finitely many" elements in a universe U, then the set of elements for which P is false is finite. Which part of that is confusing to people? It's exactly what it says.

All but finitely many primes are odd. All but finitely many natural numbers are greater than 42. The set of exceptions is finite.

If all but finitely many widgets are gadgets, that means the set of widgets that are not gadgets is a finite set. You just have to slow down and think about what "all but finitely many" says.

 

[SteveL27]

I can say like that: "There exists a person who is female" and the other way is "All but finitely many persons on Earth are female".

Those are not equivalent.

If there exists a person who is female, then at least one female exists.

If all but finitely many people are female, that would still be true in an empty population. In that case NOBODY is female, yet all are female except for a finite number (zero) who aren't.

And it would be true in a finite population of males. There are five men in a room. All but finitely many of them are female, right? Count the number who aren't female. One, two, three, four, five. Finite! So all but finitely many people in the room are female, even if there are NO females in the room.

 

[ki$$a]

Those are not equivalent.

If all but finitely many people are female, that would still be true in an empty population.

Oh ! it's getting better ! Now I see at least some difference... Thanks.

 

[skiller]

I deal with total and partial computable functions and finite/infinite sets... I have to prove some statements. Let's imagine that I proved that "there exists some x" which satisfies the task... So does this mean that I proved the same "for all but finitely many x" ? or it is not and I should prove something else?

Hello ki$$a,

I hope the above replies have satisfied your curiosity, but just to sum up:

If your set of possible "x" is FINITE, whether you prove "there exists" OR NOT, it is trivial that it is true "for all but finitely many".

If your set of possible "x" is INFINITE, then proving "there exists" IS NOT sufficient to prove "for all but finitely many".

For the latter case, you need to prove that there are only a finite number of "x" that fail the proposition.As an aside, if you need to prove "there exists", then:

If your set of possible "x" is FINITE, then proving "for all but finitely many" IS NOT sufficient to prove "there exists".

If your set of possible "x" is INFINITE, then proving "for all but finitely many" IS sufficient to prove "there exists".

 

[SteveL27]

Oh ! it's getting better ! Now I see at least some difference... Thanks.

I agree that the wording of "all but finitely many" puts our brains in knots. It is confusing at first.

When you have a problem like that, just divide the universe into two sets: things that have the property, and things that don't. If the set of things that don't have that property is finite, then we can say "all but finitely many" have the given property.

"There exists" is much stronger ... it says there's at least one.

Also note that it's frequently the case that neither set is finite. For example, there exists an even number. There exists an odd number.

But it is not the case that "all but finitely many" numbers are odd. Or even. Because there are infinitely many even numbers and infinitely many odd ones.

So "there exists" can be true yet "all but finitely many" false, or vice versa. They're really not related at all, if you think about it. They're independent notions.

 

[ki$$a]

MANY thanks! Now everything is clear!

 

[SW VandeCarr]

.Also note that it's frequently the case that neither set is finite. For example, there exists an even number. There exists an odd number.

But it is not the case that "all but finitely many" numbers are odd. Or even. Because there are infinitely many even numbers and infinitely many odd ones.

So "there exists" can be true yet "all but finitely many" false, or vice versa. They're really not related at all, if you think about it. They're independent notions.

I already provided this example in post 7.