Unique Readability

Last time we established the concept of an inductive structure. Before we get to what unique readability, we’ll have to talk a little more about inductive structures.

We will use dom f\text{dom } f to refer to the domain of ff in these notes.

Also, from now on, when we say “the closure of (X,F)(X, F)”, we mean the minimal set YXY\supset X such that YY is closed under FF.


Before, we were dealing with functions ff that possibly had tuples of different sizes in its domain. For instance, maybe ff can take 22 arguments sometimes, and 33 arguments at other times. For the purposes of an inductive structure, we can decompose such a function into f2f_2 and f3f_3, the subsets of the functions that take 22 and 33 functions respectively. This would not alter the closure whatsoever, so for the remainder of these notes we will make that simplification.

If a function ff takes nn inputs, then we say it is nn-ary. Alternatively, we say that nn is its arity. Both terms are synonymous.


Theorem. Let PP be some property and (X,F)(X, F) be an inductive structure. If PP is a property such that

then all elements in the closure of (X,F)(X, F) satisfy PP as well.

This is what a proof by induction looks like. First we prove the base case: all aXa \in X satisfy PP. Then we prove the inductive step: applying a function ff to a tuple of stuff that satisfies PP spits out something that also satisfies PP.

Consider the inductive structure ({0},{+1})(\{0\}, \{+1\}) that generates the natural numbers. Whenever we do a standard proof by induction, this is the closure we are implicitly using. But hopefully you see just how powerful this theorem is.

Outline of proof. Recall how we constructed sets XnX_n to show that (X,F)(X, F) has a closure. Now we can inductively prove that every aXna \in X_n satisfies PP.

Motivating example: propositional logic

These notes will assume a little bit of CS knowledge and no knowledge of propositional logic. If you know the latter, you can probably skim or even entirely skip this section.

So perhaps you are familiar with boolean operators such as

(a && (!b)) || c

Propositional logic works a similar way: we have formulae composed of propositional letters — like aa, bb, and cc are in the example above, though they can be anything — and operators like &&, ||, and ! that act on some number of propositional letters. However, in classical logic (the form of propositional logic we usually study) we use different symbols to represent the AND, OR, and NOT operators: they are \land, \lor, and ¬\lnot, respectively.

Well, the formulae in a propositional logic can also be represented as a closure of an inductive structure! For example, consider an inductive structure ({a,b,c},{,})(\{a, b, c\}, \{\land, \lor\}) such that (a,b)=(ab)\land(a, b) = (a \land b). Note that there is an \land function that returns a string with an \land symbol, and the two are not the same. Furthermore, note that the (( and )) characters are part of the outputted string. We can similarly define (a,b)\lor(a, b).

Here’s why we need the parentheses: ignore for a second what you know about operator precedence. Consider a formula like abca \land b \lor c. Should it represent (ab)c(a \land b) \lor c, or should it represent a(bc)a \land (b \lor c)? Another way to think of it is, without the parentheses, how was this propositional formula inductively generated: as (a,(b,c))\land(a, \lor(b, c)), or as ((ab),c)\lor((a \land b), c)? Thus it is useful for formulae to be generated in one unique way. It is useful for propositional formulae to be uniquely readable (which they are, solely because of the parentheses).

Unique readability

Definition (Unique Readability). An inductive structure (X,F)(X, F) is uniquely readable if and only if for every yy in its closure YY, exactly one of the following conditions hold:

Note that the inductive structure ({0},{+1})(\{0\}, \{+1\}) is uniquely readable. Try proving this yourself if you don’t understand why this is true!

This notion of unique readability leads to the concept of defining a function recursively. We will first explore the properties we generally want a definition by recursion to have, then establish a theorem that formalizes all of these concepts.

First, note that a definition by recursion does not always go off without a hitch. Consider some inductive structure (X,F)(X, F) with aa, bb, cXc \in X and ff, gFg \in F. Then if f(a)=cf(a) = c and g(b)=cg(b) = c, a recursive definition based on ff and gg might run into issues — what if f(a)g(b)f(a) \neq g(b)? Guaranteeing this is true in general is hard, so instead we want there to be one unique set of inputs that generates this output. In other words, we want injectivity, which comes from unique readability.

Here is our wishlist for a definition by recursion. For our starting set XX in (X,F)(X, F) with closure YY, we want to specify:

More broadly, we can define a function GG on a closure YY just by looking at the starting set XX and a set of compositions on elements in the starting set XX to define G(yY\X)G(y \in Y \setminus X).

Of course, for the reasons we have just established, (X,F)(X, F) should be uniquely readable.

Now we’re ready to formalize this idea.

Theorem (Definition by recursion). Consider a uniquely readable inductive structure (X,F)(X, F) with closure YY. If

then there is a unique function GG such that

This specifies a unique way to extend G0G_0 given an inductive structure and HfH_f for each fFf \in F.

Outline of proof: Recall the definition of XnX_n when we showed the existence of a closure. We show by inducting on nn that there exists only one possible extension of Gn1G_{n-1}, whose domain is Xn1X_{n-1}, onto GnG_n, whose domain is XnX_n.

Here is an example of a definition by recursion on the Fibonacci sequence. Our inductive structure is ({0,1},{f})(\{0, 1\}, \{f\}) where f(n,n+1)=n+2f(n, n+1) = n+2 for n0n\geq 0, and its domain is only pairs of the form (n,n+1)(n, n+1) for n0n\geq 0.

Now we define an initial function G0G_0 such that G0(0)=0G_0(0) = 0 and G0(1)=1G_0(1) = 1. Define Hf(n,n+1,G(n),G(n+1))=G(n)+G(n+1)H_f(n, n + 1, G(n), G(n + 1)) = G(n) + G(n+1), and note G(n+2)=G(f(n,n+1))=Hf(n,n+1,G(n),G(n+1))=G(n)+G(n+1)G(n + 2) = G(f(n, n + 1)) = H_f(n, n+1, G(n), G(n+1)) = G(n) + G(n+1). Yay! Our idea of unique readability and a definition of recursion makes sense on a simple function like the Fibonacci sequence, even if it is a little convoluted.

Though it is convoluted and we will not usually need to construct recursive functions like this, it is good to know what is happening under the hood. And it is good to understand why the Fibonacci sequence gives you a well-defined, unique value of f(x)f(x) for all xx \in \mathbb{N}. It is because the Fibonacci sequence is equivalent to a function GG on a uniquely readable closure (X,F)(X, F), as we have just shown.