Finite Model Theory
Finite model theory is the area of model theory which has the closest ties to universal algebra. Like some parts of universal algebra, and in contrast with the other areas of model theory, it is mainly concerned with finite algebras, or more generally, with finite σ-structures for signatures σ which may contain relation symbols as in the following example:
- The standard signature for graphs is σgrph={E}, where E is a binary relation symbol.
- A graph is a σgrph-structure satisfying the sentences and .
A σ-homomorphism is a map that commutes with the operations and preserves the relations in σ. This definition gives rise to the usual notion of graph homomorphism, which has the interesting property that a bijective homomorphism need not be invertible. Structures are also a part of universal algebra; after all, some algebraic structures such as ordered groups have a binary relation <. What distinguishes finite model theory from universal algebra is its use of more general logical sentences (as in the example above) in place of identities. (In a model-theoretic context an identity t=t' is written as a sentence .)
The logics employed in finite model theory are often substantially more expressive than first-order logic, the standard logic for model theory of infinite structures.
Read more about this topic: Model Theory
Famous quotes containing the words finite, model and/or theory:
“For it is only the finite that has wrought and suffered; the infinite lies stretched in smiling repose.”
—Ralph Waldo Emerson (1803–1882)
“... if we look around us in social life and note down who are the faithful wives, the most patient and careful mothers, the most exemplary housekeepers, the model sisters, the wisest philanthropists, and the women of the most social influence, we will have to admit that most frequently they are women of cultivated minds, without which even warm hearts and good intentions are but partial influences.”
—Mrs. H. O. Ward (1824–1899)
“By the “mud-sill” theory it is assumed that labor and education are incompatible; and any practical combination of them impossible. According to that theory, a blind horse upon a tread-mill, is a perfect illustration of what a laborer should be—all the better for being blind, that he could not tread out of place, or kick understandingly.... Free labor insists on universal education.”
—Abraham Lincoln (1809–1865)