EATCS Monographs on Theoretical Computer Science Editors: W. Brauer G. Rozenberg A. Salomaa Advisory Board: G. Ausiello M. Broy S. Even J. Hartmanis N. Jones T. Leighton M. Nivat C. Papadimitriou D. Scott Gunther Schmidt Thomas Stroh1ein Relations and Graphs Discrete Mathematics for Computer Scientists With 203 Figures Springer-Verlag Berlin Heidelberg New York London Paris Tokyo Hong Kong Barcelona Budapest Authors Gunther Schmidt Fakultat fiir Informatik, Universitat der Bundeswehr Miinchen Wemer-Heisenberg-Weg 39, W-8014 Neubiberg, FRG Thomas Strohlein Fakultat flir Informatik, Technische Universitat Miinchen Postfach 20 24 20, W-8000 Miinchen 2, FRG Editors Wilfried Brauer Fakultat flir Informatik, Technische Universitat Miinchen Arcisstrasse 21, W-8000 Miinchen 2, FRG Grzegorz Rozenberg Institute of Applied Mathematics and Computer Science University of Leiden, Niels-Bohr-Weg 1, P.O. Box 9512 2300 RA Leiden, The Netherlands Arto Salomaa The Academy of Finland Department of Mathematics, University of Turku SF-20 500 Turku, Finland Improved, extended and translated (in cooperation with Tilmann Wiirfel) from the German version Relationen und Graphen (ISBN 3-540-50304-8) which appeared in 1989 in the Springer series Mathematikfiir Informatiker, edited by F. L. Bauer CR Subject Classification (1991): G.2, B.6, F.3.1-2, D.2.4, I.2.2 Mathematics Subject Classification (1991): 00-01, 00A06, 03B70, 03GI5, 05-01, 05C50, 68Q55, 68Q60, 68RlO ISBN-13: 978-3-642-77970-1 e-ISBN -13: 978-3-642-77968-8 DOl: 10.1007/978-3-642-77968-8 This work is suhject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer, Verlag. Violations are liable for prosecution under the German Copyright Law. © Springer-Verlag Berlin Heidelberg 1993 Softcover reprint of the hardcover 1s t edition 1993 The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The authors compiled the text on a Macintosh with the TEX program Textures; figures were arranged by Canvas and MacPaint; print-outs were provided by a Hewlett-Packard LaserJet IIISi. 45/3140 -5432 I 0 -Printed on acid-free paper Preface Applications of mathematics in other sciences often take the form of a network of relations between certain objects. But in this situation one seldom does "cal culations", in contrast to problems involving mathematical analysis, although a sufficiently developed theory of relations together with a practicable calculus has been in existence for a long while. The mathematical treatment of relations is said to have its origin in Aristotle, but its modern story starts with the contributions of George Boole, Augustus de Morgan, and Charles S. Peirce. Their work was continued in a systematic way notably by Ernst Schroder who around 1890 published his three volumes of Algebra der Logik. In the preface he wrote!: "The merit is particularly due to Mr. Peirce for having built the bridge between the older, merely verbal treatment of that discipline and the new, mathematical one." This new treatment was promoted by Leopold Lowenheim who, in view of the recently arisen paradoxes in set theory, suggested "schroderizing" the whole of mathematics. Half a century later Alfred Tarski, Jacques Riguet, and J. C. C. McKinsey, among others, laid the foundations for the modern calculus of relations, but there has been no easily accessible textbook on the subject as yet. It is our aim to present the theory of relations and to give many applications of their calculus. The subjects to be treated include graphs, combinatorics (e.g., the matching problem), games such as chess and nim, the basics of the relational data base concept, and an extensive discussion of verification and correctness for programs. But we shall also give applications to more abstract areas such as the principle of transfinite induction. Reading this book requires few prerequisites. The student who has absorbed the introductory mathematics courses in his or her field should be able to read the bulk of every chapter. The later sections of some chapters may be harder, though. The number of applications and examples may even make the book a suitable text for nonexperts. In conjunction with the manuscript the formula manipulation system RALF has been developed over the past years. It comprises by now all the formulas de rived in the text, and a number of proofs have been checked with it. The system RELVIEW, in addition, allows fast and flexible calculations with Boolean ma trices; product spaces together with their projection relations as well as function spaces can easily be manipulated. We have not attempted to give a complete bibliography. The original literature on relation algebra often differs with regard to notation and assumptions so as to render quick comparison difficult. Moreover, much of this literature pursues ! "Namentlich gebiihrt Herrn Peirce das Verdienst, die Briicke von den iilteren, bloB verba len Behandlungen jener Disziplin zu der neuen rechnerisch zu Werke gehenden geschlagen zu haben." vi Preface goals more purely mathematical in nature than the applications we have in mind. Nevertheless, we have taken care to mention all the relevant literature which precedes our approach or which we took as a model, including some items of historical interest. The writing of this book extended over a number of years during which we enjoyed the support of students, friends, and colleagues to whom we wish to express our sincere gratitude. After the German version appeared in 1989 we benefitted from Tilmann Wfufel's steady help in the tedious process of translating this book into En glish. Natalia Schmidt-in addition to gracefully enduring her spouse during that time-was the first to read the emerging text. Our thanks also go to the following colleagues for their stimulating support and comments: Ludwig Bayer, Rudolf Berghammer, Thomas Gritzner, Jiirgen Janas, Wolfram Kahl, and Peter Kempf. Help and constructive criticism from several researchers from abroad who have read various parts of the book is gratefully acknowledged: Jules Desharnais, Roger Maddux, Ali Mili, Jacques Riguet, and lain A. Stewart. We are indebted to Friedrich L. Bauer for accompanying the emergence of this book over the years with stimulation and scientific impetus. We are grateful to the editors of the EATCS monographs for including the book in this series. We thank Springer-Verlag for their agreeable cooperation, in particular Hans Wossner, and not least J. Andrew Ross for his careful copy editing. Munich, August 1992 Gunther Schmidt Thomas Strohlein Table of Contents 1. Sets ............................. 1 2. Homogeneous Relations 5 2.1 Boolean Operations on Relations 5 2.2 Transposition of a Relation 9 2.3 The Product of Two Relations 12 2.4 Subsets and Points 21 2.5 References . 27 3. Transitivity 28 3.1 Orderings and Equivalence Relations 28 3.2 Closures and Closure Algorithms 34 3.3 Extrema, Bounds, and Suprema 41 3.4 References . 49 4. Heterogeneous Relations 50 4.1 Bipartite Graphs . 50 4.2 F\mctions and Mappings 54 4.3 n-ary Relations in Data Bases 64 4.4 Difunctionality . 71 4.5 References. 80 5. Graphs: Associated Relation, Incidence, Adjacency 81 5.1 Directed Graphs 81 5.2 Graphs via the Associated Relation . 86 5.3 Hypergraphs . 91 5.4 Graphs via the Adjacency Relation 96 5.5 Incidence and Adjacency 99 5.6 References . 104 6. Reachability 105 6.1 Paths and Circuits 105 6.2 Chains and Cycles 115 6.3 Terminality and Foundedness 119 6.4 Confluence and Church-Rosser Theorems 127 6.5 Hasse Diagrams and Discreteness 135 6.6 References . 141 viii Table of Contents 7. The Category of Graphs 142 7.1 Homomorphisms of I-Graphs 142 7.2 More Graph Homomorphisms 148 7.3 Covering of Graphs and Path Equivalence 153 7.4 Congruences . 158 7.5 Direct Product and n-ary Relations 161 7.6 References . 171 8. Kernels and Games 172 8.1 Absorptiveness and Stability . 172 8.2 Kernels 176 8.3 Games 185 8.4 References . 196 9. Matchings and Coverings 197 9.1 Independence 197 9.2 Coverings 202 9.3 Matching Theorems 210 9.4 Starlikeness 222 9.5 References . 228 10. Programs: Correctness and Verification 229 10.1 Programs and Their Effect 230 10.2 Partial Correctness and Verification 237 10.3 Total Correctness and Termination 245 10.4 Weakest Preconditions 252 10.5 Coverings of Programs 258 10.6 References . 264 Appendix. 265 A.1 Boolean Algebra 265 A.2 Abstract Relation Algebra. 270 A.3 Fixedpoint Theorems and Antimorphisms 278 A.4 References. 288 General References 290 Name Index 291 Table of Symbols 293 Subject Index 295 Dependence of sections Complexity of the material 1. Sets In this chapter we introduce relations on a set. For that purpose we first recall some well-known facts from set theory and explain our notation. A set M is a collection of well-defined objects called its elements. We write x E X if x is an element of the set X. The symbol 0 denotes the empty set. The set of all elements which have the property E is written as M = {x I E(x)}. The power set of a set X is denoted by 2x; so M is an element of 2x if and only if M is a subset of X . Union and intersection of two sets M, N are denoted by M U Nand M n N , respectively. If M is contained in N we use the symbol e for inclusion, MeN. The complement of a subset M with respect to a set X is denoted by X\M or, if X is tacitly given, by M. The operations of union and intersection are associative (M U N) U P = M U (N U P) , (M n N) n P = M n (N n P) , commutative MUN= NUM, MnN= NnM, distributive M U (N n P) = (M U N) n (M U P), M n (N U P) = (M n N) U (M n P), absorptive Mn(MUN)=M, MU(MnN)=M. (These are the laws of a distributive lattice.) Union and intersection are duals of one another. By the absorption law, these operations are also idempotent MUM=M, MnM=M. The inclusion MeN can also be interpreted as another way of expressing M n N = M or M U N = N. The power set 2x is ordered by inclusion, i.e., e satisfies the following conditions. It is reflexive MeM, antisymmetric MeN, N eM===? M=N, transitive MeN, N e P ===? MeP. Often, there are pairs of elements M, N which are incomparable, in the sense that neither MeN nor N eM. So far, we have emphasized the algebraic operations of set theory. For finite sets such as X = { a, b} one can set up composition tables as in Fig. 1.1. We may also start out with the ordering by inclusion e of elements M, N of the power set 2x of X. (The last table in Fig. 1.1 indicates when the relation e holds for the example above.) Using the inclusion, one can express union, and 2 1. Sets o .u. 0 {a} {b} {a, b} .n. {a} {b} {a, b} 0 0 {a} {b} {a,b} 0 0 0 0 0 o {a} {a} {a} {a,b} {a,b} {a} {a} 0 {a} {b} {b} {a, b} {b} {a, b} {b} 0 0 {b} {b} o {a, b} {a, b} {a,b} {a, b} {a,b} {a,b} {a} {b} {a,b} o .c. {a} {b} {a, b} 0 {a} {b} {a,b} 0 1 1 1 1 {a} 0 1 0 1 {a,b} {b} {a} 0 {b} 0 0 1 1 {a, b} 0 0 0 1 Fig. 1.1 Set-theoretic operations intersection as follows: M U N := least subset of X containing M and N i M n N := greatest subset of X contained in M and in N. So we are forming the least upper bound or supremum and the greatest lower bound or infimum, respectively, of two sets with respect to the ordering given by inclusion. Accordingly, we define for an arbitrary (possibly infinite) set of subsets A c 2x: sup A := least subset of X containing all subsets in Ai inf A := greatest subset of X contained in all subsets in A. If A consists of the subsets AI := {a,b,e}, A2 := {b,f} and A3:= {a,b,f} then we have sup A = Al UA2uA3 = {a, b, e,f} and inf A = Al nA2nA3 = {b}. It is possible to determine arbitrary suprema and infima in 2x in this descriptive fashion, even if there are infinitely many sets to be compared. The complement is characterized by the following conditions which hold for every subset M of X: MUM=X, MnM=0. Moreover, we have 0UM=M, 0nM= 0, XUM=X, XnM=M. Forming the complement M of a set M is an involution In connection with union and intersection there are the laws of de Morgan MUN=MnN, MnN= MUN, sup {M I MEA} = inf { N I N E A}, inf {M I MEA} = sup { N I N E A}.