Why a decidable logic is considered trivial?

198 Views Asked by At

I was reading some notes on propositional logic and I stumbled upon these related remarks:

"One way of measuring the strength of a logic is to ask whether it is decidable"

"One of the things we might mean when we say that a logic is trivial is that it is decidable"

"A logic L is decidable iff we could in principle program a computer to tell us of any given sentence of L in a finite period of time whether or not that sentence is a logical truth according to L"

"If logic is decidable then we could just grind out the consequences of any claim in an unthinking manner; in that sense, the logic took us nowhere new"

This is not the first time I read something like that, I often find propositional logic denoted as just a "toy".

Seems that this is all related, but I still don't have a grasp on the reasons.

1

There are 1 best solutions below

1
On

Well, I certainly wouldn't say that a decidable logical system is trivial (well okay, it might be trivial, but not for that reason alone). The book The classical decision problem contains a lot of information about decidable logical systems, as does this survey paper, and I think it won't be hard to find a bunch which you find plenty interesting. So I'd consider the claim "decidability$\implies$triviality" to be unjustified colorful language.

However:

  • In light of Godel's incompleteness theorem, any "sufficiently rich" logical system is undecidable. So conversely, knowing that a logical system is decidable does put a limit on its strength; certainly it can't be used to "implement" all of mathematics, or even arithmetic.

  • Second, propositional logic in particular is indeed often considered just a toy, but not because it's decidable - rather, because it's (arguably) uninteresting. The semantics for (classical) propositional logic simply isn't very rich (just maps from the set of propositional atoms to $\{\top,\perp\}$) compared with other logics (e.g. first-order structures). This is related to the previous bulletpoint: any logic with a "sufficiently complicated" semantics will have to be undecidable.