Inductive Structures

I sat in on a lecture mostly about inductive structures today in CMU’s 21-300 Basic Logic. I went with who we will refer to as cursed schedule guy (from the last post) and we talked with Professor Cummings afterwards; more on the contents at the end.

Also, I will be a lot more expository than the lecture was. I feel like you had to connect a lot of dots in your head in the lecture, whereas the point here is to at least provide a reference for myself to turn my brain off.

No guarantees that the details are entirely right since this is off memory and Google is really, really bad when it comes to formal logic stuff. Also I will be vague since this is a general overview.

Anyway, it’s math time!

First we establish the following:

(Finitary Function) A finitary function is just a function with a finite number of inputs.

An example of a finitary function is addition on the reals: it takes ×\mathbb{R}\times \mathbb{R} \to \mathbb{R}.

An example of an infinitary function (i.e. not finitary) is one that takes an infinite number of reals as input and outputs their sum; e.g. f(1,12,14,)=2f(1, \frac{1}{2}, \frac{1}{4}, \cdots) = 2.1 Now here is where things get real tricky. Take the function gg that does much the same as ff, only it takes one (which you will note is a finite number) infinite sequence of reals. For example, g([1,12,14,])=2g([1, \frac{1}{2}, \frac{1}{4}, \cdots]) = 2, where the input of gg is the sequence [1,12,14,][1, \frac{1}{2}, \frac{1}{4}, \cdots] rather than each individual element.

This seems super cursed; ff and gg are fundamentally the same and yet they are classified entirely differently for a theorem who we will see only cares about this one classification. The point is about finiteness of the number of inputs though, we don’t need the members of the input to be finite or countable or whatever.

(Inductive Structures) An inductive structure is an ordered pair (X,F)(X, F) where XX is a set and FF is a set of finitary functions.

This definition is very general. There is no restriction besides that every function is FF is finitary. FF itself may be infinite, uncountable, whatever. So may XX be. In fact, not every function in FF needs to even admit any member of XX or tuples of members of XX as inputs.

A standard inductive structure is (,{+,×})(\mathbb{R}, \{+, \times\}). Note ++ and ×\times are functions that take two inputs in \mathbb{R} and return an output in \mathbb{R}. For instance, +(2,2)=4+(2, 2) = 4. Yes, this is cursed notation, but you can think of the binary operator ++ as a function with two inputs. And in fact, you have to when strictly considering inductive structures. Also, this inductive structure feels closed. This is a word we will define later, but ++ takes two members of \mathbb{R} to a member of \mathbb{R}. So does ×\times. You should intuitively feel that this inductive structure feels closed-ish.

Here is a more cursed inductive structure. Let XX be the set of odd integers and YY be the set of even integers. Then let ff be some function from YY to YY. Then (X,{f})(X, \{f\}) is an inductive structure, despite the fact that ff’s domain does not include any member of XX. Cursed, isn’t it? But it still falls under the definition, even if this inductive structure does not actually do anything interesting.

Now for a bit of notation that will make it easier to refer to ff’s arguments for arbitrary fFf\in F. The motivation for this notation is vectors, because in some sense vectors are just lists.

We denote the list a0a_0, a1a_1, \ldots, an1a_{n-1} as a\overrightarrow{a}. We will refer to an arbitrary element in the list a\overrightarrow{a} as aia_i.

Now for our final definition:

(Closure) A closure under FF is a set XX such that for every function fFf \in F and every a\overrightarrow{a} in the domain of ff such that aiXa_i\in X, f(a)Xf(\overrightarrow{a}) \in X.

Say XX is a closure under FF. Then you can naturally construct a closed inductive structure (X,F)(X, F). We won’t worry about that in this post.

The argument

Now for the theorem.

For any set XX and any set of finitary functions FF, there exists a set YY such that XYX\subset Y and YY is a closure under FF. Furthermore, we can find a least upper bound YY, meaning that there exists some YY such that for all ZZ satisfying the same property, YZY\subset Z.

The main difficulty is showing such a YY exists. The least upper bound property is pretty easy to see just from how YY is explicitly constructed.

Y exists

We will recursively generate a sequence XiX_i. Let X0=XX_0 = X, and let Xn+1=X{f(a)fF,aiX}X_{n+1} = X \cup \{f(\overrightarrow{a}) \mid f \in F, a_i \in X\}. In other words, we look at what we get from taking f(a)f(\overrightarrow{a}) with every input in XX, and join it to XX to find Xn+1X_{n+1}.

Now let Y=X0X1X2Y = X_0 \cup X_1 \cup X_2 \cup \cdots. We claim YY works, and we show this by proving if each aia_i is in some XiX_i, then f(a)f(\overrightarrow{a}) must be too.

Note each aia_i by definition is in some XiX_i if it is in YY. Because XiXjX_i \subset X_j for iji \leq j, and there is some maximum XmX_m in the list of XiX_i that aia_i are in, aiXma_i \in X_m for all aia_i. This is where we use the finitary condition, because otherwise we have no guarantee this maximal XmX_m exists to begin with. And by definition, f(a)Xm+1Yf(\overrightarrow{a}) \in X_{m+1} \in Y.

Y is a least upper bound

This is a standard set theory argument; we just want to show that zYzZz \in Y \implies z \in Z for the YY we have just constructed. (ZZ is an arbitrary closure under FF that is a superset of XX.)

We claim that if zXnz \in X_n for any XnX_n, we must have zZz \in Z. We prove this via induction on nn.

The base case where n=0n=0 holds true by definition (XZX \subset Z).

If zXn+1z \in X_{n+1}, then either zXnz \in X_n or there is some a\overrightarrow{a} with all aiXna_i \in X_n such that f(a)=zf(\overrightarrow{a}) = z. This follows straight from the definition of XX. If zXnz \in X_n then we are done. Otherwise we are done by the definition of a closure.

Finitary is a lie

A subset of our discussion with Prof. Cummings after class. This is where I don’t really know what I’m saying, which is why it is quite hand-wavy.

The finitary condition should make you feel like something is off; like it isn’t really necessary. And in fact, it isn’t if you use the right perspective. In the “YY exists” section, we indexed the finite set XiX_i with a countable set, namely the natural numbers. The reason we cannot let XiX_i be infinite (more precisely, have the same cardinality as \mathbb{N} is because then we cannot find some maximum in \mathbb{N} of these elements in \mathbb{N}.

But what if we had a number that was guaranteed to be “bigger” than anything in \mathbb{N}? Another source of motivation: don’t you see how the size of the indexing set \mathbb{N} is “just an infinity bigger” than the finite set XiX_i? If we index with the ordinal number ω1\omega_1, then we can find some “maximum” in ω1\omega_1 that is bigger than every element in the set of size ω\omega (you can treat this as \mathbb{N} here) of our finitary set. And thus, if we commit to using ordinals for indexing, we can have the number of inputs be ordinal too. And thus the finitary condition can be dropped.

Apparently all of this is legal in set theory land. They just tighten their argument up much more than I am right now.