This site is supported by donations to The OEIS Foundation.

Inquiry Driven Systems • Part 4

From OeisWiki
Jump to: navigation, search

Author: Jon Awbrey

Cactus Language • 2


As a result, we can hardly conceive of how many possibilities there are for what we call objective reality. Our sharp quills of knowledge are so narrow and so concentrated in particular directions that with science there are myriads of totally different real worlds, each one accessible from the next simply by slight alterations — shifts of gaze — of every particular discipline and subspecialty.

— Herbert J. Bernstein, "Idols of Modern Science", [HJB, 38]

This Subsection highlights an issue of style that arises in describing a formal language. In broad terms, I use the word style to refer to a loosely specified class of formal systems, typically ones that have a set of distinctive features in common. For instance, a style of proof system usually dictates one or more rules of inference that are acknowledged as conforming to that style. In the present context, the word style is a natural choice to characterize the varieties of formal grammars, or any other sorts of formal systems that can be contemplated for deriving the sentences of a formal language.

In looking at what seems like an incidental issue, the discussion arrives at a critical point. The question is: What decides the issue of style? Taking a given language as the object of discussion, what factors enter into and determine the choice of a style for its presentation, that is, a particular way of arranging and selecting the materials that come to be involved in a description, a grammar, or a theory of the language? To what degree is the determination accidental, empirical, pragmatic, rhetorical, or stylistic, and to what extent is the choice essential, logical, and necessary? For that matter, what determines the order of signs in a word, a sentence, a text, or a discussion? All of the corresponding parallel questions about the character of this choice can be posed with regard to the constituent part as well as with regard to the main constitution of the formal language.

In order to answer this sort of question, at any level of articulation, one has to inquire into the type of distinction that it invokes, between arrangements and orders that are essential, logical, and necessary and orders and arrangements that are accidental, rhetorical, and stylistic. As a rough guide to its comprehension, a logical order, if it resides in the subject at all, can be approached by considering all of the ways of saying the same things, in all of the languages that are capable of saying roughly the same things about that subject. Of course, the all that appears in this rule of thumb has to be interpreted as a fittingly qualified sort of universal. For all practical purposes, it simply means all of the ways that a person can think of and all of the languages that a person can conceive of, with all things being relative to the particular moment of investigation. For all of these reasons, the rule must stand as little more than a rough idea of how to approach its object.

If it is demonstrated that a given formal language can be presented in any one of several styles of formal grammar, then the choice of a format is accidental, optional, and stylistic to the very extent that it is free. But if it can be shown that a particular language cannot be successfully presented in a particular style of grammar, then the issue of style is no longer free and rhetorical, but becomes to that very degree essential, necessary, and obligatory, in other words, a question of the objective logical order that can be found to reside in the object language.

As a rough illustration of the difference between logical and rhetorical orders, consider the kinds of order that are expressed and exhibited in the following conjunction of implications:

Here, there is a happy conformity between the logical content and the rhetorical form, indeed, to such a degree that one hardly notices the difference between them. The rhetorical form is given by the order of sentences in the two implications and the order of implications in the conjunction. The logical content is given by the order of propositions in the extended implicational sequence:

To see the difference between form and content, or manner and matter, it is enough to observe a few of the ways that the expression can be varied without changing its meaning, for example:

Any style of declarative programming, also called logic programming, depends on a capacity, as embodied in a programming language or other formal system, to describe the relation between problems and solutions in logical terms. A recurring problem in building this capacity is in bridging the gap between ostensibly non-logical orders and the logical orders that are used to describe and to represent them. For instance, to mention just a couple of the most pressing cases, and the ones that are currently proving to be the most resistant to a complete analysis, one has the orders of dynamic evolution and rhetorical transition that manifest themselves in the process of inquiry and in the communication of its results.

This patch of the ongoing discussion is concerned with describing a particular variety of formal languages, whose typical representative is the painted cactus language It is the intention of this work to interpret this language for propositional logic, and thus to use it as a sentential calculus, an order of reasoning that forms an active ingredient and a significant component of all logical reasoning. To describe this language, the standard devices of formal grammars and formal language theory are more than adequate, but this only raises the next question: What sorts of devices are exactly adequate, and fit the task to a "T"? The ultimate desire is to turn the tables on the order of description, and so begins a process of eversion that evolves to the point of asking: To what extent can the language capture the essential features and laws of its own grammar and describe the active principles of its own generation? In other words: How well can the language be described by using the language itself to do so?

In order to speak to these questions, I have to express what a grammar says about a language in terms of what a language can say on its own. In effect, it is necessary to analyze the kinds of meaningful statements that grammars are capable of making about languages in general and to relate them to the kinds of meaningful statements that the syntactic sentences of the cactus language might be interpreted as making about the very same topics. So far in the present discussion, the sentences of the cactus language do not make any meaningful statements at all, much less any meaningful statements about languages and their constitutions. As of yet, these sentences subsist in the form of purely abstract, formal, and uninterpreted combinatorial constructions.

Before the capacity of a language to describe itself can be evaluated, the missing link to meaning has to be supplied for each of its strings. This calls for a dimension of semantics and a notion of interpretation, topics that are taken up for the case of the cactus language in Subsection Once a plausible semantics is prescribed for this language it will be possible to return to these questions and to address them in a meaningful way.

The prominent issue at this point is the distinct placements of formal languages and formal grammars with respect to the question of meaning. The sentences of a formal language are merely the abstract strings of abstract signs that happen to belong to a certain set. They do not by themselves make any meaningful statements at all, not without mounting a separate effort of interpretation, but the rules of a formal grammar make meaningful statements about a formal language, to the extent that they say what strings belong to it and what strings do not. Thus, the formal grammar, a formalism that appears to be even more skeletal than the formal language, still has bits and pieces of meaning attached to it. In a sense, the question of meaning is factored into two parts, structure and value, leaving the aspect of value reduced in complexity and subtlety to the simple question of belonging. Whether this single bit of meaningful value is enough to encompass all of the dimensions of meaning that we require, and whether it can be compounded to cover the complexity that actually exists in the realm of meaning — these are questions for an extended future inquiry.

