A language, also called a vocabulary or signature by different authors, is a set \mathcal {L} consisting of symbols for constants, relations, and functions, often denoted by c, R, and f respectively. Languages may have any cardinality.

Given a language \mathcal {L}, an \mathcal {L}-structure \mathcal {M} in this language has a universe M (often, the structure and its universe are written the same, by abuse of notation). The structure \mathcal {M} "interprets" the symbols of \mathcal {L} as follows:

For a constant symbol c \in \mathcal {L}, the interpretation of c in \mathcal {M}, denoted c^{ \mathcal {M}} represents a fixed element of M

For an n-ary function symbol f \in \mathcal {L}, the interpretation of f in \mathcal {M}, denoted f^{ \mathcal {M}}, is a function from M^n to M

For an n-ary relation symbol R \in \mathcal {L}, the interpretation of R in \mathcal {M}, denoted R^{ \mathcal {M}}, is a subset M^n

Often, we are interested in the cardinality of a structure, denoted | \mathcal {M}|, which is defined to be the cardinality of its universe.

Given two structures \mathcal {A} and \mathcal {B} in a language \mathcal {L}, a homomorphism \varphi : \mathcal {A} \rightarrow \mathcal {B} is a function between the universes A and B of \mathcal {A} and \mathcal {B} respectively such that:

For every n-ary function f \in \mathcal {L}, for all a_1, \dots , a_n \in A, \varphi (f^{ \mathcal {A}}(a_1, \dots , a_n)) = f^{ \mathcal {B}}( \varphi (a_1), \dots , \varphi (a_n))

For every n-ary relation R \in \mathcal {L}, for all a_1, \dots , a_n \in A, \varphi (R^{ \mathcal {A}}(a_1, \dots , a_n)) \text { holds } \Rightarrow R^{ \mathcal {B}}( \varphi (a_1), \dots , \varphi (a_n)) holds

For every constant symbol c \in \mathcal {L}, \varphi (c^{ \mathcal {A}}) =c^{ \mathcal {B}}

Given two structures in a language \mathcal {L} \mathcal {A} and \mathcal {B}, an embedding \varphi : \mathcal {A} \rightarrow \mathcal {B} is a homomorphism such that:

For every n-ary relation R \in \mathcal {L}, for all a_1, \dots , a_n \in A, \varphi (R^{ \mathcal {A}}(a_1, \dots , a_n)) \text { holds } \Leftrightarrow R^{ \mathcal {B}}( \varphi (a_1), \dots , \varphi (a_n)) holds

This is stronger than a homomorphism because we now require a two way implication in the above property.

An embedding \varphi : \mathcal {A} \rightarrow \mathcal {B} between \mathcal {L}-structures is a isomorphism if it is surjective. An automorphism of a structure \mathcal {A} is an isomorphism to itself.

Given a \mathcal {L}-structure \mathcal {A}, a subset B \subseteq A is called a substructure of \mathcal {A} if:

For every constant c \in \mathcal {L}, c^{ \mathcal {A}} \in B

For every n-ary function f \in \mathcal {L}, for any b_1, \dots , b_n \in B, f^{ \mathcal {A}}(b_1, \dots ,b_n) \in B

For every n-ary relation, R \in \mathcal {L}, for any b_1, \dots , b_n \in B, we write R^B = R^{ \mathcal {A}} \cap \mathcal {P}(B^n) and require that R^{B}(b_1, \dots , b_n) holds (i.e., (b_1, \dots , b_n) \in R^{B}) if and only if R^{ \mathcal {A}}(b_1, \dots , b_n) holds (i.e., (b_1, \dots , b_n) \in R^{ \mathcal {A}}) Note that this condition is vacuously true, so only the first two conditions need to be checked when verifying a substructure.

Given two structures \mathcal {A} and \mathcal {B} in a language \mathcal {L}, a homomorphism \Phi \colon \mathcal {A} \to \mathcal {B} is an elementary embedding when for every \mathcal L-formula \varphi (x_1, \dots ,x_n) and a_1, \dots ,a_n \in A, we have \mathcal A \vDash \varphi (a_1, \dots ,a_n) if and only if \mathcal B \vDash \varphi ( \Phi (a_1), \dots , \Phi (a_n)). A partial homomorphism \Phi : \mathcal {A} \to \mathcal {B} can also be said to be an elementary embedding when for every \mathcal L-formula \varphi (x_1, \dots ,x_n) and a_1, \dots ,a_n \in dom \Phi, we have \mathcal A \vDash \varphi (a_1, \dots ,a_n) if and only if \mathcal B \vDash \varphi ( \Phi (a_1), \dots , \Phi (a_n)).

