Problems in Set Theory, Mathematical Logic and the Theory of Algorithms

by Lavrov, Igor A.; Maksimova, L. L.; Corsi, G.; Corsi, Giovanna

• ISBN13: 9780306477126
• ISBN10: 0306477122
• Format: Hardcover
• Copyright: 2003-03-31
• Publisher: Plenum Pub Corp

Summary

Problems in Set Theory, Mathematical Logic and the Theory of Algorithms by I. Lavrov & L. Maksimova is an English translation of the fourth edition of the most popular student problem book in mathematical logic in Russian. It covers major classical topics in proof theory and the semantics of propositional and predicate logic as well as set theory and computation theory. Each chapter begins with 1-2 pages of terminology and definitions that make the book self-contained. Solutions are provided. The book is likely to become an essential part of curricula in logic.

Table of Contents

Preface	vii
I Problems	1	(166)
Set theory	3	(48)
Operations on sets	3	(8)
Relations and functions	11	(8)
Special binary relations	19	(11)
Cardinal numbers	30	(4)
Ordinal numbers	34	(10)
Operations on cardinal numbers	44	(7)
Mathematical logic	51	(84)
Algebra of propositions	51	(9)
Truth functions	60	(7)
Propositional calculi	67	(12)
The language of predicate logic	79	(9)
Satisfiability of predicate formulas	88	(8)
Predicate calculi	96	(11)
Axiomatic theories	107	(11)
Reduced products	118	(8)
Axiomatizable classes	126	(9)
Theory of algorithms	135	(32)
Partial recursive functions	135	(13)
Turing machines	148	(6)
Recursive and recursively enumerable sets	154	(6)
Kleene and Post numberings	160	(7)
II Solutions	167	(104)
Set theory	169	(34)
Operations on sets	169	(5)
Relations and functions	174	(5)
Special binary relations	179	(6)
Cardinal numbers	185	(5)
Ordinal numbers	190	(8)
Operations on cardinal numbers	198	(5)
Mathematical logic	203	(46)
Algebra of propositions	203	(4)
Truth functions	207	(5)
Propositional calculi	212	(5)
The language of predicate logic	217	(2)
Satisfiability of predicate formulas	219	(6)
Predicate calculi	225	(3)
Axiomatic theories	228	(7)
Reduced products	235	(4)
Axiomatizable classes	239	(10)
Theory of algorithms	249	(22)
Partial recursive functions	249	(7)
Turing machines	256	(4)
Recursive and recursively enumerable sets	260	(5)
Kleene and Post numberings	265	(6)
References	271	(4)
Index	275