Syntax & Semantics of Formal Systems
Last Update: 25 March 2010
material is highlighted
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"
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
As an analogy to a formal system, consider a
toy made of
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
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.
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 (or the theory of signs and symbols) consists of:
- 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.
- 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).
- 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").
- Note that my description of a formal system, above,
was entirely in terms of syntax.
- 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
- Russell, Bertrand (1917),
Mysticism and Logic, Ch. 4.
- 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.)
- Semantics requires:
- a syntactic domain (usually a formal system);
call it SYN.
- 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
- 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"
- a "compositional" (i.e., homomorphic, or structure-preserving)
semantic interpretation mapping from SYN → SEM
- "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
It is also often characterized as the study of
"contexts" in which symbols are used.
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:
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 (in another sense of "means") 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).
Hofstader, Douglas R.
Gödel, Escher, Bach: An Eternal Golden Braid
(New York: Basic Books).
Rapaport, William J.
Semantics, Computation, and Cognition [postscript],
Technical Report 96-26
(Buffalo: SUNY Buffalo Department of Computer Science).
Formal System S"
Van Moer, Ard (2007),
"The Intentionality of Formal Systems",
Foundations of Science
11(1/2) (March): 81-119.
Syntax vs. Semantics
Tenenbaum & Augenstein on Data, Information, & Semantics
Engines: An Introduction to Mind Design",
in John Haugeland (ed.),
Mind Design: Philosophy, Psychology, Artificial Intelligence
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",
- An interesting history of the development of formal systems
and their application in contemporary linguistic theory (e.g.,
Copyright © 2004–2010 by
William J. Rapaport