Given two structures \mathcal {A} and \mathcal {B} in a language \mathcal {L} such that \mathcal A is a substructure of \mathcal B, \mathcal A is an elementary substructure of \mathcal B when the inclusion map \mathcal A \hookrightarrow \mathcal B is an elementary embedding. Conversely, \mathcal B is called an elementary extension of \mathcal A.

One writes \mathcal A \preceq \mathcal B to mean \mathcal A is an elementary substructure of \mathcal B.

Given a language \mathcal {L}, we define a term to be any of the following:

If c \in \mathcal {L} is a constant symbol, then c is a term

If x is a variable symbol, then x is a term. We generally assume we have countably infinitely many variable symbols

If t_1,..., t_n are terms, and f \in \mathcal {L} is an n-ary function, then f(t_1,..., t_n) is a term.

Given a language \mathcal {L}, an atomic formula is defined as follows:

If R \in \mathcal {L} is an n-ary relation symbol, and t_1, \dots , t_n are terms, then R(t_1, \dots , t_n) is an atomic formula.

If t_1 and t_2 are \mathcal {L}-terms, then t_1 = t_2 is an atomic formula.

Given a language \mathcal {L}, an \mathcal {L}-formula is defined inductively as follows:

• If \phi is an \mathcal {L}-atomic formula then \phi is a formula.
• If \phi and \psi are both formulas, then \neg \phi, \phi \land \psi, and \phi \lor \phi are formulas, where \lor , \neg , \land are the usual logical connectives.
• If \phi is a formula, then \exists x \phi and \forall x \phi are formulas, where \exists and \forall are quantifiers.
• If \phi is a formula, then \exists x \phi and \forall x \phi are formulas, where \exists and \forall are quantifiers.

Given a language \mathcal {L}, a \mathcal {L}-theory is a set of \mathcal {L}-sentences. Sometimes it is notationally convenient to assume that theories are deductively closed.

An \mathcal L-theory is complete when for every \mathcal L-formula \phi we have that \phi may be deduced from T or \neg \phi may be deduced from T.

An Elimination Set for a language \mathcal {L} and class K of \mathcal {L}-structures, then a set \Gamma of formulas \phi is an elimination set for K if for every formula \phi ( \bar {x}) of \mathcal {L} there is a formula \phi ^*( \bar {x}) which is a boolean combinations of formulas in \Gamma and \phi is equivalent to \phi ^* in every structure in K

Let K be a class of L structures and \Phi be a set of L-formulas. Denote \Phi ^- as the set of negations of formulas in \Phi.

Suppose that

1. every atomic formula of L is in \Phi and
2. for every formula \theta ( \overline {x}) of L which is of the form \exists y \bigwedge _{i<n} \psi _i ( \overline {x},y) with each \psi _i \in \Phi \cup \Phi ^-, there is an L-formula \theta ^*( \overline {x}) which is a boolean combination of formulas in \Phi and is equivalent to \theta in every structure in K.

The theory of algebraically closed fields (ACF) is a theory in the language \mathcal L= \{ 0,1,+, \cdot \} consisting of the following sentences.

• \forall x \forall y \forall z \, (x+y)+z=x+(y+z).
• \forall x \, x+0=x \land0 +x=x.
• \forall x \exists y \, x+y=0 \land y+x=0.
• \forall x \forall y \, x+y=y+x.
• \forall x \forall y \forall z \, (x \cdot y) \cdot z=x \cdot (y+ \cdot z).
• \forall x \, x \cdot1 =x \land1 \cdot x=x.
• \forall x \exists y \, x \cdot y=1 \land y \cdot x=1.
• \forall x \forall y \, x+ \cdot y=y \cdot x.
• \forall x \forall y \forall z \, x \cdot (y+z)=(x \cdot y)+(x \cdot z).
• For each n \in \mathbb N, a sentence \forall y_1 \cdots \forall y_n \exists x \, (y_1 \cdot x)+ \cdots +(y_n \cdot x)=0.

The theory of algebraically closed fields of characteristic p (\text {ACF}_p) is ACF together with the sentence 1+ \cdots +1=0, where 1 is being added p times. \text {ACF}_p is a complete theory having quantifier elimination.

The theory of algebraically closed fields of characteristic 0 (\text {ACF}_0) is ACF together with the collection of sentences of the form \neg (1+ \cdots +1=0), for any number of 1s being added together. \text {ACF}_0 is also a complete theory having quantifier elimination.

The dense linear order without endpoints (DLO) is a theory in the language \mathcal L= \{ < \} consisting of the following sentences.