Perhaps I ought to comment on the differences between the present and the standard definition of a formal grammar, since I am attempting to strike a compromise with several alternative conventions of usage, and thus to leave certain options open for future exploration. All of the changes are minor, in the sense that they are not intended to alter the classes of languages that are able to be generated, but only to clear up various ambiguities and sundry obscurities that affect their conception.

Primarily, the conventional scope of non-terminal symbols was expanded to encompass the sentence symbol, mainly on account of all the contexts where the initial and the intermediate symbols are naturally invoked in the same breath. By way of compensating for the usual exclusion of the sentence symbol from the non-terminal class, an equivalent distinction was introduced in the fashion of a distinction between the initial and the intermediate symbols, and this serves its purpose in all of those contexts where the two kind of symbols need to be treated separately.

At the present point, I remain a bit worried about the motivations and the justifications for introducing this distinction, under any name, in the first place. It is purportedly designed to guarantee that the process of derivation at least gets started in a definite direction, while the real questions have to do with how it all ends. The excuses of efficiency and expediency that I offered as plausible and sufficient reasons for distinguishing between empty and significant sentences are likely to be ephemeral, if not entirely illusory, since intermediate symbols are still permitted to characterize or to cover themselves, not to mention being allowed to cover the empty string, and so the very types of traps that one exerts oneself to avoid at the outset are always there to afflict the process at all of the intervening times.

If one reflects on the form of grammar that is being prescribed here, it looks as if one sought, rather futilely, to avoid the problems of recursion by proscribing the main program from calling itself, while allowing any subprogram to do so. But any trouble that is avoidable in the part is also avoidable in the main, while any trouble that is inevitable in the part is also inevitable in the main. Consequently, I am reserving the right to change my mind at a later stage, perhaps to permit the initial symbol to characterize, to cover, to regenerate, or to produce itself, if that turns out to be the best way in the end.

Before I leave this Subsection, I need to say a few things about the manner in which the abstract theory of formal languages and the pragmatic theory of sign relations interact with each other.

Formal language theory can seem like an awfully picky subject at times, treating every symbol as a thing in itself the way it does, sorting out the nominal types of symbols as objects in themselves, and singling out the passing tokens of symbols as distinct entities in their own rights. It has to continue doing this, if not for any better reason than to aid in clarifying the kinds of languages that people are accustomed to use, to assist in writing computer programs that are capable of parsing real sentences, and to serve in designing programming languages that people would like to become accustomed to use. As a matter of fact, the only time that formal language theory becomes too picky, or a bit too myopic in its focus, is when it leads one to think that one is dealing with the thing itself and not just with the sign of it, in other words, when the people who use the tools of formal language theory forget that they are dealing with the mere signs of more interesting objects and not with the objects of ultimate interest in and of themselves.

As a result, there a number of deleterious effects that can arise from the extreme pickiness of formal language theory, arising, as is often the case, when formal theorists forget the practical context of theorization. It frequently happens that the exacting task of defining the membership of a formal language leads one to think that this object and this object alone is the justifiable end of the whole exercise. The distractions of this mediate objective render one liable to forget that one's penultimate interest lies always with various kinds of equivalence classes of signs, not entirely or exclusively with their more meticulous representatives.

When this happens, one typically goes on working oblivious to the fact that many details about what transpires in the meantime do not matter at all in the end, and one is likely to remain in blissful ignorance of the circumstance that many special details of language membership are bound, destined, and pre-determined to be glossed over with some measure of indifference, especially when it comes down to the final constitution of those equivalence classes of signs that are able to answer for the genuine objects of the whole enterprise of language. When any form of theory, against its initial and its best intentions, leads to this kind of absence of mind that is no longer beneficial in all of its main effects, the situation calls for an antidotal form of theory, one that can restore the presence of mind that all forms of theory are meant to augment.

The pragmatic theory of sign relations is called for in settings where everything that can be named has many other names, that is to say, in the usual case. Of course, one would like to replace this superfluous multiplicity of signs with an organized system of canonical signs, one for each object that needs to be denoted, but reducing the redundancy too far, beyond what is necessary to eliminate the factor of "noise" in the language, that is, to clear up its effectively useless distractions, can destroy the very utility of a typical language, which is intended to provide a ready means to express a present situation, clear or not, and to describe an ongoing condition of experience in just the way that it seems to present itself. Within this fleshed out framework of language, moreover, the process of transforming the manifestations of a sign from its ordinary appearance to its canonical aspect is the whole problem of computation in a nutshell.

It is a well-known truth, but an often forgotten fact, that nobody computes with numbers, but solely with numerals in respect of numbers, and numerals themselves are symbols. Among other things, this renders all discussion of numeric versus symbolic computation a bit beside the point, since it is only a question of what kinds of symbols are best for one's immediate application or for one's selection of ongoing objectives. The numerals that everybody knows best are just the canonical symbols, the standard signs or the normal terms for numbers, and the process of computation is a matter of getting from the arbitrarily obscure signs that the data of a situation are capable of throwing one's way to the indications of its character that are clear enough to motivate action.

Having broached the distinction between propositions and sentences, one can see its similarity to the distinction between numbers and numerals. What are the implications of the foregoing considerations for reasoning about propositions and for the realm of reckonings in sentential logic? If the purpose of a sentence is just to denote a proposition, then the proposition is just the object of whatever sign is taken for a sentence. This means that the computational manifestation of a piece of reasoning about propositions amounts to a process that takes place entirely within a language of sentences, a procedure that can rationalize its account by referring to the denominations of these sentences among propositions.

