Unicity of functions and their infinite expressions.

Question

While studying boolean algebra (where the lattice is over A={0,1}) I realized that I can have the set of all the functions from A × A × ... × A to A, the set A^(A×...×A). This set is finite, however i can write the functions f in infinite ways composing the other functions (to wich corresponds various algebraic expressions). I then realized that i can do this even in Linear Algebra by multiplying matrixes in infinite ways, in Analyis, etc... I don't understand clearly the relationship between the infinite ways in which a function can be expressed and their unique existence (seen as relations over sets). Is there a set of all the possible expressions over which an equivalence relationship is defined? (The quotient set should be isomorphic to the set of unique functions). I appologise for the bad language, hope that the answer was clear.

Answer 1

A function is not an expression or rule, a function is just a set of pairs. More precisely, a function $A\to B$ is a set of pairs $(a,b) \in A \times B$ such that every $a\in A$ appears exactly once in a pair.

Some functions may be given by an expression or a rule. Different rules may (and do) have the same set of pairs. Some (most) set of pairs that define a function do not have an apparent rule but still define a function.

The idea of rule is attractive but cannot work in all cases. For instance, one definition of rule is something that is obtained as a finite combination of primitives, such as addition, multiplication, mod, etc. Now, the number of such rules is countable but there are uncountably many functions $\mathbb N \to \mathbb N$.

Have a look at these:

• Recursive set

• Recursively enumerable set

• Primitive recursive function

• Computable function