2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Are you talking about a predicate logic with a finite number of variables? $\endgroup$ – bof Jan 17 '18 at 22:52
  • $\begingroup$ Yes, since we have no free variables and just k many quantifiers (at most), we also have at most k many variables. $\endgroup$ – multiplex Jan 17 '18 at 23:00
  • $\begingroup$ @multiplex It's worth noting that we usually don't place any restriction on the number of quantifiers allowed ... $\endgroup$ – Noah Schweber Jan 17 '18 at 23:07
  • $\begingroup$ @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. $\endgroup$ – multiplex Jan 17 '18 at 23:11
  • $\begingroup$ @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. $\endgroup$ – Noah Schweber Jan 17 '18 at 23:37
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ He did say there is a bound on the number of quantifiers. $\endgroup$ – GEdgar Jan 17 '18 at 23:00
  • $\begingroup$ 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. $\endgroup$ – multiplex Jan 17 '18 at 23:07
  • $\begingroup$ @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. $\endgroup$ – Stefan Mesken Jan 17 '18 at 23:17
  • $\begingroup$ @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) $\endgroup$ – multiplex Jan 17 '18 at 23:21
  • 2
    $\begingroup$ 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. $\endgroup$ – Fabio Somenzi Jan 19 '18 at 0:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.