The application of these considerations in the immediate setting is this: Do not worry too much about what roles the empty string and the blank symbol are supposed to play in a given species of formal languages. As it happens, it is far less important to wonder whether these types of formal tokens actually constitute genuine sentences than it is to decide what equivalence classes it makes sense to form over all of the sentences in the resulting language, and only then to bother about what equivalence classes these limiting cases of sentences are most conveniently taken to represent.

These concerns about boundary conditions betray a more general issue. Already by this point in discussion the limits of the purely syntactic approach to a language are beginning to be visible. It is not that one cannot go a whole lot further by this road in the analysis of a particular language and in the study of languages in general, but when it comes to the questions of understanding the purpose of a language, of extending its usage in a chosen direction, or of designing a language for a particular set of uses, what matters above all else are the pragmatic equivalence classes of signs that are demanded by the application and intended by the designer, and not so much the peculiar characters of the signs that represent these classes of practical meaning.

Any description of a language is bound to have alternative descriptions. More precisely, a circumscribed description of a formal language, as any effectively finite description is bound to be, is certain to suggest the equally likely existence and the possible utility of other descriptions. A single formal grammar describes but a single formal language, but any formal language is described by many different formal grammars, not all of which afford the same grasp of its structure, provide an equivalent comprehension of its character, or yield an interchangeable view of its aspects. Consequently, even with respect to the same formal language, different formal grammars are typically better for different purposes.

With the distinctions that evolve among the different styles of grammar, and with the preferences that different observers display toward them, there naturally comes the question: What is the root of this evolution?

One dimension of variation in the styles of formal grammars can be seen by treating the union of languages, and especially the disjoint union of languages, as a sum, by treating the concatenation of languages as a product, and then by distinguishing the styles of analysis that favor sums of products from those that favor products of sums as their canonical forms of description. If one examines the relation between languages and grammars carefully enough to see the presence and the influence of these different styles, and when one comes to appreciate the ways that different styles of grammars can be used with different degrees of success for different purposes, then one begins to see the possibility that alternative styles of description can be based on altogether different linguistic and logical operations.

It possible to trace this divergence of styles to an even more primitive division, one that distinguishes the additive or the parallel styles from the multiplicative or the serial styles. The issue is somewhat confused by the fact that an additive analysis is typically expressed in the form of a series, in other words, a disjoint union of sets or a linear sum of their independent effects. But it is easy enough to sort this out if one observes the more telling connection between parallel and independent. Another way to keep the right associations straight is to employ the term sequential in preference to the more misleading term serial. Whatever one calls this broad division of styles, the scope and sweep of their dimensions of variation can be delineated in the following way:

  1. The additive or parallel styles favor sums of products as canonical forms of expression, pulling sums, unions, co-products, and logical disjunctions to the outermost layers of analysis and synthesis, while pushing products, intersections, concatenations, and logical conjunctions to the innermost levels of articulation and generation. In propositional logic, this style leads to the disjunctive normal form (DNF).
  2. The multiplicative or serial styles favor products of sums as canonical forms of expression, pulling products, intersections, concatenations, and logical conjunctions to the outermost layers of analysis and synthesis, while pushing sums, unions, co-products, and logical disjunctions to the innermost levels of articulation and generation. In propositional logic, this style leads to the conjunctive normal form (CNF).

There is a curious sort of diagnostic clue that often serves to reveal the dominance of one mode or the other within an individual thinker's cognitive style. Examined on the question of what constitutes the natural numbers, an additive thinker tends to start the sequence at 0, while a multiplicative thinker tends to regard it as beginning at 1.

In any style of description, grammar, or theory of a language, it is usually possible to tease out the influence of these contrasting traits, namely, the additive attitude versus the mutiplicative tendency that go to make up the particular style in question, and even to determine the dominant inclination or point of view that establishes its perspective on the target domain.

In each style of formal grammar, the multiplicative aspect is present in the sequential concatenation of signs, both in the augmented strings and in the terminal strings. In settings where the non-terminal symbols classify types of strings, the concatenation of the non-terminal symbols signifies the cartesian product over the corresponding sets of strings.

In the context-free style of formal grammar, the additive aspect is easy enough to spot. It is signaled by the parallel covering of many augmented strings or sentential forms by the same non-terminal symbol. Expressed in active terms, this calls for the independent rewriting of that non-terminal symbol by a number of different successors, as in the following scheme:

It is useful to examine the relationship between the grammatical covering or production relation and the logical relation of implication with one eye to what they have in common and one eye to how they differ. The production says that the appearance of the symbol in a sentential form implies the possibility of exchanging it for Although this sounds like a possible implication, to the extent that implies a possible or that possibly implies the qualifiers possible and possibly are the critical elements in these statements, and they are crucial to the meaning of what is actually being implied. In effect, these qualifications reverse the direction of implication, yielding as the best analogue for the sense of the production.

One way to sum this up is to say that non-terminal symbols have the significance of hypotheses. The terminal strings form the empirical matter of a language, while the non-terminal symbols mark the patterns or the types of substrings that can be noticed in the profusion of data. If one observes a portion of a terminal string that falls into the pattern of the sentential form then it is an admissible hypothesis, according to the theory of the language that is constituted by the formal grammar, that this piece not only fits the type but even comes to be generated under the auspices of the non-terminal symbol

A moment's reflection on the issue of style, giving due consideration to the received array of stylistic choices, ought to inspire at least the question: "Are these the only choices there are?" In the present setting, there are abundant indications that other options, more differentiated varieties of description and more integrated ways of approaching individual languages, are likely to be conceivable, feasible, and even more ultimately viable. If a suitably generic style, one that incorporates the full scope of logical combinations and operations, is broadly available, then it would no longer be necessary, or even apt, to argue in universal terms about which style is best, but more useful to investigate how we might adapt the local styles to the local requirements. The medium of a generic style would yield a viable compromise between additive and multiplicative canons, and render the choice between parallel and serial a false alternative, at least, when expressed in the globally exclusive terms that are currently most commonly adopted to pose it.

