Download PDF - Definability within structures related to Pascal’s triangle modulo an integerAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

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

Authors 1, 2

Affiliations

  1. Université Paris 7, Equipe de Logique URA 753, 2, place Jussieu, 75251 Paris Cedex 05, France
  2. Mathematical Institute, Slovak Academy of Sciences, Štefánikova 49, 81473 Bratislava, Slovakia

Abstract

Let Sq denote the set of squares, and let SQn be the squaring function restricted to powers of n; let ⊥ denote the coprimeness relation. Let Bn(x,y)=({x+ya⊤x})MODn. 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.

Keywords

ENG
Pascal's triangle modulo n, decidability, definability

Bibliography

  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.
  2. [Be] A. Bès, On Pascal triangles modulo a prime power, Ann. Pure Appl. Logic 89 (1997), 17-35.
  3. [Bo] B. A. Bondarenko, Generalized Pascal Triangles and Pyramids, their Fractals, Graphs and Applications, "Fan", Tashkent, 1990 (in Russian).
  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.
  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.
  9. [Fi] N. J. Fine, Binomial coefficients modulo a prime, Amer. Math. Monthly 54 (1947), 589-592.
  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.
  11. [Ko2] I. Korec, Structures related to Pascal's triangle modulo 2 and their elementary theories, Math. Slovaca 44 (1994), 531-554.
  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.
  15. [Pu] H. Putnam, Decidability and essential undecidability, J. Symbolic Logic 22 (1957), 39-54.
  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.
  17. [Ro] J. Robinson, Definability and decision problems in arithmetic, J. Symbolic Logic 14 (1949), 98-114.
  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.
  19. [Th] W. Thomas, A note on undecidable extensions of monadic second order successor arithmetic, Arch. Math. Logik Grundlagenforsch. 17 (1975), 43-44.
  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.
Fundamenta Mathematicae
1998/156/2
Export to PBN, Opens in new tab
Pages:
111-129
Main language of publication
English
Received
1996-11-07
Accepted
1997-07-27
Published
1998
Exact and natural sciences