Leopold Löwenheim [ˈle:o:pɔl̩d ˈlø:vɛnhaɪm] (26 June 1878 in Krefeld – 5 May 1957 in Berlin ) was a German mathematician doing work in mathematical logic . The Nazi regime forced him to retire because under the Nuremberg Laws he was considered only three quarters Aryan . In 1943 much of his work was destroyed during a bombing raid on Berlin. Nevertheless, he survived the Second World War , after which he resumed teaching mathematics .
66-507: Löwenheim (1915) gave the first proof of what is now known as the Löwenheim–Skolem theorem , often considered the starting point for model theory . Leopold was the son of Ludwig Löwenheim, a mathematics teacher at the polytechnic in Krefeld and Elizabeth Röhn, a writer. In 1881 the three of them left Krefeld first for Naples and then Berlin where Ludwig was a private scholar working on
132-489: A 1 , … , a n {\displaystyle a_{1},\dots ,a_{n}} to b 1 , … , b n {\displaystyle b_{1},\dots ,b_{n}} respectively, then a 1 , … , a n {\displaystyle a_{1},\dots ,a_{n}} and b 1 , … , b n {\displaystyle b_{1},\dots ,b_{n}} realise
198-416: A 1 , … , a n {\displaystyle a_{1},\dots ,a_{n}} . This is called the complete (n-)type realised by a 1 , … , a n {\displaystyle a_{1},\dots ,a_{n}} over A . If there is an automorphism of M {\displaystyle {\mathcal {M}}} that is constant on A and sends
264-480: A 2 {\displaystyle a_{1}=a_{2}} or a 2 < a 1 {\displaystyle a_{2}<a_{1}} . Over the subset Z ⊆ R {\displaystyle \mathbb {Z} \subseteq \mathbb {R} } of integers, the 1-type of a non-integer real number a depends on its value rounded down to the nearest integer. More generally, whenever M {\displaystyle {\mathcal {M}}}
330-480: A n {\displaystyle a_{1},\dots ,a_{n}} of a structure M {\displaystyle {\mathcal {M}}} and a subset A of M {\displaystyle {\mathcal {M}}} , one can consider the set of all first-order formulas φ ( x 1 , … , x n ) {\displaystyle \varphi (x_{1},\dots ,x_{n})} with parameters in A that are satisfied by
396-408: A ) {\displaystyle \varphi (a)} is true. In this way, one can study definable groups and fields in general structures, for instance, which has been important in geometric stability theory. One can even go one step further, and move beyond immediate substructures. Given a mathematical structure, there are very often associated structures which can be constructed as a quotient of part of
462-406: A and b are connected by the order automorphism that shifts all numbers by b-a . The complete 2-type over the empty set realised by a pair of numbers a 1 , a 2 {\displaystyle a_{1},a_{2}} depends on their order: either a 1 < a 2 {\displaystyle a_{1}<a_{2}} , a 1 =
528-426: A formal language expressing statements about a mathematical structure ), and their models (those structures in which the statements of the theory hold). The aspects investigated include the number and size of models of a theory, the relationship of different models to each other, and their interaction with the formal language itself. In particular, model theorists also investigate the sets that can be defined in
594-468: A certain type over A is called type-definable over A . For an algebraic example, suppose M {\displaystyle M} is an algebraically closed field . The theory has quantifier elimination . This allows us to show that a type is determined exactly by the polynomial equations it contains. Thus the set of complete n {\displaystyle n} -types over a subfield A {\displaystyle A} corresponds to
660-435: A comprehensive account of the influence of Democritus on modern science. Although he hoped this would gain him a teaching job at Humboldt University Ludwig died in 1894. This article about a German mathematician is a stub . You can help Misplaced Pages by expanding it . Model theory In mathematical logic , model theory is the study of the relationship between formal theories (a collection of sentences in
726-399: A curve. In general, definable sets without quantifiers are easy to describe, while definable sets involving possibly nested quantifiers can be much more complicated. This makes quantifier elimination a crucial tool for analysing definable sets: A theory T has quantifier elimination if every first-order formula φ( x 1 , ..., x n ) over its signature is equivalent modulo T to
SECTION 10
#1732891845046792-510: A first-order formula ψ( x 1 , ..., x n ) without quantifiers, i.e. ∀ x 1 … ∀ x n ( ϕ ( x 1 , … , x n ) ↔ ψ ( x 1 , … , x n ) ) {\displaystyle \forall x_{1}\dots \forall x_{n}(\phi (x_{1},\dots ,x_{n})\leftrightarrow \psi (x_{1},\dots ,x_{n}))} holds in all models of T . If
858-452: A formula of the following form: where ψ is quantifier free. A theory that is not model-complete may have a model completion , which is a related model-complete theory that is not, in general, an extension of the original theory. A more general notion is that of a model companion . In every structure, every finite subset { a 1 , … , a n } {\displaystyle \{a_{1},\dots ,a_{n}\}}
924-443: A model fluctuated in the history of the subject, and the two directions are summarised by the pithy characterisations from 1973 and 1997 respectively: where universal algebra stands for mathematical structures and logic for logical theories; and where logical formulas are to definable sets what equations are to varieties over a field. Nonetheless, the interplay of classes of models and the sets definable in them has been crucial to
990-484: A model of T which is itself a model of T is an elementary substructure. There is a useful criterion for testing whether a substructure is an elementary substructure, called the Tarski–Vaught test . It follows from this criterion that a theory T is model-complete if and only if every first-order formula φ( x 1 , ..., x n ) over its signature is equivalent modulo T to an existential first-order formula, i.e.
1056-399: A model of a theory, and the relationship of such definable sets to each other. As a separate discipline, model theory goes back to Alfred Tarski , who first used the term "Theory of Models" in publication in 1954. Since the 1970s, the subject has been shaped decisively by Saharon Shelah 's stability theory . Compared to other areas of mathematical logic such as proof theory , model theory
1122-1314: A set of symbols is commonly used to express logical representation. The following table lists many common symbols, together with their name, how they should be read out loud, and the related field of mathematics . Additionally, the subsequent columns contains an informal explanation, a short example, the Unicode location, the name for use in HTML documents, and the LaTeX symbol. ⇒ → ⊃ ⇔ ↔ ≡ ¬ ˜ ! ∧ · & ∨ + ∥ ⊕ ⊻ — ≢ ⊤ ⊥ ∀ ∃ ∃! ( ) 𝔻 ⊢ ⊨ — ⇔ ≡ — ⇔ ≔ = d e f {\displaystyle {\stackrel {\scriptscriptstyle \mathrm {def} }{=}}} \stackrel{ \scriptscriptstyle \mathrm{def}}{=} The following symbols are either advanced and context-sensitive or very rarely used: It may also denote
1188-424: A structure are the isolated types, then the structure is called atomic . On the other hand, no structure realises every type over every parameter set; if one takes all of M {\displaystyle {\mathcal {M}}} as the parameter set, then every 1-type over M {\displaystyle {\mathcal {M}}} realised in M {\displaystyle {\mathcal {M}}}
1254-445: A structure is also called the theory of that structure . It's a consequence of Gödel's completeness theorem (not to be confused with his incompleteness theorems ) that a theory has a model if and only if it is consistent , i.e. no contradiction is proved by the theory. Therefore, model theorists often use "consistent" as a synonym for "satisfiable". A signature or language is a set of non-logical symbols such that each symbol
1320-404: A theory does not have quantifier elimination, one can add additional symbols to its signature so that it does. Axiomatisability and quantifier elimination results for specific theories, especially in algebra, were among the early landmark results of model theory. But often instead of quantifier elimination a weaker property suffices: A theory T is called model-complete if every substructure of
1386-431: A σ'-theory, and one can extend it (in more than one way) to a complete σ'-theory. The terms reduct and expansion are sometimes applied to this relation as well. The compactness theorem states that a set of sentences S is satisfiable if every finite subset of S is satisfiable. The analogous statement with consistent instead of satisfiable is trivial, since every proof can have only a finite number of antecedents used in
SECTION 20
#17328918450461452-472: Is a 1-type over Z ⊆ R {\displaystyle \mathbb {Z} \subseteq \mathbb {R} } that is not realised in the real number line R {\displaystyle \mathbb {R} } . A subset of M n {\displaystyle {\mathcal {M}}^{n}} that can be expressed as exactly those elements of M n {\displaystyle {\mathcal {M}}^{n}} realising
1518-458: Is complete . The set of complete n -types over A is often written as S n M ( A ) {\displaystyle S_{n}^{\mathcal {M}}(A)} . If A is the empty set, then the type space only depends on the theory T {\displaystyle T} of M {\displaystyle {\mathcal {M}}} . The notation S n ( T ) {\displaystyle S_{n}(T)}
1584-452: Is syntactic in nature, in contrast to model theory, which is semantic in nature. The most prominent scholarly organization in the field of model theory is the Association for Symbolic Logic . This page focuses on finitary first order model theory of infinite structures. The relative emphasis placed on the class of models of a theory as opposed to the class of definable sets within
1650-559: Is a finite union of points and intervals. Particularly important are those definable sets that are also substructures, i. e. contain all constants and are closed under function application. For instance, one can study the definable subgroups of a certain group. However, there is no need to limit oneself to substructures in the same signature. Since formulas with n free variables define subsets of M n {\displaystyle {\mathcal {M}}^{n}} , n -ary relations can also be definable. Functions are definable if
1716-405: Is a map f : A → B between the domains which can be written as an isomorphism of A {\displaystyle {\mathcal {A}}} with a substructure of B {\displaystyle {\mathcal {B}}} . If it can be written as an isomorphism with an elementary substructure, it is called an elementary embedding. Every embedding is an injective homomorphism, but
1782-408: Is a model of a theory exactly when the superstructure is a model. Example: While the field of algebraic numbers Q ¯ {\displaystyle {\overline {\mathbb {Q} }}} is an elementary substructure of the field of complex numbers C {\displaystyle \mathbb {C} } , the rational field Q {\displaystyle \mathbb {Q} }
1848-456: Is a sentence and A {\displaystyle {\mathcal {A}}} an elementary substructure of B {\displaystyle {\mathcal {B}}} , then A ⊨ φ {\displaystyle {\mathcal {A}}\models \varphi } if and only if B ⊨ φ {\displaystyle {\mathcal {B}}\models \varphi } . Thus, an elementary substructure
1914-432: Is a structure and A a subset of M {\displaystyle {\mathcal {M}}} , a (partial) n-type over A is a set of formulas p with at most n free variables that are realised in an elementary extension N {\displaystyle {\mathcal {N}}} of M {\displaystyle {\mathcal {M}}} . If p contains every such formula or its negation, then p
1980-404: Is a structure that models T {\displaystyle T} . A substructure A {\displaystyle {\mathcal {A}}} of a σ-structure B {\displaystyle {\mathcal {B}}} is a subset of its domain, closed under all functions in its signature σ, which is regarded as a σ-structure by restricting all functions and relations in σ to
2046-419: Is a subset of Q 2 {\displaystyle \mathbb {Q} ^{2}} ), one obtains a structure ( Q , σ o r ) {\displaystyle (\mathbb {Q} ,\sigma _{or})} . A structure N {\displaystyle {\mathcal {N}}} is said to model a set of first-order sentences T {\displaystyle T} in
Leopold Löwenheim - Misplaced Pages Continue
2112-535: Is a unary (= 1-ary) function symbol, and < {\displaystyle <} is a binary relation symbol. Then, when these symbols are interpreted to correspond with their usual meaning on Q {\displaystyle \mathbb {Q} } (so that e.g. + {\displaystyle +} is a function from Q 2 {\displaystyle \mathbb {Q} ^{2}} to Q {\displaystyle \mathbb {Q} } and < {\displaystyle <}
2178-486: Is called isolated . Since the real numbers R {\displaystyle \mathbb {R} } are Archimedean , there is no real number larger than every integer. However, a compactness argument shows that there is an elementary extension of the real number line in which there is an element larger than any integer. Therefore, the set of formulas { n < x | n ∈ Z } {\displaystyle \{n<x|n\in \mathbb {Z} \}}
2244-497: Is called a (first-order) theory , which takes the sentences in the set as its axioms. A theory is satisfiable if it has a model M ⊨ T {\displaystyle {\mathcal {M}}\models T} , i.e. a structure (of the appropriate signature) which satisfies all the sentences in the set T {\displaystyle T} . A complete theory is a theory that contains every sentence or its negation. The complete theory of all sentences satisfied by
2310-506: Is commonly used for the set of types over the empty set consistent with T {\displaystyle T} . If there is a single formula φ {\displaystyle \varphi } such that the theory of M {\displaystyle {\mathcal {M}}} implies φ → ψ {\displaystyle \varphi \rightarrow \psi } for every formula ψ {\displaystyle \psi } in p , then p
2376-439: Is definable by a quantifier-free formula in one variable. Quantifier-free formulas in one variable express Boolean combinations of polynomial equations in one variable, and since a nontrivial polynomial equation in one variable has only a finite number of solutions, the theory of algebraically closed fields is strongly minimal. On the other hand, the field R {\displaystyle \mathbb {R} } of real numbers
2442-552: Is definable with parameters: Simply use the formula Since we can negate this formula, every cofinite subset (which includes all but finitely many elements of the domain) is also always definable. This leads to the concept of a minimal structure . A structure M {\displaystyle {\mathcal {M}}} is called minimal if every subset A ⊆ M {\displaystyle A\subseteq {\mathcal {M}}} definable with parameters from M {\displaystyle {\mathcal {M}}}
2508-451: Is either a constant symbol, or a function or relation symbol with a specified arity . Note that in some literature, constant symbols are considered as function symbols with zero arity, and hence are omitted. A structure is a set M {\displaystyle M} together with interpretations of each of the symbols of the signature as relations and functions on M {\displaystyle M} (not to be confused with
2574-501: Is either finite or cofinite. The corresponding concept at the level of theories is called strong minimality : A theory T is called strongly minimal if every model of T is minimal. A structure is called strongly minimal if the theory of that structure is strongly minimal. Equivalently, a structure is strongly minimal if every elementary extension is minimal. Since the theory of algebraically closed fields has quantifier elimination, every definable subset of an algebraically closed field
2640-419: Is isolated by a formula of the form a = x for an a ∈ M {\displaystyle a\in {\mathcal {M}}} . However, any proper elementary extension of M {\displaystyle {\mathcal {M}}} contains an element that is not in M {\displaystyle {\mathcal {M}}} . Therefore, a weaker notion has been introduced that captures
2706-479: Is not minimal: Consider, for instance, the definable set This defines the subset of non-negative real numbers, which is neither finite nor cofinite. One can in fact use φ {\displaystyle \varphi } to define arbitrary intervals on the real number line. It turns out that these suffice to represent every definable subset of R {\displaystyle \mathbb {R} } . This generalisation of minimality has been very useful in
Leopold Löwenheim - Misplaced Pages Continue
2772-413: Is not, as we can express "There is a square root of 2" as a first-order sentence satisfied by C {\displaystyle \mathbb {C} } but not by Q {\displaystyle \mathbb {Q} } . An embedding of a σ-structure A {\displaystyle {\mathcal {A}}} into another σ-structure B {\displaystyle {\mathcal {B}}}
2838-454: Is often less concerned with formal rigour and closer in spirit to classical mathematics. This has prompted the comment that "if proof theory is about the sacred, then model theory is about the profane" . The applications of model theory to algebraic and Diophantine geometry reflect this proximity to classical mathematics, as they often involve an integration of algebraic and model-theoretic results and techniques. Consequently, proof theory
2904-573: Is the Löwenheim-Skolem theorem . According to the Löwenheim-Skolem Theorem, every infinite structure in a countable signature has a countable elementary substructure. Conversely, for any infinite cardinal κ every infinite structure in a countable signature that is of cardinality less than κ can be elementarily embedded in another structure of cardinality κ (There is a straightforward generalisation to uncountable signatures). In particular,
2970-448: The Boolean connectives ¬ , ∧ , ∨ , → {\displaystyle \neg ,\land ,\lor ,\rightarrow } and prefixing of quantifiers ∀ v {\displaystyle \forall v} or ∃ v {\displaystyle \exists v} . A sentence is a formula in which each occurrence of a variable is in
3036-422: The rational numbers , regarded as a structure in the signature {+,0} can be expanded to a field with the signature {×,+,1,0} or to an ordered group with the signature {+,0,<}. Similarly, if σ' is a signature that extends another signature σ, then a complete σ'-theory can be restricted to σ by intersecting the set of its sentences with the set of σ-formulas. Conversely, a complete σ-theory can be regarded as
3102-541: The Löwenheim-Skolem Theorem implies that any theory in a countable signature with infinite models has a countable model as well as arbitrarily large models. In a certain sense made precise by Lindström's theorem , first-order logic is the most expressive logic for which both the Löwenheim–Skolem theorem and the compactness theorem hold. In model theory, definable sets are important objects of study. For instance, in N {\displaystyle \mathbb {N} }
3168-405: The converse holds only if the signature contains no relation symbols, such as in groups or fields. A field or a vector space can be regarded as a (commutative) group by simply ignoring some of its structure. The corresponding notion in model theory is that of a reduct of a structure to a subset of the original signature. The opposite relation is called an expansion - e.g. the (additive) group of
3234-446: The definitions mentioned here are parameter-free , that is, the defining formulas don't mention any fixed domain elements. However, one can also consider definitions with parameters from the model . For instance, in R {\displaystyle \mathbb {R} } , the formula uses the parameter π {\displaystyle \pi } from R {\displaystyle \mathbb {R} } to define
3300-526: The development of model theory throughout its history. For instance, while stability was originally introduced to classify theories by their numbers of models in a given cardinality , stability theory proved crucial to understanding the geometry of definable sets. A first-order formula is built out of atomic formulas such as R ( f ( x , y ) , z ) {\displaystyle R(f(x,y),z)} or y = x + 1 {\displaystyle y=x+1} by means of
3366-440: The equality symbol has a double meaning here.) It is intuitively clear how to translate such formulas into mathematical meaning. In the semiring of natural numbers N {\displaystyle {\mathcal {N}}} , viewed as a structure with binary functions for addition and multiplication and constants for 0 and 1 of the natural numbers, for example, an element n {\displaystyle n} satisfies
SECTION 50
#17328918450463432-679: The formal notion of an " interpretation " of one structure in another). Example: A common signature for ordered rings is σ o r = ( 0 , 1 , + , × , − , < ) {\displaystyle \sigma _{or}=(0,1,+,\times ,-,<)} , where 0 {\displaystyle 0} and 1 {\displaystyle 1} are 0-ary function symbols (also known as constant symbols), + {\displaystyle +} and × {\displaystyle \times } are binary (= 2-ary) function symbols, − {\displaystyle -}
3498-530: The formula φ {\displaystyle \varphi } if and only if n {\displaystyle n} is a prime number. The formula ψ {\displaystyle \psi } similarly defines irreducibility . Tarski gave a rigorous definition, sometimes called "Tarski's definition of truth" , for the satisfaction relation ⊨ {\displaystyle \models } , so that one easily proves: A set T {\displaystyle T} of sentences
3564-490: The formula defines the subset of prime numbers, while the formula defines the subset of even numbers. In a similar way, formulas with n free variables define subsets of M n {\displaystyle {\mathcal {M}}^{n}} . For example, in a field, the formula defines the curve of all ( x , y ) {\displaystyle (x,y)} such that y = x 2 {\displaystyle y=x^{2}} . Both of
3630-403: The function graph is a definable relation, and constants a ∈ M {\displaystyle a\in {\mathcal {M}}} are definable if there is a formula φ ( x ) {\displaystyle \varphi (x)} such that a is the only element of M {\displaystyle {\mathcal {M}}} such that φ (
3696-464: The given language if each sentence in T {\displaystyle T} is true in N {\displaystyle {\mathcal {N}}} with respect to the interpretation of the signature previously specified for N {\displaystyle {\mathcal {N}}} . (Again, not to be confused with the formal notion of an " interpretation " of one structure in another) A model of T {\displaystyle T}
3762-409: The idea of a structure realising all types it could be expected to realise. A structure is called saturated if it realises every type over a parameter set A ⊂ M {\displaystyle A\subset {\mathcal {M}}} that is of smaller cardinality than M {\displaystyle {\mathcal {M}}} itself. Table of logic symbols In logic ,
3828-396: The interpreted structures to the language of the original structure. Thus one can show that if a structure M {\displaystyle {\mathcal {M}}} interprets another whose theory is undecidable, then M {\displaystyle {\mathcal {M}}} itself is undecidable. For a sequence of elements a 1 , … ,
3894-425: The model theory of ordered structures. A densely totally ordered structure M {\displaystyle {\mathcal {M}}} in a signature including a symbol for the order relation is called o-minimal if every subset A ⊆ M {\displaystyle A\subseteq {\mathcal {M}}} definable with parameters from M {\displaystyle {\mathcal {M}}}
3960-409: The original structure via an equivalence relation. An important example is a quotient group of a group. One might say that to understand the full structure one must understand these quotients. When the equivalence relation is definable, we can give the previous sentence a precise meaning. We say that these structures are interpretable . A key fact is that one can translate sentences from the language of
4026-475: The proof. The completeness theorem allows us to transfer this to satisfiability. However, there are also several direct (semantic) proofs of the compactness theorem. As a corollary (i.e., its contrapositive), the compactness theorem says that every unsatisfiable first-order theory has a finite unsatisfiable subset. This theorem is of central importance in model theory, where the words "by compactness" are commonplace. Another cornerstone of first-order model theory
SECTION 60
#17328918450464092-410: The same complete type over A . The real number line R {\displaystyle \mathbb {R} } , viewed as a structure with only the order relation {<}, will serve as a running example in this section. Every element a ∈ R {\displaystyle a\in \mathbb {R} } satisfies the same 1-type over the empty set. This is clear since any two real numbers
4158-534: The scope of a corresponding quantifier. Examples for formulas are φ {\displaystyle \varphi } (or φ ( x ) {\displaystyle \varphi (x)} to indicate x {\displaystyle x} is the unbound variable in φ {\displaystyle \varphi } ) and ψ {\displaystyle \psi } (or ψ ( x ) {\displaystyle \psi (x)} ), defined as follows: (Note that
4224-408: The set of prime ideals of the polynomial ring A [ x 1 , … , x n ] {\displaystyle A[x_{1},\ldots ,x_{n}]} , and the type-definable sets are exactly the affine varieties. While not every type is realised in every structure, every structure realises its isolated types. If the only types over the empty set that are realised in
4290-482: The subset. This generalises the analogous concepts from algebra; for instance, a subgroup is a substructure in the signature with multiplication and inverse. A substructure is said to be elementary if for any first-order formula φ {\displaystyle \varphi } and any elements a 1 , ..., a n of A {\displaystyle {\mathcal {A}}} , In particular, if φ {\displaystyle \varphi }
4356-451: The theory of a structure has quantifier elimination, every set definable in a structure is definable by a quantifier-free formula over the same parameters as the original definition. For example, the theory of algebraically closed fields in the signature σ ring = (×,+,−,0,1) has quantifier elimination. This means that in an algebraically closed field, every formula is equivalent to a Boolean combination of equations between polynomials. If
#45954