One set of indications comes from the study of machines, languages, and computation, especially the theories of their structures and relations. The forms of composition and decomposition that are generally known as parallel and serial are merely the extreme special cases, in variant directions of specialization, of a more generic form, usually called the cascade form of combination. This is a well-known fact in the theories that deal with automata and their associated formal languages, but its implications do not seem to be widely appreciated outside these fields. In particular, it dispells the need to choose one extreme or the other, since most of the natural cases are likely to exist somewhere in between.

Another set of indications appears in algebra and category theory, where forms of composition and decomposition related to the cascade combination, namely, the semi-direct product and its special case, the wreath product, are encountered at higher levels of generality than the cartesian products of sets or the direct products of spaces.

In these domains of operation, one finds it necessary to consider also the co-product of sets and spaces, a construction that artificially creates a disjoint union of sets, that is, a union of spaces that are being treated as independent. It does this, in effect, by indexing, coloring, or preparing the otherwise possibly overlapping domains that are being combined. What renders this a chimera or a hybrid form of combination is the fact that this indexing is tantamount to a cartesian product of a singleton set, namely, the conventional index, color, or affix in question, with the individual domain that is entering as a factor, a term, or a participant in the final result.

One of the insights that arises out of Peirce's logical work is that the set operations of complementation, intersection, and union, along with the logical operations of negation, conjunction, and disjunction that operate in isomorphic tandem with them, are not as fundamental as they first appear. This is because all of them can be constructed from or derived from a smaller set of operations, in fact, taking the logical side of things, from either one of two sole sufficient operators, called amphecks by Peirce, strokes by those who re-discovered them later, and known in computer science as the NAND and the NNOR operators. For this reason, that is, by virtue of their precedence in the orders of construction and derivation, these operations have to be regarded as the simplest and the most primitive in principle, even if they are scarcely recognized as lying among the more familiar elements of logic.

I am throwing together a wide variety of different operations into each of the bins labeled additive and multiplicative, but it is easy to observe a natural organization and even some relations approaching isomorphisms among and between the members of each class.

