Geodesic
Definability within structures related to Pascal’s triangle modulo an integer
Fundamenta Mathematicae, Tome 156 (1998) no. 2, pp. 111-129

Voir la notice de l'article provenant de la source Institute of Mathematics Polish Academy of Sciences

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.
DOI : 10.4064/fm-156-2-111-129
Keywords: Pascal's triangle modulo n, decidability, definability

Alexis Bès 1 ; Ivan Korec 1

1 
@article{10_4064_fm_156_2_111_129,
     author = {Alexis B\`es and Ivan Korec},
     title = {Definability within structures related to {Pascal{\textquoteright}s} triangle modulo an integer},
     journal = {Fundamenta Mathematicae},
     pages = {111--129},
     publisher = {mathdoc},
     volume = {156},
     number = {2},
     year = {1998},
     doi = {10.4064/fm-156-2-111-129},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4064/fm-156-2-111-129/}
}
TY  - JOUR
AU  - Alexis Bès
AU  - Ivan Korec
TI  - Definability within structures related to Pascal’s triangle modulo an integer
JO  - Fundamenta Mathematicae
PY  - 1998
SP  - 111
EP  - 129
VL  - 156
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4064/fm-156-2-111-129/
DO  - 10.4064/fm-156-2-111-129
LA  - en
ID  - 10_4064_fm_156_2_111_129
ER  - 
%0 Journal Article
%A Alexis Bès
%A Ivan Korec
%T Definability within structures related to Pascal’s triangle modulo an integer
%J Fundamenta Mathematicae
%D 1998
%P 111-129
%V 156
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4064/fm-156-2-111-129/
%R 10.4064/fm-156-2-111-129
%G en
%F 10_4064_fm_156_2_111_129
Alexis Bès; Ivan Korec. Definability within structures related to Pascal’s triangle modulo an integer. Fundamenta Mathematicae, Tome 156 (1998) no. 2, pp. 111-129. doi: 10.4064/fm-156-2-111-129

Cité par Sources :