What is a Formal System?
Table of Contents
Formal system #
A formal system is like a game in which tokens are manipulated according to rules in order to see what configurations can be obtained. Examples: chess, checkers, go, tic-tac-toe. Nonexamples: marbles, billiards, baseball.
A formal system consists of a language over some alphabet of symbols together with (axioms and) inference rules that distinguish some of the strings in the language as theorems.
Each formal system has a formal language composed of primitive symbols acted on by certain rules of formation (statements concerning the symbols, functions, and sentences allowable in the system) and developed by inference from a set of axioms.
In an axiomatic system, the primitive symbols are undefined; and all other symbols are defined in terms of them.
Given some set of symbols (or tokens) and some rules on how we can put those symbols together, we can produce new configurations. This is a very simple idea which lies in the center of logic and math.
Examples #
Construction toys (like Lego), can be thought as formal systems. You have a set of tokens, and rules are based on physical restrictions.
The “MU Puzzle” proposed by Hofstadter in his GEB book.
Peano axioms which describe natural numbers with 0 and +1 (successor operation).
Euclidean geometry which builds a set of rules based on a small set of axioms.
John Conway’s Game of Life consists of a field of cels and rules which define the state of the board on the next move.
Metalogic #
Metalogic has led to a great deal of work of a mathematical nature in axiomatic set theory, model theory, and recursion theory (in which functions that are computable in a finite number of steps are studied).
Axiom #
Axiom, in logic, an indemonstrable first principle, rule, or maxim, that has found general acceptance or is thought worthy of common acceptance whether by virtue of a claim to intrinsic merit or on the basis of an appeal to self-evidence. An example would be: “Nothing can both be and not be at the same time and in the same respect.”
- a statement accepted as true as the basis for argument or inference
- an established rule or principle or a self-evident truth
- a maxim widely accepted on its intrinsic merit
Axiom is some statement which is given without proof. Both symbols and rules from formal systems can be referred to as axioms.
Cogito, ergo sum. (Latin for “I think, therefore I am”)
– René Descartes
If axioms are unprovable how do we know what we know? Isn’t it all just a castle built in the air.
Model #
To model a phenomenon is to construct a formal theory that describes and explains it. (In a closely related sense, you model a system or structure that you plan to build, by writing a description of it.)
– SEP
A map is not the territory it represents, but, if correct, it has a similar structure to the territory, which accounts for its usefulness.
– Science and Sanity, Alfred Korzybski
Model is not the same as reality. It is just a useful representation. The usefulness of the model comes from it impreciseness - some details removed, which allows us to focus on what matters (see abstraction).
Because the model is just some symbolic representation of reality, it can “fit” for more than one reality. When we find similarities between different models we call it correspondence, for example, see Physics, Topology, Logic, and Computation: A Rosetta Stone.
| Category Theory | Physics | Topology | Logic | Computation |
|---|---|---|---|---|
| object | system | manifold | proposition | data type |
| morphism | process | cobordism | proof | program |
As well we can define more than one model to represent the same reality.