Input/output relations

The lattice of set partitions is one of the most important constructions in mathematics, because of its key role in the theory of functions. As functions are relations between input and output, all aspects of the relationship between set partitions and functions can be described by input/output relationships. First, I will briefly discuss set partitions.

Lattice of set partitions:
Set partitions play two different roles: they represent equivalences and they represent differences. Therefore, they can be ordered in two different ways: the equivalence ordering and the differences ordering. The equivalence ordering is useful for example because there is a monotone mapping between subalgebras of the symmetric group (permutation groups) and the lattice of equivalence relations defined by orbits. The differences ordering is useful because it determines the information ordering of functions on a given input. A function has more information then another if preserves more differences then it. In order to avoid confusion between these dual lattices, the semilattices can be labeled individually:

• Differences join: the join in the differences ordering
• Equality join: the join in the equvialence ordering

It may be useful to given these semilattices different labels as well, but in any case which semilattice is being referred to will always be made clear. It is a basic fact of the lattice of set partitions that these two semilattices are actually very different. There are far more difference atoms then equality atoms: difference atoms are bits of information and equality atoms are simply unordered pairs. The general behaviour of the two semilattices is very different as well, which is one reason they need to be considered separately and always distinguished from one another. This is not like the case in set theory where union and intersection are very similar.

Input/output relations:
Suppose that we have a function $f : A \to B$ with an input set $A$ and an an output set $B$. This essentially means that the function defines an input/output relationship between the inputs and the outputs. Given any input a single output is defined. We can relate this to set partitions by defining a set partition of the input set $I$ and a set partition of the output set $O$. Using these set partitions, we can define a criterion for a functional input/output relationship between these set partitions: \[ x =_I y \implies f(x) =_O f(y) \] Intuitively this means that given the information in the input, then we can determine the information in the output. Partitions can be defined from anything from indices of sequences, fields, or any other piece of information which makes this possible. So this general construction lets us determine when any piece of information determines another. Congruences defined in abstract algebra are also defined in this way.

Functions as composite objects:
Given an input/output relationship on a function, then we can always get a quotient function which defines how given an element of I we can determine which element of O is produced. That is the quotient function defines how we can get the output information from the input information. In this way, we see how functions are partially ordered: that is they have parts. As functions are input/output relationships the most natural way to define their parts is not through subsets but rather through set partitions that determine input/output relationships that can produce new quotient functions. These are new input/output relationships which are parts of functions.