Formal Systems

Formal Systems

1. primitive ("atomic") symbols
   • Some people understand the term "symbol" to mean a "marker" or "token" that has a meaning. Although I don't use that term in this way, everything I say here can be understood with either interpretation.

2. recursive rules for forming new (complex, or "molecular") symbols, ultimately from the primitive ones.
   • These are usually called "well-formed formulas", or "wffs".

3. a distinguished subset of the wffs
   • In an "axiomatic" system, these are the axioms.
   • Although axioms are often understood as "self-evidently true" statements, I think it is better to consider them merely as wffs that are "given" initially.

4. recursive rules for forming "new" wffs from "old" ones, ultimately from the axioms
   • These rules are sometimes called "transformation rules" or—more often—"rules of inference".

   • The "new" wffs are new only in the sense that they are produced (or "generated", or "proved") from "previous" ones. Since they are wffs, they are formed (or constructed) from the primitive symbols, and so aren't "new" in the sense of never previously existing. The "old" wffs from which these new ones are generated are merely ones that are generated before the "new" ones.

   • Usually (but not necessarily), these rules are supposed to be "truth-preserving", i.e., if the "old" ones are true, then so are the "new" ones. But the rules themselves are silent about both this and the truth values of the wffs.

   • A sequence of wffs (usually beginning with axioms) that is such that each wff in the sequence is either an axiom or is generated by (or "follows from") previous wffs in the sequence according to one of the rules of inference is sometimes called a "proof" (or, a "proof of" the last wff in the sequence). The last wff in the sequence is often called a "theorem".
     1. If the axioms are true, and if the rules are truth-preserving, then, of course, the theorems will be true. This property of a formal system is called "soundness".

     2. On the other hand, if all wffs that are independently known to be true can be proved to be theorems, then the formal system is said to be (semantically) "complete".
        • Gödel's Incompleteness Theorem is sometimes expressed as follows: Any formal system containing axioms and rules of inference for first-order logic and Peano's axioms for arithmetic is such that, if it is consistent (i.e., if there is no wff P such that both P and not-P can be proved), then it is incomplete.

As an analogy, consider a "Transformer" toy made of Lego blocks. For those of you who don't have (or who weren't themselves) children (probably boys) of a certain elementary-school age, Transformers are toys that, in one configuration, look like monsters, but can be manipulated so that they turn into something else, often (believe it or not) a truck or other vehicle. Lego blocks are small building blocks that can be attached to each other to form larger structures.

1. The Lego blocks can be likened to the primitive symbols.

2. The instructions for building larger structures from the individual Lego blocks can be likened to the rules for producing wffs from primitive symbols. To continue the analogy, suppose that the only wffs are Transformers, either monsters or trucks. (This is a bit imaginary: You can't make Transformers out of Lego blocks; even if you could, the manipulations to turn them from monsters into trucks would probably cause them to fall apart.)

3. The instructions for transforming a monster into a truck, or vice versa, can be likened to the rules of inference, and if a given monster is likened to an axiom, then the truck that it can be transformed into can be likened to a theorem.

The above analogy falls apart if you look at it too closely, so please don't!

Semiotics

1. Syntax
   1. Syntax is the study of the relations among the symbols of a formal symbol system. It can be more generally understood as the study of the relations among the entities of some domain, preferably a domain that can be understood more or less in the terms of a formal system.

   2. Grammatical syntax (or just "grammar", for short) is the study of which sequences (or "strings") of symbols are well formed (according to the recursive rules of grammar).

   3. Proof-theoretical syntax (or "proof theory") is the study of which sequences of wffs are "derivable" from the transformation rules (or "provable via the rules of inference").

   4. Note that my description of a formal system, above, was entirely in terms of syntax.

   5. Syntax does not include the study of such things as "truth", "meaning", "reference", etc.

2. Semantics
   1. Semantics is the study of the relations between the symbols of a formal system and what they represent, mean, refer to (etc.) in the "world" (where this "world" could be the real world, some possible world, some fictional world, some situation or state of affairs that is part of a world, etc.)

   2. Semantics requires:
      1. a syntactic domain (usually a formal system); call it SYN.

      2. a semantic domain, characterized by an "ontology"; call it SEM.
         • The ontology can be understood as a (syntactic) theory of the semantic domain, in the sense that it specifies:
           • the parts of the semantic domain
           • their relationships (structural [parts and wholes] and inferential [model theory, or a theory of truth and satisfaction])
           • in this sense, SEM is a "model" of SYN!

      3. a "compositional" (i.e., homomorphic, or structure-preserving) semantic interpretation mapping from SYN —> SEM

3. Pragmatics
   1. "Pragmatics" is a grab-bag term used by different people to mean different things. The most accurate meaning is probably that pragmatics is the study of everything else that is interesting about formal systems and their interpretations that isn't covered by either syntax or semantics. Most people would agree that pragmatics includes the study of the relations among symbol systems, their interpretations, and the cognitive agents who use them. It is also often characterized as the study of "contexts" in which symbols are used. "Context", however, is another grab-bag term; it can mean "social" context, or "situational" context, or "indexical" context (e.g., the fact that the sentence "I am hungry" (which contains an "indexical" or "deictic" term: "I") means the same thing (in one sense of "means") no matter who says it (i.e., it means that the speaker is hungry), yet means different things depending on who says it (if you say it, it means that you are hungry, whereas if I say it, it means that I am hungry, which might have different truth values).

Examples

1. Hofstader, Douglas R. (1979), Gödel, Escher, Bach: An Eternal Golden Braid (New York: Basic Books).
   • Ch. I ("The MU-puzzle"), pp. 33-41 [PDF].
   • MU-puzzle solution [PDF]

2. Rapaport, William J. (1996), Understanding Understanding: Semantics, Computation, and Cognition [postscript], pre-printed as Technical Report 96-26 [postscript ftp] (Buffalo: SUNY Buffalo Department of Computer Science).
   • Ch. 2, §"Tarskian Semantics"

3. Suber, Peter (2002), "Sample Formal System S"

4. 
   Van Moer, Ard (2007), "The Intentionality of Formal Systems", Foundations of Science 11(1/2) (March): 81-119.

Other References:

• Haugeland, John (1981), "Semantic Engines: An Introduction to Mind Design", in John Haugeland (ed.), Mind Design: Philosophy, Psychology, Artificial Intelligence (Cambridge, MA: MIT Press): 95-128.

• Posner, Roland (1992), "Origins and Development of Contemporary Syntactics", Languages of Design 1: 37-50.

• Tomalin, Marcus (2002), "The Formal Origins of Syntactic Theory", Lingua 112(10): 827-848.
  • An interesting history of the development of formal systems and their application in contemporary linguistic theory (e.g., Chomsky).