Open Collections

Some useful generalizations of first order languages

University of British Columbia

We begin with a disucssion of some of the serious deficiencies of first order predicate languages. These include the non-characterizability by first order sentences of such common mathematical structures as the class of well-ordered sets, the class of finite sets, the class of Archimedean fields and the standard models of arithmetic and analysis. Two methods of generalizing first order predicate languages are then studied. The first approach is to allow for "expressions of infinite length"; the second method is the introduction of "generalized quantifiers." For the languages resulting from each approach, we consider to what extent such deficiencies as those mentioned above may be overcome and also to what extent some of the elementary model-theoretic and proof-theoretic theorems of first order logic may be generalized to these new languages. Among the languages with expressions of infinite length, we first consider the Lω₁ω languages which generalize first order languages by extending the recursive definition of a formula to allow countable conjunctions and disjunctions of formulas as formulas. It is shown that with the use of such languages we are able to describe categorically the standard model of arithmetic, the class of finite sets, the class of Archimedean fields and other common mathematical structures which cannot be characterized in first order languages. Generalizations of the Lowenheim-Skolem and completeness theorems of first order logic are given as well as a countable isomorphism theorem due to Dana Scott. We make use of a characterization of rank equivalence due to Carol Karp to demonstrate that neither the standard model of analysis nor the class of well-ordered sets may be described in any Lω₁ω -language. In fact, our argument indicates that these characterizations are not possible in any extension of a Lω₁ω - language which, for any infinite cardinal α , allows as formulas conjunctions and disjunctions of less than a formulas. This result leads us naturally to a consideration of the class of Lω₁ω - languages, any element of which is obtained from a Lω₁ω - language by modifying the rules for formula formation to allow not only denumerable conjunctions and disjunctions but also quantifications over denumerable sets of variables. (These ideas are made more precise in the text of the thesis.) The standard model of analysis and the class of well-ordered sets are each seen to be characterizable by single Lω₁ω - sentences. Other infinitary languages are also mentioned, including languages with infinitely long atomic formulas. Among the languages with generalized quantifiers we restrict ourselves to the L(Qα) - languages, where α is an ordinal, which are obtained from first order languages by adding a new quantifier symbol Qα to be read "there exist Ɲα... .” In addition to being able to characterize sets of various cardinalities, we give a categorical description of the standard model of arithmetic by a single L(Qօ) - sentence. Among the model-theoretic results possible are generalizations of the compactness theorem, Lŏs's theorem and the downward Lowenheim - Skolem theorem of first order logic. Finally, on the proof-theoretic side, we show that in the case α = 0 there exists no recursive axiomatization which yields a completeness result; in the case α = 1 , however, such an axiomatization is possible.

Text

2011-05-06

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/34341

Mathematics

University of British Columbia

Graduate