10
$\begingroup$

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)?

$\endgroup$
0

4 Answers 4

Reset to default
21
$\begingroup$

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.

$\endgroup$
0
14
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Less elementary than mine, but more rigorous, +1 $\endgroup$
    – Charles Siegel
    Commented Jul 28, 2010 at 2:13
-1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – bryn
    Commented Jul 28, 2010 at 2:17
-3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Asaf Karagila ♦
    Commented Feb 27, 2013 at 18:32
  • $\begingroup$ (This, by the way, is the difference between expressibility in logic and expressibility in a theory and expressibility in a structure.) $\endgroup$
    – Asaf Karagila ♦
    Commented Feb 27, 2013 at 18:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .