User:SergioPi/Sandbox

Structure in partially ordered sets

A set by itself has no order and no structure. But when a partial order is enforced on the set, and a functional defined below is optimized over the space of legal permutations of the set, a rich structural organization comes into existence. The structures include hierarchies of block systems induced in the set, many global and local maxima and minima, attractors, and basins of attraction. The phenomenon is observed in sets of any size, even small sets with as few as 3 elements, and is independent of the nature of the elements of the set.

The optimization of the functional must be performed by some suitable dynamical process, such as a search algorithm running on a computer, or a suitable natural process in a natural system. As a partially ordered set, when equipped with the dynamics of the optimization process, can be viewed as a complex dynamical system, the observed phenomenon is interpreted as one of emergence and self-organization.

The importance of the finding lies in the fact that any system amenable to mathematical analysis can be described by a partially ordered set. It is particularly easy to convert software, and the conversion can be automated. And some important systems can be directly cast in partially ordered set form by simple examination and without any mathematical analysis. More details are provided below. Once the partially ordered set representation is obtained, the structures can be mathematically calculated. The process of calculating the structures is called Emergent Inference.

Phenomena such as the emergence of structural hierarchies and the presence of attractors and basins of attraction are being routinely observed in many kinds of dynamical systems, but their origin remains unexplained. Are these phenomena related to the structures observed in the underlying partially ordered sets?

The significance of structure

Today, the concept of structure is an essential foundation of nearly every mode of inquiry and discovery in science, philosophy, and art. Complex Systems Science (CSS) is no exception. At the heart of CSS are the phenomena of emergence and self-organization, which have been observed in a large variety of complex dynamical systems, natural and artificial, living or inanimate, where stable and recognizable structures and organized behaviors unexpectedly appear during the evolution of the system. The classical example is a hurricane, where the atmosphere, initially in an unstructured and disorganized state, suddenly becomes organized as a very large, stable vortex. The phenomena have attracted considerable attention in large part because the emergence of structure in an initially unstructured complex system and without any external director is a phenomenon of inference, the concept that "something new can be introduced that is not inherent in any of the parts" (, p.217). But emergence has not been explained and is still being described as "a case of complexity outstripping computer resources and human ingenuity."

The brain is an important example of a complex dynamical system where phenomena of emergence and self-organization can be observed. If you see a pencil, you recognize it as a pencil in about 0.5s. But you don't really see a pencil. You see 100,000,000 dots of light on your retinas, and your brain processes them and organizes them into a functional structure that you call "pencil." We use structures like that all the time to think and communicate. The brain also contains physical structures called neural cliques, and hierarchies of neural cliques, which can be correlated by functional MRI to the functional structures. Since inference is considered as an essential part of intelligence, some researchers in Artificial Intelligence believe that intelligence is an emergent phenomenon.

Reported here is the emergence of structure in partially ordered sets. A partially ordered set is simply a set equipped with a partial order, where the nature of the elements of the set is irrelevant. The structures are actually found in the space of legal permutations of the given set. To find the structures, a functional defined below must be optimized, and a dissipative dynamical process is required to effect the optimization. The process can be a natural one or a suitable simulation running on a computer. The assortment of structures is very rich. They include hierarchies of block systems very similar to UML models used in object-oriented programming, many extrema, both maxima and minima, local and global, and attractors with basins of attraction of different depths, widths, and populations.

One more connection needs to be made before the picture is complete: the connection between complex systems and partially ordered sets. The following claim has been made:

Claim C1. Knowledge base. Any finite system susceptible to mathematical analysis can be represented as a partially ordered set, where the nature of the elements of the set is irrelevant.

The Turing equivalence of partially ordered sets has not been published yet, but transformations from software to partially ordered set representations has been discussed in detail in .

This article does not necessarily follow the chronological order of discovery. First, it is necessary to equip the reader with an understanding of the mechanics of the procedure for finding structures in partially ordered sets. To do this, a functional is first introduced, more or less arbitrarily, and the procedure is described at a basic level. Next, it is necessary to explain the connection between partially ordered sets and natural or artifical dynamical systems.

Basics

Let S be a finite set of size n, the elements of which are irrelevant, and let ω be a partial order on S. A partial order is a set of precedence relations among the elements of S. The partial order is assumed to be strict, meaning that no element of S precedes itself. These two components, n and ω alone, are necessary and sufficient to fully specify the problem at hand and to develop the theory. For example, $S={a,b,c,d,e,f,g,h,i}$ is a set with n = 9 elements, and Failed to parse (syntax error): {\displaystyle <big>ω</big> = {} } is a partial order with 8 precedence relations.

Let K be any strict total order of set S. If total order K is compatible with ω, then K is called a configuration of S. Set S has n! different total orders on S, but many of them are not compatible with ω, and, therefore, are not configurations of S.

A permutation of set S is a function S → S that maps S to itself. Permutations can be represented in two-line notation, where the elements of S are listed in the top line in some arbitrary order and their corresponding images in the bottom line. However, a more practical one-line notation is obtained if the top line is assumed to always list the elements of S in some conventional order, say the alphabetical order. In this case, the bottom line alone is sufficent to represent the permutation. For example (h f i d e a b g c) maps a → h, b → f, c → i, d → d, etc. One disadvantage of the one-line notation, is that the same notation is also used for tuples, where the parenthesis indicate a total order. But that disadvantage can be turned to advange by considering that a permutation is always a map from the default total order to another total order. In this case, permutation (h f i d e a b g c) is a map from total order (a b c d e f g h i) to total order (h f i d e a b g c). The terms permutation and total order can now be used interchageably, with their meaning being clear from context. A permutation is a function, while a total order is not. The term permutation is preferred in this article, because terms such as space or functional apply to functions, but usually not to total orders.