View source for Non-classical theory of models

''non-classical model theory''

A theory of models (cf. [[Model theory|Model theory]]) that differs from the classical theory in the sense that either the relevant [[Formal language|formal language]] is not the first-order language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n0669701.png" />, or the logic on which it is based is not the classical (two-valued) logic. In what follows, unless otherwise stated, the logic is assumed to be two-valued.

In the theory of models of a language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n0669702.png" /> the most important problems are the following.

a) The axiomatizability of the set of identically true formulas. If there is an effective enumeration of the formulas of the language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n0669703.png" /> by natural numbers, the problem becomes more precise: Is the set of numbers of the identically true formulas recursively enumerable?

b) A language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n0669704.png" /> is called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n0669706.png" />-compact if for any set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n0669707.png" /> of propositions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n0669708.png" /> of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n0669709.png" />, realizability of every subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697010.png" /> of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697011.png" /> implies realizability of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697012.png" />. The compactness problem consists in describing the pairs of cardinal numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697013.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697014.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697015.png" />-compact.

c) If the formulas of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697016.png" /> form a set (rather than a proper class), then there is a cardinal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697017.png" /> such that every set of propositions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697018.png" /> that has a model of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697019.png" /> also has models of arbitrarily large cardinalities. The least such cardinal number is called the Hanf number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697020.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697021.png" /> this is the countable cardinal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697022.png" />. The problem consists in computing the Hanf number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697023.png" /> and in establishing conditions for the existence of models of small cardinality.

Below the best studied non-classical languages are listed and for each of them solutions of the problems a)–c) are described.

1) The language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697024.png" /> of second-order logic. It is obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697025.png" /> by adding variables for predicates as well as quantifiers over such predicate-variables. A proposition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697026.png" /> of the language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697027.png" /> is said to be true in a system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697028.png" /> (where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697029.png" /> is a model of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697030.png" /> and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697031.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697032.png" />, are sets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697033.png" />-ary predicates on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697034.png" />) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697035.png" /> is true in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697036.png" /> for the restriction of the quantifiers to the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697037.png" />-ary predicates in the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697038.png" />. If here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697039.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697040.png" />, are the sets of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697041.png" />-ary predicates on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697042.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697043.png" /> is said to be true in the model <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697044.png" />. There is a proposition of the language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697045.png" /> that characterizes the arithmetic of natural numbers up to an isomorphism. From the [[Gödel incompleteness theorem|Gödel incompleteness theorem]] for arithmetic it follows that the set of propositions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697046.png" /> that are true in all models is not axiomatizable. However, there is a natural generalization <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697047.png" /> of the axioms of first-order predicate calculus for which Henkin's completeness theorem holds: From <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697048.png" /> those and only those propositions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697049.png" /> are deducible that are true in all systems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697050.png" /> satisfying the axioms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697051.png" />. In this case there is an analogue of the Löwenheim–Skolem theorem for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697052.png" />: If a proposition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697053.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697054.png" /> is true together with the axioms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697055.png" /> in the same system, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697056.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697057.png" /> are true in a system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697058.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697059.png" /> and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697060.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697061.png" />, are at most countable. Some questions in the theory of models of the language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697062.png" /> are connected with problems of set theory and are unsolvable in the Zermelo–Fraenkel axiomatic set theory.

2) The language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697064.png" /> (where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697065.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697066.png" /> are cardinal numbers). The formulas of this language are constructed from the formulas of the first-order language by means of conjunctions and disjunctions of sets of formulas of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697067.png" /> and by negation and quantification over strings of variables of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697068.png" />. The truth of a formula in a model is defined, as in the first-order language, by induction on the structure of the formula. A cardinal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697069.png" /> is said to be compact if for any cardinal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697070.png" /> the language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697071.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697072.png" />-compact. Among the languages <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697073.png" />, the best studied after <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697074.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697075.png" />. Every countable model of countable signature can be characterized by a proposition of the language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697076.png" /> up to an isomorphism. The language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697077.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697078.png" />-compact for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697079.png" />. The Hanf number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697080.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697081.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697082.png" /> is defined by induction over the ordinal numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697083.png" />: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697084.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697085.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697086.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697087.png" /> is a limit ordinal.

3) The language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697089.png" /> with the quantifier  "there exist at least wa many" . The language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697090.png" /> is obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697091.png" /> by adding a new quantifier <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697092.png" />. The truth of a formula is determined by induction on its length. Here a formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697093.png" /> is true in a model <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697094.png" /> if the cardinality of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697095.png" /> is at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697096.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697097.png" /> denote the set of formulas of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697098.png" /> that are true in all models of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n06697099.png" />. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970100.png" /> is not axiomatizable, but <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970101.png" /> is. The language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970102.png" /> is not <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970103.png" />-compact. However, a certain compactness holds in the languages <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970104.png" />. Let the symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970105.png" /> indicate that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970106.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970107.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970108.png" />) imply that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970109.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970110.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970111.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970112.png" />-compact. The Hanf number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970113.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970114.png" />.

In the models considered so far any proposition of a language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970115.png" /> of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970116.png" /> was either true or false. Alternatively, one can consider models <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970117.png" /> of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970118.png" /> in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970119.png" />-ary predicates are regarded not as subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970120.png" /> but as mappings from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970121.png" /> into a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970122.png" />. If on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970123.png" /> operations corresponding to the logical connectives of the language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970124.png" /> and quantifiers (understood as infinitary operations) are defined, then one can define the truth value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970125.png" /> of any proposition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970126.png" /> of the language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970127.png" /> in the model <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970128.png" />. Thus one obtains a model theory with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970129.png" /> as set of truth values. The theory is most fruitful in case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970130.png" /> is a compact Hausdorff space or a complete Boolean algebra. In these cases many methods of the classical theory of models work. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970131.png" /> is a complete [[Boolean algebra|Boolean algebra]], then conjunction, disjunction and negation are defined as intersection, union and complementation, respectively. The value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970132.png" /> is defined as the intersection of all elements of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970133.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066970/n066970134.png" />. Boolean-valued models have found wide-spread application in proofs of the compatibility of various propositions of set theory with the basic axioms of axiomatic set theory.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A. Church,   "Introduction to mathematical logic" , '''1''' , Princeton Univ. Press  (1956)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  C.C. Chang,   H.J. Keisler,   "Model theory" , North-Holland  (1973)</TD></TR></table>



====Comments====
Additional references on infinitary logic are [[#References|[a1]]], [[#References|[a2]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  H.J. Keisler,   "Model theory for infinitary logic" , North-Holland  (1971)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M.A. Dickmann,   "Large infinitary languages" , North-Holland  (1975)</TD></TR></table>