Definability and simplicity

Abstract

In the following pages we wish to clarify some questions concerning definitions of relations in terms of other relations. A study is made of how a definition of a relation R 1 in terms of another relation R 2 works in a given specified universe U . The definition is regarded as a correlation rule between the “possible extensions” of R 1 and R 2 . There are no difficulties in formulating necessary, and in a certain sense also sufficient, formal conditions for the existence of a definition relation between R 1 and R 2 . In particular, we are concerned with questions such as: “Is every relation of the form s 1 definable in terms of some relation of the form s 2 ?” (§ IV) A related question concerns the criterion used by Goodman1 for degrees of complexity, namely, whether for every relation R 2 of the form s 1 there is some relation R 2 of the form s 2 such that R 1 and R 2 are mutually definable (§ V). Some concrete results concerning this condition are stated in the theorems 22–24. The “complexity function” which is defined (definition 17) and which very naturally suggests itself from the discussion of the definability conditions, seems to furnish an adequate measure of the sort of complexity discussed by Goodman.