The paper outlines a possible computability-theoretic approach to the theory of Boolean-valued models. We introduce the notion of a decidable Boolean-valued model \(\textbf{A}\) . This notion is a natural extension of the classical definition of a decidable structure. Intuitively speaking, in order to formally define \(\textbf{A}\) , one needs to (algorithmically) work only with countably many truth values taken from a computable Boolean algebra. This convention allows us to view such \(\textbf{A}\) through the lens of computable structure theory. We show that the introduced approach provides a rich class of computable structures. We prove that any possible computable dimension can be realized by an appropriately constructed, decidable Boolean-valued model \(\textbf{A}\) . Consequently, there exists a model \(\textbf{A}\) having computable dimension 2 (that is, \(\textbf{A}\) possesses precisely two computable presentations, up to computable isomorphisms). In contrast, it is known that dimension 2 can be realized neither by a classical decidable structure nor by a computable Boolean algebra.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On a Computability-Theoretic Approach to Boolean-Valued Models

  • Nikolay Bazhenov,
  • Manat Mustafa

摘要

The paper outlines a possible computability-theoretic approach to the theory of Boolean-valued models. We introduce the notion of a decidable Boolean-valued model \(\textbf{A}\) . This notion is a natural extension of the classical definition of a decidable structure. Intuitively speaking, in order to formally define \(\textbf{A}\) , one needs to (algorithmically) work only with countably many truth values taken from a computable Boolean algebra. This convention allows us to view such \(\textbf{A}\) through the lens of computable structure theory. We show that the introduced approach provides a rich class of computable structures. We prove that any possible computable dimension can be realized by an appropriately constructed, decidable Boolean-valued model \(\textbf{A}\) . Consequently, there exists a model \(\textbf{A}\) having computable dimension 2 (that is, \(\textbf{A}\) possesses precisely two computable presentations, up to computable isomorphisms). In contrast, it is known that dimension 2 can be realized neither by a classical decidable structure nor by a computable Boolean algebra.