Formalism 101
Escaping local optima on a random walk through life.

1.1 An alphabet \(\Sigma\) is a finite set, it’s elements are called symbols.

1.2 Words over an alphabet \(\Sigma\) are sequences of symbols in \(\Sigma\), so a word is a function \(w: \{ i | i \in \mathbb{N}_{0}, i < n\} \rightarrow \Sigma\), where \(n := |w|\) is the length of the word.

1.3 The empty word \(\epsilon\) is the sequence that doesn’t contain any symbol, so \(\epsilon: \emptyset \rightarrow \Sigma\).

1.4 Concatenating two words over \(\Sigma\) is the operation that joins those two words end-to-end:

\[\cdot: \{ i | i \in \mathbb{N}_{0}, i < n + m \} \rightarrow \Sigma.\]

1.5 The Kleene star \(*\), also known as the free monoid construction, is a unary operation on an alphabet and we write \(\Sigma^{*}\) for the Kleene star applied on \(\Sigma\).

\(\Sigma^{*}\) is the smallest superset of \(\Sigma\) that contains the empty string \(\epsilon\) and is closed under concatenation.

We define it inductively:

If

• \(\Sigma^{0} := \{ \epsilon \}\) and
• \(\forall i \geq 0: \Sigma^{i+1} := \{ wv | w \in \Sigma^{i}, v \in \Sigma \}\),

then \(\Sigma^{*} := \bigcup\limits_{i \geq 0} \Sigma^{i}\).

The elements \(w \in \Sigma^{*}\) are exactly the words over \(\Sigma\).

1.6 A formal language \(L \subseteq \Sigma^{*}\) over an alphabet \(\Sigma\) is a set of words over that alphabet.

2.1 A grammar \(G = (N, \Sigma, P, S)\) is nefined as follows:

• \(N\) is an alphabet of nonterminal symbols,
• \(\Sigma\) is an alphabet of terminal symbols,
• \(P\) is a finite set of production rules, which are elements \((p, q) \in (\Sigma \cup N)^{*}N(\Sigma \cup N)^{*} \times (\Sigma \cup N)^{*} \text{, but we usually write } p \rightarrow q \text{ for } (p, q)\) and \(p \rightarrow q_{1} | q_{2}\) for \((p, q_{1}), (p, q_{2})\).
• \(S \in N\) is the start symbol.

Note that \(N \cap \Sigma = \emptyset\) is required, as each symbol is either nonterminal or terminal.

2.2 Every grammar \(G\) defines a formal language \(L(G)\) as follows:

The binary relation \(\Rightarrow_{G} \subseteq (\Sigma \cup N)^{*} \times (\Sigma \cup N)^{*}\), called \(G\) derives in one step, is defined as \[ x \Rightarrow_{G} y \iff \exists u, v, p, q \in (\Sigma \cup N)^{*}: (x = upv) \wedge (y = uqv) \wedge (p \rightarrow q \in P) \text{.} \] The binary relation \(\Rightarrow_{G}^{*}\), called \(G\) derives in zero or more steps, is the reflexive transitive closure of \(\Rightarrow_{G}\). The grammar \(G\) thus defines a formal language \(L(G) := \{ w \in \Sigma^{*} | S \Rightarrow_{G}^{*} w \text{ in finitely many steps} \}\).

3.1 A formal system \(F = (\Sigma, G, A, R)\) consists of

• an alphabet \(\Sigma\), which is a finite set of symbols,
• a grammar \(G\) over \(\Sigma\), which describes how valid formulas can be built from the symbols in the alphabet (\(L(G)\) is the set of valid formulas),
• a set of axioms and axiom schemata \(A \subseteq L(G)\), which are valid formulas that are assumed to be true, and
• a set of inference rules \(R \subseteq L(G) \times L(G)\) for inferring theorems from the axioms and one another.

Schemata are formulas in the metalanguage of the system that generalize formulas in that systems language and thus allow the formulation of an infinite amount of axioms of the same structure. A good example is the induction schema of the Peano axioms for the natural numbers.

Within such a system, we can use its grammar to build valid formulas from the symbols contained in its alphabet and we can use its inference rules to derive theorems from its axioms and thus prove them.

4.1 The lambda calculus is a formal system for expressing computation. Like Turing machines, it’s a universal model for doing so, i.e. the lambda calculus is turing complete. However, it’s a lot simpler and in my opinion also more elegant than the bulky Turing machines. It’s also the fundament to functional programming languages, like Haskell.

We can now use the basic concepts defined above to define the untyped lambda calculus. The untyped lambda calculus is the formal system \(F_{\lambda} = (\Sigma_{\lambda}, G_{\lambda}, A_{\lambda}, R_{\lambda})\), where

• \(\Sigma_{\lambda} = \{\lambda, ., v, {}_{0}, {}_{1}, \dots, {}_{9}, (, )\}\),
• \(G_{\lambda} = \{N_{\lambda}, \Sigma_{\lambda}, P_{\lambda}, S_{\lambda} \}\), defined inductively,
• \(A_{\lambda} = \{ \forall t. t = t \}\),
• \(R_{\lambda}\), as defined below.

\(\Sigma_{\lambda}\) contains the abstraction symbols \(\lambda\) and ., the parentheses ( and ) and symbols to build variables \(v_{0}, v_{1}, \dots\) from. One can define the grammar \(G_{\lambda}\) by listing all productions, but we will do so inductively in the definition of lambda expressions below.

5.1 We’re writing \(\Lambda := L(G_{\lambda})\) for the set of all valid lambda expressions. Here, we’re defining \(\Lambda\) inductively:

• Variables: All variables \(v_{0}, v_{1}, \dots\) are lambda expressions, so \(\forall i \in \mathbb{N}_{0}: v_{i} \in \Lambda\).
• Abstraction: For every variable \(v \in \Lambda\) and every \(M \in \Lambda\), we have \((\lambda v. M) \in \Lambda\) as well.
• Application: For every \(M, N \in \Lambda\), we also have \((M N) \in \Lambda\).

Sometimes the \(v_{i}\)’s are hard to distinguish, so we’re allowing \(a, b, c, \dots\) as names for variables as well. One can easily formalize this correctly by simply adding them to \(\Sigma_{\lambda}\) and \(G_{\lambda}\).

We can also define \(G_{\lambda} = \{N_{\lambda}, \Sigma_{\lambda}, P_{\lambda}, S_{\lambda} \}\) in the ordinary way. Let \(N_{\lambda} = \{S_{\lambda}, V, D, D'\}\), and let \[ P_{\lambda} = \{S_{\lambda} \rightarrow V \text{ } | \text{ } (\lambda V. S_{\lambda}) \text{ } | \text{ } ( S_{\lambda} S_{\lambda} ),\] \[V \rightarrow vD,\] \[D \rightarrow {}_{0} \text{ } | \text{ } {}_{1}D' \text{ } | \text{ } \dots \text{ } | \text{ } {}_{9}D',\] \[D' \rightarrow \epsilon \text{ } | \text{ } {}_{0}D' \text{ } | \text{ } {}_{1}D' \text{ } | \text{ } \dots \text{ } | \text{ } {}_{9}D'\\ \}. \]