0
$\begingroup$

Which of these properties hold for all FO theories? (but not regarding fragments thereof)

a. Decidable

b. At least expressive as propositional logic

c. NP-complete

a) Decidable: no, some first order theories are not decidable.

b) Propositional logic lacks expressiveness, so possibly yes. However, are hence all FO theories more expressive than propositional logic?

c) NP-complete: An undecidable FO-theory is not NP-complete

Are a) and c) correct? How about b), is there a counter example?

$\endgroup$
2
  • $\begingroup$ What notion of "relative expressiveness" are you using here? There are multiple reasonable candidates. $\endgroup$ – Noah Schweber Nov 27 '20 at 19:09
  • $\begingroup$ What are your reasons? $\endgroup$ – philipxy Dec 28 '20 at 1:45
1
$\begingroup$

Your answers to (a) and (c) are correct. To tell whether (b) is correct we need a precise notion of expressiveness.

The issue is that propositional logic and first-order logic have totally different semantics: their notions of "model" are valuation and structure respectively. When two logics use the same notion of "model" we can straightforwardly compare their expressive powers by looking at what sets of models their sentences can pin down respectively. For example, SOL is strictly more expressive than FOL since there is an SOL-sentence whose class of models is not the class of models of any FOL-sentence (e.g. take an SOL-sentence whose models are exactly the finite structures, and observe via compactness that no FOL-sentence can do this). But this direct comparison idea doesn't even make sense for FOL vs. propositional logic.

Now for the specific question you ask, due to the fact that you look at all FOL theories this is arguably a moot point since there is a particular FOL-theory which is extremely simple, namely it only has two formulas up to semantic equivalence and it is linear-time decidable:

Take the theory in the empty language of a one-element pure set.

(Of course if you allow inconsistent theories this is even easier, but that seems silly. Incidentally note that $(i)$ the example above really does have to be that "small" per here and here, and $(ii)$ this also addresses (c).)

Since propositional logic isn't that simple, it's pretty clear that this is an FOL-theory which is not as expressive as propositional logic in any meaningful sense. But I think it's still worth highlighting this ambiguity, since there will be less trivial situations where we want to compare very different logics and there we will absolutely need a precise definition to say anything.

$\endgroup$
1
  • $\begingroup$ Thanks, I will discuss the question and give you the answer, depending on the definition which we are using. $\endgroup$ – Tijani Eric van Lessen Nov 29 '20 at 17:34

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.