• \forall x \, \neg x<x
• \forall x \forall y \, (x<y \rightarrow \neg (y<x))
• \forall x \forall y \forall z \, ((x<y \land y<z) \rightarrow x<z)
• \forall x \forall y \, (( \neg x=y) \rightarrow (x<y \lor y<x))
• \forall x \forall y \, x<y \rightarrow ( \exists z \, x<z \land z<y)
• \forall x \exists z \, z<x
• \forall x \exists z \, x<z

The set of rationals \mathbb Q with the usual ordering is a model of DLO, and DLO is \aleph _0-categorical, so every countable model is isomorphic to ( \mathbb Q,<). DLO is also a complete theory with quantifier elimination.

The Morleyisation of an L-theory T is the theory T^m in the language L^m \supset L. The expanded language L^m is formed by taking every L-formula \phi (x_1,...,x_n) and adding an n-placed relation symbol R_ \phi. To T we add the axioms

\forall x_1,...,x_n (R_ \phi (x_1,...,x_n) \leftrightarrow \phi (x_1,...,x_n))

Morleyisation preserves many properties such as \kappa-categoricity, though the relations R_ \phi and the corresponding definable sets may be quite hard to understand.

Given a language, \mathcal {L}, and a \mathcal {L}-theory T, a partial type of T is a finitely satisfiable set of formulas in a fixed tuple of variables x.

A partial type p(x) (meaning that the denoted type consists of formulas each in the variables x) is complete if for every \mathcal {L}-formula in the variables x, \varphi (x) \in p(x), either \varphi (x) \in p(x) or \neg \varphi (x) \in p(x).

Given a language, \mathcal {L}, and a \mathcal {L}-theory T, a partial type of T {p(x)} is principal when there is an \mathcal {L}-formula \varphi (x) such that \models \exists x \varphi (x) and for every \varpsi (x) \in p(x) we have that \models \forall x ( \varphi (x) \rightarrow \varpsi (x)). In the case that p(x) is complete, we must have that \varphi (x) \in p(x), and the first condition is redundant.

A complete type of T, p(x) is isolated if it is principal as a partial type. Equivalently, {p(x)} is isolated if \{ p(x) \} is open S_n(T). This coincides with the usual topological terminology.

Given a language, \mathcal {L}, and a \mathcal {L}-theory T, S_n(T) denotes a topological space whose underlying set is the set of all complete n-types of T. The topology on S_n(T) has a basis of open sets given by all sets of the form [ \varphi (x)] := \{ p(x) \in S_n(T): \varphi (x) \in p(x) \} (for \varphi (x) an \mathcal {L}-formula). This space is a Stone Space in the usual sense and the Boolean Algebra associated to it via Stone Duality is the nth Tarski-Lindenbaum Algebra of T.

An \mathcal L-theory T is finitely satisfiable when every finite subset of T is satisfiable.

A structure M is \lambda-saturated, for a cardinal \lambda, when for every A \subseteq M such that |A|< \lambda, every type over A is realized in M. M is simply said to be saturated if M is |M|-saturated.

A structure M is \lambda-homogeneous, for a cardinal \lambda, when for every cardinal \eta < \lambda and sequences (a_i \in M|i \in \eta ), \{ b_i \in M|i \in \eta \} such that (M,(a_i)_{i< \eta }) \equiv (M,(b_i)_{i< \eta }), for each c \in M there is d \in M such that (M,(a_i)_{i< \eta },c) \equiv (M,(b_i)_{i< \eta },d). Here (M,(a_i)_{i< \eta }),(M,(b_i)_{i< \eta }) refers to M with its language expanded by a constant C_i for each i< \eta, such that C_i is interpreted as a_i, b_i respectively. (M,(a_i)_{i< \eta },c) and (M,(b_i)_{i< \eta },d) are further expansions, when the language is further expanded by a constant D that is interpreted as c or d respectively. Equivalently, M is \lambda-homogeneous if every partial elementary embedding \Phi :M \to M such that |dom \Phi |< \lambda extends to another partial elementary mapping of M to itself with a larger domain. The first definition follows Chang & Keisler, and the second follows Shelah. The two definitions are equivalent.

A model M is strongly \lambda-homogeneous, if for every partial elementary embedding \Phi :M \to M extends to an automorphism of M. Clearly, strongly \lambda-homogeneous implies \lambda-homogeneous.

A countable structure M is ultrahomogeneous, per Hodges, when every isomorphism between two finite substructures of M extends to a global automorphism. Also, ultrahomogeneous is strictly stronger than strongly \omega-homogeneous. For a strongly \omega-homogeneous structure that is not ultrahomogeneous, consider the disjoint union of a countable random graph and a countable triangle-free random graph. This structure is \omega-homogenous but not ultrahomogeneous.

