Fractal Images of Formal Systems
Paul St. Denis and Patrick Grim

Journal of Philosophical Logic 26: 181-222, 1997

Introduction

Familiar formal systems include propositional calculus, predicate calculus, higher-order logic and systems of number theory and arithmetic. As standardly envisaged, these consist of a grammar specifying well-formed formulae together with a set of axioms and rules. Derivations are ordered lists or series of formulae each of which is either an axiom or is generated from earlier items by means of the rules of the system, and the theorems of a formal system are simply those formulae for which there are derivations.

Given this standard approach to formal systems, however, attempts to envisage formal systems as a whole seem of necessity remotely abstract and incomplete. As a psychological matter, if one is asked to envisage the theorems of predicate calculus as a whole, one seems at best able to conjure up an image of the axioms and an empty category of 'all that follows from them'. The incompleteness of such a psychological picture accords perfectly with constructivist approaches to formal systems, and may even seem to confirm them.

In what follows we want to outline some importantly different and immediately visual ways of envisaging formal systems, including a modelling of systems in terms of fractals. The progressively deeper dimensions of fractal images can be used to map increasingly complex wffs or what we will term 'value spaces', which correspond quite directly to columns of traditional truth tables. Within such an image, tautologies, contradictions, and various forms of contingency can be coded in terms of color or shading, resulting in a visually immediate and geometrically suggestive representation of systems as an infinite whole. One promise of such an approach, it is hoped, is the possibility of asking and answering questions about formal systems in terms of fractal geometry. As a psychological matter, it is interesting to note, complete fractal images of formal systems seem to correspond to a realist and non-constructivist approach to formal systems.

In what follows we begin with the example of tic-tac-toe, a simple game rather than a simple formal system, in order to make clear both the general approach and a number of the tools used at later stages. In Sections 3 and 4 we offer different geometrical patterns for mapping aspects of formal systems, starting with 'rug' images for fragments of predicate calculus and moving on to more complex systems and more complete forms of mapping. An alternative portrayal of formal systems in terms of 'value spaces' and 'value solids' offers a number of surprises, three of which are emphasized in Sections 5 through 7: the appearance of the Sierpinski gasket, a familiar fractal, as the pattern of tautologies in standard value spaces; an intriguing correspondence between value solid for classical logic and rival connectives for infinite-valued logics; and the possibility of generating the value spaces of standard logics using elementary cellular automata.