Is there only a finite number of non-equivalent formulas in the predicate logic?

Question

My intuition says: Yes of course. Let's say that we have a finite signature and just k many quantifiers and no free variables. Therefore I tried to prove it by converting it into the prenex form and making an combinatorial argument over the amount of possible quantifier prefixes, but that didn't work out. Afterwards I tried to convert it to a propositional formula, but then I have to rely on a structure. (But I know that there are just a finite number of non-equivalent formulas in the propositional logic over a static set of variables.) Could anyone provide me with an approach to that problem?

Answer 1

No, there are infinitely many non-equivalent formulas in predicate logic. A very simple example is $(\phi_n \mid n < \omega)$ with $$ \phi_n = \exists v_1 \exists v_2 \ldots \exists v_n \colon \bigwedge_{i < j \le n} v_i \neq v_j. $$

$\phi_n$ is true in a given model (in the empty language) iff that model has at least $n$ elements.

---

The body of your post appears to ask a different question from its title: Given a finite signature. How many non-equivalent sentences (formulas with no free variables) with at most $k$ quantifiers are there?

If your signature contains a constant symbol $f$ and a $2$-ary relation symbol $\prec$, consider $$ \phi_n \equiv \forall x \exists y \underbrace{f \circ f \circ \ldots \circ f}_{n \text{-times}}(x) \prec y.$$

The sequence $(\phi_n \mid n \in \mathbb N)$ is pairwise non-equivalent as can be seen by looking at the structure $(\{1, 2, \ldots, n \}, f, \prec)$, where $\prec = < \restriction \{1,2, \ldots, n \}$ and $$ f(i) = \begin{cases} i +1 & \text{, if } i < n, \\ n & \text{, otherwise.} \end{cases} $$

Hence the answer to your question, in general, is: No, even under those restrictions there can be infintely many non-equivalent first order formulas.