Decidability and Definability Results Concerning Well-Orderings and Some Extensions of First Order Logic

✍ Scribed by Bogdan Stanislaw Chlebus

• Publisher: John Wiley and Sons
• Year: 1980
• Tongue: English
• Weight: 452 KB
• Volume: 26
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19800263402

✦ Synopsis

DECIDABILITY AND DEFINABILITY RESULTS CONCERNING WELL-ORDERINGS AND SOME EXTENSIONS OF FIRST ORDER LOGIC by BOGDAN STANISLAW CHLEBUS in Warsaw (Poland)

1. Introdiirtion

Let L* denote a countable extension of the first order language L. I n this paper 1 ) definability of the class of well-ordered structures, 2) decidability of the theory of a given ordinal or a class of ordinals, 3) the classification of the set of tautologies in the analytical hierarchy.

We assume that L and L* have no constants and function symbols and that L* has no new predicate symbols. The following are examples of extensions of L : L(Q,) denotes L extended by adding the Chang quantifier Q, with the satisfaction clause ?[ k (Q,x) @(x) iff card ' 21 = card{a E I'UI : % k @(a)}, L(Q,) denotes L with the added quantifier "there are a t least N ~" , L(Q,) denotes L with the Hartig quantifier Q I defined by the following problems concerning L are investigated :

This quantifier binds one variable in each formula of the pair of formulas.

L"(") for a natural n or n = co denotes the (first order) expansion of L obtained by adding to L two predicate symbols 7 and E. By a structure appropriate for L'(") is meant any structure = (A", . . .) defined as follows :

1. ?( = ( A , , . . .) is a structure appropriate for L in the ordinary sense, 2) for a natural n, the universe of %@+l) is the set A,,