Finding a primitive recursion representation of a given function \(f\) can be reduced to finding functions \(g, h, k\) such that \(f(m,0) = g(m)\) \(f(m,S(n)) = k(h(m,n), f(m,n))\) where \(S: \mathbf{N} \rightarrow \mathbf{N}\) is a successor function turning a natural number into its successor (1 maps to 2, 2 maps to 3, and so on). The sought functions should be a composition of one of the following primitive functions: ...
Recall universal algebra approach to definining algebraic structures. Instead of explicitly stating existence of certain elements – for exapmle, by designating a unit element in a group or associating an inverse – we replace them with a collection of functions. With this in mind, if \(A\) is a group, a unit element can be replaced with 0-arity function that chooses an element of \(A\) . An inverse is a 1-arity function \(A \rightarrow A\) . ...
Look at this interesting stuff Let I be a finite set, X be another set I -> X is a selector function X -> I is a partition function for example, Let I = {0, 1}, X = N f: {0, 1} -> N selects two natural numbers g: N -> {0, 1} partitions N into two subsets now, what happenes if we categorify this notion I becomes a discrete category – elements as objects, only identity morphisms X becomes a category of all sets ...