Functions essentially depending on at most one variable (Q5937133)

Let \(\omega\) be the set of nonnegative integers. The author analyzes the question: When does a function \(f: \omega^d\to\omega\) essentially depend on at most one coordinate? He defines: A function \(f: X^d\to X\) is elementary if its domain can be covered by finitely many rectangles (= sets of the form \(A_0\times\cdots\times A_{d-1}\)) such that \(f\) depends on at most one coordinate on each one of them. If \(I\cap J= \emptyset\), then, for \({\mathbf x}\in X^I\), \({\mathbf y}\in X^J\), a function \({\mathbf x}\wedge{\mathbf y}\) is defined by \(({\mathbf x}\wedge{\mathbf y})(\xi)={\mathbf x}(\xi)\) if \(\xi\in I\), resp. \(={\mathbf y}(\xi)\) if \(\xi\in J\). Let be \(f: X^d\to X\) and \(g\) a mapping from a subset of \(Y^k\) into \(Y\). Then \(g\) is called reducible to \(f\) if there is a disjoint partition \(d= s_0\cup\cdots\cup s_{k-1}\) of \(d\) into nonempty sets and maps \(p_i: Y\to X^{s_i}\) for \(i< k\) such that the mapping \(p: Y^k\to X^d\), defined by \(p(y_0,\dots, y_{k-1})= p_0(y_0)\wedge\cdots\wedge p_{k-1}(y_{k-1})\), satisfies: \(g({\mathbf y})\neq g({\mathbf z})\to f(p({\mathbf y}))\neq f(p({\mathbf z}))\), whenever \({\mathbf y}\) and \({\mathbf z}\) are in the domain of \(g\). The main result then states: Assume \(f: X^d\to X\). Then exactly one of the following holds: (A) \(f\) is elementary. (B) The mapping \(g^*\) is reducible to \(f\). Here \(g^*: \omega^2\to \{0,1\}\) is given by \(g^*(m, n)= 1\), if \(m< n\), \(=0\) if \(m= n\), undefined, if \(m> n\).