Theories of generalized Pascal triangles

Decidability of theories and sets of sentences (03B25) Binomial coefficients; factorials; (q)-identities (11B65) Decidability (number-theoretic aspects) (11U05)

Review text

Generalized Pascal triangles (GPT) are mappings of the set \[ \mathbb{D}_n= \bigl\{ (x,y) \in\mathbb{N} \times \mathbb{N}\mid x+ y\geq n-1\bigr\},\;n>0, \] into finite sets associated to some finite algebras, analogous to the way in which the classical Pascal triangle can be associated to the (infinite) algebra \(\langle\mathbb{N}; +,0\rangle\) and ``the word 1 (of length 1). In this paper the author summarizes some of his results concerning first order theories of GPT. The paper consists of the following parts: Definition of GPT and a motivation, Structures associated to GPT, An example of a GPT (for which decidability of its theory surprisingly strongly depends on the chosen structure), Decidability results for theories of GPT modulo an integer (in this case decidability or undecidability of the theory of a GPT mainly depends on the factorization of the modulus), and Decidability results for theories of small algebras (the smallest cardinalities of the underlying algebras are shown where the theories of the corresponding GPT can be undecidable).

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Theories of generalized Pascal triangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377634)