# 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.