Theorem of Łoś

The Łoś theorem , named after the Polish mathematician Jerzy Łoś , is a sentence from model theory from 1955, which allows an alternative approach to the compactness theorem . The existence of models of certain mathematical structures is attributed to the existence of ultrafilters .

Concept formation

Boolean expansion

Let it be a given signature, that is, a set of non-logical symbols, such as for describing rings or bodies . Next, let us be a non-empty family of - structures and their Cartesian product , which we want to denote in the following for short . ${\displaystyle S}$ ${\displaystyle S=\{0,1,+,\cdot \}}$ ${\displaystyle (M_{i})_{i\in I}}$ ${\displaystyle S}$ ${\displaystyle \prod _{i\in I}M_{i}}$ ${\displaystyle M}$

Let further be a formula of the language of first-order predicate logic , the free variables of which can be found under the . For each tuple there is a statement that may or may not apply to, that is, for them or not. one reads as is a model of . This not very clean but common notation is intended to indicate that the elements take the place of the free variables with the same index and thus form a statement in the model . ${\displaystyle \varphi =\varphi (x_{1},\ldots ,x_{n})}$ ${\displaystyle L_{I}^{S}}$ ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle (a_{1}(i),\ldots ,a_{n}(i))\in M_{i}^{n}}$ ${\displaystyle \varphi (a_{1}(i),\ldots ,a_{n}(i))}$ ${\displaystyle M_{i}}$ ${\displaystyle M_{i}\vDash \varphi (a_{1}(i),\ldots ,a_{n}(i))}$ ${\displaystyle M_{i}\vDash \varphi (a_{1}(i),\ldots ,a_{n}(i))}$ ${\displaystyle M_{i}}$ ${\displaystyle \varphi (a_{1}(i),\ldots ,a_{n}(i))}$ ${\displaystyle \varphi (a_{1}(i),\ldots ,a_{n}(i))}$ ${\displaystyle a_{1}(i),\ldots ,a_{n}(i)\in M_{i}}$ ${\displaystyle M_{i}}$

We now consider a tuple and are interested in the set of all indices for which is a model of . We therefore define ${\displaystyle \varphi =\varphi (x_{1},\ldots ,x_{n})}$ ${\displaystyle (a_{1},\ldots a_{n}):I\rightarrow M^{n}}$ ${\displaystyle M_{i}}$ ${\displaystyle \varphi (a_{1}(i),\ldots ,a_{n}(i))}$

${\displaystyle \|\varphi (a_{1},\ldots ,a_{n})\|\,:=\,\{i\in I;\,M_{i}\vDash \varphi (a_{1}(i),\ldots ,a_{n}(i))\}}$

and call this set the Boolean expansion of . ${\displaystyle \varphi (a_{1},\ldots ,a_{n})}$

Reduced products

In addition to the situation described above, we now consider a filter on the index set and define it ${\displaystyle F}$ ${\displaystyle I}$

${\displaystyle a\cong _{F}b\quad \Leftrightarrow \quad \{i\in I;\,a(i)=b(i)\}\in F}$

for . This set is nothing more than the Boolean expansion of the formula applied to the two-tuple . ${\displaystyle a,b\in M}$ ${\displaystyle \|(x_{1}=x_{2})(a,b)\|}$ ${\displaystyle (x_{1}=x_{2})}$ ${\displaystyle (a,b):I\rightarrow M^{2}}$

The properties of a filter show that this defines an equivalence relation on the Cartesian product of . The amount of factors after this equivalence relation is called the reduced product of the filter and is denoted by. ${\displaystyle M_{i}}$ ${\displaystyle F}$ ${\displaystyle M/F}$

The reduced product also becomes a structure through the following determinations, the well-definedness of which must be shown : ${\displaystyle S}$

• ${\displaystyle c^{M/F}:=(c^{M_{i}})_{i\in I}/F}$for each constant symbol . ${\displaystyle c\in S}$

• ${\displaystyle f^{M/F}(a_{1}/F,\ldots ,a_{n}/F):=(f^{M_{i}}(a_{1}(i),\ldots ,a_{n}(i)))_{i\in I}/F}$for each n-digit function symbol . ${\displaystyle f\in S}$

• ${\displaystyle R^{M/F}(a_{1}/F,\ldots ,a_{n}/F)}$if and only if for every n-place relation symbol . ${\displaystyle \{i\in I;R^{M_{i}}(a_{1}(i),\ldots ,a_{n}(i))\}\in F}$ ${\displaystyle R\in S}$

