There are exactly N objects in the universe in first-order logic

Question

For one object in the universe, the sentence would be: ∃x∀y (x=y)

For two: ∃x1,x2∀y [(x1=y ∨ x2=y) ∧ (x1 ≠ x2)]

But what about for N objects? The only way I can think of doing this is by using ellipses, which aren't really allowed in FOL.

Answer 1

Your ellipsis idea is perfectly valid shorthand if you want to express a schema of statements. And if you want to say there are a specific number of objects in the universe, you see how to do it.

So, the only other application that I can see for your question is to express that there are a finite number of objects in the universe. This is provably impossible. Suppose $F$ is a statement expressing that there are finitely many objects in the universe. Then $-F$ expresses that there are infinitely many objects, call this statement $I$.

So, you can construct a theory for any Turing machine that has a discrete ordering with a single initial element, and that has certain elements distinguished by a unary relation that represent the stages in execution of a Turing Machine. This is a bit of a complicated construction, but it is possible for all Turing Machines. You can also make a halting step the last element in the universe for all models of such a theory. Then, in such a theory, all models are infinite if the machine does not halt, and there is a finite model if the machine does halt.

Now, take a first order theory representing a Turing Machine $M$. The completeness theorem suggests that $I$ is provable in that theory if it is true in all models of that theory. So, imagine an algorithm that simultaneously runs $M$ and searches for a proof of $I$ in the corresponding first order theory. Either the machine halts, and the portion running $M$ proves so, or it does not halt and the portion trying to prove $I$ succeeds, proving $M$ does not halt. We solved the Halting Problem! So, see, no such $I$ can exist.