1

How can one prove that every first-order-logic formula with equality over the empty signature is equivalent to either False, or "there are exactly n elements in the domain", or "there are at least n elements in the domain"?

Udi
  • 11
  • 1
    Something that looks somewhat like this is true, but the expressiveness is somewhat greater than stated. – André Nicolas Jan 03 '16 at 22:19
  • You presumably mean not only these three sorts of sentences but also their (finitary) propositional combinations, such as "there are at most $n$ elements" or "the number of elements is 3 or 17 or 2016." – Andreas Blass Jan 03 '16 at 22:27

1 Answers1

-1

I assume you mean a formula with no parameters. In this case take any structure in this language = a set with no additional structure. Now look at all permutations of this structure = all permutations of the set. In this way any subset of size $n$ can be mapped to any other subset of order $n$. That is all finite sets of the same size are conjugate under automorphisms, so no formula can distinguish between one set of size $n$ and another set of size $n$. Thus the formulas you mention are the only possible ones.

Rene Schipperus
  • 39,526
  • This just shows that every first-order formula is equivalent to "If the domain is finite, it has cardinality $\in X$" for some $X\subseteq \mathbb{N}$. The question is asking much more than this - essentially, to classify what sorts of $X$ are possible. For instance, there is no first-order formula true in exactly those finite structures of even cardinality. (And in fact, the OP is not stated correctly; but the point stands.) – Noah Schweber Jan 03 '16 at 22:47
  • @NoahSchweber Use compactness: if a formula is valid on domains of abitrary large cardinality, then it is true in the infinite domain. In particular both $\varphi$ and $\neg \varphi$ cannot hold in domains of arbitrary large size. – Rene Schipperus Jan 03 '16 at 22:56