518 M SO УДК 5)9. 95 Introduction to Mathematical Logic by Elliott Mendelson Associate Professor of Mathematics Queens College Flushing, New York D. VAN NOSTRAND COMPANY, INC. PRINCETON, NEW JERSEY TORONTO NEW YORK LONDON Эллнот Мендельсон ВВЕДЕНИЕ В МАТЕМАТИЧЕСКУЮ ЛОГИКУ M., 1971 г., 320 стр. с илл. Редактор В. В. Донченко. Техн. редактор К. Ф. Брудно. Корректоры 3. В. Автонеева, Л. С. Сомова. Сдано в набор 28/Х 1970 г. Подписано к печати 19/V 1971 г. Бумага 60><90l/ie. Физ. печ. л. 20. Условн. печ. л. 20. Уч.-изд. п. 21,61. Тираж 30000 экз. Цена книги 1 р. 77 к. Заказ № 1451. Издательство «Наука». Главная редакция физико-математической литературы. Москва. В-71. Ленинский проспект. 15. Ордена Трудового Красного Знамени Ленинградская типография № 1 «Печатный Двор» им. А. M. Горького Главполиграфпрома Комитета по печати при Совете Министров СССР, г. Ленинград, Гатчинская ул., 26. 2-2-S 42-71 Оглавление От редактора перевода ............................. 5 Предисловие ................................... 6 Введение ..................................... 7 Глава 1. Исчисление высказываний ................... 19 § 1. Пропозициональные связки. Истинностные таблицы ...... 19 § 2. Тавтологии ............................. 24 § 3. Полные системы связок ...................... 31 § 4. Система аксиом для исчисления высказываний ........ 36 § 5. Независимость. Многозначные логики .............. 46 § 6. Другие аксиоматизации ...................... 48 Глава 2. Теории первого порядка ..................... 53 § 1. Кванторы .............................. 53 § 2. Интерпретации. Выполнимость и истинность. Модели ..... 57 § 3. Теории первого порядка ..................... 64 § 4. Свойства теорий первого порядка ................ 67 § 5. Теоремы о полноте ........................ 71 § 6. Некоторые дополнительные метатеоремы ............ 81 § 7. Правило С ............................. 83 § 8. Теории первого порядка с равенством ............. 86 § 9. Введение новых функциональных букв и предметных констант 93 § 10. Предваренные нормальные формы ................ 96 § 11. Изоморфизм интерпретаций. Категоричность теорий ...... 102 § 12. Обобщенные теории первого порядка. Полнота и разреши- мость ................................. 104 Глава 3. Формальная арифметика ..................... 115 § 1. Система аксиом ........................... 115 § 2. Арифметические функции и отношения ............. 132 § 3. Примитивно рекурсивные и рекурсивные функции ....... 135 § 4. Арифметизация. Гёделевы номера ................. 151 § 5. Теорема Гёделя для теории S ................... 158 § 6. Рекурсивная неразрешимость. Теорема Тарского. Система Робинсона .............................. 167 Глава 4. Аксиоматическая теория множеств .............. 177 § 1. Система аксиом ........................... 177 § 2. Порядковые числа ... ...................... 188 § 3. Равномощность. Конечные и счетные множества ........ 199 § 4. Теорема Хартогса. Начальные порядковые числа. Арифметика порядковых чисел .......................... 207 § 5. Аксиома выбора. Аксиома ограничения ............. 217 I* 4 ОГЛАВЛЕНИЕ Глава 5. Эффективная вычислимость .................. 228 § 1. Нормальные алгорифмы Маркова ................. 228 § 2. Алгорифмы Тьюринга ........................ 251 § 3. Вычислимость по Эрбрану-Гёделю. Рекурсивно перечислимые множества ....................••••••.... 261 § 4. Неразрешимые проблемы ...................... 278 Дополнение. Доказательство непротиворечивости формальной арифметики .................. ..... 282 Литература ........................•••••••••••• 296 Алфавитный указатель ............................. 310 Символы и обозначения ............................. 318 Литература *) Здесь перечисляются не только книги и статьи, упоминаемые в тексте, но также и некоторые другие публикации, которые будут полезны при дальнейшем изучении математической логики. Дополнительные ссылки могут быть найдены в рефератах в Journal of Symbolic Logic и в Mathematical Reviews **). Аккерман (Ackermann W.) [1928] Zum Hilbertschen Auibau der reelen Zahlen, Math. Ann. 99, 118—133. [1940] Zur Widerspruchsfreiheil der Zahlentheorie, Math. Ann. 117, 162—194. [1951] Konstruktiver Aufbau eines Abschnittes der zweiten Cantorschen Zahlen- klasse, Math. Z. 53, 403—413. [1954] Solvable Cases oi the Decision Problem, Amsterdam. Accep (Asser G.) [1955] Das Reprasentantenproblem im Pradikatenkalktil der ersten Stufe mit Iden- titat, Z. math. Logik Grundl. Math. 1, 252—263. [1959] Turing-Maschinen und Markowsche Algorithem, Z. math. Logik Grundl. Math. 5, 346—365. Бахман (Bachman H.) [1955] Transfinite Zahlen, Berlin. Бернайс (Bernays P.) [1937—1954] A system of axiomatic set theory. J. Symbolic Logic. 1, 2 (1937), 65-77; II, 6 (1941), 1—17; 111, 7 (1942), 65—89; IV, 7 (1942), 133—145; V, 8 (1943), 89—106; VI, 13 (1948), 65—79; VII, 19 (1954), 81—96. [1957] Реферат статьи Майхилла [1955], J. Symbolic Logic 22, 73—76. [1958] Axiomatic Set Theory, Amsterdam. [1961] Zur Frage der Unendlichkeitsschemata in der axiomatischen Mengenlehre, Essavs on the Foundations of Mathematics, Jerusalem, 3—49. Бет (В e t h Е.) [1951] A topological proof of the theorem of Lowenheim—Skolem — Godel, Indag. Math. 13, 436—444. [1953] Some consequences of the theorem of Lowenheim—Skolem—Godel— Malcev, Indag. Math. 15, 66—71. ЛИТЕРАТУРА 297 [1959] The Foundations of Mathcm.ilics, Amsterdam. [1962] Formal Methods, New York. Б и р к г о ф (В i r k h о f f G.) 11948] Lattice Theory, New York. [Русский перевод: Бнркгоф Г., Теория структур, ИЛ, 1952.] де Брёйн (Bruijn N. G. de) и Эрдёш (Erdos Р.) [1951] A colour problem for infinite graphs and a problem in the theorv of rela- tions, Indag. Math. 13, 369—373. Бриттон (Britton J.L.) [1958] The word problem for groups, Proc. London Math. Soc. 8, 493—506. Б у н (Boon W.) [1959] The word problem, Ann. Math. 70, 207—265. Бурбаки (Bourbaki N.) [1947^ Algebre, Livre 11, Chap. II, Paris. [Русский перевод: Бурбаки Н., Элементы математики. Алгебра (алгебраические структуры, линейная и полилинейная алгебра), Физматгиз, 1962.] В а и с б е р г (W a j s b e r g М.) [1933] Untersuchungen fiber den Funktionenkalkiil fur endliche Individuenberei- che, Math. Ann. 108, 218—228. Ван дер Варден (van der Waerden В.) [1930—1931] Moderne Algebra, Berlin, Springer (второе издание, 1940; третье издание, 1950). [Русский перевод: Ван дер Варден Б. Л., Сов- ременная алгебра, Гостехиздат, 1947.] Ван Хао (Wang На о) [1951 a] Arithmetic translations of axiom systems, Trans. Amer. Math. Soc. 71, 283—291. [1951 b] Arithmetic models for formal systems, Methodos 3, 217—232. [1954] The formalization of mathematics, J. Symbolic Logic 19, 241—266. J1955| Undecidable sentences generated by semantical paradoxes, J. Symbolic Logic 20, 31—43. [1957 a] The axiomatization of arithmetic, J. Symbolic Logic 22, 145—158. [1957 b] Remarks on constructive ordinals and set theory, Summer Inst. Svmb. Logic, Cornel], 383—390. [1957 с] A variant to Turing's theory of computing machines, J. Assoc. Сотр. Mach. 4, 63—92. [1959] Ordinal numbers and predicative set theory, Z. math. Logic Grundl. Math. 5, 216—239. Ван Хао (Wang На о) и Мак-Нотон (McNaughton R.) [1953] Les systemes axiomatiques de la theorie des ensembles, Paris. [Русский перевод: Ван Хао и Мак-Нотон Р., Аксиоматические системы теории множеств, ИЛ, 1963.] Виноградов И.М. [1952] Основы теории чисел, 6-е изд., Гостехиздат. BOOT (V aught R.) [1954] Applications of the Lowenheim—Skolem—Tarski theorem to problems of completeness and decidability, Indag. Math. 16, 467—472. [1959] Sentences true in all constructive models, J. Symbolic Logic 24, 1—15. [1961] Denumerable models of complete theories, Infinitistic Methods, War- szawa, 303—321. [1962] Cobham's theorem on undecidable theories, Logic, Methodology and Philosophy of Science (Proc. Int. Cong., 1960), Stanford, 14—25. [Рус- ский перевод; В о о т Р. Л., О теореме Кобхама, касающейся нераз- решимых теорий, сб. «Математическая логика и ее применения», «Мир», 1965, 9—22.] Вопенка (Vopenka P.) "[1965 a] The limits of sheaves and applications on constructions of models, Bull. Acad. Polon. Sci., Ser. Math. 13, 189—192. ЛИТЕРАТУРА °|1965b] Properties of V-models, там же, 441—444. °[i966] V-modeis in which the generalized continuum hypothesis does not hold там же 14, 95—99. ' Г а л л е р (Q а 11 е г В. А.) (1957] Cylindric and polyadic algebras, Proc. Amer. Math. Soc. 8, 176—183. Гёдель (Qodel К.) [1930] Die Vollstandigkeit der Axiome des logischen Funktionenkalkiils, Mo- natsh. Math. Phys. 37, 349—360. [1931] Ueber formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme I, там же 38, 173—198. [1933] Zum intuitionistischen Aussagenkalkul; Zur intuitionistischen Arithmetik und Zahlentheorie, Ergeb. math. Koll. 4, 34—38, 40. [1934] On undecidable propositions of formal mathematical svstems, Princeton. [1936] (Jber die Lange der Beweise, Ergeb. math. Koll. 7, 23—24. [1940] The consistency of the axiom of choice and of the generalized conti- nuum hypothesis with the axioms of set theory, Princeton. [Русский перевод: Гёдель К., Совместимость аксиомы выбора и обобщенной континуум-гипотезы с аксиомами теории множеств, УМН 3, JM« I (1948), 96—149.] [1944] .Russel's Mathematical Logic, в книге «The Philosophy of Bertrand Russell» под ред. Шильпа, Chicago, 123—153. [1947] What is Cantor's continuum problem? Amer. Math. Monthly 54, 515—. 5.25. [1953] Obcr eine bisher noch nicht benutzte Erweiterung des finiten Stand- punkts,Diaiectical2,280—287. [Русский перевод: Гёдель К., Об одном еще не использованном расширении финитной точки зрения, сб. «Математическая теория логического вывода», «Наука», 1967, 299—305.] Гейтинг (Heyting A.) [1956] Intuitionism, Amsterdam. [Русский перевод: Гейтинг А., Интуи- ционизм, «Мир», 1965.] Генкин (Henkin L.) [1949] The completeness of the first-order functional calculus, J. Symbolic Logic 14, 159—166. [1950] Completeness in the theory of types, там же 15, 81—91. [1953] Some interconnections between modern algebra and mathematical logic. Trans. Amer. Math. Soc. 74, 410—427. ]1954] Boolean representation through prepositional calculus, Fundam. Math, 41, 89—96. (1955 a] The representation theorem for cylindrical algebras, Mathematical inter- pretations of Formal Svstems, Amsterdam, 85—97. [1955 b] On a theorem of Vaught, J. Symbolic Logic 20, 92—93. [1956] La structure algebrique des theories mathematiques, Paris. Генкин (Henkin L.)иTapcкий (TarskiA.) [1961] Cvlindric Algebras, Proc. Symp. Pure Math. A. M. S., II, Lattice Theory, 83—113. Генцен (Gentzen Q.) [1934] Untersuchungen fiber das Logische Schliessen, Math. Z. 39, 176—210, 405—431. [Русский перевод: Генцен Г., Исследования логических выводов, сб. «Математическая теория логического вывода», «Наука», 1967, 9—74.] [1936] Die Widerspruchsfreiheit der reinen Zahlentheorie, Math. Ann. 112, 493—565. [Русский перевод: Генцен Г., Непротиворечивость чистой теории чисел, сб. «Математическая теория логического вывода», «Наука», 1967, 77—153.] [1938 a] Die gegenwartige Lage in der mathematischen Grundlagenforschung, Forschungen zur Logik, N. Folge, Heft 4, 5—18. ЛИТЕРАТУРА 299 [!938b] Neue Fassung des Widerspriichstreiheitsbeweiscs fUr die reine Zaiiien- theorie, там же, 19—44. [Русский перевод: Генцен Г., Новое изло- жение доказательства непротиворечивости для чистой теории чисел, сб. «Математическая теория логического вывода», «Наука», 1967, 154—190.] [1943] Beweisbarkeit und Unbeweisbarkeit von Anfangsfallen der transfiniten Induktion in der reinen Zahlentheorie, Math. Ann. 119, 140—161. Гермес (Hermes H.) [1961] Aufzahlbarkeit, Entscheidbarkeit, Berechenbarkeit, Berlin—Gottingen— Heidelberg. Гжегорчик (Qrzegorczyk A.) [1956] Some proofs of undecidability of arithmetic, Fundam. Math. 43, 166— 177. Гжегорчик (Qrzegorczyk A.), M о с т о в с к и И (M о s t о w s k i А.) и Рыль-Нардзевский (Ryll-Nardzewski С.) 11958] The classical and the a-complete arithmetic, J. Symbolic Logic 23, 188—206. Гильберт (Hilbert D.) и Аккерман (Ackermann VV.) [1938] Grundzilge der theoretischen Logik, Berlin. [Русский перевод: Г и л ь- б е р т Д. и Аккерман В., Основы теоретической логики, ИЛ, 1947.] Гильберт (Hilbert D.) и Б е р н а и с (В е г n a v s Р.) [1934], [1939]. Qrundlagen der Mathematik, т. 1 (1934), т. II (1939), Berlin. Д е в и с (D а v i s M.) [1958] Computability and Unsolvability, New York. Девис (Davis M.), Пут нам (Putnam Н.)иРобинсон (Robinson J.) [1961] The decision problem for exponential diophantine equation.-», Ann. Math. 74, 425—436. [Русский перевод: Д е в и с M., П у т н а м X., Робин- сон Д ж., Проблема разрешимости для показательно-диофантовых уравнений, Математика (сб. переводов) 9, №5 (1965), 69—79.) Дедекинд (Dedekind R.) [1901] Essays on the theory of numbers, Chicago. Деккер (Dekker J.) |1953] Two notes on recursively enumerable sets, Proc. Amer. Math. Soc. 4, 495—501. [1955] Productive sets, Тгапз. Amer. Math. Soc. 78, 129—149. Деккер (Dekker J.) и Майхилл (Myhill J.) [I960] Recursive Equivalence Types, Univ. Calif. Publ. Math. 3, 67—213. Дгтловс В. К. 11958] Эквивалентность нормальных алгорифмов и рекурсивных функций, Тр. Матем. ин-та АН СССР им. В. А. Стеклова LII, Изд-во АН СССР, 66-69. Д и к с о н (D i с k s о n L. Е.) 11929] Introduction to the theory of numbers, Chicago. Дpeбeн(Dreben B.) [1952] On the completeness of quantification theory, Proc. Nat. Acad. Sci. L). S. A. 38, 1047—1052. Зейденберг (Seidenberg A.) [1954] A new decision method for elementary algebra, Ann. Math. 60, 365— 374. 3 и м а н (Z е е m a n E. С.) [1955] On direct sums of free cycles, J. London Math. Soc. 30, 195—212. Кальмар (К almarL.) [1936] Zurilckfuhrung des Entscheidungsproblems auf den Fall von Pormein mit einer einzigen binaren Punktionsvariablen, Сотр. Math. 4, 137—144. Камке (К а т k е Е.) [1950] Theory of sets, New York. 300 ЛИТЕРАТУРА Карнап(Сагпар R.) [1934) Logische Syntax der SSprache, Wien. [1939] Foundations of logic and mathematics, «International Encyklopedia of Unified Science> I, № 3, Chicago. [1942—1943] Studies in Semantics. Introduction to Semantics and Formalization of Logic, Cambridge, Mass. [1950] Logical foundations of probability, Chicago. [1958] Introduction to symbolic logic, New York. К арр и (С urr у Н. В.) 1950] A theory of formal deducibility, Notre Dame. 1951] Outlines of a Formalist Philosophy of Mathematics, Amsterdam. 1952] Lecons de logique algebrique, Paris—Louvain. '[1963] Foundations of Mathematical Logic, New York. [Русский перевод: К арр и X. Б., Основания математической логики, «Мир», 1969.] К а р р и (С и г г у Н. В.) и Ф е и с (F е у s R.) [1958] Combinatory logic, Amsterdam. Кемени (Kemeny J.) [1948] Models of logical systems, J. Symbolic Logic 13, 16—30. [1958] Undecidable problems of elementary number theory, Math. Ann. 135, 160—169. К л и н и (К 1 е е n е S. С.) [1936 a] General recursive functions of natural numbers, Math. Ann. 112, 727— 742. 1936 b] X-definability and recursiveness, Duke Math. J. 2, 340—353. 1938] On notation for ordinal numbers, J. Symbolic Logic 3, 150—155. 1943] Recursive predicates and quantifiers, Trans. Amer. Math. Soc. 53,41—73. 1944] On the forms of the predicates in the theory of constructive ordinals, Amer. J. Math. 66, 41—58. [1945] On the interpretation of intuitionistic number theory, J. Symbolic Logic 10, 109—124. [1952] Introduction to Metamathematics, Van Nostrand, Princeton. [Русский перевод: К л и н и С. К., Введение в метаматематику, ИЛ, 1957.] [1955 a] Hierarchies of number-theoretic predicates, Bull. Amer. Math. Soc. 61, 193—213. [1955 b] Arithmetical predicates and function quantifiers, Trans. Amer. Math. Soc. 79, 312—340. [1955с] On the form of the predicates in the theorv of constructive ordinals 11, Amer. J. Math. 77, 405—428. [1960] Mathematical logic: constructive and non-constructive operations, Proc. Int. Cong. Math., F.dinburgh, 1958, 137—153. К л и н и (К 1 е е n е S. С.) и Пост (Post E.) [1954] The upper semi-lattice of degrees of recursive unsolvability, Ann. Math. 59, 379—407. К о 9 н (С о h е n P. J.) °[1963—1964] The independence of the continuum hypothesis, Proc. Nat. Acad. Sci. U.S.A. 50, № 6, 1143—1148; 51, № 1, 105—110. [Русский перевод: К о э н П. Д ж., Независимость континуум-гипотезы. Математика (сб. переводов) 9, №4 (1965), 142—155.] °[]966] Set theory and the continuum hypothesis. New York—Amsterdam. [Рус- ский перевод: К о э н П. Дж., Теория множеств и континуум-гипо- теза, «Мир», 1969.] К р е и г (С г a i g W.) [1953] On axiomatizability within a system, J. Symbolic Logic 18, 30—32. [1957 a] Linear reasoning. A new form of the Herbrand—Gentzen theorem, J. Symbolic Logic 22, 250—268. [1957 b] Three uses of the Herbrand—Gentzen theorem in relating model theory and proof theory, J. Symbolic Logic 22, 269—285. ЛИТЕРАТУРА 301 К р е и д е р (К г е i d е г D. L.) и Роджерс (Rogers П., Jr.) [1961] Constructive versions of ordinal number classes, Trans. Amer. Math. Soc. 100, 325—369. К р е и с е л (К г е i s е 1 G.) [1950] Note on arithmetic models for consistent formulae of the predicate cal- culus, Fundam. Math. 37, 265—285. [1951—1952] On the interpretation of non-Sinitist proofs, J. Symbolic Logic 16, 241-267; 17, 43-58. [1952 a] On the concepts of the completeness and interpretation of formal sys- tems, Fundam. Math. 39, 103—127. [1952 b] Some concepts concerning formal systems of number theory, Math. Z. 57, 1-12. [1953 a] A variant to Hilbert's theory of the foundations of arithmetic, British J. Phil. of Science 4, 107—129. [1953 b] On a problem of Henkin's, Indag. Math. 15, 405—406. [1955] Models, translations and interpretations, Mathematical Interpretations of Formal Systems, Amsterdam, 26—50. [1958 a] Mathematical significance of consistency proofs, J. Symbolic Logic 23, 155-182. [1958 b] Hilbert's programme, Dialectica 12, 346—372. [1960] Ordinal logics and characterization of informal concepts of proof, Proc. Int. Cong. Math., Edinburgh, Cambridge, 289—299. Kpeйceл(KreiselG.)иBaнXao(WangHao) [1955] Some applications of formalized consistency proofs, Fundam. Math. 42, 101-110. К у а и н (Q u i n е W. V.) [1937] New foundations for mathematical logic, Amer. Math. Monthly 44, 70-80. [1938] On the theory of types, J. Symbolic Logic 3, 125—139. 1950 Methods of logic, New York. 1951] Mathematical logic, Cambridge, Mass. 1953] From the logical point of view, Cambridge, Mass. 1955] On Frege's way out, Mind 64, 145—159. Лaдpиep(Ladгiёre J.) [1957] Les limitations internes des formalismes, Paris. Ландау (Landau E.) [1930] Grundlagen der Analysis, Leipzig. [Русский перевод: Ландау Э. Основы анализа, ИЛ, 1947.] Лёб (Lob М. Н.) [1955] Solution of a problem of Leon Henkin, J. Symbolic Logic 20, 115—118. Лёвенгейм (Lowenheim L.) [1915] Uber Moglichkeiten im Relativkalkul, Math. Ann. 76, 447—470. Л е в и (L e v у А.) [1960] Axiom schemata of strong infinity, Pacific J. Math. 10, 223—238. Ленгфорд (LangfordC.H.) [1927] Some theorems of deducibility, Ann. Math. 1, 28, 16—40; II, 28, 459— 471. Л и н д о н (L у n d о n R. С.) [1959] Properties preserved under algebraic construction, Bull. Amer. Math. Soc. 65, 143—299. Л о и х л и (L a u с h 1 i H.) [1962] Auswahlaxiom in der Algebra, Comment. Math. Helvetic! 37, 1—18. Лоренцен^огепгепР.) [1951] Algebraische und logistische Untersuchungen iiber freie Verbandc, J. Symbolic Logic 16, 81—106. [1955] Einfilhrung in die operative Logik und Mathematik, Berlin— Gotingen— Heidelberg. 302 ЛИТЕРАТУРА Л о с ь О- о s J.) [1954 a] Sur la theoreme de Oodel pour les theories indenombrables. Bull. de Г ^cad. Polon. des Sci. Ill, 2, 319-320. [1954 bj On the existence of linear order in a group, там же, 21—23. (1954с) On the cathegoricity in power of elementary deductive systems and some related problems, Coil. Math. 3, 58—62. [1955] The algebraic treatement of the methodology of elementary deductive systems, Studia Logica 2, 151—212. Лось (Los J.) и Р ы л л ь - Н а р д з е в с к и и (R у 11-N ardzewski С.) [1954] Effectiveness of the representation theory for Boolean algebras, Fun- dam. Math. 41, 49—56. Люксембург (Luxemburg W. A. J.) [1962] Non-standard analysis, Pasadena. M а и х и л л (М v h i 11 J.) [1955] Creative sets, Z. math. Logik Qrundl. Math. 1, 97—108. Макдоуэлл (Macdowell R.) и Шпеккер (S pecker E.) [1961] Modele der Arithmetik, Infinitistic Methods, Warszawa, 257- Мак-Кинсн (McKinsey J. С. С.) и Тарский (Tarski A.) [1948] Some theorems about the sentential calculi of Lewis and Hevtine, J. Symbolic Logic 13, 1—15. М а к л а ф л и н (М а с 1 a u g h I i n T.) [1961] A muted variation on a theme of Mendelson, Z. math. Logic Orundl. Matli. 17, 57-60. Мальцев А. И. [1936] Untersuchungcn aus dem Qebiet der mathematischen Logik, Матем. сб 5, № 1, 323-336. °[1965] Алгоритмы и рекурсивные функции, «Наука». М а р к в а л ь д (М а г k w a 1 d S.) [1954j Zur Theoric der konstruktiven Wohlordnungen, Math. Ann. 127, 135—149. М а р к о в А. А. '[1947 а] Невозможность некоторых алгорифмов в теории ассоциативных си- стем, ДАН СССР 55, 587-590. °[1947b] Невозможность некоторых алгорифмов в теории ассоциативных си- стем, ДАН СССР 58, 353-356. [1954] Теория алгорифмов. Тр. Матем. ин-та АН СССР им. В. А. Стеклова XLII, Изд-во АН СССР. Матиясевич Ю. В. "[1970] Диофантовость перечислимых множеств, ДАН СССР 191, 279—282. Мендельсон (Mendelson E.) [1956 а| Some proofs of independence in axiomatic set theory, J. Symbolic Lo- gic 21, 291-303. [1956b| The independence of weak axiom of choice, там же, 350—366. [1958] The axiom of Fundierung and the axiom of choice, Arch. Math. Logik Orundlagenforsch. 4, 65—70. [1961] On non-standard models for number theory, Essays on the Foundations of Mathematics, Jerusalem, 259—268. Мередит (Meredith С. А.) [1953| Single axioms for the systems (C, N), (C, 0) and (A, N) of the two- valued propositional calculus, J. Compt. Syst. 3, 155—164. М о н v е г ю (М о n t a g u e R.) и В о о т (V а u g h t R. L.) [1959] Natural models of set theories, Fundam. Math, 47, 219—242. Мостовский (Mostowski A). [1939] Ober die Unabhangigkeit des Wohlordnungssatzes vom Ordnungsprin- zip, Fundam. Math. 32, 201—252. [1947 a] On definable sets of positive integers, Pundam. Math. 34, 81—112. [1947 b] On absolute properties of relations, J, Symbolic Logic 12, 33—42. [1949] An undecidable arithmetic statement, Fundam. Math. 36, 143—164. ЛИТЕРАТУРА 303 11951 a1 Some imprcdicative definitions in the axiomatic set theory, F-undam. Math. 37, 111-124 (также 38 (1952), стр. 238). 1951 b] A classification of logical systems, Studia Philosophica 4, 237—274. 1952 a] Sentences undecidable in formalized arithmetic, Amsterdam. 1952 b] On models of axiomatic systems, Fundam. Math. 39, 133—158. 1952с] On direct powers of theories, J. Symbolic Logic 17, 1—31. 1955] The present state of investigations on the foundations of mathematics, Rozprawy Math. 9. [Русский перевод: Мостовский А., Совре- менное состояние исследований по основаниям математики, УМН, 9, № 3 (61) (1954).] [1956] Concerning a problem of Scholz, Z. math. Logik Orundl. Math. 2, 210-214. [1957] On generalization of quantifiers, Fundam. Math. 44, 12—36. [1958] Quelques observations sur 1'usage des methodes nonfinitistes dans la metamathematique, Colloq. Int. Cent. Nat. Rech. Sci., Paris. [1961] A generalization of the incompleteness theorem, Fundam. Math. 49, 205—232. Мучник А. А. '[1956] Неразрешимость проблемы сводимости теории алгоритмов, ДАН СССР 108, 194—197. '[1958] Решение проблемы сводимости Поста и некоторых других проблем теории алгоритмов, Тр. Моск. матем. о-ва 7, 391—405. М ю л л е р.. (М и 11 е г О.) [1961] Ober die unendliche Induktion, Infinitistic Methods, Warszawa, 75—95. Нагорный H. М. [19531 К усилению теоремы приведения теории алгоритмов, ДАН СССР 90, 341-342. фон Нейман (von Neumann J.) [1925] Eine Axiomatizierung der Mengenlehre, J. fiir Math. 154, 219—240. (Исправления, там же 155 (1926), стр. 128.) [1928] Die Axiomatizierung der Mengenlehre, Math. Z. 27, 669—752. H икод (N i с о d J. О.) [1917] A reduction in the number of primitive propositions oi logic, Proc. Cambridge Phil. Soc. 19, 32—41. Нова к (Novak I. L. (G a 1 L. N.)) [1951] A construction for models of consistent systems, Fundam. Math. 37, 87—110. Новиков П. С. °[1943] On the consistency of certain logical calculus, Матем. сб. 12 (54), 231—261. [1955] Об алгоритмической неразрешимости проблемы тождества слов в тео- рии групп, Тр. Матем. ин-та АН СССР им. В. А. Стеклова XLIV, Изд-во АН СССР. °[1959] Элементы математической логики, Физматгиз. Ори (О г е у S.) [1956] On (в-consistency and related properties, J. Symbolic Logic 21, 246—252. [1961] Relative interpretations, Z. math. Logik Grundl. Math. 7, 146—153. П е а н о (Р е a n о О.) ; [1891] Sul concetto di numero, Rivista di Mat. 1, 87—102. П е т е р (Р ё I e r R.) [1935] Konstruktion nichtrekursiver Funktionen, Math. Ann. Ill, 42—60. ]1951] Rekursive Funktionen, Budapest; второе расширенное издание, Buda- pest, 1957. [Русский перевод: Петер Р., Рекурсивные функции, ИЛ, 1954.] Пост (Post E.) [1921] introduction to a general theory oi elementary propositions, Amer. J. Math. 43, 163—185. 304 ЛИТЕРАТУРА [1936] Finite combinatorv processes—tormulation 1. J. Symbolic Logic 1, 103-105. [1943| Formal reductions oi the general combinatorial decision problem, Amer. J. Math. 65, 197—215. 11944] Recursively enumerable sets oi positive integers and their decision problems, Bull. Amer. Math. Soc. 50, 284—316. [1947] Recursive unsolvability of a problem of Thue, J. Symbolic Logic 12, 1—11. П р е с б у р.г ep (Presburger М.) [1929] Uber die Vollstandigkeit eines gewissen Systems der Arithmetik ganzer Zahlen in welchem die Addition als einzige Operation hervortritt, Comptes Rendus, I Congres des Math. des Pays Slaves, Warszawa, 192—201, 395. П у т н а м (Р u t n a m Н.) [1957] Decidability and essential undecidability, J. Symbolic Logic 22, 39—54. Pa б и н (R a b in M.) [1958] On recursively enumerable and arithmetic models oi set theory, J. Symbolic Logic 23, 408—416. [1959] Arithmetical extensions with prescribed cardinality, Indag. Math. 21, 439_446. [1960] Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc. 95, 341—360. [1961] Non-standard models and independence of the induction axiom, Essays in the Foundations of Mathematics, Jerusalem, 287—299. [1962] Diophantine equations and non-standard models oi arithmetic, Logic, Methodology and Philosophy oi Science (Proc. Int. Congr., I960), Stanford, 151—158. [Русский перевод: Р а б и н М., Диофантоиы урав- нения и нестандартные модели арифметики, сб. «Математическая логика и се применения», «Мир», 1965, 176—184.] Райе (Rice Н. О.) (1953] Classes o{ recursively enumerable sets and their decision problems, Trans. Amer. Math. Soc. 74, 358-366. Р а с с н а (R a s i о w а Н.) [1951] Algebraic treatment oi the functional calculi o{ Heyting and Lewis, Pundam. Math. 38, 99—126. [1955] Algebraic models oi axiomatic theories, там же 41, 291—310. [1956] On the e-theorems, там же 43, 156—165. Расёва (Rasiowa Н.) и Сикорский (Sikorski R.) [1951] A prooi of ttie completeness theorem of Godel, Fundam. Math. 37, 193—200. [1952] A proof of the Skolem — Lowenheim theorem, там же 38, 230—232. [1953] Algebraic treatment of the notion of satisfiability, там же 40, 62—95. Рассел (Russell В.) [1908] Mathematical logic as based on the theory of types, Amer. J. Math. 30, 222—262. Рассел (Russell В.) и Уайтхед (WhiteheadA.N.) [1910—1913] Principia Mathematica, тт. 1—111, Cambridge Univ. Press. Робинсон A. (Robinson A.) [1951] On the metamathematics oi algebra, Amsterdam. [1Э52] On the application of symbolic logic to algebra, Int. Cong. Math., Cambridge, Mass. I, 686—694. [1955] On ordered fields and definite functions, Math. Ann. 130, 257—271. [1956] Complete theories, Amsterdam. [1961] Model theory and non-standard arithmetic, Infinitistic Methods, War- szawa, 266—302. '[1963] Introduction to model theory and to the metamathematics of algebra, Amsterdam. [Русский перевод: Робинсон А., Введение в теорию моделей и метаматематику алгебры, «Наука», 1967.] ЛИТЕРАТУРА 305 о б и н с о н Дж. (Robinson ,1.) [19491 Definability and decision problem in arithmetic, J. Symbolic Logic 14, 98—114. 1950| General recursive tLinctions, Proc. Amer. Math. Soc. 1, 703—718. 1952] Existential definability in arithmetic, Trans. Amer. Math. Soc. 72, 437—449. [Русский перевод: Робинсон Дж., Экзистенциальная выоазимость в арифметике, Математика (сб. переводов) 8, № 5 (1964), 3—14.] Робинсон P. (Robinson R. M.) [1937] The theory of classes. A modification of von Neumann's system, J. Symbolic Logic 2, 69—72. [1947] Primitive recursive functions, Bull. Amer. Math. Soc. 53, 925—942. [1948] Recursion and double recursion, там же 54, 987—993. [1950] An essentially undecidable axiom system, Proc. Int. Cong. Math., Cambridge, 1950, 1, 729—730. [1956] Arithmetical representation of recursively enumerable sets, J. Symbolic Logic 21, 162—186. [Русский перевод: Робинсон Р. М., Арифмети- ческое представление рекурсивно-перечислимых множеств, Матема- тика (сб. переводов) 8, № 5 (1964), 23—47.] Роджерс (Rogers H., Jr.) [1956] Theory of recursive functions and effective computability, тт. I—II, MIT, Cambridge, Mass. [1958] G6del numberings of partial recursive functions, J. Symbolic Logic 23, 331—341. [1959] Computing degrees oi unsolvability. Math. Ann. 138, 125—140. Розенблюм (Rosenbloom P.) [1950] Elements oi mathematical logic, New York. Росс ep (R osser J. B.) [1936a] Constructibility as a criterion for existence, J. Symbolic Logic 1, 36—39. |1936b] Extensions of some theorems of Godel and Church, там же, 87—91. 1937] Godel theorems for non-constructive logics, J. Symbolic Logic 2, 129—137. [1939a] On the consistency of Quine's «New foundations for mathematical logic», J. Symbolic Logic 4, 15—24. [1939b] An informal exposition of proofs of Godel's theorem and Church's theorem, там же, 53—60. [1953] Logic for Mathematicians, New York. [1954] The relative strength of Zermelo's set theory and Quine's New Foun- dations, Proc. Int. Cong. Math., Amsterdam, III, 289—294. [1955] Deux esquisses de logique, Paris. Poccep (R osser J. В.) и В а н Хао (Wang Hao) [1950] Non-standard models for formal logics, J. Symbolic Logic 15, 113—129. Poccep (R osser J. В.) и Тюркетт (Turquette A.) [1952] Many-valued logics, Amsterdam. Р ы л л ь-Н ардзевский (Ryl 1-N ardzewski С.) [1953] The role of the axiom of induction in elementary arithmetic, Fundam. Math. 39, 239—263. Саппс (Suppes P.) [1957] Introduction to logic, Van Nostrand, Princeton. [1960] Axiomatic set theory, Van Nostrand, Princeton. Серпинский (Sierpinski W.) [1947] L'hypothese generalisee du continu et 1'axiome du choix, Fundam. Math. 34, 1-5. [1958] Cardinal and ordinal numbers, Warszawa. Сикорский (Sikorski R.) [1960] Boolean algebras, Berlin—Gottingen—Heidelberg, второе издание, 306 ЛИТЕРАТУРА 1964. [Русский перевод: С и к о р с к и и Р., Булевы алгебры, «Мио». 1969.] Сколем (S k о i e m Т.) [1919] Lugisch-kornbinatorische Untersuchungen uber die Erftillbarkeit oder Bcwcisbarkeit mathematischer Satze ncbst einem Theoreme Qber dichte Mengen, Skrifter Vidensk, Kristiania, I, 1—36. [1934] Ober die Nicht-Charakterisierbarkeit der Zahlenreihe mittels endlich odcr abzahlbar unendlich vieler Aussagen mit ausschliesslich Zahlen- variablen, Fundam. Math. 23, 150—161. [1955] Peano's axioms and models of arithmetic, Mathematical Interpretations of Formal Systems, Amsterdam, 1—14. Скотт (Scott D.) [1961] On constructing models for arithmetic, Iniinitistic Methods, Warszawa, 235—255. Спектор (Spector С.) [1955] Recursive well-orderings, J. Symbolic Logic 20, 151—163. [1956] On degrees of recursive unsoivability, Ann. Math. 64, 581—592. С т о у н (S t о n e M.) [1936] The representation theorem for Boolean algebras, Trans. Amer. Math. Soc. 40, 37-111. Тарский (Tarski A.) [1925] Sur les ensembles finis, Fundam. Math. 6, 45—95. [1933] Einige Betrachtungen liber die Begriffe der a-Widerspruchsfreiheit und der a-Vollstandigkeit, Monatsh. Math. Phys. 40, 97—112. [1936] Der Wahrheitsbegriff in den iormalisierten Sprachen, Studia Philos. 1, 261—405. [Также в [1956].] [1938] Ober unerreichbare Kardinalzahlen, Fundam. Math. 30, 68—89. [1944] The semantic conception of truth and the foundations of semantics, Philos. and Phenom. Res. 4, 341—376. [1951] A decision method for elementary algebra and geometry, Berkeley. [1952] Some notions and methods on the borderline of algebra and metama- thematics, Int. Cong. Math,, Cambridge, Mass., 705—720. [1954—1955] Contributions to the theory of models, Indag. Math. 16, 572—588; 17, 56—64. [1956] Logic, Semantics, Metamathematics, Oxford. Тарский (Tarski А.) и BOOT (V aught R.) [1957] Arithmetical extensions of relational systems, Сотр. Math. 18, 81—102. Тарский (Tarski A.), MocTOBCKHti(MostowskiA.)nPo6HHCOHP. (Robinson R.) [1953] Undecidable theories, Amsterdam. Тьюринг (Turing A.) [1936—1937] On computable numbers, with an application to the Entschei- dungsproblem, Proc. London Math. Soc. 42, 230-265; 43, 544—546. [1937] Computability and ^-definability, J. Symbolic Logic 2, 153—163. [1939] Systems of logic based on ordinals, Proc. London Math. Soc. 45, 161—228. [1950a] The word problem in semigroups with cancellation, Ann. Math. 52, 491-505. [1950b] Computing Machinery and Intelligence, Mind 59, 433—460. У л а м (U 1 а т S.) [1930] Zur Masstheorie in der allgemeinen Mengenlehre, Fundam. Math. 16, 140—150. Успенский В. А. •[I960] Лекции о вычислимых функциях, Физматгиз. Феферман (Feferman S.) [1957] Degrees of unsolvability associated with classes of formalized theories, J. Symbolic Logic 22, 161—175. ЛИТЕРАТУРА 307 [1960а1 Arithmetizatio.n. of metarnatheniatics in a general setting, Fundam. Math. 49, 35-92. [1960b| Transfinite recursive progressions of axiomatic theories, Tech. Report No. 2, Appl. Math. & Stat. Lab., Stanford. Феферман (Feferman S.) и BOOT (V aught R.L.) [ 1959] The first order properties of products of algebraic systems, Fundam. Math. 47, 57-103. Феферман (Feferman S.), К p e и с e л (К г e i s e 1 О.) и Ори (О г е у S.) [1961] 1-consistencv and faithful interpretations, Arch. Math. Logik u. Grund- lagenf. 6, 52—63. Ф p e г e (F г e g e G.) [1884] Grundlagen der Arithmetik, Breslau. [1893, 1903] Orundgesetze der Arithmetik, 1, II, Jena. Ф p e н к e ль (F r a e n k e 1 A. A.) [1953] Abstract set theory, Amsterdam (второе издание, 1961). Френкель (Fraenkel А. А.) и Ба р-Х и л л е л (В a r-H i 11 е 1 Y.) [1958] Foundations of set theory, Amsterdam. [Русский перевод: Френ- кель А.иБа р-Х и л л е л И., Основания теории множеств, «Мир», 1966.) Фридберг (Friedberg R.) [1957] Two recursively enumerable sets of incomparable degrees of unsolva- bility, Proc. Nat. Acad. Sci. U. S. A. 43, 236—238. Фридберг (Friedberg R.) и Роджерс (Rogers H., Jr.) [1959] Reducibility and completeness for set of integers, Z. math. Logik Grundl. Math. 5, 117—125. Хазенъегер (Hasenjager G.) [1952] Ober oi-Unvollstandigkeit in der Peano-Arithmetik, J. Symbolic Logic 17, 81—97. [1953] Eine Bemerkung zu Henkins Beweis flir Vollstandigkeit des Pradika- tenkalkills der ersten Stufe, J. Symbolic Logic 18, 42—48. [1960] Unabhangigkeitsbeweise in Mengenlehre und Stuienlogik der Modelle, Jahresber. Deutsch. Math. Ver. 63, 141—162. Хазенъегер (Hasenjager G.) и Шольц (Scholz Н.) [1961] Grundziige der mathematischen Logik, Berlin—Gottingen—Heidelberg. X а л м о ш (H a 1 m о s P.) [1960] Naive set theory, Van Nostrand, Princeton. [1962] Algebraic logic, New York. XanMOiu(HalmosP.) и BooH(Vaughn H.) [1950] The marriage problem, Amer. J. Math. 72, 214—215. X a p т о г с (Н a r t о g s F.) [1915] Ober das Problem der Wohlordnung, Math. Ann. 76, 438-443. Холлман (H oilman М.) [1961] A short proof of an equivalent form of the Schroder—Bernstein theo- rem, Amer. Math. Monthly 68, 770. X и г м е н (Н i g m a n G.) [1961] Subgroups of finitely presented groups, Proc. Roy. Soc., A 262, 455— 475. X и н т и к к a (H i n t i k k a K. J.) [1954] An application of logic to algebra, Math. Scand. 2, 243—246. [1955a] Form and content in quantification theory, Acta Phil. Fcnnica 8, 11—55. [1955b| Notes on the quantilicafion theory, Comment. Phys.-Math., Soc. Sci. Pennica 17, 1—13. [1956] Identity, variables and impredicative definitions, J. Symbolic Logic 21, 225—245. [1957] Vicious circle principle and the paradoxes, J. Symbolic Logic 22, 245—249. 308 ЛИТЕРАТУРА Хлодовский И. Н. [1959] Новое доказательство непротиворечивости арифметики, УМН 14 :№ 6, 105—140. X о л л (Н а 11 М., Jr.) [1949] The word problem for semigroups with two generators, J. Symbolic Logic 14, 115—118. Хон (Hohn F.) [1960] Applied Boolean algebra, New York. Ц e p M e л о (Z e r m е 1 о Е.) [1908] Untersuchungen fiber die Grundlagen der Mengenlehre, I, Math. Ann 65, 261-281. Ч ёр ч (Church A.) [1936а] A note on the Entscheidungsproblem, J. Symbolic Logic 1, 40—41; исправления, там же, 101—102. [1936b] An unsolvable problem of elementary number theory, Amer, J. Math 58, 345—363. [1940] A formulation of the simple theory of types, J. Symbolic Logic 5, 56—68. E1941] The calculi of lambda-conversion, Princeton. 1956] Introduction to mathematical logic, I, Princeton. Русский перевод: Чёрч А., Введение в математическую логику, том I, ИЛ, 1961.] Чёрч (Church А.) и К л и н и (К 1 е е n e S. С.) [1936] Formal definitions in the theory oi ordinal numbers, Fundam. Math. 28, 11—21. Ч e p ч (С h u г с h А.) и К у а и н (Q u i n e W. V.) [1951] Some theorems on definability and decidability, J. Symbolic Logic 17, 179—187. Чудновский Г. В. °[1970] Диофантовы предикаты, УМН 25, № 4, 185—186. Шапиро (Shapiro N.) [1956] Degrees of computability, Tnns. Amer. Math. Soc. 82, 281—299. Шеннон (Shannon С.) [1938] A symbolic analysis of relay and switching circuits, Trans. Amer. Inst. Elect. Eng. 57, 713—723. Ш ё н ф и л ь д (S h о е n f i e I d J.) [1954] A relative consistency proof, J. Symbolic Logic 19, 21—28. [1958] Degrees of formal systems, J. Symbolic Logic 23, 389—392. [1959] On a restricted ю-rule, Bull. Acad. Pol. Sci., Ser. Sci. Math. Astr. Phys. 7, 405-407. Шепердсон (Shepherdson J.) [1951—1953] Inner models for set theory, J. Symbolic Logic, I, 16, 161—190; 11, 17, 225—237; III, 18, 145-167. [1961] Representability of recursively enumerable sets in formal theories, Arch. math. Logic Grundlagenf. 5, 119—127. Шестаков В. И. *[1941] Алгебра двухполюсных схем, построенных исключительно из двухпо- люсников, Журнал физической техники 11, вып. 6, 532—549. Шмелева (Szmielew W.) [1955J Elementary properties of abelian groups, Pundam. Math. 41, 203—271. Ш м и дт (Schm i dt А.) [1960] Mathematische Gesetze der Logik, I, Vorlesungen Ober Aussagenlogik, Berlin—Gottingen—Heidelberg. Ш м у л ь я н (S m u 11 у a n R.) [1961] Theory of formal systems, Princeton. Ш п е к к с p (S p e с k e r E.) [1949] Nicht-konstruktiv beweisbare Satze der Analysis, J. Symbolic Logic 14, 145—148. ЛИТЕРАТУРА 309 [1953] The axiom of choice in Quine's «New Foundations for Mathematical Logic», Proc. Acad. Sci. U. S. A. 39, 972—975. [1954] Verallgemeinerte Kontinuumshypothese und Auswahlaxiom, Archiv der Matli. 5, 332—337. [1957] Zur Axiomatik der Mengenlehre (Fundierungs- und Auswahlaxiom), Z. math. Logik Grundl. Math. 3, 173—210. [1962] Typical ambiguity, Logic, Methodology and Philosophy of Science (Proc. Int. Cong., 1960), Stanford, 116—124. [Русский перевод: Ш п е к к е p Э., Типовая неопределенность, сб. «Математическая логика и ее приме- нения», «Мир», 1965.] Шураньи (Suranyi J.) [1959] Reduktionstheorie des Entscheidungsproblems im Pradikatenkalkiil der ersten Stufe, Budapest. Ш ют те (Schiitte К.) [1951] Beweistheoretische Erfassung der unendlichen Induktion in der Zahlen- theorie, Math. Ann. 122, 369—389. [1960] Beweistheorie, Berlin — Gottingen—Heidelberg. 3p6paH(HerbrandJ.) [1930] Recherches sur la theorie de la demonstration, Travaux de la Soc. des Sci. et des Lettres de Varsovie, HI, 33, 33—160. [1931] Sur le probleme fondamental de la logique mathematique, Comptcs Rend. Warszawa, 24, 12—56. [1932] Sur la non-contradiction de 1'arithmetique, J. f. Math. 168, 1—8. Э рд ё ш (E r d os Р.) и Т а р с к и и (Т a r s k i A.) [1961] On some problems involving inaccessible cardinals, Essays on the Foundations of Mathematics, Jerusalem, 50—82. Эренфойхт (Ehrenfeucht A.) [1957a] On theories categorical in power, Fundam. Math. 44, 241—248. [1957b| Two theories with axiome built by means of pleonasms, J. Symbolic Logic 22, 36—38. [1958] Theories having at least continuum many non-isomorphic models in each infite power (abstract), Notices Amer. Math. Soc. 5, 680. Эренфойхт (Ehrenfeucht А.) и Мостовский (Mostowski A.) [1957] Models of axiomatic theories admitting automorphisms, Fundam. Math. 43, 50—68. Эренфойхт (Ehrenfeucht А.) и Феферман (FefermanS.) [1960] Representability of recursively enumerable sets in formal theories, Arch. math. Logik Grundlagenf. 5, 37—41. Яблонский С. В. "[1958] Функциональные построения в й-значной логике, Тр. Матем. ин-та АН СССР им. В. А. Стеклова, LI, 5—143, Яськовский (Jaskowski S.) [1936] Recherches sur le systeme de la logique intuitioniste, Act. Sci. Ind. 393, Paris, 58—61. Алфавитный указатель Автологическое прилагательное 9 Аккерман (Ackermann W.) 49, 273, 281, 282, 296, 299 Аксиома 36 — бесконечности (аксиома I) 187 — выбора (аксиома АС) 17, 217 — выделения (аксиома S) 186 — замещения (аксиома R) 187 — логическая 65, 66 — множества всех подмножеств (ак- сиома W) 186 — мультипликативная {Mult) 17, 218 — объединения (аксиома U) 185 — объемности (аксиома Т) 179 — ограничения (аксиома D) 221 — пары (аксиома Р) 179 — пустого множества (аксиома N) 179 — собственная (или нелогическая) 66 — фундирования 221 Аксиоматическая теория множеств 10, 177 Аксиомы существования классов 181 Алгебра Линденбаума 52,'113, 114 — полиадическая 114 — цилиндрическая 114 Алгорифм в алфавите 229 — Маркова 230 —над алфавитом 229 —, применимость к слову 229 — рекурсивный 246 — Тьюринга 252 — удваивающий 233, 251 Алфавит 229 — машины Тьюринга 251, 253 Арифметизация 152 Арифметика мощностей 214 — формальная 115 Ассер (Asser G.) 260, 296 Атомарное высказывание 23, 24 Бар-Хиллел (Bar-Hillel Y.) 227, 307 Бахман (Bachmann H.) 217, 295, 296 Бернайс (Bernays P.) 10, 65, 93, 96, 108, 111, 112, 131, 165, 177, 224— 226, 276, 295, 296, 299 Бернштейн (Bernstein F.) 8, 15, 201, 208, 214, 217 Берри (Berry G. D. W.) 9, 160 Бесконечная индукция (правило вы- вода системы Sy) 283 Бесскобочная система записи 28 Бет (Beth E. W.) 75, 78, 109, 170, 296 Биркгоф (Birkhoff G.) 297 Брауэр (Brower L. E. J.) 10 Брёйн, де (Bruijn N., de) 110, 297 Бриттон (Britton J. L.) 279, 297 Буква 229 — предикатная 54 — пропозициональная 22, 38 — функциональная 54, 261 — — вспомогательная 261 — — главная 261 — — начальная 261 Булева алгебра 17, 52 Бун (Boon W.) 279, 297 Бурали-Форти (Burali-Forti С.) 8, 188 Бурбаки (Bourbaki N.) 104, 297 Вайсберг (Wajsberg M.) 93, 297 Ван дер Варден (Waerden В., van tier) 108, 297 Ван Хао (Wang Hao) 115, 160, 227, 297, 300, 305 Введение новых функциональных букв и предметных констант 93 — фиктивных переменных 136 Взаимно однозначное соответствие 15 — однозначно эквивалентные множе- ства 276 Виноградов И. M. 130, 141, 297 Включение 11, 177 Внутреннее состояние машины Тью- ринга 251, 253 Внутренняя модель 224 АЛФАВИТНЫЙ УКАЗАТЕЛЬ 311 Возведение-в степень для порядковых чисел 197 Возвратная рекурсия 145 Возвращающая а-последовательность 226 Воон (Vaughn H.) 110, 307 BOOT (Vaught R.) 106, 108, 226, 297, 302, 306, 307 Вопенка (Vopenka P.) 225, 297 Вполне упорядочение 17 — эквивалентные алгорифмы 235 Вторая 8-теорема 111 Вхождение переменной свободное 55 — — связанное 55 Вывод 36, 39 — в системе S^ 285 — из гипотез (посылок) 37 — равенства 261 Выполнимая формула 62 Выполнимость 58 Выражение 36 Выразимое в теории S арифметическое отношение (предикат) 132 Вычисление машины 253 Галлер (Galler В. А.) 298 Гальперн (Halpern J. D.) 114 Гёдель (Gndel К.) 10, 11, 51, 65, 75, 78, 91, 146, 152, 159—161,163—166, 173, 176, 177, 225, 227, 250, 261, 262, 265, 267, 273, 280, 282, 298 Гёделев номер 151 — — выражения 151 — — поледовательности выражений 152 — — символа 151 Гейтинг (Heyting A.) 10, 52, 298 Генкин (Henkin L.) 75, 105, 108, 114, 298 Генцен (Gentzen G.) 165, 282, 295, 298 Гермес (Hermes H.) 250, 260, 299 Гетерологическое прилагательное 9 Гжегорчик (Grzegorczyk A.) 299 Гильберт (Hilbert D.) 49, 65, 93, 108, 110—112, 131, 165, 228, 295, 299 Гипотеза 37 Граф 109 График функции 135 Греллинг (Grelling К.) 9 Двойник буквы 236 Девис (Davis M.) 255, 299 Дедекинд (Dedekind R.) 115, 116, 204 206, 207, 277, 299 Декартова степень 12, 184 Декартово произведение 12, 184, 220 — — классов 184 распространение алго- Декартово произведение .1-кратное 12, 184 Деккер (Dekker J.) 277, 299 Делимость 128 Дерево вывода 284 Десятая проблема Гильберта 228 Детловс В. К. 299 Дизъюнктивная нормальная форма 34 — — — совершенная 35 Дизъюнктивный член 20 Дизъюнкция 20 — отрицаний (alternative denial) 34, 51 Диксон (Dixon L. E.) 299 Дирихле (Dirichlet P. G. L.) 130 Длина выражения 61 Дополнение 181 Допустимое определение 174 Дребен (Dreben В.) 78, 299 Евклид 228 Естественное рифма 237 Зависимость в выводе 69 Заключение 20, 283 Заключительная вершина 283 — формула 285 Закон исключенного третьего 10 Замыкание формулы 60 Зейденберг (Seidenberg A.) 299 Зиман (Zeeman E. G.) 226, 299 Идеал 17 — максимальный 18 — собственный 18 Изоморфные интерпретации 102 — множества 276 Импликация 20 Индекс рекурсивного предиката 267 — рекурсивно перечислимого множе- ства 275 — частично рекурсивной функции 267 Индуктивное предположение 16 Индукция по х 16 — трансфинитная 17, 193, 195 Интерпретация 57 Интуиционизм 10, 11 Интуиционистское исчисление высказы- ваний 51 Истинностная таблица 19 — — сокращенная 23 — функция 22, 24 Истинностное значение 19 — — выделенное 47 История формулы 29] Исходные функции 1.35 АЛФАВИТНЫЙ УКАЗАТЕЛЬ 312 Исчисление высказываний 19 — предикатов первого порядка 66 — — — — насыщенное (PF) 172 — _ _ — чистое (РР) 172 Кальмар (Kalinar L.) 45, 174, 299 Камке (Kamke E.) 103, 104, 299 Кантор (Cantor G.) 8, 188, 202 Кардинальное число 8, 15, 203, 221, 224 Карнап (Carnap R.) 39, 300 Карри (Curry H. В.) 300 Квантификация 283 Квантор всеобщности 53 — ограниченный 139 — существования 53, 55, 235 Кемени (Kemeny J.) 300 Кёниг (Konig J.) 110 Китайская теорема об остатках 151 Класс 178 — бесконечный 204 — — по Дедекинду 204 — взаимно однозначный 187 — всех подмножеств 184 — однозначный 186 — счетный 204 — транзитивный 190 — /^-эквивалентности 13 Клини (Kleene S. С.) 11, 49, 50, 52, 65, 96, 152, 170, 202, 250, 260, 261, 263, 266, 268, 279, 300, 308 Команда 252, 253 Композиция алгорифмов 236 — функций 14, 199 «Конечная» аксиома выбора 220 Конечное расширение теории 171 Контрапозиция 28 Контрфактическое условное предложе- ние 21 Конфигурация 253 Конъюнктивная нормальная форма 35 — — — совершенная 35 Конъюнктивный член 19 Конъюнкция 19 — отрицаний (joint denial) 33 Коэн (Cohen P. J.) 225, 300 Крейг (Craig W.) 300 Крейдер (Kreider D. L.) 300 Крейсел (Kreisel G.) 301, 307 Куайн (Quine W. V.) 10, 21, 22, 39, 227, 301, 308 Куратовский (Kuratowski К.) 180 Ладриер (Ladriere L.) 301 Ландау (Landau E.) 115, 116, 301 Лёб (Lob M. H.) 301 Лёвенгейм (Lowenheim L.) 79, 92, 301 Леви (Levy A.) 226, 301 Лемма Линденбаума 74, 105 — Тайхмюллера — Тьюки 220 — Цорна 218 Aen"hop.1 (Langford С. H.) 107, 301 Лента 251 Линденбаум (Lindenbaum A.) 52, 74 105, 113, 114 Линдон (Lyndon R. С.) 301 Литерал 35 Логика 7 — двузначная 48 — математическая 7, 11 — многозначная 48 Логически истинное высказывание 26 — — предложение 63 — ложное высказывание 26 — — предложение 63 — общезначимая формула 62 — эквивалентные пропозициональные формы 25 — — формулы 62 Логическое следствие 25, 62 Лойхли (Lauchli H.) 301 Лоренцен (Lorenzen P.) 282, 301 Aocb(fcosJ.) 103, 110, 112, 114,301,302 Люксембург (Luxemburg W. A. J.) 302 Майхилл (Myhill J.) 276, 277, 299, 302 Макдоуэлл (Macdowell R.) 302 Мак-Кинси (McKinsey J. С. С.) 48, 302 Маклафлин (Maclaughlin T.) 302 Мак-Нотон (McNaughton R.) 227, 297 Максимальный элемент класса 206 Мальцев А. И. 302 Марков А. А. 229, 230, 235, 242, 244, 248—250, 255, 256, 260, 279, 280, 302 Массовая проблема 278 — — неразрешимая 278 Матиясевич Ю. В. 228, 302 Машина Тьюринга 251—253 — —, вычисление частичной арифме- тической функции 254 — —, остановка при конфигурации а 253 — —, перевод конфигурации а в кон- фигурацию р 253 Мендельсон (Mendelson E.) 222, 225, 302 Мередит (Meredith С. А.) 51, 302 Метаматематика 39 Метатеорема 39 Метаязык 39 Метод бесконечного спуска 128 — последовательного исключения кванторов существования 107, 108 АЛФАВИТНЫЙ УКАЗАТЕЛЬ 313' Минимальный элемент класса 206 Множество 7, 11, 178 — бесконечное 15 — взаимно однозначно сводимое 276 — вполне упорядоченное 17 — всех подмножеств 186 — выбирающее 218 — выбора 17 — значений бинарного отношения 13 — изолированное 277 — иммунное 277 — конечное 15, 203 — — по Дедекинду 206 — креативное 276 — не более чем счетное 15 — однозначно сводимое 276 — одноэлементное 12 — примитивно рекурсивное 140 — продуктивное 277 — простое 276 — пустое 12, 179, 180 — рекурсивное 140 — рекурсивно перечислимое 273 — счетное 15 Модель 59 — нестандартная 121, 131 — нормальная 91 — стандартная 121 — счетная 75 Монтегю (Montague R.) 226, 302, 307 Морли (Morley M. D.) 104 Мостовский (Mostowski A.) 171, 174, 175, 179, 213, 227, 268, 299, 302, 306, 309 Мощность 15, 203, 221 — континуума !5 Мучник А. А. 303 Мюллер (Miiller G.) 295, 303 Нагорный H. M. 251, 303 Наибольшее из двух чисел 137 Наименьшее из двух чисел 137 Начальная вершина 283 Независимое подмножество аксиом 46 Независимость 46, 92, 93 — аксиомы выбора 225 — обобщенной континуум-гипотезы 225 Нейман, фон (Neumann J., von) 10, 177, 222, 303 Нелогическая константа 175 Непересекающиеся множества 12 Непосредственное следствие 36 Непосредственно следующее порядко- вое число 193 — — число 115 Непротиворечивость 45 — исчисления предикатов 68, 92 Непротиворечивость формальной ариф- метики 282 Неразрешимое предложение 161 Никод (Nicod J.) 51, 303 Нить дерева вывода 285 Новак (Novak J. L. (Gal L. N.)) 227, 303 Новиков П. С. 279, 282, 303 Нормальная композиция алгорифмов 237 — форма Сколема 100 Нормальный алгорифм 230 — — замкнутый 235 — — над алфавитом 232 — — проектирующий 237 — — универсальный 248 Нуль-функция 133, 135 Нумерация рекурсивно перечислимых множеств 275 — частично рекурсивных функций 267 Область действия квантора 54 — значений 185 — интерпретации 57 — определения 13, 181 Обобщенная континуум-гипотеза 225 — теорема о полноте 112 Обобщенные теории первого порядка 104 Образ 14 Обращение слова 231 Объединение 12, 181 — всех элементов класса 184 Ограничение областью 186 — функции 14 Ограниченные произведения 138 — сумм.ы 138 Однозначно эквивалентные множества 276 Операция 14 Ори (Orey S.) 303, 307 Ослабление (правило вывода системы SJ 283 Остаток от деления 137 Относительное дополнение 12 Отношение 12, 184 — бинарное 12 — вполне упорядочивающее 17, 190 — иррефлексивное 189 — обратное 13, 185 — порядка 190 — — в системе S 125 — примитивно рекурсивное 139 — принадлежности 190 — рекурсивное 139 — рефлексивное 13 — связное 189 — симметричное 13 314 АЛФАВИТНЫЙ УКАЗАТЕЛЬ Отношение тождества 13, 184 — транзитивное 13, 189 — эквивалентности 13 — n-местное 12 — fX вполне упорядочивает У» 189 — <:Х упорядочивает Y» 189 — «X частично упорядочивает У» 189 Отображение в 14 — на 14 — подобное 189 Отождествление переменных 136 Отрицание 19 — (правило вывода системы S^) 283 Павел, апостол 8 Пара 12 — 'неупорядоченная 12, 179 — упорядоченная 12, 180, 184 Парадокс 7—10 — Берри 9 — Бурали-Форти 8 — Греллинга 9 — Кантора 8 — критянина 8, 9 — лжеца 8 — логический 7, 8 — Рассела 7, 8, 188 — Ришара 9 — семантический 8—10 — Сколема 202 Параметры рекурсии 135 Пеано (Peano G.) 115, 116, 131, 303 Перевод 250 Переименование связанных перемен- ных 83 Пересечение 12, 181 Перестановка (правило вывода систе- мы S^) 282 — переменных 136 Петер (Peter R.) 273, 303 Повторение алгорифма 240 Подмножество 11 — собственное 12 Подобно упорядоченная структура 189 Подобные формулы 72 Подстановка 133, 135 Поле класса 190 — отношения 13 Полная индукция 127 — система связок 31 Полное повторение алгорифма 241 Порядковое число 191 — — второго рода 194 — — конечное 194, 203 — — начальное 207 — — недостижимое '226 — — предельное 194 Порядковое число регулярное 226 — — сильно недостижимое 226 — — сингулярное 226 — — слабо недостижимое 226 Порядковый класс 191 Порядок дерева вывода 285 Последовательность конечная 15 — счетная 15 — Фибоначчи 145 Пост (Post E.) 250, 278, 279, 303 Посылка 20, 37, 283 Правило вывода 36 — — для равенств 261 — — системы S^ 282, 283 — _ _ -- сильное 283 — — — — слабое 282 — — теории первого порядка 66 — де Моргана 283 — дизъюнкции 81 — индивидуализации (правило А4) 81 — индукции 116 — конъюнкции 81 — подстановки 135 — рекурсии 135 — существования (правило Е4) 81 — С 84, 85 — Gen 66 Предваренная нормальная форма 96 Предикат арифметический 151 — рекурсивный 150 Предложение 39 Предметная константа 54 — переменная 54 Представимая в теории S арифметиче- ская функция 132, 133 Представляющее отношение 135 Предшественник вершины 283 Пресбургер (Presburger M.) 131, 281, 304 Прибавление единицы (N (х)) 133, 135 Примитивная связка 38, 48, 49 Принцип вполне упорядочения (W.O.) 17, 218 — двойственности 28 — индукции 115, 127 — максимальности Хаусдорфа 220 — математической индукции 16, 116 — наименьшего числа 127 — нормализации 249 — полной индукции 16, 17, 127 — трансфинитной индукции 195 Проблема остановки машины Тьюрин- га 280 — разрешения 279 Проектирующая функция 133, 135 Проекция слова на алфавит 237 Прообраз Г4 АЛФАВИТНЫЙ УКАЗАТЕЛЬ 315 Пропозициональная буква 22, 38 — связка 22 — — бинарная 27 — — главная 23 — форма 22 — — выделенная 48 Противоречие 25, 62 Пустое слово 229 Путнам (Putnam H.) 277, 299, 304 Рабин (Rabin M.) 170, 304 Равенство 261 — в теории множеств 177 Равномощные классы 199 — множества 15 Разветвление алгорифмов 240 Райе (Rice H. G.) 304 Ранг 223 Расёва (Rasiowa H.) 75, 78, 111, 112, 304 Рассел (Russell В.) 7, 10, 188, 304 Расширение алфавита 229 — теории 74 Рекурсивная неразрешимость 173 — перестановка 276 Рекурсивно эквивалентные множества 277 Рекурсия 135 Ришар (Richard J.) 9, 160 Робинсон A. (Robinson A.) 109, 110, 304 Робинсон Дж. (Robinson J.) 299, 304 Робинсон P. (Robinson R.) 10, 166, 169, 171, 174, 175, 177, 213, 273, 305, 306 Роджерс (Rogers H., Jr.) 270, 278, 280, 300, 303, 305, 307 Розенблюм (Rosenbloom P.) 114, 305 Poccep (Rosser J. В.) 10, 11, 39, 49, 50, 85, 96, 161, 163, 164, 227, 295, 305 Рылль-Нардзевский (Ryll-Nardzew- ski С.) 114, 170, 299, 302, 305 Cannc (Suppes P.) 39, 227, 305 Свободная переменная 56 Свойство 12 Связанная переменная 56 Связка «если .... то ...» 20 — «и» 19 — «или» 20 — — в разделительном и соединитель- ном смысле 20 —, соответствующая данной таблице истинности 48 Сегмент 190 Семантические концепции и построе- ния 65 Семнадцатая проблема Гильберта 110 Серпинский (Sierpinski W.) 104, 216, 217, 225, 305 Сечение (правило вывода системы S ) 283 — класса 190 Сикорский (Sikorski R.) 18, 75, 78, 112, 113, 304, 305 Сильно Представимая в S функция 133 Символ ленты 251 — теории 36 Синтаксические концепции и построе- ния 65 Система аксиом Пеано 115 — равенств 261 — Р. Робинсона 169 — New Foundations (NF) 10, 227 Скобки, экономное употребление 27, 55 Сколем (Skolem T.) 79, 92, 100, 202, 227, 305 Скотт (Scott D.) 306 Следование 20 Следствие 37 Слово 229 —, вхождение в слово 230 Сложение 116 — порядковых чисел 196 Собственное включение 177 Собственный класс 178 Совместимость аксиомы выбора 225 — обобщенной континуум-гипотезы 225 Совместимые теории 171 Соединение алгорифмов 237 — слов 229 Сокращение (правило вывода системы S„) 282 Спектор (Spector С.) 306 Степень дерева вывода 285 — сечения 283 Стоун (Stone M.) 112, 306 Сужение модели 91 Схема аксиом 38 — алгорифма 230 Тавтология 24 Тайхмюллер (Teichmuller О.) 220 Тарский (Tarski A.) 11, 48,58,65, 108, 114, 171, 174, 175, 206,213,226,281, 298, 302, 306, 309 Тезис Чёрча 164, 249, 250 Теорема Гёделя вторая 165 — — в форме Россера 161 — — для теории S 159 — — о полноте 78, 91 АЛФАВИТНЫЙ УКАЗАТЕЛЬ 316 Теорема дедукции 40, 70 — Кантора 8, 202 — о булевом представлении 112 — — замене 83 — — максимальном идеале 112 — — полноте (для L) 44 — — существовании классов 182 — системы S . 285 0^ — Сколема — Лёвенгейма 79, 92 — Тарского 168 — формальной теории 36 — Хартогса 207 — Чёрча 173 — Шредера — Бернштейна 8, 15, 201 — эквивалентности 82 Теории высших порядков 65 Теория абсолютно непротиворечивая 45 — аксиоматическая 36 — алгебраически замкнутых полей ха- рактеристики р 110 — групп 67 — достаточно сильная 175 — интерпретируемая (в другой тео- рии) 175 — коммутативных групп с однознач- ным делением 103, 104 — непротиворечивая 45 — неразрешимая 37 —• относительно интерпретируемая (в другой теории) 175 — первого порядка 65 — — — полная 73 — — — с равенством 86 — — — m-категоричная 103 —, подходящая для данной логики 48 — разрешимая 37 — рекурсивно аксиоматизируемая 163 — — неразрешимая 168 — существенно неполная 164 — — рекурсивно неполная 170 — — — неразрешимая 168 — типов 10, 227 — формальная 25, 36 — частичного упорядочения 67 — эффективно аксиоматизированная 36 — й-неполная 160 — о-непротиворечивая 158 Терм 54, 261 — замкнутый 76 —, свободный для переменной в фор- муле 56 Тихонов А. Н. 110 Томпсон (Thompson F. В.) 114 Точное описание (definite description) 96 Транзитивное замыкание 222 Трихотомия (Trick) 218 Тьюки (Tukey J. W.) 220 Тьюринг (Turing A. M.) 251—257, 260 261, 280, 306 Тюркетт (Turquette A. R.) 48, 305 Уайтхед (Whitehead A. N.) 10, 304 Уитекер (Whitaker J.) 201 Улам (Ulam S.) 226, 306 Умножение 116 — порядковых чисел 196, 197 Универсальная выбирающая функция 221 Универсальный класс 181 Упорядочение 16 — полное 16 — рефлексивное 16 — частичное,16, 67 — — рефлексивное 16 Упорядоченная структура 189 — га-ка 12, 181, 184 Упорядочиваемая группа 110 Фейс (Feys R.) 300 Ферма (Format P.) 143 Феферман (Feferman S.) 108, 165, 166, 277, 306, 307, 309 Фибоначчи (Fibonacci, Leonardo Pisa- no) 145 Финитные методы 39 Формальное расположение алгорифма 237 Формула 36, 38, 54 — боковая 283 — выделенная 46 —, выполнимость на последовательно- сти 59 — главная 283 — гротескная 47 — двойственная 83 — замкнутая 57 —, истинная в данной интерпретации 59 — корректная 282 —, ложная в данной интерпретации 59 — некорректная 282 — подстановки 229 — — заключительная 230 — — простая 229, 230 — предикативная 182 — секущая 283 — элементарная 54 — fe-общезначимая 93 Фреге (Frege G.) 307 Френкель (Fraenkel A. A.) 225, 227, 307 Фридберг (Friedberg R.) 307 АЛФАВИТНЫЙ УКАЗАТЕЛЬ 317 Функция 13, 186 — взаимно однозначная 14 — всюду определенная 14 — выбирающая 217 —, вычислимая по Маркову 235 —, — — Тьюрингу 254 —, — — Эрбрану — Гёделю (ЭГ-вы- числимая) 262 —, — с помощью системы равенств 262 — на множестве 14 — общерекурсивная 136 — от п аргументов 14 — потенциально рекурсивная 276 — примитивно рекурсивная 136 — рекурсивная 136 — характеристическая 134 — частичная 14 —, частично вычислимая по Маркову 235 — — рекурсивная 235 — эффективно вычислимая 228 Хазенъегер (Hasenjager G.) 65, 75, 176, 307 Халмош (Xalmos P.) 110, 114, 307 Характеристика поля 108 Хартогс (Hartogs F.) 207, 307 Хаусдорф (Hausdorff F.) 220 Хеллман (Hellman M.) 201, 307 Хигмен (Higman G.) 279, 307 Хинтикка (Hintikka К. J.) 75, 78, 307 Хлодовский И. Н. 282, 307 Холл (Hall M., Jr.) 308 Хон (Hohn F.) 29, 308 Цепь 218 Цермело (Zermelo E.) 10, 225, 227, 308 Цифра 121, 231, 261 Цорн (Zorn M.) 218 Частное 137 Частный случай пропозициональной формы 60 Чёрч (Church A.) 11, 39, 51, 65, 164, 173, 174, 227, 250, 308 Чистое исчисление одноместных пре- дикатов 174 — — предикатов (первого порядка) 99, 172 Читающая головка 251 Чудновский Г. В. 228, 308 Шапиро (Shapiro N.) 308 Шеннон (Shannon С.) 29, 308 Шёнфильд (Shoenfield J.) 227, 295, 308 Шепердсон (Shepherdson J.) 226, 308 Шестаков В. И. 29, 308 Шмелева (Szmielew W.) 108, 281, 308 Шмидт (Schmidt A.) 308 Шмульян (Smullyan R.) 152, 213, 277, 308 Шольц (Scholz H.) 65, 176, 307 Шпеккер (Specker E.) 225, 227, 302, 308 Шредер (Schroder E.) 8, 15, 201, 208, 214, 217 Штрих Шеффера 34 Шураньи (Suranyi J.) 281, 309 Шютте (Schutte К.) 165, 282, 291, 295, 309 ЭГ-вычислимая функция 262 Эквивалентность 21 Эквивалентные алгорифмы 235 Элемент множества 8, 11 — /^-наименьший 17 Элементарная теория 65 — — абелевых групп 90 — — групп 89 — — коммутативных колец с едини- цей 90 — — плотно упорядоченных множеств без первого и последнего элементов 89 — — полей 90 — — равенства 89 — — упорядоченных полей 90 Эпименид 8, 9 Эрбран (Herbrand J.) 40, 78, 250, 261, 309 Эрдёш (Erdos P.) 110, 226, 297, 309 Эренфойхт (Ehrenfeucht A.) 131, 277. 309 Эффективная неразрешимость 173 Эффективность 64 Яблонский С. В. 29, 309 Язык-объект 39 Яськовский (Jaskowski S.) 52, 309 /'-свободный образ 94 Modus ponens 38 Reduktionssatz Шютте 291 а-последовательность 226 Р-функция Гёделя 146 Г-дерево 283 i-терм 96 ^-вычислимость 250 ^-оператор 135 — ограниченный 139 г-отношение 181