Advanced Search

The elementary theory of ⟨α;×⟩, where α is an ordinal and × denotes ordinal multiplication, is decidable if and only if $\alpha <{\omega }^{\omega }$. Moreover if ${|}_r$ and ${|}_l$ respectively denote the right- and left-hand divisibility relation, we show that Th $⟨{\omega }^{{\omega }^{\xi }}{;|}_r⟩$ and Th $⟨{\omega }^{\xi }{;|}_l⟩$ are decidable for every ordinal ξ. Further related definability results are also presented.

Let Sq denote the set of squares, and let $S{Q}_n$ be the squaring function restricted to powers of n; let ⊥ denote the coprimeness relation. Let $B_n(x,y)=\left(\genfrac{}{}{0pt}{}{x+y}{x}\right)MODn$. For every integer n ≥ 2 addition and multiplication are definable in the structures ⟨ℕ; Bn,⊥⟩ and ⟨ℕ; Bn,Sq⟩; thus their elementary theories are undecidable. On the other hand, for every prime p the elementary theory of ⟨ℕ; Bp,SQp⟩ is decidable.

We prove that there exists a structure whose monadic second order theory is decidable, and such that the first-order theory of every expansion of by a constant is undecidable.