Decidability and undecidability of extensions of second (first) order theory of (generalized) successor

Autor:	Calvin C. Elgot, Michael O. Rabin
Rok vydání:	1966
Předmět:	Combinatorics Successor cardinal Discrete mathematics Philosophy Logic Predicate (mathematical logic) First order theory Decidability Mathematics
Zdroj:	Journal of Symbolic Logic. 31:169-181
ISSN:	1943-5886 0022-4812
DOI:	10.2307/2269808
Popis:	We study certain first and second order theories which are semantically defined as the sets of all sentences true in certain given structures. Let be a structure where A is a non-empty set, λ is an ordinal, and Pα is an n(α)-ary relation or function4 on A. With we associate a language L appropriate for which may be a first or higher order calculus. L has an n(α)-place predicate or function constant P for each α < λ. We shall study three types of languages: (1) first-order calculi with equality; (2) second-order monadic calculi which contain monadic predicate (set) variables ranging over subsets of A; (3) restricted (weak) second-order calculi which contain monadic predicate variables ranging over finite subsets of A.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::73530fabae162cad3519674ad0ab82a5 https://doi.org/10.2307/2269808 Zobrazit plný text záznamu