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

Bès, Alexis; Korec, Ivan

Fundamenta Mathematicae, Tome 158 (1998), p. 111-129 / Harvested from The Polish Digital Mathematics Library

Résumé

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) = (\binom{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.

Publié le : 1998-01-01

Zbl 0905.11013

EUDML-ID : urn:eudml:doc:212264

@article{bwmeta1.element.bwnjournal-article-fmv156i2p111bwm,
     author = {Alexis B\`es and Ivan Korec},
     title = {Definability within structures related to Pascal's triangle modulo an integer},
     journal = {Fundamenta Mathematicae},
     volume = {158},
     year = {1998},
     pages = {111-129},
     zbl = {0905.11013},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-fmv156i2p111bwm}
}

Bès, Alexis; Korec, Ivan. Definability within structures related to Pascal’s triangle modulo an integer. Fundamenta Mathematicae, Tome 158 (1998) pp. 111-129. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-fmv156i2p111bwm/

Bibliographie

[00000] [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. | Zbl 0785.03002

[00001] [Be] A. Bès, On Pascal triangles modulo a prime power, Ann. Pure Appl. Logic 89 (1997), 17-35. | Zbl 0889.11008

[00002] [Bo] B. A. Bondarenko, Generalized Pascal Triangles and Pyramids, their Fractals, Graphs and Applications, "Fan", Tashkent, 1990 (in Russian). | Zbl 0706.05002

[00003] [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. | Zbl 0804.11024

[00004] [Ce] P. Cegielski, Definability, decidability, complexity, Ann. Math. Artificial Intelligence 16 (1996), 311-342.

[00005] [Di] L. E. Dickson, History of the Theory of Numbers, Vol. I, Chelsea, New York, 1952, Ch. IX.

[00006] [El] W. and F. Ellison, Prime Numbers, Hermann, Paris, 1985.

[00007] [FV] S. Feferman and R. L. Vaught, The first order properties of products of algebraic systems, Fund. Math. 47 (1959), 57-103. | Zbl 0088.24803

[00008] [Fi] N. J. Fine, Binomial coefficients modulo a prime, Amer. Math. Monthly 54 (1947), 589-592. | Zbl 0030.11102

[00009] [Ko1] I. Korec, Definability of arithmetic operations in Pascal triangle modulo an integer divisible by two primes, Grazer Math. Ber. 318 (1993), 53-62. | Zbl 0797.11024

[00010] [Ko2] I. Korec, Structures related to Pascal's triangle modulo 2 and their elementary theories, Math. Slovaca 44 (1994), 531-554. | Zbl 0824.11008

[00011] [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.

[00012] [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.

[00013] [MMT] R. McKenzie, J. Mycielski and D. Thompson, On boolean functions and connected sets, Math. Systems Theory 5 (1971), 259-270. | Zbl 0221.02047

[00014] [Pu] H. Putnam, Decidability and essential undecidability, J. Symbolic Logic 22 (1957), 39-54. | Zbl 0078.24501

[00015] [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. | Zbl 0562.03006

[00016] [Ro] J. Robinson, Definability and decision problems in arithmetic, J. Symbolic Logic 14 (1949), 98-114. | Zbl 0034.00801

[00017] [Si] D. Singmaster, Notes on binomial coefficients III - Any integer divides almost all binomial coefficients, J. London Math. Soc. (2) 8 (1974), 555-560. | Zbl 0293.05007

[00018] [Th] W. Thomas, A note on undecidable extensions of monadic second order successor arithmetic, Arch. Math. Logik Grundlagenforsch. 17 (1975), 43-44. | Zbl 0325.02032

[00019] [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.

[00020] [Wo] A. R. Woods, Some problems in logic and number theory and their connections, thesis, University of Manchester, 1981.