freely generated inductive set

In the parent entry, we see that an inductive set is a set that is closed under the successor operator. If $A$ is a non-empty inductive set, then $\mathbb{N}$ can be embedded in $A$.

More generally, fix a non-empty set $U$ and a set $F$ of finitary operations on $U$. A set $A\subseteq U$ is said to be inductive (with respect to $F$) if $A$ is closed under each $f\in F$. This means, for example, if $f$ is a binary operation on $U$ and if $x,y\in A$, then $f(x,y)\in A$. $A$ is said to be inductive over $X$ if $X\subseteq A$. The intersection of inductive sets is clearly inductive. Given a set $X\subseteq U$, the intersection of all inductive sets over $X$ is said to be the inductive closure of $X$. The inductive closure of $X$ is written $⟨X⟩$. We also say that $X$ generates $⟨X⟩$.

Another way of defining $⟨X⟩$ is as follows: start with

$$X_0:=X.$$

Next, we “inductively” define each $X_{i+1}$ from $X_i$, so that

$$X_{i+1}:=X_i\cup \bigcup \{f(X_i^n)\mid f\in F,f\text{ is }n\text{-ary}\}.$$

Finally, we set

$$\overline{X}:=\bigcup _{i=0}^{\mathrm{\infty }}{X}_i.$$

It is not hard to see that $\overline{X}=⟨X⟩$.

Proof.

By definition, $X\subseteq \overline{X}$. Suppose $f\in F$ is $n$-ary, and $a_1,\mathrm{\dots },a_n\in \overline{X}$, then each $a_i\in X_{m(i)}$. Take the maximum $m$ of the integers $m(i)$, then $a_i\in X_m$ for each $i$. Therefore $f(a_1,\mathrm{\dots },a_n)\in X_{m+1}\subseteq \overline{X}$. This shows that $\overline{X}$ is inductive over $X$, so $⟨X⟩\subseteq \overline{X}$, since $⟨X⟩$ is minimal. On the other hand, suppose $a\in \overline{X}$. We prove by induction that $a\in ⟨X⟩$. If $a\in X$, this is clear. Suppose now that $X_i\subseteq ⟨X⟩$, and $a\in X_{i+1}$. If $a\in X_i$, then we are done. Suppose now $a\in X_{i+1}-X_i$. Then there is some $n$-ary operation $f\in F$, such that $a=f(a_1,\mathrm{\dots },a_n)$, where each $a_j\in X_i$. So $a_j\in ⟨X⟩$ by hypothesis. Since $⟨X⟩$ is inductive, $f(a_1,\mathrm{\dots },a_n)\in ⟨X⟩$, and hence $a\in ⟨X⟩$ as well. This shows that $X_{i+1}\subseteq A$, and consequently $\overline{X}\subseteq ⟨X⟩$.∎

The inductive set $A$ is said to be freely generated by $X$ (with respect to $F$), if the following conditions are satisfied:

1. $A=⟨X⟩$,

2. for each $n$-ary $f\in F$, the restriction of $f$ to $A^n$ is one-to-one;

3. for each $n$-ary $f\in F$, $f(A^n)\cap X=\mathrm{\varnothing }$;

4. if $f,g\in F$ are $n,m$-ary, then $f(A^n)\cap g(A^m)=\mathrm{\varnothing }$.

For example, the set $\overline{V}$ of well-formed formulas (wffs) in the classical proposition logic is inductive over the set of $V$ propositional variables with respect to the logical connectives (say, $\mathrm{\neg }$ and $\vee$) provided. In fact, by unique readability of wffs, $\overline{V}$ is freely generated over $V$. We may readily interpret the above “freeness” conditions as follows:

1. $\overline{V}$ is generated by $V$,

2. for distinct wffs $p,q$, the wffs $\mathrm{\neg }p$ and $\mathrm{\neg }q$ are distinct; for distinct pairs $(p,q)$ and $(r,s)$ of wffs, $p\vee q$ and $r\vee s$ are distinct also

3. for no wffs $p,q$ are $\mathrm{\neg }p$ and $p\vee q$ propositional variables

4. for wffs $p,q$, the wffs $\mathrm{\neg }p$ and $p\vee q$ are never the same

A characterization of free generation is the following:

Proposition 1.

The following are equivalent:

1. $A$ is freely generated by $X$ (with respect to $F$)

2. if $V\ne \mathrm{\varnothing }$ is a set, and $G$ is a set of finitary operations on $V$ such that there is a function $\varphi :F\to G$ taking every $n$-ary $f\in F$ to an $n$-ary $\varphi (f)\in G$, then every function $h:X\to B$ has a unique extension $\overline{h}:A\to B$ such that

   $$\overline{h}(f(a_1,\mathrm{\dots },a_n))=\varphi (f)(\overline{h}(a_1),\mathrm{\dots },\overline{h}(a_n)),$$

   where $f$ is an $n$-ary operation in $F$, and $a_i\in A$.