Definability within structures related to Pascal’s triangle modulo an integer

Volume 156 / 1998

Alexis Bès, Ivan Korec Fundamenta Mathematicae 156 (1998), 111-129 DOI: 10.4064/fm-156-2-111-129


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.


  • Alexis Bès
  • Ivan Korec

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image