 Library Home /
 Search Collections /
 Open Collections /
 Browse Collections /
 UBC Theses and Dissertations /
 Some useful generalizations of first order languages
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Some useful generalizations of first order languages Finlay, James Andrew
Abstract
We begin with a disucssion of some of the serious deficiencies of first order predicate languages. These include the noncharacterizability by first order sentences of such common mathematical structures as the class of wellordered 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 modeltheoretic and prooftheoretic 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 LowenheimSkolem 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 wellordered 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 wellordered 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 modeltheoretic 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 prooftheoretic 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.
Item Metadata
Title 
Some useful generalizations of first order languages

Creator  
Publisher 
University of British Columbia

Date Issued 
1971

Description 
We begin with a disucssion of some of the serious deficiencies of first order predicate languages. These include the noncharacterizability by first order sentences of such common mathematical structures as the class of wellordered 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 modeltheoretic and prooftheoretic 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 LowenheimSkolem 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 wellordered 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 wellordered 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 modeltheoretic 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 prooftheoretic 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.

Genre  
Type  
Language 
eng

Date Available 
20110506

Provider 
Vancouver : University of British Columbia Library

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

DOI 
10.14288/1.0080440

URI  
Degree  
Program  
Affiliation  
Degree Grantor 
University of British Columbia

Campus  
Scholarly Level 
Graduate

Aggregated Source Repository 
DSpace

Item Media
Item Citations and Data
Rights
For noncommercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.