The relation between logical disjunction and set-theoretic union and the relation between logical conjunction and set-theoretic intersection ought to be clear enough for the purposes of the immediately present context. In any case, all of these relations are scheduled to receive a thorough examination in a subsequent discussion (Subsection But the relation of a set-theoretic union to a category-theoretic co-product and the relation of a set-theoretic intersection to a syntactic concatenation deserve a closer look at this point.

The effect of a co-product as a disjointed union, in other words, that creates an object tantamount to a disjoint union of sets in the resulting co-product even if some of these sets intersect non-trivially and even if some of them are identical in reality, can be achieved in several ways. The most usual conception is that of making a separate copy, for each part of the intended co-product, of the set that is intended to go there. Often one thinks of the set that is assigned to a particular part of the co-product as being distinguished by a particular color, in other words, by the attachment of a distinct index, label, or tag, being a marker that is inherited by and passed on to every element of the set in that part. A concrete image of this construction can be achieved by imagining that each set and each element of each set is placed in an ordered pair with the sign of its color, index, label, or tag. One describes this as the injection of each set into the corresponding part of the co-product.

For example, given the sets and overlapping or not, one can define the indexed or marked sets and amounting to the copy of into the first part of the co-product and the copy of into the second part of the co-product, in the following manner:

Using the coproduct operator () for this construction, the sum, the coproduct, or the disjointed union of and in that order can be represented as the ordinary union of and

The concatenation of the formal languages and is just the cartesian product of sets without the extra ’s, but the relation of cartesian products to set-theoretic intersections and thus to logical conjunctions is far from being clear. One way of seeing a type of relation is to focus on the information that is needed to specify each construction, and thus to reflect on the signs that are used to carry this information. As a first approach to the topic of information, according to a strategy that seeks to be as elementary and as informal as possible, I introduce the following set of ideas, intended to be taken in a very provisional way.

A stricture is a specification of a certain set in a certain place, relative to a number of other sets, yet to be specified. It is assumed that one knows enough to tell if two strictures are equivalent as pieces of information, but any more determinate indications, like names for the places that are mentioned in the stricture, or bounds on the number of places that are involved, are regarded as being extraneous impositions, outside the proper concern of the definition, no matter how convenient they are found to be for a particular discussion. As a schematic form of illustration, a stricture can be pictured in the following shape:

A strait is the object that is specified by a stricture, in effect, a certain set in a certain place of an otherwise yet to be specified relation. Somewhat sketchily, the strait that corresponds to the stricture just given can be pictured in the following shape:


In this picture is a certain set and is the universe of discourse that is relevant to a given discussion. Since a stricture does not, by itself, contain a sufficient amount of information to specify the number of sets that it intends to set in place, or even to specify the absolute location of the set that its does set in place, it appears to place an unspecified number of unspecified sets in a vague and uncertain strait. Taken out of its interpretive context, the residual information that a stricture can convey makes all of the following potentially equivalent as strictures:

With respect to what these strictures specify, this leaves all of the following equivalent as straits:

Within the framework of a particular discussion, it is customary to set a bound on the number of places and to limit the variety of sets that are regarded as being under active consideration, and it is also convenient to index the places of the indicated relations, and of their encompassing cartesian products, in some fixed way. But the whole idea of a stricture is to specify a strait that is capable of extending through and beyond any fixed frame of discussion. In other words, a stricture is conceived to constrain a strait at a certain point, and then to leave it literally embedded, if tacitly expressed, in a yet to be fully specified relation, one that involves an unspecified number of unspecified domains.

A quantity of information is a measure of constraint. In this respect, a set of comparable strictures is ordered on account of the information that each one conveys, and a system of comparable straits is ordered in accord with the amount of information that it takes to pin each one of them down. Strictures that are more constraining and straits that are more constrained are placed at higher levels of information than those that are less so, and entities that involve more information are said to have a greater complexity in comparison with those entities that involve less information, that are said to have a greater simplicity.

In order to create a concrete example, let me now institute a frame of discussion where the number of places in a relation is bounded at two, and where the variety of sets under active consideration is limited to the typical subsets and of a universe Under these conditions, one can use the following sorts of expression as schematic strictures:

These strictures and their corresponding straits are stratified according to their amounts of information, or their levels of constraint, as follows:

Within this framework, the more complex strait can be expressed in terms of the simpler straits, and More specifically, it lends itself to being analyzed as their intersection, in the following way:

From here it is easy to see the relation of concatenation, by virtue of these types of intersection, to the logical conjunction of propositions. The cartesian product is described by a conjunction of propositions, namely, subject to the following interpretation:

  1. asserts that there is an element from the set in the first place of the product.
  2. asserts that there is an element from the set in the second place of the product.

The integration of these two pieces of information can be taken in that measure to specify a yet to be fully determined relation.

In a corresponding fashion at the level of the elements, the ordered pair is described by a conjunction of propositions, namely, subject to the following interpretation:

  1. says that is in the first place of the product element under construction.
  2. says that is in the second place of the product element under construction.

Notice that, in construing the cartesian product of the sets and or the concatenation of the languages and in this way, one shifts the level of the active construction from the tupling of the elements in and or the concatenation of the strings that are internal to the languages and to the concatenation of the external signs that it takes to indicate these sets or these languages, in other words, passing to a conjunction of indexed propositions, and or to a conjunction of assertions, and that marks the sets or the languages in question for insertion in the indicated places of a product set or a product language, respectively. In effect, the subscripting by the indices and can be recognized as a special case of concatenation, albeit through the posting of editorial remarks from an external mark-up language.

In order to systematize the relations that strictures and straits placed at higher levels of complexity, constraint, information, and organization have with those that are placed at the associated lower levels, I introduce the following pair of definitions:

The excerpt of a stricture of the form regarded within a frame of discussion where the number of places is limited to is the stricture of the form In the proper context, this can be written more succinctly as the stricture an assertion that places the set in the place of the product.

The extract of a strait of the form constrained to a frame of discussion where the number of places is restricted to is the strait of the form In the appropriate context, this can be denoted more succinctly by the stricture an assertion that places the set in the place of the product.

In these terms, a stricture of the form can be expressed in terms of simpler strictures, to wit, as a conjunction of its excerpts:

In a similar vein, a strait of the form can be expressed in terms of simpler straits, namely, as an intersection of its extracts:

There is a measure of ambiguity that remains in this formulation, but it is the best that I can do in the present informal context.


We are only now beginning to see how this works. Clearly one of the mechanisms for picking a reality is the sociohistorical sense of what is important — which research program, with all its particularity of knowledge, seems most fundamental, most productive, most penetrating. The very judgments which make us push narrowly forward simultaneously make us forget how little we know. And when we look back at history, where the lesson is plain to find, we often fail to imagine ourselves in a parallel situation. We ascribe the differences in world view to error, rather than to unexamined but consistent and internally justified choice.

— Herbert J. Bernstein, "Idols of Modern Science", [HJB, 38]

In this Subsection, I discuss the mechanics of parsing the cactus language into the corresponding class of computational data structures. This provides each sentence of the language with a translation into a computational form that articulates its syntactic structure and prepares it for automated modes of processing and evaluation. For this purpose, it is necessary to describe the target data structures at a fairly high level of abstraction only, ignoring the details of address pointers and record structures and leaving the more operational aspects of implementation to the imagination of prospective programmers. In this way, I can put off to another stage of elaboration and refinement the description of the program that constructs these pointers and operates on these graph-theoretic data structures.

The structure of a painted cactus, insofar as it presents itself to the visual imagination, can be described as follows. The overall structure, as given by its underlying graph, falls within the species of graph that is commonly known as a rooted cactus, and the only novel feature that it adds to this is that each of its nodes can be painted with a finite sequence of paints, chosen from a palette that is given by the parametric set

It is conceivable, from a purely graph-theoretical point of view, to have a class of cacti that are painted but not rooted, and so it is frequently necessary, for the sake of precision, to more exactly pinpoint the target species of graphical structure as a painted and rooted cactus (PARC).

A painted cactus, as a rooted graph, has a distinguished node that is called its root. By starting from the root and working recursively, the rest of its structure can be described in the following fashion.

Each node of a PARC consists of a graphical point or vertex plus a finite sequence of attachments, described in relative terms as the attachments at or to that node. An empty sequence of attachments defines the empty node. Otherwise, each attachment is one of three kinds: a blank, a paint, or a type of PARC that is called a lobe.

Each lobe of a PARC consists of a directed graphical cycle plus a finite sequence of accoutrements, described in relative terms as the accoutrements of or on that lobe. Recalling the circumstance that every lobe that comes under consideration comes already attached to a particular node, exactly one vertex of the corresponding cycle is the vertex that comes from that very node. The remaining vertices of the cycle have their definitions filled out according to the accoutrements of the lobe in question. An empty sequence of accoutrements is taken to be tantamount to a sequence that contains a single empty node as its unique accoutrement, and either one of these ways of approaching it can be regarded as defining a graphical structure that is called a needle or a terminal edge. Otherwise, each accoutrement of a lobe is itself an arbitrary PARC.

Although this definition of a lobe in terms of its intrinsic structural components is logically sufficient, it is also useful to characterize the structure of a lobe in comparative terms, that is, to view the structure that typifies a lobe in relation to the structures of other PARC's and to mark the inclusion of this special type within the general run of PARC's. This approach to the question of types results in a form of description that appears to be a bit more analytic, at least, in mnemonic or prima facie terms, if not ultimately more revealing. Working in this vein, a lobe can be characterized as a special type of PARC that is called an unpainted root plant (UR-plant).

An UR-plant is a PARC of a simpler sort, at least, with respect to the recursive ordering of structures that is being followed here. As a type, it is defined by the presence of two properties, that of being planted and that of having an unpainted root. These are defined as follows:

  1. A PARC is planted if its list of attachments has just one PARC.
  2. A PARC is UR if its list of attachments has no blanks or paints.

In short, an UR-planted PARC has a single PARC as its only attachment, and since this attachment is prevented from being a blank or a paint, the single attachment at its root has to be another sort of structure, that which we call a lobe.

To express the description of a PARC in terms of its nodes, each node can be specified in the fashion of a functional expression, letting a citation of the generic function name "" be followed by a list of arguments that enumerates the attachments of the node in question, and letting a citation of the generic function name "" be followed by a list of arguments that details the accoutrements of the lobe in question. Thus, one can write expressions of the following forms:

    a node with no attachments.
    a node with the attachments
    a lobe with no accoutrements.
    a lobe with the accoutrements

Working from a structural description of the cactus language, or any suitable formal grammar for it is possible to give a recursive definition of the function called that maps each sentence in to the corresponding graph in One way to do this proceeds as follows:

  1. The parse of the concatenation of the sentences is defined recursively as follows:
    1. For

  2. The parse of the surcatenation of the sentences is defined recursively as follows:
    1. For

For ease of reference, Table 13 summarizes the mechanics of these parsing rules.

A substructure of a PARC is defined recursively as follows. Starting at the root node of the cactus any attachment is a substructure of If a substructure is a blank or a paint, then it constitutes a minimal substructure, meaning that no further substructures of arise from it. If a substructure is a lobe, then each one of its accoutrements is also a substructure of and has to be examined for further substructures.

The concept of substructure can be used to define varieties of deletion and erasure operations that respect the structure of the abstract graph. For the purposes of this depiction, a blank symbol is treated as a primer, in other words, as a clear paint or a neutral tint. In effect, one is letting In this frame of discussion, it is useful to make the following distinction:

  1. To delete a substructure is to replace it with an empty node, in effect, to reduce the whole structure to a trivial point.
  2. To erase a substructure is to replace it with a blank symbol, in effect, to paint it out of the picture or to overwrite it.

A bare PARC, loosely referred to as a bare cactus, is a PARC on the empty palette In other veins, a bare cactus can be described in several different ways, depending on how the form arises in practice.

  1. Leaning on the definition of a bare PARCE, a bare PARC can be described as the kind of a parse graph that results from parsing a bare cactus expression, in other words, as the kind of a graph that issues from the requirements of processing a sentence of the bare cactus language
  2. To express it more in its own terms, a bare PARC can be defined by tracing the recursive definition of a generic PARC, but then by detaching an independent form of description from the source of that analogy. The method is sufficiently sketched as follows:
    1. A bare PARC is a PARC whose attachments are limited to blanks and bare lobes.
    2. A bare lobe is a lobe whose accoutrements are limited to bare PARC's.
  3. In practice, a bare cactus is usually encountered in the process of analyzing or handling an arbitrary PARC, the circumstances of which frequently call for deleting or erasing all of its paints. In particular, this generally makes it easier to observe the various properties of its underlying graphical structure.


Alas, and yet what are you, my written and painted thoughts! It is not long ago that you were still so many-coloured, young and malicious, so full of thorns and hidden spices you made me sneeze and laugh — and now? You have already taken off your novelty and some of you, I fear, are on the point of becoming truths: they already look so immortal, so pathetically righteous, so boring!

— Nietzsche, Beyond Good and Evil, [Nie-2, ¶ 296]

In this Subsection, I describe a particular semantics for the painted cactus language, telling what meanings I aim to attach to its bare syntactic forms. This supplies an interpretation for this parametric family of formal languages, but it is good to remember that it forms just one of many such interpretations that are conceivable and even viable. In deed, the distinction between the object domain and the sign domain can be observed in the fact that many languages can be deployed to depict the same set of objects and that any language worth its salt is bound to to give rise to many different forms of interpretive saliency.

In formal settings, it is common to speak of interpretation as if it created a direct connection between the signs of a formal language and the objects of the intended domain, in other words, as if it determined the denotative component of a sign relation. But a closer attention to what goes on reveals that the process of interpretation is more indirect, that what it does is to provide each sign of a prospectively meaningful source language with a translation into an already established target language, where already established means that its relationship to pragmatic objects is taken for granted at the moment in question.

With this in mind, it is clear that interpretation is an affair of signs that at best respects the objects of all of the signs that enter into it, and so it is the connotative aspect of semiotics that is at stake here. There is nothing wrong with my saying that I interpret a sentence of a formal language as a sign that refers to a function or to a proposition, so long as you understand that this reference is likely to be achieved by way of more familiar and perhaps less formal signs that you already take to denote those objects.

On entering a context where a logical interpretation is intended for the sentences of a formal language there are a few conventions that make it easier to make the translation from abstract syntactic forms to their intended semantic senses. Although these conventions are expressed in unnecessarily colorful terms, from a purely abstract point of view, they do provide a useful array of connotations that help to negotiate what is otherwise a difficult transition. This terminology is introduced as the need for it arises in the process of interpreting the cactus language.

The task of this Subsection is to specify a semantic function for the sentences of the cactus language in other words, to define a mapping that "interprets" each sentence of as a sentence that says something, as a sentence that bears a meaning, in short, as a sentence that denotes a proposition, and thus as a sign of an indicator function. When the syntactic sentences of a formal language are given a referent significance in logical terms, for example, as denoting propositions or indicator functions, then each form of syntactic combination takes on a corresponding form of logical significance.

By way of providing a logical interpretation for the cactus language, I introduce a family of operators on indicator functions that are called propositional connectives, and I distinguish these from the associated family of syntactic combinations that are called sentential connectives, where the relationship between these two realms of connection is exactly that between objects and their signs. A propositional connective, as an entity of a well-defined functional and operational type, can be treated in every way as a logical or a mathematical object, and thus as the type of object that can be denoted by the corresponding form of syntactic entity, namely, the sentential connective that is appropriate to the case in question.

There are two basic types of connectives, called the blank connectives and the bound connectives, respectively, with one connective of each type for each natural number

  1. The blank connective of places is signified by the concatenation of the sentences that fill those places.

    For the special case of the blank connective is taken to be an empty string or a blank symbol — it does not matter which, since both are assigned the same denotation among propositions.

    For the generic case of the blank connective takes the form In the type of data that is called a text, the use of the center dot is generally supplanted by whatever number of spaces and line breaks serve to improve the readability of the resulting text.

  2. The bound connective of places is signified by the surcatenation of the sentences that fill those places.

    For the special case of the bound connective is taken to be an empty closure — an expression enjoying one of the forms with any number of blank symbols between the parentheses — all of which are assigned the same logical denotation among propositions.

    For the generic case of the bound connective takes the form

At this point, there are actually two different dialects, scripts, or modes of presentation for the cactus language that need to be interpreted, in other words, that need to have a semantic function defined on their domains.

  1. There is the literal formal language of strings in the painted and rooted cactus expressions that constitute the language
  2. There is the figurative formal language of graphs in the painted and rooted cacti themselves, a parametric family of graphs or a species of computational data structures that is graphically analogous to the language of literal strings.

Of course, these two modalities of formal language, like written and spoken natural languages, are meant to have compatible interpretations, and so it is usually sufficient to give just the meanings of either one. All that remains is to provide a codomain or a target space for the intended semantic function, in other words, to supply a suitable range of logical meanings for the memberships of these languages to map into. Out of the many interpretations that are formally possible to arrange, one way of doing this proceeds by making the following definitions:

  1. The conjunction of a set of propositions, is a proposition that is true if and only if every one of the is true.

    is true    is true for every

  2. The surjunction of a set of propositions, is a proposition that is true if and only if exactly one of the is untrue.

    is true    is untrue for unique

If the number of propositions that are being joined together is finite, then the conjunction and the surjunction can be represented by means of sentential connectives, incorporating the sentences that represent these propositions into finite strings of symbols.

If is finite, for instance, if consists of the integers in the interval and if each proposition is represented by a sentence then the following strategies of expression are open:

  1. The conjunction can be represented by a sentence that is constructed by concatenating the in the following fashion:

  2. The surjunction can be represented by a sentence that is constructed by surcatenating the in the following fashion:

If one opts for a mode of interpretation that moves more directly from the parse graph of a sentence to the potential logical meaning of both the PARC and the PARCE, then the following specifications are in order:

A cactus rooted at a particular node is taken to represent what that node denotes, its logical denotation or its logical interpretation.

  1. The logical denotation of a node is the logical conjunction of that node's arguments, which are defined as the logical denotations of that node's attachments. The logical denotation of either a blank symbol or an empty node is the boolean value The logical denotation of the paint is the proposition a proposition that is regarded as primitive, at least, with respect to the level of analysis that is represented in the current instance of
  2. The logical denotation of a lobe is the logical surjunction of that lobe's arguments, which are defined as the logical denotations of that lobe's accoutrements. As a corollary, the logical denotation of the parse graph of otherwise called a needle, is the boolean value

If one takes the point of view that PARCs and PARCEs amount to a pair of intertranslatable languages for the same domain of objects, then denotation brackets of the form can be used to indicate the logical denotation of a cactus or the logical denotation of a sentence

Tables 14 and 15 summarize the relations that serve to connect the formal language of sentences with the logical language of propositions. Between these two realms of expression there is a family of graphical data structures that arise in parsing the sentences and that serve to facilitate the performance of computations on the indicator functions. The graphical language supplies an intermediate form of representation between the formal sentences and the indicator functions, and the form of mediation that it provides is very useful in rendering the possible connections between the other two languages conceivable in fact, not to mention in carrying out the necessary translations on a practical basis. These Tables include this intermediate domain in their Central Columns. Between their First and Middle Columns they illustrate the mechanics of parsing the abstract sentences of the cactus language into the graphical data structures of the corresponding species. Between their Middle and Final Columns they summarize the semantics of interpreting the graphical forms of representation for the purposes of reasoning with propositions.

Aside from their common topic, the two Tables present slightly different ways of conceptualizing the operations that go to establish their maps. Table 14 records the functional associations that connect each domain with the next, taking the triplings of a sentence a cactus and a proposition as basic data, and fixing the rest by recursion on these. Table 15 records these associations in the form of equations, treating sentences and graphs as alternative kinds of signs, and generalizing the denotation bracket operator to indicate the proposition that either denotes. It should be clear at this point that either scheme of translation puts the sentences, the graphs, and the propositions that it associates with each other roughly in the roles of the signs, the interpretants, and the objects, respectively, whose triples define an appropriate sign relation. Indeed, the "roughly" can be made "exactly" as soon as the domains of a suitable sign relation are specified precisely.

A good way to illustrate the action of the conjunction and surjunction operators is to demonstrate how they can be used to construct the boolean functions on any finite number of variables. Let us begin by doing this for the first three cases,

A boolean function on variables is just an element of the boolean domain Table 16 shows several different ways of referring to these elements, just for the sake of consistency using the same format that will be used in subsequent Tables, no matter how degenerate it tends to appear in the initial case.

Column 1 lists each boolean element or boolean function under its ordinary constant name or under a succinct nickname, respectively.

Column 2 lists each boolean function in a style of function name that is constructed as follows: The superscript gives the dimension of the functional domain, that is, the number of its functional variables, and the subscript is a binary string that recapitulates the functional values, using the obvious translation of boolean values into binary values.

Column 3 lists the functional values for each boolean function, or possibly a boolean element appearing in the guise of a function, for each combination of its domain values.

Column 4 shows the usual expressions of these elements in the cactus language, conforming to the practice of omitting the underlines in display formats. Here I illustrate also the convention of using the expression as a visible stand-in for the expression of the logical value a value that is minimally represented by a blank expression that tends to elude our giving it much notice in the context of more demonstrative texts.

Table 17 presents the boolean functions on one variable, of which there are precisely four.


Here, Column 1 codes the contents of Column 2 in a more concise form, compressing the lists of boolean values, recorded as bits in the subscript string, into their decimal equivalents. Naturally, the boolean constants reprise themselves in this new setting as constant functions on one variable. Thus, one has the synonymous expressions for constant functions that are expressed in the next two chains of equations:

As for the rest, the other two functions are easily recognized as corresponding to the one-place logical connectives, or the monadic operators on Thus, the function is recognizable as the negation operation, and the function is obviously the identity operation.

Table 18 presents the boolean functions on two variables, of which there are precisely sixteen.


As before, all of the boolean functions of fewer variables are subsumed in this Table, though under a set of alternative names and possibly different interpretations. Just to acknowledge a few of the more notable pseudonyms:

The constant function appears under the name
The constant function appears under the name
The negation and identity of the first variable are and respectively.
The negation and identity of the second variable are and respectively.
The logical conjunction is given by the function
The logical disjunction is given by the function

Functions expressing the conditionals, implications, or if-then statements are given in the following ways:

The function that corresponds to the biconditional, the equivalence, or the if and only statement is exhibited in the following fashion:

Finally, there is a boolean function that is logically associated with the exclusive disjunction, inequivalence, or not equals statement, algebraically associated with the binary sum operation, and geometrically associated with the symmetric difference of sets. This function is given by:

Let me now address one last question that may have occurred to some. What has happened, in this suggested scheme of functional reasoning, to the distinction that is quite pointedly made by careful logicians between (1) the connectives called conditionals and symbolized by the signs and and (2) the assertions called implications and symbolized by the signs and , and, in a related question: What has happened to the distinction that is equally insistently made between (3) the connective called the biconditional and signified by the sign and (4) the assertion that is called an equivalence and signified by the sign ? My answer is this: For my part, I am deliberately avoiding making these distinctions at the level of syntax, preferring to treat them instead as distinctions in the use of boolean functions, turning on whether the function is mentioned directly and used to compute values on arguments, or whether its inverse is being invoked to indicate the fibers of truth or untruth under the propositional function in question.

Stretching Exercises

Taking up the preceding arrays of particular connections, namely, the boolean functions on up to two variables, for in it is possible to illustrate the use of the stretch operation in a variety of concrete cases.

For example, suppose that is a connection of the form that is, any one of the sixteen possibilities in Table 18, while and are propositions of the form that is, propositions about things in the universe or else the indicators of sets contained in

Then one has the imagination and the stretch of the connection to on amounts to a proposition that may be read as the stretch of to and If one is concerned with many different propositions about things in or if one is abstractly indifferent to the particular choices for and then one may detach the operator called the stretch of over and consider it in isolation from any concrete application.

When the cactus notation is used to represent boolean functions, a single sign at the end of the expression is enough to remind the reader that the connections are meant to be stretched to several propositions on a universe

For example, take the connection such that:

The connection in question is a boolean function on the variables that returns a value of just when just one of the pair is not equal to or what amounts to the same thing, just when just one of the pair is equal to There is clearly an isomorphism between this connection, viewed as an operation on the boolean domain and the dyadic operation on binary values that is otherwise known as

The same connection can also be read as a proposition about things in the universe If is a sentence that denotes the proposition then the corresponding assertion says exactly what one states in uttering the sentence In such a case, one has and all of the following expressions are ordinarily taken as equivalent descriptions of the same set:

Notice the distinction, that I continue to maintain at this point, between the logical values and the algebraic values This makes it legitimate to write a sentence directly into the righthand side of a set-builder expression, for instance, weaving the sentence or the sentence into the context thereby obtaining the corresponding expressions listed above. It also allows us to assert the proposition in a more direct way, without detouring through the equation since it already has a value in and thus can be taken as tantamount to an actual sentence.

If the appropriate safeguards can be kept in mind, avoiding all danger of confusing propositions with sentences and sentences with assertions, then the marks of these distinctions need not be forced to clutter the account of the more substantive indications, that is, the ones that really matter. If this level of understanding can be achieved, then it may be possible to relax these restrictions, along with the absolute dichotomy between algebraic and logical values, which tends to inhibit the flexibility of interpretation.

This covers the properties of the connection treated as a proposition about things in the universe Staying with this same connection, it is time to demonstrate how it can be "stretched" to form an operator on arbitrary propositions.

To continue the exercise, let and be arbitrary propositions about things in the universe that is, maps of the form and suppose that are indicator functions of the sets respectively. In other words, we have the following data:

Then one has an operator the stretch of the connection over and a proposition the stretch of to on with the following properties:

As a result, the application of the proposition to each returns a logical value in all in accord with the following equations:

For each choice of propositions and about things in the stretch of to and on is just another proposition about things in a simple proposition in its own right, no matter how complex its current expression or its present construction as makes it appear in relation to and Like any other proposition about things in it indicates a subset of namely, the fiber that is variously described in the following ways: