Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In First Order Logic with Identity (FOL+I), one can express the proposition that there are exactly 3 items that have the property P.

Why is it not possible to express the proposition that there is a finite number of items that have the property P (in FOL+I)?

share|improve this question
add comment

4 Answers 4

up vote 14 down vote accepted

We can define formula $P_i$ that says "there are at most $i$ elements satisfying $P$". Now, if the infinite disjunction of the $P_i$ was definable in FO, it would (by compactness) imply a conjunction of some finite subset of the $P_i$, hence it would imply $P_i$ for some $i$. That is not true, if $P$ can have (say) $i+1$ elements satisfying it.

share|improve this answer
2  
+1 for compactness. –  starblue Jul 28 '10 at 20:24
add comment

Any property expressible under first-order logic is closed under ultraproducts. The property of finite sets is not, however, closed under ultraproducts.

share|improve this answer
    
Less elementary than mine, but more rigorous, +1 –  Charles Siegel Jul 28 '10 at 2:13
add comment

Well, it would mean that you have the statement $P_1\vee P_2\vee\ldots$ where $P_i$ stands for "there are $i$ objects with property $P$", and infinite disjunctions aren't allowed. As for proving that this isn't equivalent to anything else you can write that IS allowed, I don't know how to do that.

share|improve this answer
    
Yes, I agree that the fact that I could define $P_3$ was irrelevant because of the inability to form an infinite disjunction, but I included it to give the question a bit of a context. –  bryn Jul 28 '10 at 2:17
add comment

I think you can express "forall but finitely many" in FOL, which means "for all sufficiently large". But I am not sure whether this is equivalent to "finitely many", it seems to be a little bit different. See http://arxiv.org/pdf/math/0602415.pdf.

share|improve this answer
1  
This is not the same thing. Not all structures are the natural numbers, and not all languages have a binary symbol interpreted as a linear order. It is true that in $(\Bbb N,\leq)$ you can say that something happens to only finitely many numbers; or to all but finitely many. But it is not true in general for FOL. –  Asaf Karagila Feb 27 '13 at 18:32
    
(This, by the way, is the difference between expressibility in logic and expressibility in a theory and expressibility in a structure.) –  Asaf Karagila Feb 27 '13 at 18:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.