科研之友
微信
新浪微博
Facebook
分享链接
摘要
We study the weak truth table (wtt) degree spectra of first-order relational structures. We prove a dichotomy among the possible wtt degree spectra along the lines of Knight's upward-closure theorem for Turing degree spectra. We prove new results contrasting the wtt degree spectra of finite-and infinite-signature structures. We show that, as a method of defining classes of reals, the wtt degree spectrum is, except for some trivial cases, strictly more expressive than the Turing degree spectrum.
- 出版日期2015
