The elementary theory of ⟨α;×⟩, where α is an ordinal and × denotes ordinal multiplication, is decidable if and only if $α < ω^{ω}$. Moreover if $|_{r}$ and $|_{l}$ respectively denote the right- and left-hand divisibility relation, we show that Th $⟨ω^{ω^{ξ}};|_{r}⟩$ and Th $⟨ω^{ξ};|_{l}⟩$ are decidable for every ordinal ξ. Further related definability results are also presented.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Let Sq denote the set of squares, and let $SQ_n$ be the squaring function restricted to powers of n; let ⊥ denote the coprimeness relation. Let $B_n(x,y)=({x+y \atop x}) MOD n$. For every integer n ≥ 2 addition and multiplication are definable in the structures ⟨ℕ; B_n,⊥⟩ and ⟨ℕ; B_n,Sq⟩; thus their elementary theories are undecidable. On the other hand, for every prime p the elementary theory of ⟨ℕ; B_p,SQ_p⟩ is decidable.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.