Logical Labyrinths

Logical Labyrinths Logical Labyrinths Raymond M. Smullyan A K Peters, Ltd. Wellesley, Massachusetts Editorial, Sales, and Customer Service Office A K Peters, Ltd. 888 Worcester Street, Suite 230 Wellesley, MA 02482 www.akpeters.com c 2009 by A K Peters, Ltd. Copyright  All rights reserved. No part of the material protected by this copyright notice may be reproduced or utilized in any form, electronic or mechanical, including photocopying, recording, or by any information storage and retrieval system, without written permission from the copyright owner. Library of Congress Cataloging-in-Publication Data Smullyan, Raymond M. Logical labyrinths / Raymond M. Smullyan. p. cm. Includes bibliographical references and index. ISBN 978-1-56881-443-8 (alk. paper) 1. Logic, Symbolic and mathematical. 2. Mathematical recreations. 3. Puzzles. I. Title. QA9.S575 2009 511.3–dc22 2008039863 Printed in Canada 13 12 11 10 09 10 9 8 7 6 5 4 3 2 1 Contents Preface I ix Be Wise, Generalize! 1 1 The Logic of Lying and Truth-Telling 2 Male or Female? 17 3 Silent Knights and Knaves 21 4 Mad or Sane? 25 5 The Difficulties Double! 31 6 A Unification 37 II Be Wise, Symbolize! 3 41 7 Beginning Propositional Logic 43 8 Liars, Truth-Tellers, and Propositional Logic 55 9 Variable Liars 67 10 Logical Connectives and Variable Liars 73 11 The Tableau Method 83 12 All and Some 99 13 Beginning First-Order Logic v 111 Contents vi III Infinity 133 14 The Nature of Infinity 135 15 Mathematical Induction 157 ¨ 16 Generalized Induction, Konig’s Lemma, Compactness 173 IV Fundamental Results in First-Order Logic 189 17 Fundamental Results in Propositional Logic 191 18 First-Order Logic: Completeness, Compactness, ¨ Skolem-Lowenheim Theorem 205 19 The Regularity Theorem 217 V Axiom Systems 227 20 Beginning Axiomatics 229 21 More Propositional Axiomatics 245 22 Axiom Systems for First-Order Logic 267 VI More on First-Order Logic 275 23 Craig’s Interpolation Lemma 277 24 Robinson’s Theorem 285 25 Beth’s Definability Theorem 291 26 A Unification 297 27 Looking Ahead 309 References 321 Index 323 Preface This book serves as a bridge from all my previous recreational puzzle books to all my technical writings in the fascinating field of