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

Alexis Bès; Ivan Korec

Fundamenta Mathematicae (1998)

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

Abstract

top
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 ) = ( x + y x ) M O D 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.

How to cite

top

Bè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
  1. [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
  2. [Be] A. Bès, On Pascal triangles modulo a prime power, Ann. Pure Appl. Logic 89 (1997), 17-35. Zbl0889.11008
  3. [Bo] B. A. Bondarenko, Generalized Pascal Triangles and Pyramids, their Fractals, Graphs and Applications, "Fan", Tashkent, 1990 (in Russian). Zbl0706.05002
  4. [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
  5. [Ce] P. Cegielski, Definability, decidability, complexity, Ann. Math. Artificial Intelligence 16 (1996), 311-342. 
  6. [Di] L. E. Dickson, History of the Theory of Numbers, Vol. I, Chelsea, New York, 1952, Ch. IX. 
  7. [El] W. and F. Ellison, Prime Numbers, Hermann, Paris, 1985. 
  8. [FV] S. Feferman and R. L. Vaught, The first order properties of products of algebraic systems, Fund. Math. 47 (1959), 57-103. Zbl0088.24803
  9. [Fi] N. J. Fine, Binomial coefficients modulo a prime, Amer. Math. Monthly 54 (1947), 589-592. Zbl0030.11102
  10. [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
  11. [Ko2] I. Korec, Structures related to Pascal's triangle modulo 2 and their elementary theories, Math. Slovaca 44 (1994), 531-554. Zbl0824.11008
  12. [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. 
  13. [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. 
  14. [MMT] R. McKenzie, J. Mycielski and D. Thompson, On boolean functions and connected sets, Math. Systems Theory 5 (1971), 259-270. Zbl0221.02047
  15. [Pu] H. Putnam, Decidability and essential undecidability, J. Symbolic Logic 22 (1957), 39-54. Zbl0078.24501
  16. [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
  17. [Ro] J. Robinson, Definability and decision problems in arithmetic, J. Symbolic Logic 14 (1949), 98-114. Zbl0034.00801
  18. [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
  19. [Th] W. Thomas, A note on undecidable extensions of monadic second order successor arithmetic, Arch. Math. Logik Grundlagenforsch. 17 (1975), 43-44. Zbl0325.02032
  20. [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. 
  21. [Wo] A. R. Woods, Some problems in logic and number theory and their connections, thesis, University of Manchester, 1981. 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.