Unsorted notes


The purpose of this series of articles, is to share my thoughts on recursive sets. This is something I enjoy thinking about from time to time. I do not expect to make any serious progress in recursion theory, termination analysis, or the like. I am doing this simply because I enjoy thinking about recursive sets, and for no other reason.

Whenever I say "function," I mean a function which takes an n-tuple of natural numbers to a single natural number. If I do not specify, I am likely referring to a function which takes one natural number to another.

Whenever I say "predicate," I mean a predicate which takes one natural number to a boolean value. 0 will denote false, and 1 will denote true.

Definition of a strictly increasing function

There are two ways to characterize a strictly increasing natural number function. The first, is the same way you would characterize a strictly increasing real number function:

$$\forall x, y : x \lt y \longrightarrow f(x) < f(y)$$

The second, works only for the naturals:

$$\forall x : f(x) < f(x + 1)$$

You can prove these definitions are equivalent. It's not difficult, nor, in my opinion, necessary.

Useful properties of recursive sets

The predicate for a recursive set always terminates. Let A be a recursive set. Then you can always ask "is x in A?" or "is x not in A?" for any number x, and eventually receive an answer.

The complement, union, intersection, and difference of recursive sets is recursive.

TODO: If I give you two recursive sets, P and Q, and tell you R is the union of P and Q, how can you use that knowledge to express R directly?

Useful properties of total functions

Every total function terminates.

The composition of two total functions is total.

Bijection between total and strictly increasing

There is a bijection between the set of total functions, and the set of strictly increasing functions. What follows is the simplest way to show this correspondence.

Let f be total. Then g(0) = f(0), g(x + 1) = [g(x) + 1] + f(x + 1) is strictly increasing.

Let g be strictly increasing. Then f(0) = g(0), f(x + 1) = [g(x + 1) - 1] - f(x + 1) is total.

For example, the total function f(x) = 0, corresponds with the strictly increasing function g(x) = x.

Describing recursive sets using functions and predicates

The image of a strictly increasing function, is an infinite recursive set. For example, the image of f(x) = 2x, is the set of even numbers. The complement of the image of a strictly increasing function can define a finite set. For example, the complement of the image of f(x) = x + 3, is {0, 1, 2}.

A set is recursive if and only if it can be expressed as a total predicate. For example, the even numbers can be expressed by P(x) = 2 | x.

Recursion and constant addition

A function involving multiplication can be rewritten as a recursive function involving only addition. For example, f(x) = 2x can be rewritten as

$$\begin{align} & f(0) = 0 \\ & f(x + 1) = f(x) + 2 \end{align}$$

Unnecessary base cases

Functions can be expressed using more base cases than necessary. Induction can be used to establish when a base case is unnecessary. For example, induction can be used to prove f(x) = 0, is equal to

$$\begin{align} & f(0) = 0 \\ & f(x + 1) = f(x). \end{align}$$

If only recursion and constant addition are allowed, some functions become extremely difficult to express without multiple arguments. For example, the triangular numbers can be expressed concisely as f(n) = n(n + 1)/2, or recursively as

$$\begin{align} & \text{add}(x, 0) = 0 \\ & \text{add}(x, S(y)) = S(\text{add}(x, y)) \\[1em] & f(0) = 0 \\ & f(x + 1) = \text{add}(f(x), x + 1). \end{align}$$

Without that two-argument "add" function, \(f\) would be very difficult to express.

Notion of pairing

If you want to encode an ordered triple as a single natural number, you only need a pairing function. That's because an ordered triple can be represented as a pair within a pair. For example, the triple (a, b, c) can be represented as ((a, b), c), or (a, (b, c)). This notion also applies to functions which are associative. For example, the min function is associative, and so

$$\min(x, y, z) = \min(\min(x, y), z) = \min(x, \min(y, z))$$

If you want to break the natural numbers into three mutually distinct sets, you can start by breaking them into two sets, then break one of those sets in two again. In this way, you can break the natural numbers into any number of sets.

Every recursive, or piecewise function, is essentially breaking the natural numbers into two or more sets. For example,

$$\begin{align} & f(0) = \ldots \\ & f(x + 1) = \ldots \end{align}$$

is breaking the natural numbers into the sets {0} and {1, 2, 3, ...}.

Recursive functions and induction rules

Every pattern for a recursive function induces an induction rule. For example, the pattern

$$\begin{align} & \text{add}(x, 0) = 0 \\ & \text{add}(x, S(y)) = S(\text{add}(x, y)), \end{align}$$

induces the induction rule,

$$\left[\forall x : P(x, 0)\right] \wedge \left[\forall x, y : P(x, y) \longrightarrow P(x, S(y))\right] \longrightarrow \forall x, y : P(x, y)$$