If there is an ultrafilter in particular , that is to say at most under all filters , the ultra product is called the ultrafilter . ${\displaystyle F}$ ${\displaystyle I}$ ${\displaystyle M/F}$ ${\displaystyle M_{i}}$ ${\displaystyle F}$

Formulation of the sentence

The Łoś theorem provides a criterion for the validity of formulas in ultra products:

Let it be a non-empty family of structures and an ultrafilter . Then applies ${\displaystyle (M_{i})_{i\in I}}$ ${\displaystyle S}$ ${\displaystyle U}$ ${\displaystyle I}$

${\displaystyle \prod _{i\in I}M_{i}/U\vDash \varphi (a_{1}/U,\ldots ,a_{n}/U)}$ exactly when ${\displaystyle \|\varphi (a_{1},\ldots ,a_{n})\|\in U}$

for all formulas from and all tuples . ${\displaystyle \varphi =\varphi (x_{1},\ldots ,x_{n})}$ ${\displaystyle L_{I}^{S}}$ ${\displaystyle (a_{1},\ldots ,a_{n}):I\rightarrow (\prod _{i\in I}M_{i})^{n}}$

Applications

Typical applications of the Łoś theorem are presented using two examples.

Compactness theorem

For the compactness theorem it has to be shown that a set of sets already has a model if a model can be found for every finite subset of . In order to apply Łoś's theorem, one considers the set of all finite subsets of and for each a presupposed model of as the index set . The supersets of the finite averages of the sets form a filter that is contained in an ultrafilter . From the Łoś theorem it follows easily that a model is for . ${\displaystyle \Phi }$ ${\displaystyle L_{I}^{S}}$ ${\displaystyle \Phi }$ ${\displaystyle I}$ ${\displaystyle \Phi }$ ${\displaystyle i\in I}$ ${\displaystyle M_{i}}$ ${\displaystyle i}$ ${\displaystyle \{j\in I;i\subset j\}}$ ${\displaystyle U}$ ${\displaystyle \prod _{i\in I}M_{i}/U}$ ${\displaystyle \Phi }$

This proof has the advantage over Gödel's proof that the use of the syntactic derivability concept (see first-order predicate logic ) and the completeness theorem can be dispensed with. This procedure is consistently carried out in the textbook given below by Philipp Rothmaler.

Ring theory

• Let it be a sentence of the language with which applies to all rings of characteristic 0. Then the theorem is already valid in rings with a sufficiently high characteristic. ${\displaystyle \varphi }$ ${\displaystyle L_{I}^{S}}$ ${\displaystyle S=\{0,1,+,\cdot \}}$

Assuming for the purposes of an opposition evidence that it rings , arbitrarily high characteristics are, for which the rate does not apply, without limitation , we consider an ultrafilter in which the Fréchet filter comprises. Sentences of the form are wrong in almost all of them because of the ascending characteristics and, according to the Łoś theorem, therefore also in the ultra product , that is, the latter is a ring with the characteristic 0. According to the assumption, therefore, in the ultra product and with a renewed application of the Łoś theorem, is Set of all indices for which the sentence in is correct, contained in the ultrafilter, that is, contrary to the assumption of some, even of infinitely many, it must be satisfied. This contradiction ends the proof. ${\displaystyle M_{i}}$ ${\displaystyle i\in \mathbb {N} }$ ${\displaystyle m_{i}}$ ${\displaystyle \varphi }$ ${\displaystyle m_{1}<m_{2}<m_{3}<\ldots }$ ${\displaystyle U}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle 1+\ldots +1=0}$ ${\displaystyle M_{i}}$ ${\displaystyle \prod M_{i}/U}$ ${\displaystyle \varphi }$ ${\displaystyle M_{i}}$ ${\displaystyle M_{i}}$

Individual evidence

1. ↑ J. Łoś: Quelques remarques, théorèmes et Genealogie sur les classes définissables d'algèbres , Mathematical interpretation of formal systems, editors LEJ Brower et al., Amsterdam 1955, pp. 98-113
2. ↑ Philipp Rothmaler: Introduction to Model Theory , Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5 , Chapter 4.1
3. ^ Thomas Jech : Set Theory , Springer-Verlag (2003), ISBN 3-540-44085-2 , Theorem 12.3
4. ↑ Philipp Rothmaler: Introduction to the model theory , Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5 , sentence 4.2.1
5. ↑ Philipp Rothmaler: Introduction to the model theory , Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5 , sentence 4.3.2
6. ^ Louis H. Rowen: Ring Theory I , Academic Press Inc. (1988), ISBN 0-12-599841-4