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 $\langle X\rangle$ . We also say that $X$ generates $\langle X\rangle$ .

Another way of defining $\langle X\rangle$ 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 \lbrace f(X_i^n)\mid f\in F, f \mbox{ is } n\mbox{-ary}\rbrace.$$ Finally, we set $$\overline{X}: = \bigcup_{i=0}^{\infty} X_i.$$ It is not hard to see that $\overline{X}=\langle X\rangle$ .

Proof. By definition, $X\subseteq \overline{X}$ . Suppose $f\in F$ is $n$ -ary, and $a_1,\ldots, 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,\ldots, a_n) \in X_{m+1} \subseteq \overline{X}$ . This shows that $\overline{X}$ is inductive over $X$ , so $\langle X\rangle \subseteq \overline{X}$ , since $\langle X\rangle$ is minimal. On the other hand, suppose $a\in \overline{X}$ . We prove by induction that $a\in \langle X\rangle$ . If $a\in X$ , this is clear. Suppose now that $X_i\subseteq \langle X\rangle$ , 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,\ldots, a_n)$ , where each $a_j\in X_i$ . So $a_j\in \langle X\rangle$ by hypothesis. Since $\langle X\rangle$ is inductive, $f(a_1,\ldots, a_n) \in \langle X\rangle$ , and hence $a\in \langle X\rangle$ as well. This shows that $X_{i+1}\subseteq A$ , and consequently $\overline{X} \subseteq \langle X\rangle$ .

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

1. $A=\langle X\rangle$ ,
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=\varnothing$ ;
4. if $f,g\in F$ are $n,m$ -ary, then $f(A^n)\cap g(A^m)=\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, $\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 $\neg p$ and $\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 $\neg p$ and $p\vee q$ propositional variables
4. for wffs $p,q$ , the wffs $\neg p$ and $p\vee q$ are never the same

A characterization of free generation is the following:

Bibliography

1

H. Enderton: A Mathematical Introduction to Logic, Academic Press, San Diego (1972).