Fraïssé's theorem

from Wikipedia, the free encyclopedia

The set of Fraisse , named after Roland Fraïssé is a sentence from the mathematical logic . Is a finite set of symbols, he characterizes the elementary equivalence of two - structures in a purely algebraic way, without reference to the first-order logic to take.

Finite isomorphism

We assume a finite set of symbols and the associated language of first-order predicate logic. For the desired characterization we need the following algebraic terms.

If and -structures, then a mapping is called a partial isomorphism from to , if the following applies:

  • is an illustration with a domain and a set of images .
  • is injective .
  • If it is a constant symbol, then:
    • Is so is .
    • Is , so is and .
  • If there is a -digit function symbol and are , then applies
.
  • If a -digit relation symbol and are , then applies
.

This includes the interpretations of the symbols in the model . In the case of a partial isomorphism, the usual notation for mappings is also used, meaning that the domain as defined above is contained in.

If there is a partial isomorphism, then obviously , where and . If further is a subset, then the restriction is also a partial isomorphism and it is .

Two structures and are called finitely isomorphic if there is a sequence of non-empty sets of partial isomorphisms such that the following continuation properties are satisfied:

  • For each and there is a with and .
  • For each and there is a with and .

A partial isomorphism can thus be extended to any elements to a partial isomorphism, namely one after the other to partial isomorphisms ; and that also applies to.

If and are two isomorphic structures and if one isomorphism, then and are also finitely isomorphic, because the above definition is also fulfilled for all . The reverse is not true; further below it will be proved that the ordered sets and , the symbol set is here , are finitely isomorphic, but they can not be isomorphic for reasons of power .

Formulation of the sentence

The concept of finite isomorphism, which makes use of symbols but does not make any further reference to the first-level predicate logic, can be used to characterize the elementary equivalence of two structures in the first-level predicate logic:

Fraïssé's theorem : For a finite set of symbols and for two -structures and are equivalent:

  • and are elementarily equivalent.
  • and are finitely isomorphic.

application

To clarify the terms, we want to apply Fraïssé's theorem as an example to the theory of dense, linear orders without extremes . An ordered set is called linearly ordered if two elements can be compared. It is called dense if there is a third between every two elements. An extremum of an order is an element that is larger or smaller than any other. The theory of dense linear orders without extrema is therefore defined by the following sentences of language :

.

The first two sentences express irreflectivity and transitivity . Together, this results in antisymmetry :

The third sentence says that the elements are ordered linearly. The next two sentences demand that there are no extremes and the last apparently gives the definition of tightness. Let it be the conjunction of these six sentences, whereby the index d is supposed to remind of the impermeability of the order. From the third and sixth statements it immediately follows that dense orders contain an infinite number of elements.

Every partial isomorphism with a finite domain can be extended to a further partial isomorphism on any element. If, for example, is and is a further element, then, because of the tightness of, one can find an element that is in the same size relation to as to . The definition

then defines a partial isomorphism that continues on the element . The same goes for , because it is also tight. So if you put

,

so defines a finite isomorphism between and . Any two structures that satisfy are therefore finitely isomorphic. This also proves the finite isomorphism between and claimed above .

From Fraïssé's theorem it follows:

  • Any two models of the class of dense orders are elementarily equivalent.

A typical application of this statement is:

  • For every sentence , or .

As proof , we have to show. We do this indirectly by assuming that there is a model that satisfies, but not . Then there is a dense order, since it fulfills, which does not fulfill and therefore has to be a model for . But since all the dense orders are elementarily equivalent according to the above and therefore satisfy the same propositions, it follows for every model that satisfies, that is, it applies in contradiction to the assumption made. It must therefore apply.

See also

Ehrenfeucht-Fraïssé games : characterization of elementary equivalence by means of a game-theoretical interpretation of finite isomorphism.

literature

  • Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Introduction to mathematical logic. Spektrum Akademischer Verlag, Heidelberg / Berlin / Oxford 1996, ISBN 3-8274-0130-5 , especially Chapter XII