## You are here

Homefreely generated inductive set

## Primary tabs

# 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. $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:

###### Proposition 1.

The following are equivalent:

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

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

## Mathematics Subject Classification

03B99*no label found*03E20

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections