scientific article; zbMATH DE number 1046302

Publication date 8 December 1997

binomial coefficients elementary definability equivalence relation Pascal's triangles modulo \(n\)

Basic properties of first-order languages and structures (03C07) Other classical set theory (including functions, relations, and set algebra) (03E20) Algebraic structures (08A99) Binomial coefficients; factorials; (q)-identities (11B65)

Review text

To every binary relation \(f\) on a set \(M\), an equivalence relation \(R\) on \(M^2\) can be associated in which \((x,y)\) is equivalent with \((u,v)\) iff \(f(x,y)= f(u,v)\). The equivalence \(R\) can be considered as a 4-ary relation on \(M\), and the problem is to reconstruct \(f\) from \(R\) (more precisely to define \(f\) elementarily in \(\langle M;R\rangle\). The scope of this paper is to solve this problem for Pascal's triangles modulo \(n\) for \(1\leq n\leq 6\) (clearly Pascal's triangles modulo \(n\) can be considered as binary operations on the set \(\mathbb{N}\) of non-negative integers). The answer is positive for \(n=4\) and \(n=6\), negative for \(n=1\) and \(n\) prime (even greater than 6). As a corollary, the author obtains that the operations \(+\), \(\times\) are definable in the structure \(\langle\mathbb{N},\text{EqB}_6\rangle\), where \(\text{EqB}_6= \{(x,y,u,v)\in \mathbb{N}^4:{x+y\choose x}={u+v\choose u}(\text{mod }6)\}\); the integer 6 cannot be replaced by any smaller positive integer. The above-mentioned problem is solved (positively, resp. negatively) also for addition and multiplication on the set \(\mathbb{N}\), resp. \(\mathbb{Z}\) and for some other operations.

Cited in

(5)

This page was built for publication:

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