On First-Order Bit Theory
Juvenal Murwanashyaka · Duo Research Archive (University of Oslo) · 2019
We identify a number of decidable and undecidable fragments of five structures, B, D, F, G and H, in the language {e, 0, 1, •, } where e, 0 and 1 are constant symbols, • is a binary function symbol and is a binary relation symbol.In the language {0, 1, •}, we formulate three minimal essentially undecidable theories, WBT ⊂ BT ⊂ BTQ, with different degrees of interpretability.We show that WBT is mutually interpretable with the Tarski-Robinson-Mostowski theory R and that BTQ is mutually interpretable with Robinson arithmetic Q.In the language {0, 1, •, }, where is a binary relation symbol, we formulate three essentially undecidable theories, WD ⊂ C ⊂ D, with purely universal axiomatizations and different degrees of interpretability.We show that WBT and WD are mutually interpretable and that BTQ and D are mutually interpretable.We show that C is interpretable in BT, but we are unable to determine whether BT is interpretable in C. I thank Arne Tobias Malkenes Ødegaard