Cardinality of theories, signatures and decidability

146 Views Asked by At

I have been searching the Internet for some days, but I cannot find a resource accessible to me about the cardinality of a decidable set of axioms, or, in general, a theory. If I correctly understand, a decidable theory necessarily is countable and, therefore, employs at most a countable set of elements of the signature.

Nevertheless, I do not think that the signature employed in writing a decidable theory is necessarily finite; am I right? Thank you very much for any clarification!

1

There are 1 best solutions below

7
On BEST ANSWER

You are correct on all accounts. Simply consider the signature which has infinitely many constant symbols; but no other extralogical symbols (I consider equality as part of the logic here). Then the theory $\{c_n\neq c_k\mid n<k\in\Bbb N\}$ is decidable.

Another example is the language which has infinitely many unary predicates $R_n$ and nothing else, and axioms $\{\forall x(R_n(x))\mid n\in\Bbb N\}$.