Syntax & Semantics of Formal Systems

Last Update: 25 March 2010

Note: or material is highlighted

Formal Systems

A formal system (also known as: "symbol system", "formal symbol system", "formal language", "formal theory", etc.) consists of:

primitive ("atomic") symbols (or "markers", or "tokens")
- 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.
recursive rules for forming new (complex, or "molecular") symbols, ultimately from the primitive ones.
- These are usually called "well-formed formulas", or "wffs".
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.
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.
    If all of the theorems are true, then the formal system is said to be "sound".
  2. If all of the wffs that are 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:

As an analogy to a formal system, 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.

The Lego blocks can be likened to the primitive symbols.
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.)
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

Semiotics (or the theory of signs and symbols) consists of:

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.
  - This may be why Bertrand Russell said, "Mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true."
    - Russell, Bertrand (1917), Mysticism and Logic, Ch. 4.
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
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.

Examples

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]
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" [PDF]
Suber, Peter (2002), "Sample Formal System S"
Van Moer, Ard (2007), "The Intentionality of Formal Systems", Foundations of Science 11(1/2) (March): 81-119.

Other References:

Syntax vs. Semantics
Tenenbaum & Augenstein on Data, Information, & Semantics
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).