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

Fundamenta Mathematicae (1998)

- Volume: 156, Issue: 2, page 111-129
- ISSN: 0016-2736

## Access Full Article

top## Abstract

top## How to cite

topBès, Alexis, and Korec, Ivan. "Definability within structures related to Pascal’s triangle modulo an integer." Fundamenta Mathematicae 156.2 (1998): 111-129. <http://eudml.org/doc/212264>.

@article{Bès1998,

abstract = {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 ⟨ℕ; 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.},

author = {Bès, Alexis, Korec, Ivan},

journal = {Fundamenta Mathematicae},

keywords = {Pascal's triangle modulo n; decidability; definability; decidability of theories; squaring function; Pascal triangle},

language = {eng},

number = {2},

pages = {111-129},

title = {Definability within structures related to Pascal’s triangle modulo an integer},

url = {http://eudml.org/doc/212264},

volume = {156},

year = {1998},

}

TY - JOUR

AU - Bès, Alexis

AU - Korec, Ivan

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

JO - Fundamenta Mathematicae

PY - 1998

VL - 156

IS - 2

SP - 111

EP - 129

AB - 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 ⟨ℕ; 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.

LA - eng

KW - Pascal's triangle modulo n; decidability; definability; decidability of theories; squaring function; Pascal triangle

UR - http://eudml.org/doc/212264

ER -

## References

top- [BJW] P. T. Bateman, C. G. Jockusch and, A. R. Woods, Decidability and undecidability with a predicate for the primes, J. Symbolic Logic 58 (1993), 672-687. Zbl0785.03002
- [Be] A. Bès, On Pascal triangles modulo a prime power, Ann. Pure Appl. Logic 89 (1997), 17-35. Zbl0889.11008
- [Bo] B. A. Bondarenko, Generalized Pascal Triangles and Pyramids, their Fractals, Graphs and Applications, "Fan", Tashkent, 1990 (in Russian). Zbl0706.05002
- [BHMV] V. Bruyère, G. Hansel, C. Michaux and R. Villemaire, Logic and p-recognizable sets of integers, Bull. Belg. Math. Soc. Simon Stevin 1 (1994), 191-238. Zbl0804.11024
- [Ce] P. Cegielski, Definability, decidability, complexity, Ann. Math. Artificial Intelligence 16 (1996), 311-342.
- [Di] L. E. Dickson, History of the Theory of Numbers, Vol. I, Chelsea, New York, 1952, Ch. IX.
- [El] W. and F. Ellison, Prime Numbers, Hermann, Paris, 1985.
- [FV] S. Feferman and R. L. Vaught, The first order properties of products of algebraic systems, Fund. Math. 47 (1959), 57-103. Zbl0088.24803
- [Fi] N. J. Fine, Binomial coefficients modulo a prime, Amer. Math. Monthly 54 (1947), 589-592. Zbl0030.11102
- [Ko1] I. Korec, Definability of arithmetic operations in Pascal triangle modulo an integer divisible by two primes, Grazer Math. Ber. 318 (1993), 53-62. Zbl0797.11024
- [Ko2] I. Korec, Structures related to Pascal's triangle modulo 2 and their elementary theories, Math. Slovaca 44 (1994), 531-554. Zbl0824.11008
- [Ko3] I. Korec, Elementary theories of structures containing generalized Pascal triangles modulo a prime, in: Proc. 5th Conf. on Discrete Mathematics and Applications (Blagoevgrad/Predel, 1994), S. Shtrakov and I. Mirchev (eds.), Blagoevgrad, 1995, 91-102.
- [Lu] E. Lucas, Sur les congruences des nombres eulériens et des coefficients différentiels des fonctions trigonométriques, suivant un module premier, Bull. Soc. Math. France 6 (1878), 49-54.
- [MMT] R. McKenzie, J. Mycielski and D. Thompson, On boolean functions and connected sets, Math. Systems Theory 5 (1971), 259-270. Zbl0221.02047
- [Pu] H. Putnam, Decidability and essential undecidability, J. Symbolic Logic 22 (1957), 39-54. Zbl0078.24501
- [Ri] D. Richard, All arithmetical sets of powers of primes are first-order definable in terms of the successor function and the coprimeness predicate, Discrete Math. 53 (1985), 221-247. Zbl0562.03006
- [Ro] J. Robinson, Definability and decision problems in arithmetic, J. Symbolic Logic 14 (1949), 98-114. Zbl0034.00801
- [Si] D. Singmaster, Notes on binomial coefficients III - Any integer divides almost all binomial coefficients, J. London Math. Soc. (2) 8 (1974), 555-560. Zbl0293.05007
- [Th] W. Thomas, A note on undecidable extensions of monadic second order successor arithmetic, Arch. Math. Logik Grundlagenforsch. 17 (1975), 43-44. Zbl0325.02032
- [Vi] R. Villemaire, Joining k- and l-recognizable sets of natural numbers, in: Proc. 9th Sympos. Theoretical Aspects of Computer Science STACS'92 (Paris), Lecture Notes in Comput. Sci. 577, Springer, 1992, 83-94.
- [Wo] A. R. Woods, Some problems in logic and number theory and their connections, thesis, University of Manchester, 1981.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.