A structure M is strongly \lambda-saturated if it is \lambda-saturated and strongly \lambda-homogeneous.

A model M is \lambda-Universal, per Chang & Keisler, when for every model N such that |N|< \lambda that is elementarily equivalent to M can elementarily embeds into M.

A model M is \lambda-Universal, per Shelah, when for every model N that is elementarily equivalent to M, and a set A \subseteq N such that |A| \leq \lambda, there is a partial elementary embedding f:M \to N such that dom(f)=A.

\lambda-universality per Shelah implies \lambda ^+-universality per Chang & Keisler. By the Lowenheim-Skolem Theorem, if the language |L| \leq \lambda, then \lambda-universality per Shelah and \lambda ^+-universality per Chang & Keisler are equivalent.

Per Shelah, a model M is < \lambda-universal if it is \mu-universal for all \mu < \lambda, and a model M simply said to be universal if it is |M|-universal.

A back-and-forth argument establishes that if \mathcal {M} has infinite cardinality, then \mathcal {M} is homogeneous if and only if \mathcal {M} is strongly homogeneous.

If \mathcal {M} and \mathcal {N} are each saturated, | \mathcal {M}|=| \mathcal {N}| and Th( \mathcal {M})=Th( \mathcal {N}) , then \mathcal {M} and \mathcal {N} are isomorphic.

Moreover, every partial elementary embedding f:M \to N extends to an isomorphism. Therefore, for every saturated model M, a subset A \subseteq M, and two elements x,y \in M of the same type over A, there is an automorphism of M fixing A pointwise and takes x to y. This is sometimes known as the Model-Theoretic Galois Theory.

If \mathcal {M} is \kappa-saturated, then \mathcal {M} is \kappa ^+-universal.

The following are equivalent, given a model M and a cardinal \lambda.

1: M is \lambda-saturated.

2: M is \lambda-universal and \lambda-homogeneous.

3: M is < \aleph _0-universal and \lambda-homogeneous.

Let I be any set. Then a filter \mathcal {F} on the power set \mathcal {P}(I) is a collection of subsets of I with the following properties:

1: I \in \mathcal {F}.

2: If A \in \mathcal {F} and A \subseteq B, then B \in \mathcal {F}.

3: If A,B \in \mathcal {F}, then we have A \cap B \in \mathcal {F}.

Furthermore, a filter is proper if \emptyset \notin \mathcal {F}.

Let I be any set. Then an ultrafilter \mathcal {U} on \mathcal {P}(I) is a proper filter on I with the additional property:

For every A \subseteq I, either A \in \mathcal {U} or I \backslash A \in \mathcal {U}.

Every proper filter can be extended into an ultrafilter.

Fix any i \in I. Then \mathcal {U}_i := \{ A \subseteq I: i \in A \} is an ultrafilter. This is referred to as the principal ultrafilter concentrated at i.

For any set I of infinite cardinality, the family of cofinite sets forms a proper filter. This filter is referred to as the Fréchet filter.

When extending the Fréchet filter to an ultrafilter, the result is not principal.

Fix an index set I and a language L. Let \{ \mathcal {A}_i: i \in I \} be a family of L-structures, and let \mathcal {U} be any ultrafilter on \mathcal {P}(I). Then the ultraproduct is the L-structure \mathcal {A}_* := \prod \limits _{i \in I} A_i / \mathcal {U}.

In \mathcal {A}_*, the elements of the universe of \mathcal {A}_* are functions \underline {a} with domain I and \underline {a}(i) \in A_i under the equivalence class \sim _{ \mathcal {U}}, where \underline {a} \sim _{ \mathcal {U}} \underline {b} \text { if and only if } \{ i \in I: \underline {a}(i)= \underline {b}(i) \} \in \mathcal {U}.

The constant symbols are interpreted by c^{ \mathcal {A}_*} := \prod \limits _{i \in I} c^{ \mathcal {A}_i} / \mathcal {U}.

The function symbols are interpreted by f^{ \mathcal {A}_i}( \underline {a}_1, \dots , \underline {a}_n) := \prod \limits _{i \in I} f^{ \mathcal {A}_i}( \underline {a}_1(i), \dots , \underline {a}_n(i)) / \mathcal {U} .

The relation symbols are interpreted by \mathcal {A}_* \models R^{ \mathcal {A}_*}( \underline {a}_1, \dots , \underline {a}_n) if and only if \{ i \in I: \mathcal {A}_i \models R^{ \mathcal {A}_i}( \underline {a}_1(i), \dots , \underline {a}_n(i)) \} \in \mathcal {U}.

