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.
Read more about this topic: Structure (mathematical Logic)
Famous quotes containing the words induced and/or closed:
“Few can be induced to labor exclusively for posterity; and none will do it enthusiastically. Posterity has done nothing for us; and theorize on it as we may, practically we shall do very little for it, unless we are made to think we are at the same time doing something for ourselves.”
—Abraham Lincoln (1809–1865)
“My old Father used to have a saying that “If you make a bad bargain, hug it the tighter”; and it occurs to me, that if the bargain you have just closed [marriage] can possibly be called a bad one, it is certainly the most pleasant one for applying that maxim to, which my fancy can, by any effort, picture.”
—Abraham Lincoln (1809–1865)