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:
“It is a misfortune that necessity has induced men to accord greater license to this formidable engine, in order to obtain liberty, than can be borne with less important objects in view; for the press, like fire, is an excellent servant, but a terrible master.”
—James Fenimore Cooper (1789–1851)
“The return of the asymmetrical Saturday was one of those small events that were interior, local, almost civic and which, in tranquil lives and closed societies, create a sort of national bond and become the favorite theme of conversation, of jokes and of stories exaggerated with pleasure: it would have been a ready- made seed for a legendary cycle, had any of us leanings toward the epic.”
—Marcel Proust (1871–1922)