Let \mathcal {A}_* = \prod \limits _{i \in I} \mathcal {A}_i / \mathcal {U} be an ultraproduct. Then for any L-formula \phi (x_1, \dots ,x_n), we have \mathcal {A}_* \models \phi ( \underline {a}_1, \dots , \underline {a}_n) \text { if and only if } \{ i \in I: A_i \models \phi ( \underline {a}_1(i), \dots , \underline {a}_n(i)) \} \in \mathcal {U}.

Let L be any language, and T be any L-theory. Then T is satisfiable if and only if every finite subset T_0 \subseteq T is satisfiable.

A Theory T in a first order language L is Model-Complete if every L-embedding between models of T is an elementary embedding.

Let T be a theory. Then the following are equivalent:

1. T is model complete.
2. For all models M \subseteq M' of T and all existential setnences \phi from L(M), then M' \vDash \phi \implies M \vDash \phi
3. Each formula is, modulo T, equivalent to a universal formula.

Proof:

• 1 \implies 2, Given that the definition of model complete implies that every embedding of models is an elementary emedding,then condition 2 above is actually true for all sentences, in particular existential sentences.
• 2 \implies 3, Given an existential formula \phi,
• 3 \implies 1

Given a cardinal \kappa and a language \mathcal {L}, an \mathcal {L}-theory is \kappa-categorical if whenever \mathcal {M} and \mathcal {N} are \mathcal {L}-structures with | \mathcal {M}|=| \mathcal {M}|= \kappa, then \mathcal {M} \cong \mathcal {N}.

Given a language, \mathcal {L}, and an \mathcal {L}-theory, T, the n'th Tarski-Lindenbaum algebra of T is the set of \mathcal {L}-formulas quotiented by the relation of T-equivalence.

For \aleph _0-categoricity, there are a number of useful characterisations. The following are due to Ryll-Nardjewski.

Given a language, \mathcal {L}, and an \mathcal {L}-theory T, the following are equivalent:

• T is \aleph _0-categorical.
• For every n \in \omega, there are finitely many \mathcal {L}-formulas in n-variables up to T-equivalence.
• For every n \in \omega, the n'th Tarski-Lindenbaum algebra of T is finite.
• Every type over T is isolated.
• For some/any countable model M of T, the automorphism group Aut(M) is oligomorphic, meaning that for each n, the action of Aut(M) on M^n has finitely mant orbits.
• For all n, S_n(T) is finite.

The dense linear order without endpoints (DLO) is a theory in the language \mathcal L= \{ < \} consisting of the following sentences.

• \forall x \, \neg x<x
• \forall x \forall y \, (x<y \rightarrow \neg (y<x))
• \forall x \forall y \forall z \, ((x<y \land y<z) \rightarrow x<z)
• \forall x \forall y \, (( \neg x=y) \rightarrow (x<y \lor y<x))
• \forall x \forall y \, x<y \rightarrow ( \exists z \, x<z \land z<y)
• \forall x \exists z \, z<x
• \forall x \exists z \, x<z

The set of rationals \mathbb Q with the usual ordering is a model of DLO, and DLO is \aleph _0-categorical, so every countable model is isomorphic to ( \mathbb Q,<). DLO is also a complete theory with quantifier elimination.

The theory of algebraically closed fields (ACF) is a theory in the language \mathcal L= \{ 0,1,+, \cdot \} consisting of the following sentences.

• \forall x \forall y \forall z \, (x+y)+z=x+(y+z).
• \forall x \, x+0=x \land0 +x=x.
• \forall x \exists y \, x+y=0 \land y+x=0.
• \forall x \forall y \, x+y=y+x.
• \forall x \forall y \forall z \, (x \cdot y) \cdot z=x \cdot (y+ \cdot z).
• \forall x \, x \cdot1 =x \land1 \cdot x=x.
• \forall x \exists y \, x \cdot y=1 \land y \cdot x=1.
• \forall x \forall y \, x+ \cdot y=y \cdot x.
• \forall x \forall y \forall z \, x \cdot (y+z)=(x \cdot y)+(x \cdot z).
• For each n \in \mathbb N, a sentence \forall y_1 \cdots \forall y_n \exists x \, (y_1 \cdot x)+ \cdots +(y_n \cdot x)=0.

The theory of algebraically closed fields of characteristic p (\text {ACF}_p) is ACF together with the sentence 1+ \cdots +1=0, where 1 is being added p times. \text {ACF}_p is a complete theory having quantifier elimination.

The theory of algebraically closed fields of characteristic 0 (\text {ACF}_0) is ACF together with the collection of sentences of the form \neg (1+ \cdots +1=0), for any number of 1s being added together. \text {ACF}_0 is also a complete theory having quantifier elimination.

