|
|||||
|
|
Degree Spectra of Relations on Boolean Algebras |
|
| Authors: | S S Goncharov R G Downey D R Hirschfeldt |
| Institution: | (1) Akademika Koptyuga Prospekt, 4, Institute of Mathematics SB RAS, Novosibirsk, 630090;(2) School of Mathematical and Computing Sciences, Victoria University, Wellington, New Zealand;(3) Department of Mathematics, University of Chicago, USA |
| Abstract: | We show that every computable relation on a computable Boolean algebra
is either definable by a quantifier-free formula with constants from
(in which case it is obviously intrinsically computable) or has infinite degree spectrum. |
| Keywords: | computable Boolean algebra computable relation intrinsically computable relation |
| 本文献已被 SpringerLink 等数据库收录！ | |