Complexity and the Decomposability of Relations

Martin Zwick

Talk delivered at the International Conference on Complex Systems
Nashua, New Hampshire
Sept. 21-26, 1997
(session on Measures of Structural Complexity)

Abstract

A discrete multivariate relation, defined set-theoretically, is a subset of a cartesian product of sets which specify the possible values of a number of variables. Where three or more variables are involved, the highest order relation, namely the relation between all the variables, may or may not be decomposable without loss into sets of lower order relations which involve subsets of the variables. In a completely parallel manner, the highest order relation defined information-theoretically, namely the joint probability distribution involving all the variables, may or may not be decomposed without loss into lower-order distributions involving subsets of the variables. Decomposability analysis, also called "reconstructability analysis," is the specification of the losses suffered by all possible decompositions.

The decomposability of relations, defined either set- or information- theoretically, offers a fundamental approach to the idea of "complexity" and bears on all of the themes prominent in both the new and the old "sciences of complexity." Decomposability analysis gives precise meaning to the idea of structure, i.e., to the interrelationship between a whole and its parts, where these are conceived either statically or dynamically. It specifies the structuring and distribution and the amount of information needed to describe complex systems. It is partially predictive of chaotic versus non-chaotic dynamics in discrete dynamic systems. It provides a framework for characterizing processes of integration and differentiation which are involved in the diachronics of self-organization.