How to represent in first order logic the expression:
"there are infinitely many"
To be honest I'm confused and not even sure whether you can represent them in first order logic.
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
The existing answers provide examples of contexts where "there are infinitely many" can be expressed. However, there is an important sense in which "there are infinitely many" cannot be expressed in a first-order way without some additional context restrictions:
Specifically, fix your favorite first-order language $\Sigma$. Then it's a consequence of the compactness theorem that there is no $\Sigma$-sentence $\varphi$ which is true in exactly the infinite $\Sigma$-structures:
If there were, then $\neg\varphi$ would hold in exactly the finite $\Sigma$-structures.
Then the $\Sigma$-theory $\{\exists x_1...x_n(\bigwedge_{1\le i<j\le n}x_i\not=x_j): n\in\mathbb{N}\}\cup\{\neg\varphi\}$ would be consistent (since any finite fragment holds of any sufficiently large $\Sigma$-structure), so by compactness has a (presumably non-unique) model $\mathcal{M}$.
But $\mathcal{M}$ must be infinite, since any structure satisfying $\exists x_1...x_n(\bigwedge_{1\le i<j\le n}x_i\not=x_j)$ has at least $n$ many elements. By assumption on $\varphi$, this means $\mathcal{M}\not\models\neg\varphi$, and we have a contradiction.
Phrased most relevantly to your question, what we've shown is that even the sentence "There are infinitely many $x$ satisfying $x=x$" is not expressible in first-order logic.
On the other hand, when we restrict attention to specific structures we often have a better situation:
- There are many natural structures over which the quantifier "there are infinitely many $x$ such that" is expressible. For example, in $(\mathbb{N}; +,\times,<)$, we may write "there are infinitely many $z$ such that $\varphi(z)$" as "$\forall x\exists y(x<y\wedge \varphi(y))$."
The other two answers fall into this category: they exhibit structures over which "there are infinitely many" is a first-order definable generalized quantifier.
-
$\begingroup$ thank you so much for your answer and clarification. this was the point of confusion. $\endgroup$– PushpaJul 20, 2018 at 14:12
-
$\begingroup$ Can a nonstandard quantifier for "infinitely many" be defined as follows? $\exists^\infty x \phi \leftrightarrow \exists x (\phi \land \exists^\infty y (\phi [x := y] \land y \neq x))$ $\endgroup$ Jan 12 at 5:00
$\begingroup$
$\endgroup$
You'll need to be a little bit more precise about what "there are infinitely many" means.
But for example, if you want to say that there are infinitely many natural numbers, you could rephrase that as "there is no largest natural number", or "for every natural number there exists a larger natural number". Either of these could be expressed in FOL.
So if you wanted to say that there are infinitely many stars in the universe, you might say "there is no furthest star from the Sun": in other words, for every star, there exists a star further from the Sun. This can also be expressed in FOL.
$\begingroup$
$\endgroup$
It depends on how you interpret the logic.
For an example on $\{x\mid x\subseteq\mathbb{N}\}$, if a predicate symbol $P(x)$ is interpreted as "the set $x$ have infinite many numbers", then "there are infinitely many numbers in $x$" can be expressed as $P(x)$ directly.
For another example on $\{x\mid x\subseteq\mathbb{N}\text{ or }x\text{ is a function }\mathbb{N}\rightarrow\mathbb{N}\}$, assume
the predicate symbol $I(f)$ is interpreted as "$f$ is an injection", and
the predicate symbol $R(f,x)$ is interpreted as "$x$ is the range of $f$".
Then "there are infinitely many numbers in $x$" can be expressed as $\exists f( I(f)\wedge R(f, x))$.
