Atlas home || Conferences | Abstracts | about Atlas

Second St.Petersburg Days of Logic and Computability
August 24-26, 2003
Petersburg Department of Steklov Institute of Mathematics
St. Petersburg, Russia

Organizers
Sergei ADIAN (Russia), Sergei ARTEMOV (Russia/USA), Nikolai KOSSOVSKI (Russia), Maurice MARGENSTERN (France), Grigori MINTS (USA), Yuri MATIYASEVICH (Russia), the chairman, Nikolai NAGORNY (Russia), Vladimir OREVKOV (Russia), Anatol SLISSENKO (France)

View Abstracts
Conference Homepage

Quasi-solvability of \omega-order Predicate Calculus
by
Andreas Schumann
Chair of high algebra of Belorussian State University

In this paper, I demonstrate how the problem of construction of lattice with \Omega\omega -signature relations an a scope of predicates (formulas) of language L\omega of \omega-order predicate calculus can be solved. Every class is assigned set Th(K\omega ) of all formulas, which are true on each \Omega\omega - lattice M     in     K\omega . Every \Omega\omega-signature formulas set \Sigma corresponds to the class K\omega (\Sigma). The main difficulty, which arises in the process of construction, is that the class isn't axiomatizable - K\omega     subset K\omega(Th(K\omega )). This difficulty has been already revealed for the class K2 of \Omega\omega -signature algebraic systems of language L2 of second-order predicate calculus. On account of obvious incompleteness of logical calculus of language L\omega, the attribute \Sigma    subset Th(K\omega (\Sigma)) can be pointed. The calculus of language L\omega is undecidable, that is for any \Omega\omega-signature formulas set \Sigma it is known that \Sigma{\Phi : \Phi in     \Sigma} isn't recursive subset of set \omega. I prove that \omega-order predicate calculus coincides with the \omega-order theory. The key definition of the paper is the following: Set is quasi-solvable, if it is recursively enumerable or its supplement is recursively enumerable. Thus, recursive, recursively enumerable and completed cohesive subsets of set \omega are quasi-solvable sets. The ensemble of quasi-solvable sets is regarded as set of indexes of formulas. This approach permits to use solvable and recursively enumerable predicates, a well as predicates pointed to incompleteness of axioms system. I prove that for every \Omega\omega -signature formulas set \Sigma it is true, that the set \Sigma{\Phi : \Phi in     \Sigma} is quasi-solvable subset of set \omega. As a result two following definitions are given its sense. The set of quasi-solvable axioms \Sigma of signature \Omega\omega is quasi-full. In this case \Sigma = Th(K\omega (\Sigma)). The set of models K\omega of signature \Omega\omega , an it set of quasi-solvable axioms \Sigma is true, is hyper-axiomatizable class. In this case K\omega=K\omega (Th(K\omega )).

Date received: April 22, 2003

Copyright © 2003 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cajy-29.