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 nonempty inductive set, then $\mathbb{N}$ can be embedded in $A$.
More generally, fix a nonempty 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 $\u27e8X\u27e9$. We also say that $X$ generates $\u27e8X\u27e9$.
Another way of defining $\u27e8X\u27e9$ 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}=\u27e8X\u27e9$.
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 $\u27e8X\u27e9\subseteq \overline{X}$, since $\u27e8X\u27e9$ is minimal^{}. On the other hand, suppose $a\in \overline{X}$. We prove by induction^{} that $a\in \u27e8X\u27e9$. If $a\in X$, this is clear. Suppose now that ${X}_{i}\subseteq \u27e8X\u27e9$, 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 \u27e8X\u27e9$ by hypothesis^{}. Since $\u27e8X\u27e9$ is inductive, $f({a}_{1},\mathrm{\dots},{a}_{n})\in \u27e8X\u27e9$, and hence $a\in \u27e8X\u27e9$ as well. This shows that ${X}_{i+1}\subseteq A$, and consequently $\overline{X}\subseteq \u27e8X\u27e9$. ∎
The inductive set $A$ is said to be freely generated by $X$ (with respect to $F$), if the following conditions are satisfied:

1.
$A=\u27e8X\u27e9$,

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

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 wellformed 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$.
References
 1 H. Enderton: A Mathematical Introduction to Logic, Academic Press, San Diego (1972).
Title  freely generated inductive set 

Canonical name  FreelyGeneratedInductiveSet 
Date of creation  20130322 18:51:24 
Last modified on  20130322 18:51:24 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  11 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03B99 
Classification  msc 03E20 
Related topic  ClosureOfSetsClosedUnderAFinitaryOperation 
Defines  inductive closure 