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

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?

• Are you talking about a predicate logic with a finite number of variables? – bof Jan 17 '18 at 22:52
• Yes, since we have no free variables and just k many quantifiers (at most), we also have at most k many variables. – multiplex Jan 17 '18 at 23:00
• @multiplex It's worth noting that we usually don't place any restriction on the number of quantifiers allowed ... – Noah Schweber Jan 17 '18 at 23:07
• @Noah Schweber But when we remove the restriction the set of all formulas in the predicate logic does instantly become infinitely huge, right? Just as Stefan Meske pointed out. – multiplex Jan 17 '18 at 23:11
• @multiplex Yup. My point was just that you seemed to implicitly assume that we're only allowed a bounded number of quantifiers in predicate logic, and that's not the case. – Noah Schweber Jan 17 '18 at 23:37

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.

• He did say there is a bound on the number of quantifiers. – GEdgar Jan 17 '18 at 23:00
• Yes exactly, since we are pretty much bounded by the number of quantifiers, variables and the size of the signature, I would still say that it is finite. – multiplex Jan 17 '18 at 23:07
• @GEdgar Yes, I didn't catch that on my first read (since I considered the question in the title of OP's post). If my answer doesn't seem relevant, I'd be happy to remove it. – Stefan Mesken Jan 17 '18 at 23:17
• @Stefan Meske Sorry for being unclear in the question. How would you make it more specific? Should I mention the restrictions directly in the question? (Although it becomes a beast of a question) – multiplex Jan 17 '18 at 23:21
• Incidentally, it may be worth noting that it is a well-known fact that the Herbrand universe is infinite if the signature contains at least a function symbol with positive arity. – Fabio Somenzi Jan 19 '18 at 0:19