# 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 $\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\{f(X_{i}^{n})\mid f\in F,f\mbox{ is }n\mbox{-ary}\}.$

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. 1.

$A=\langle X\rangle$,

2. 2.

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

3. 3.

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

4. 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. 1.

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

2. 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. 3.

for no wffs $p,q$ are $\neg p$ and $p\vee q$ propositional variables

4. 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:

###### Proposition 1.

The following are equivalent:

1. 1.

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

2. 2.

if $V\neq\varnothing$ is a set, and $G$ is a set of finitary operations on $V$ such that there is a function $\phi:F\to G$ taking every $n$-ary $f\in F$ to an $n$-ary $\phi(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},\ldots,a_{n}))=\phi(f)(\overline{h}(a_{1}),\ldots,% \overline{h}(a_{n})),$

where $f$ is an $n$-ary operation in $F$, and $a_{i}\in A$.

## References

• 1 H. Enderton: A Mathematical Introduction to Logic, Academic Press, San Diego (1972).
Title freely generated inductive set FreelyGeneratedInductiveSet 2013-03-22 18:51:24 2013-03-22 18:51:24 CWoo (3771) CWoo (3771) 11 CWoo (3771) Definition msc 03B99 msc 03E20 ClosureOfSetsClosedUnderAFinitaryOperation inductive closure