The theory of vector spaces over a field F is a theory in the language \mathcal L= \{ 0,+,( \times _f)_{f \in F} \} consisting of the following sentences.

• \forall x \forall y \forall z \, (x+y)+z=x+(y+z).
• \forall x \, x+0=x \land0 +x=x.
• \forall x \exists y \, x+y=0 \land y+x=0.
• \forall x \forall y \, x+y=y+x.
• For each f,g \in F, the sentence \forall x \, \times _f( \times _g(x)) = \times _{fg}(x), where fg is the product of f and g in F.
• \forall x \, \times _1(x) = x where 1 is the multiplicative identity in F.
• For each f \in F, the sentence \forall x \forall y \, \times _f(x+y) = \times _f(x)+ \times _f(y).
• For each f,g \in F, the sentence \forall x \, \times _(f+g)(x) = \times _f(x)+ \times _g(x), where f+g is the sum of f and g in F.

The theory of an equivalence relation is a theory in the language \mathcal L= \{ E \}, where E is a binary relation, consisting of the following sentences.

• \forall x \, xEx.
• \forall x \forall y \, xEy \rightarrow yEx.
• \forall x \forall y \forall z \, (xEy \land yEz) \rightarrow xEz.

Being uncomplicated, this theory is usually shown as an initial example (or rather, counterexample) of various properties. It is straightforward to add more restrictions, such as stating that there are only n equivalence classes:

• \exists x_1 \cdots \exists x_n \forall y \, \bigvee _{i=1}^nx_iEy.

• \forall x \exists y_1 \cdots \exists y_k \forall z \, (x=z) \rightarrow \bigvee _{i=1}^ny_iEz.

• For each k, the sentence \forall x_1 \cdots \forall x_k \exists y \, \bigwedge _{i=1}^n \neg (x_iEy).

The theory of a graph is a theory in the language \mathcal L= \{ R \}, where R is a binary relation. Depending on the author, the theory may only demand symmetry, \forall x \forall y \, xRy \rightarrow yRx, or additionally include irreflexivity: \forall x \, \neg xRx.

The theory of the Rado graph (also called the random graph) is an extension of the theory of the graph by the extension axiom schema:

• For each n and m, the sentence \forall x_1 \cdots \forall x_n \forall y_1 \cdots \forall y_m \exists z \, \bigwedge _{i=1}^nzRx_i \land \bigwedge _{j=1}^m \neg zRy_j.

Given a language \mathcal {L}, a class K is defined to be a set of \mathcal {L}-structures

Often, we want there to be a relation \leq acting on the structures in K, and when we do, we write the class and relation as a pair (K, \leq )

Given a structure A in a language \mathcal {L}, the Age (pronounced ah-zh) of A is \{ B \subseteq A: B \text { is finitely generated } \}

The age of a structure is itself a class, often under the relation of substructure

Given a class and relation (K, \leq ), we say that K has the Amalgamation Property if for every A,B,C \in K, if there exists an embedding f:A \rightarrow B such that f(A) \leq B and and embedding g:A \rightarrow C such that A \leq B, then there exists a structure D and embeddings h_1:C \rightarrow D and h_2:B \rightarrow D such that h_1(C) \leq D and h_2(B) \leq D and h_2(f(A)) = h_1(g(A))

Given a class and relation (K, \leq ), we say that K has the Amalgamation Property if for every A,B \in K, there exists a structure D and embeddings h_1:C \rightarrow D and h_2:B \rightarrow D such that h_1(C) \leq D and h_2(B) \leq D

Amalgamation Property does NOT necessarily imply JEP, unless the empty set \emptyset is in K and for all A \in K, we have that \emptyset \leq A

A class (K, \leq ) has the hereditary property if for every A \in K, and any B \subseteq A finitely generated, then there is some C \in K such that C \cong B

If \mathcal {L} is countable, and (K, \subset ) a class of finitely generated structures has the amalgamation property, the joint embedding property, and the hereditary property, Then there is a unique, countable structure \mathcal {M} whose age is K with the property that any isomorphism f:A \rightarrow B with A,B \subseteq \mathcal {M} and A,B \in K extends to an automorphism of \mathcal {M}.

The structure \mathcal {M} is the Fraisse limit of K.

We call a class (K, \subseteq ) satisfying AP, HP, and JEP a Fraisse class

When a structure has the above isomorphism extension property, we say it is ultrahomogeneous (or homogeneous). The converse of Fraisse's Theorem is also true in the sense that if we have a structure which is ultrahomogeneous with respect to its age, then its age is a Fraisse class.

