Structure (mathematical Logic) - Induced Substructures and Closed Subsets

Induced Substructures and Closed Subsets

is called an (induced) substructure of if

• and have the same signature ;
• the domain of is contained in the domain of : ; and
• the interpretations of all function and relation symbols agree on .

The usual notation for this relation is .

A subset of the domain of a structure is called closed if it is closed under the functions of, i.e. if the following condition is satisfied: for every natural number n, every n-ary function symbol f (in the signature of ) and all elements, the result of applying f to the n-tuple is again an element of B: .

For every subset there is a smallest closed subset of that contains B. It is called the closed subset generated by B, or the hull of B, and denoted by or . The operator is a finitary closure operator on the set of subsets of .

If and is a closed subset, then is an induced substructure of, where assigns to every symbol of σ the restriction to B of its interpretation in . Conversely, the domain of an induced substructure is a closed subset.

The closed subsets (or induced substructures) of a structure form a lattice. The meet of two subsets is their intersection. The join of two subsets is the closed subset generated by their union. Universal algebra studies the lattice of substructures of a structure in detail.