Structures related to Pascal’s triangle modulo 2 and their elementary theories. (English) Zbl 0824.11008

Korec, Ivan

Math. Slovaca 44, No. 5, 531-554 (1994).

Author’s abstract: The elementary theory of the structure \((\mathbb{N}; B_ 2)\), where \(\mathbb{N}\) is the set of nonnegative integers and \(B_ 2 (x,y)= {{x+y} \choose x} \bmod 2\), is decidable. On the other hand, addition and multiplication on \(\mathbb{N}\) are definable in the structure \((\mathbb{N}; B_ 2, \text{Sq})\), where Sq is the set of squares of integers, and hence the elementary theory of \((\mathbb{N}; B_ 2, \text{Sq})\) is undecidable. Further definability results are presented.

Reviewer: T.Pheidas (Iraklion)

MSC:

11B65	Binomial coefficients; factorials; \(q\)-identities
11U05	Decidability (number-theoretic aspects)

Keywords:

decidability; elementary theory

References:

[1]	BONDARENKO B. A.: Generalized Pascal Triangles and Pyramids, Their Fractals. Graphs and Applications (Russian), Fan, Tashkent, 1990. · Zbl 0706.05002
[2]	KOREC I.: Generalized Pascal triangles. Decidability results. Acta Math. Univ. Comenian. 46-47 (1985), 93-130. · Zbl 0607.05002
[3]	KOREC I.: Generalized Pascal triangles. Proceedings of the V. Universal Algebra Symposium, Turawa, Poland, May 1988 (K. Halkowska and S. Stawski, World Scientific, Singapore, 1989, pp. 198-218. · Zbl 0612.68048
[4]	KOREC I.: Definability of arithmetic operations in Pascal triangle modulo an integer divisible by two primes. Grazer Math. Ber. 318 (1993), 53-61. · Zbl 0797.11024
[5]	LE M.: On the number of solutions of the generalized Ramanjuan-Nagell equation \(x^2 - D = 2^{n+2}\). Acta Arith. 60 (1991), 149-167. · Zbl 0747.11016
[6]	MONK J. D.: Mathematical Logic. Springer Verlag, New York, 1976. · Zbl 0354.02002
[7]	RICHARD D.: Answer to a problem raised by J. Robinson: the arithmetic of positive or negative integers is definable from successor and divisibility. J. Symbolic Logic 50 (1985), 927-935. · Zbl 0612.03009 · doi:10.2307/2273981
[8]	ROBINSON J.: Definability and decision problems in arithmetic. J. Symbolic Logic 14 (1949), 98-114. · Zbl 0034.00801 · doi:10.2307/2266510
[9]	SEMENOV A. L.: On definability of arithmetic in their fragments. (Russian), Dokl. Akad. Nauk SSSR 263 (1982), 44-47.
[10]	SHOENFIELD J. R.: Mathematical Logic. Addison -Wesley, Reading, 1967. · Zbl 0155.01102
[11]	SINGMASTER D.: Notes on binomial coefficients III - Any integer divides almost all binomial coefficients. J. London Math. Soc. (2) 8 (1974), 555-560. · Zbl 0293.05007 · doi:10.1112/jlms/s2-8.3.555
[12]	WOODS A.: Some Problems in Logic and Number Theory, and Their Connection. Ph.D. Thesis, University of Manchester, Manchester, 1981.
[13]	YERSHOW, JU. L.: Decidability Problems and Constructive Models. (Russian), Nauka, Moscow, 1980.