If M is the Fraisse Limit of a class (K, \leq ), then Th(M) has quantifier elimination and is \omega-categorical

Rado's famous random graph is indeed the Fraisse Limit of the class of finite graphs in the language \mathcal {L} = \{ E \} where E is a binary relation representing "there is an edge" between two points.

More precisely, a graph is an \mathcal {L}-structure for which E is anti-reflexive and symmetric.

The Dense Linear Order ( \mathbb {Q}, \leq ) is the Fraisse Limit of the class of all finite linear orders

Given a class and relation (K, \leq ), we say that K has the Disjoint Amalgamation Property if for every A,B,C \in K such that B \cap C =A, if there exists an embedding f:A \rightarrow B such that f(A) \leq B and and embedding g:A \rightarrow C such that A \leq B, then there exists a structure D and embeddings h_1:C \rightarrow D and h_2:B \rightarrow D such that h_1(C) \leq D and h_2(B) \leq D, h_2(f(A)) = h_1(g(A)), and h_2(C) \cap h_1(B) = h_1(A)

An example of a class which has the dAP is the Fraisse class of finite graphs

An example of a smooth class which does not have the dAP is The class of initial segments

For structures A,B, let \binom {B}{A} = \{ A_0: A_0 \leq B & ; A_0 \cong B \}

Given a class and relation (K, \leq ), we say that K has the Ramsey property on substructures if for every A \leq B \in K, there is some C \in K with B \leq C such that for every k-coloring c: \binom {C}{A} \rightarrow k, there is some B' \in \binom {C}{B} with c|_{ \binom {B'}{A}} constant.

Ramsey classes are highly related to descriptive set theory, in particular, extremely amenable sets.

Take care not to mix up RPS and RPE

We define different Ramsey properties on classes.

We assume the language \mathcal {L} is countable and only relational.

A class (K, \leq ) of finite \mathcal {L}-structures (closed under isomorphism) is called a smooth class if \leq is transitive, A \leq B \Rightarrow A \subsetq B, and for each A \in K, there is a set of universal formulas \Phi _A such that: A \leq B \Leftrightarrow B \models \Phi _A(A) and we require that A \cong A' \Leftrightarrow \Phi _A = \Phi _{A'}

This definition comes from On Generic structures

An alternative definition, or characterization, from Baldwin and Shi, is a class that satisfies the following:

If A \in K, A \leq A

If A \leq B, then A \subseteq B

\leq is transitive

If A \leq C, and A \subseteq B \subseteq C, then A \leq B for A,B,C \in K

\emptyset \in K and \emptyset \leq A for all A \in K

The only difference between these two characterizations is that in the first definition, we essentially stipulate that \leq is definable/determined by a set of universal formulas. This turns out to be an advantage in working with these classes. Certainly, classes satisfying the first definition will satisfy Baldwin-Shi's. In this way, it is perhaps wiser to regard the second definition as a characterization as opposed to an actual definition.

Let (K, \leq _*) be the class of be finite, initial segements of the linear order ( \omega , \leq ), where A \leq _* B is "A is an initial segment of B".

It is clear that \leq fits into the definition of a smooth class, simply by the universal formula \Phi _A(y_1, \dots , y_n) = \forall x(( x=y_1 \lor \dots \lor x=y_n) \lor \bigwedge _i^n x \geq y_i)

This class has AP and JEP, but not HP or dAP

If \mathcal {L} is countable, and (K, \leq ) is a smooth class of finite structures has the amalgamation property and the joint embedding property, then there is a unique, countable structure \mathcal {M} with the following properties:

1. Any isomorphism f:A \rightarrow B with A,B \leq \mathcal {M} and A,B \in K extends to an automorphism of \mathcal {M}.

2. \mathcal {M} = \bigcup ^ \omega _n A_n where A_n \leq A_{n+1} and for all n, A_n \in K

3. For every A \in K, there is an embedding f:A \rightarrow M of A into M such that f(A) \leq M

The structure \mathcal {M} is the generic, or sometimes, the limit of K.

An equivalent characterization of a generic is properties 2 and 3 and the following property:

4. If A \leq M and A \leq B for B \in K, then there is an isomorphism f: B \rightarrow M extending the identity map id: A \rightarrow M such that f(B) \leq M

The following theorem first appears in this paper by Laskowski and Kueker

Let (K, \leq ) be a smooth class with a generic \mathcal {A}. If \mathcal {A} is weakly saturated, then \mathcal {A} is indeed saturated

Let (K, \leq ) be a smooth class with a generic \mathcal {A}. If for every A \in K, \Phi _A (see here) consists of a single universal formula, then \mathcal {A} is an atomic model.

