Definability of arithmetic operations in Pascal triangle modulo an integer divisible by two primes. (English) Zbl 0797.11024

Korec, Ivan

Grazer Math. Ber. 318, 53-61 (1993).

Summary: We investigate the structures (\(\mathbb{N};B_ n)\), where \(B_ n(x,y) = {x+y \choose x}\) mod \(n\). Addition and multiplication on the set \(\mathbb{N}\) of nonnegative integers are first order definable in \((\mathbb{N};B_ n)\) provided \(n>0\) is divisible by two distinct primes. Consequently, the elementary theory of \((\mathbb{N};B_ n)\) is undecidable for such \(n\). On the other hand, the elementary theory of \((\mathbb{N};B_ 2)\) is shown to be decidable.

MSC:

11B75	Other combinatorial number theory
11U05	Decidability (number-theoretic aspects)
03B25	Decidability of theories and sets of sentences

Keywords:

Pascal triangle; elementary theory