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.

First we show a few well known mathematical diagonal reasonings. Then we concentrate on diagonal reasonings typical for mathematical logic.