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, \frac{1}{2}, \frac{1}{4}, \cdots) = 2$.¹ Now here is where things get real tricky. Take the function $g$ that does much the same as $f$, only it takes one (which you will note is a finite number) infinite sequence of reals. For example, $g([1, \frac{1}{2}, \frac{1}{4}, \cdots]) = 2$, where the input of $g$ is the sequence $[1, \frac{1}{2}, \frac{1}{4}, \cdots]$ rather than each individual element.

This seems super cursed; $f$ and $g$ 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)$ where $X$ is a set and $F$ is a set of finitary functions.

This definition is very general. There is no restriction besides that every function is $F$ is finitary. $F$ itself may be infinite, uncountable, whatever. So may $X$ be. In fact, not every function in $F$ needs to even admit any member of $X$ or tuples of members of $X$ 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$. 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 $X$ be the set of odd integers and $Y$ be the set of even integers. Then let $f$ be some function from $Y$ to $Y$. Then $(X, \{f\})$ is an inductive structure, despite the fact that $f$’s domain does not include any member of $X$. 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 $f$’s arguments for arbitrary $f\in F$. The motivation for this notation is vectors, because in some sense vectors are just lists.

We denote the list $a_0$, $a_1$, $\ldots$, $a_{n-1}$ as $\overrightarrow{a}$. We will refer to an arbitrary element in the list $\overrightarrow{a}$ as $a_i$.

Now for our final definition:

(Closure) A closure under $F$ is a set $X$ such that for every function $f \in F$ and every $\overrightarrow{a}$ in the domain of $f$ such that $a_i\in X$, $f(\overrightarrow{a}) \in X$.

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

The argument

Now for the theorem.

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

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

Y exists

We will recursively generate a sequence $X_i$. Let $X_0 = X$, and let $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(\overrightarrow{a})$ with every input in $X$, and join it to $X$ to find $X_{n+1}$.

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

Note each $a_i$ by definition is in some $X_i$ if it is in $Y$. Because $X_i \subset X_j$ for $i \leq j$, and there is some maximum $X_m$ in the list of $X_i$ that $a_i$ are in, $a_i \in X_m$ for all $a_i$. This is where we use the finitary condition, because otherwise we have no guarantee this maximal $X_m$ exists to begin with. And by definition, $f(\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 $z \in Y \implies z \in Z$ for the $Y$ we have just constructed. ($Z$ is an arbitrary closure under $F$ that is a superset of $X$.)

We claim that if $z \in X_n$ for any $X_n$, we must have $z \in Z$. We prove this via induction on $n$.

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

If $z \in X_{n+1}$, then either $z \in X_n$ or there is some $\overrightarrow{a}$ with all $a_i \in X_n$ such that $f(\overrightarrow{a}) = z$. This follows straight from the definition of $X$. If $z \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 “$Y$ exists” section, we indexed the finite set $X_i$ with a countable set, namely the natural numbers. The reason we cannot let $X_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 $X_i$? If we index with the ordinal number $\omega_1$, then we can find some “maximum” in $\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.