Given a cardinal \kappa, the sequence of n-tuples of elements in a model M, \{ \overline {b_i} \} _{i< \kappa } is an indiscernibles sequence in M over A \subseteq M means that: for any k< \omega and indices i_1,...,i_k and j_1,...,j_k, and any formula \varphi ( \overline {x_1},..., \overline {x_k}, \overline {a}) where \overline {a} is a tuple of parameters from A, we have M \models \varphi ( \overline {b_{i_1}},..., \overline {b_{i_k}}, \overline {a}) \leftrightarrow \varphi ( \overline {b_{j_1}},..., \overline {b_{j_k}}, \overline {a}). In other words, any two finite subsequence of \{ \overline {b_i} \} _{i< \kappa } of the same length have the same type over A, i.e, tp(( \overline {b_{i_1}},..., \overline {b_{i_k}})/A)=tp(( \overline {b_{j_1}},..., \overline {b_{j_k}})/A). Notice that the above definition, the index of the sequence, i.e. the ordinal \omega, can be substituted by any other ordinal, or just any linear order. This would define another kind of "indiscernible seuqnece," but we still refer to it with the same term. A set of n-tuples is an Indiscernible set if it is an indiscernible sequence under any well-order over the set.

Forking and Dividing

The formula \varphi (x;y) has the independence property if there are sequences of tuples (a_i : i \in \omega ) and (b_S : S \subseteq \omega ) such that for every subset S \subseteq \omega i \in S \Longleftrightarrow \mathbb {M} \models \varphi (a_i; b_S).

The formula \varphi (x;y) is said to be NIP if it does not have the independence property.

The following conditions are equivalent:

1. The formula \varphi (x;y) has the independence property.
2. The formula \varphi ^{ \vee }(y;x) has the independence property, where \varphi ^{ \vee }(y;x) is the formula \varphi (x;y) with the opposite partition.
3. For any two finite sets U and V, and any subset R \subseteq U \times V, there are (a_i : i \in U) and (b_j : j \in U) such that \mathbb \models \varphi (a_i;b_j) \Longleftrightarrow (i,j) \in R.
4. There is an indiscernible sequence (a_i : i \in \omega ) and some b such that \mathbb M \models \varphi (a_i;b) \Longleftrightarrow i is even.

We are also interested in the following characterization, which is more amenable to computations.

A model M has elimination of imaginaries, when given a formula \theta ( \bar {x}, \bar {y}) where l( \bar {x})=l( \bar {y})=n that defines an equivalence relation on M^n, for every equivalence class \bar {a}/ \theta represented by \bar {a}, there is a formula \phi, such that the equivalence class \bar {a}/ \theta is defined by \phi ( \bar {x}, \bar {b}), where \bar {b} is unique given \phi and \bar {a}/ \theta. A theory T is said to have elimination of imaginaries, if every model M of T has elimination of imaginaries.

A model M has uniform elimination of imaginaries, if, in addition to having elimination of imaginaries, the formula \phi is independent of \bar {a} and is dependent only on \theta. Equivalently, we can say $M$ has uniform elimination of imaginaries if there is a $0$-definable function f, such that f( \bar {a})= \bar {b} where \bar {b} is the unique tuple that defines \bar {a}/ \theta.

A model M has weak elimination of imaginaries, when given a formula \theta ( \bar {x}, \bar {y}) where l( \bar {x})=l( \bar {y})=n that defines an equivalence relation on M^n, for every equivalence class \bar {a}/ \theta, there is a formula \phi, and a finite set of tuples X in M such that the equivalence class \bar {a}/ \theta is defined by \phi ( \bar {x}, \bar {b}) if and only if \bar {b} \in X. A theory T is said to have weak elimination of imaginaries, if every model M of T has weak elimination of imaginaries.

Let L be any language. Then a monadic expansion of L is a language L':= L \cup \{ R_i \} _{i \in I}, where \{ R_i \} _{i \in I} is a collection of unary relation symbols.

Let M be an L-structure. Then M is monadically NFCP if it is NFCP under every monadic expansion of L.

Let X be a non-empty set and l \geq1. Then a subset C \subseteq X^l is mutually algebraic if there exists some K such that for all a \in X, we have | \{ \overline {c} \in C: a \in \overline {c} \} | \leq K.

For l=2, if C \subseteq X^2 is a set of mated pairs, i.e. every element in X has a unique "mate," which is symmetric, then C is mutually algebraic.

Suppose M is an L-structure and \phi ( \overline {z}) is an L(M) definable set. Then \phi is a mutually algebraic formula if D= \phi ( \overline {z}) is a mutually algebraic subset of M^{lg( \overline {z})}.