Algebraic combinatorics

A set of transformations on a data structure forms a transformation monoid. Place forms are a special type of transformation monoid. Another important type of transformation monoid is a permutation group. The permutation groups arise in combinatorics as the automorphism groups of graphs and various other discrete data structures such as lists.

The set of transformation monoids can be partially ordered to form a lattice. Transformation monoids that are disjoint with respect to one another and that commute with all the operations contained in each other set are independent of one another. Each transformation monoid of the cartesian product of zero or more independent transformation monoids.

By understanding transformational independence we can begin to develop an understanding of parallelism because independent operations can be run in parallel. We can also version independent objects separately to implement fine grained versioning.

Describing structures by transformations

The automorphism group of a data structure transformations of that data structure that do not have any effect on it. The automorphism group of a list is the set of operations that map indexes to other indexes with equal value. We can enumerate all the orbits of this automorphism group on its parent symmetric group in order to enumerate all distinct permutations of the list.

Likewise, all graphs have an automorphism group of permutations that do not effect the underlying graph. Weak orderings have an automorphism group equivalent to that of a list, equivalence relations have an automorphism group that also includes exchanges of equally sized parts, and the automorphism group of an permutation is the set of all operations that commute with it.

Periodic sequences can be described by the effect of the rest operation on the sequence and finitely differentiable functions like sine and cosine can be described by the effect of differentiation on them. In this sense, the transformations on a data structure are important in both discrete and continuous mathematics.

The well ordering principle

The set of natural numbers $\mathbb{N}$ is well ordered which means that every subset of the natural numbers can be described by a monotone increasing enumeration. Consider for example the set of prime numbers:

(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53)

We can convert any prime number back into a natural number $\mathbb{N}$. For example, 547 can be converted to 100. These enumerations are endofunctions $\mathbb{N} \to \mathbb{N}$ that are reversible but not surjective. With finite functions all reversible surjective operations are automorphisms. The square numbers are another enumeration of natural numbers:

(0 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225)

The set of all subsets of $\mathbb{N}$ under set union and set intersection forms a boolean algebra with $\mathbb{N} - S$ as the complement operation. The differences between elements of this enumeration form an integer sequence. Consider the sum of the totient function:

(0 1 2 4 6 10 12 18 22 28 32 42 46 58 64 72)

The additive differences of the sum of totients is the eulers totient function itself. In this sense, these monotone enumerations are related to integer sequences in general. We can generalize integer sequences by describing sequences of rational numbers $\mathbb{N} \to \mathbb{Q}$, however, an important difference is that the set of rational numbers $\mathbb{Q}$ is not well ordered.

Finitely differentiable functions

Functions that have a differentiation iteration type with a finite size are solutions to a simple two element homogeneous LODE with constant coefficients. The solutions to a LODE can be described by a basis which in this case can be ordered by the total ordering of rational number sequences.

The function $x^2+2x+1$ would become [1,2,1,0] for the LODE $y''''=y'''$. If we set the default value of each field in this ordered basis this vector could be reduced to [1,2,1] which is equivalent to description of this function as a polynomial. The function $e^x$ is unaffected by differentiation so it would simply be [1] for $y'=y$.

The hyperbolic trigonometric functions $cosh(x)$ and $sinh(x)$ are involutions under differentiation so they would be represented by [1/2,1/2] and [1/2,-1/2]. The trigonometric functions $sin(x)$ and $cos(x)$ have order four so they would be represented as [0,0,1,0] and [0,0,0,1].

Enumerating structure types

Structures associate places with types. If the types of the fields of a structure are enumerated then the entire structure can be enumerated. The following elements are generated by (structure {:x (enum 0 1), :y (enum 0 1)}):

{:x 0, :y 0}, {:x 0, :y 1}, {:x 1, :y 0}, {:x 1, :y 1} 

By using slot places we can enumerate other associative collections as structures. Here is {first (enum 0 1), second (enum 0 1)}

[0 0], [0 1], [1 0], [1 1]

Sets use the contains? place system so here is all subsets of #{false, true} using {(contains? false) bool, (contains? true) bool} where bool is (enum false true):

#{}, #{false}, #{true}, #{false true}

We can also associate places with structures within a structure to enumerate grids. In general, structures are essential because they combine both enumerations and places together into one.

The linear continuum

Discrete mathematics is founded on the integers, directed graphs and other discrete structures. On the other hand, continuous mathematics is based upon continuous structures the simplest of which is the linear continuum. The unit interval [0,1] is a linear continuum whose every element can be represented by an infinite sequence of binary digits the positions of which are natural numbers.

The infinite subsets of the natural numbers numbers cannot be enumerated because attempting to determine the equality of infinite data structures leads to the halting problem. Without an enumeration these infinite subsets cannot be described by discrete mathematics and herein lies the fundamental distinction between discrete and continuous mathematics.

The probabilities of statements form a linear continuum [0,1]. Negation is defined by $1-x$, conjunction is defined by $xy$, and disjunction is defined by by $x+y-xy$. The values of zero and one are the absolute certainties used in deductive logic but that aren't used in probabilistic logic.

In order to convert [0,1] to another interval [a,b] with finite length we can use a linear polynomial $|b-a|x+a$. With infinite intervals we can use the reciprocal function and the logarithm function to achieve the same effect. A discrete partition of the linear continuum is equivalent to a discrete probability distribution.

Iteration types of differentiation

The differentiation operation is a transformation of differentiable functions and it has different iteration types for different differentiable functions:

• Identity: $c_1e^x$
• Idempotent: $c_1e^x + c_2$
• Involution: $c_1e^x + c_2e^{-x}$

All functions of a certain iteration type come from solutions to first order linear ordinary differential equations such as $y'=y$, $y''=y$, and $y''=y'$. The partial ordering of iteration types helps us to understand these differential equations. In general, polynomials, exp, sin, cos, sinh, and cosh and other similar functions all produce a finite number of differentiations.