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

• Autorzy: Alexis Bès , Ivan Korec
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Pascal's triangle modulo n; decidability; definability

Kategorie tematyczne

• 11U05: Decidability
• 03F30: First-order arithmetic and fragments
• 03B25: Decidability of theories and sets of sentences
• 11B65: Binomial coefficients; factorials; q -identities

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Fundamenta Mathematicae
• Rocznik: 1998
• Tom: 156
• Numer: 2
• Strony: 111-129

Daty

wydano

1998

otrzymano

1996-11-07

poprawiono

1997-07-27

Twórcy

autor

Alexis Bès

• Université Paris 7, Equipe de Logique URA 753, 2, place Jussieu, 75251 Paris Cedex 05, France

autor

Ivan Korec

• Mathematical Institute, Slovak Academy of Sciences, Štefánikova 49, 81473 Bratislava, Slovakia

Bibliografia

• [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.
• [Be] A. Bès, On Pascal triangles modulo a prime power, Ann. Pure Appl. Logic 89 (1997), 17-35.
• [Bo] B. A. Bondarenko, Generalized Pascal Triangles and Pyramids, their Fractals, Graphs and Applications, "Fan", Tashkent, 1990 (in Russian).
• [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.
• [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.
• [Fi] N. J. Fine, Binomial coefficients modulo a prime, Amer. Math. Monthly 54 (1947), 589-592.
• [Ko1] I. Korec, Definability of arithmetic operations in Pascal triangle modulo an integer divisible by two primes, Grazer Math. Ber. 318 (1993), 53-62.
• [Ko2] I. Korec, Structures related to Pascal's triangle modulo 2 and their elementary theories, Math. Slovaca 44 (1994), 531-554.
• [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.
• [Pu] H. Putnam, Decidability and essential undecidability, J. Symbolic Logic 22 (1957), 39-54.
• [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.
• [Ro] J. Robinson, Definability and decision problems in arithmetic, J. Symbolic Logic 14 (1949), 98-114.
• [Si] D. Singmaster, Notes on binomial coefficients III - Any integer divides almost all binomial coefficients, J. London Math. Soc. (2) 8 (1974), 555-560.
• [Th] W. Thomas, A note on undecidable extensions of monadic second order successor arithmetic, Arch. Math. Logik Grundlagenforsch. 17 (1975), 43-44.
• [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.