freely generated inductive set

In the parent entry, we see that an inductive setMathworldPlanetmath is a set that is closed underPlanetmathPlanetmath the successorMathworldPlanetmathPlanetmathPlanetmath operator. If A is a non-empty inductive set, then can be embedded in A.

More generally, fix a non-empty set U and a set F of finitary operations on U. A set AU is said to be inductive (with respect to F) if A is closed under each fF. This means, for example, if f is a binary operationMathworldPlanetmath on U and if x,yA, then f(x,y)A. A is said to be inductive over X if XA. The intersectionMathworldPlanetmath of inductive sets is clearly inductive. Given a set XU, 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


Next, we “inductively” define each Xi+1 from Xi, so that

Xi+1:=Xi{f(Xin)fF,f is n-ary}.

Finally, we set


It is not hard to see that X¯=X.


By definition, XX¯. Suppose fF is n-ary, and a1,,anX¯, then each aiXm(i). Take the maximum m of the integers m(i), then aiXm for each i. Therefore f(a1,,an)Xm+1X¯. This shows that X¯ is inductive over X, so XX¯, since X is minimalPlanetmathPlanetmath. On the other hand, suppose aX¯. We prove by inductionMathworldPlanetmath that aX. If aX, this is clear. Suppose now that XiX, and aXi+1. If aXi, then we are done. Suppose now aXi+1-Xi. Then there is some n-ary operation fF, such that a=f(a1,,an), where each ajXi. So ajX by hypothesisMathworldPlanetmathPlanetmath. Since X is inductive, f(a1,,an)X, and hence aX as well. This shows that Xi+1A, and consequently X¯X. ∎

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

  1. 1.


  2. 2.

    for each n-ary fF, the restrictionPlanetmathPlanetmathPlanetmath of f to An is one-to-one;

  3. 3.

    for each n-ary fF, f(An)X=;

  4. 4.

    if f,gF are n,m-ary, then f(An)g(Am)=.

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

  1. 1.

    V¯ is generated by V,

  2. 2.

    for distinct wffs p,q, the wffs ¬p and ¬q are distinct; for distinct pairs (p,q) and (r,s) of wffs, pq and rs are distinct also

  3. 3.

    for no wffs p,q are ¬p and pq propositional variables

  4. 4.

    for wffs p,q, the wffs ¬p and pq are never the same

A characterizationMathworldPlanetmath of free generation is the following:

Proposition 1.

The following are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath:

  1. 1.

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

  2. 2.

    if V is a set, and G is a set of finitary operations on V such that there is a function ϕ:FG taking every n-ary fF to an n-ary ϕ(f)G, then every function h:XB has a unique extensionPlanetmathPlanetmathPlanetmath h¯:AB such that


    where f is an n-ary operation in F, and aiA.


  • 1 H. Enderton: A Mathematical Introduction to Logic, Academic Press, San Diego (1972).
Title freely generated inductive set
Canonical name FreelyGeneratedInductiveSet
Date of creation 2013-03-22 18:51:24
Last modified on 2013-03-22 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