Relations: Concrete, Abstract, and Applied: An Introduction

Description

The book is intended as an invitation to the topic of relations on a rather general basis. It fills the gap between the basic knowledge offered in countless introductory papers and books (usually comprising orders and equivalences) and the highly specialized monographs on mainly relation algebras, many-valued (fuzzy) relations, or graphs. This is done not only by presenting theoretical results but also by giving hints to some of the many interesting application areas (also including their respective theoretical basics). This book is a new — and the first of its kind — compilation of known results on binary relations. It offers relational concepts in both reasonable depth and broadness, and also provides insight into the vast diversity of theoretical results as well as application possibilities beyond the commonly known examples. This book is unique by the spectrum of the topics it handles. As indicated in its title these are: Concrete aspects are covered in detail in Part 2 for two-valued, and in Part 3 for many-valued relations. Various kinds of relations and their properties are presented in the familiar form of first order formulas, but mainly algebraically in the point-free version as used in the so-called calculus of relations. Abstract points of view are the content of Part 4: The connections of relations to semigroups, as well as the concept of relation algebras, and how relations are handled within category theory are presented in some detail. Applied relations in Part 5 give a broad spectrum of classical and newer topics where relations of various kinds play a dominant role. This way, readers should get an idea how diverse the possibililties are where relations can be used, and how mighty their modeling abilities turn out to be. Contents Preface Acknowledgments Index of Notations PART 1 : Relations - Historical and Mathematical Preliminaries 1. A Short Look into (Relations’) History 1.1 Syllogisms 1.1.2 The Syllogistic Basics 1.1.3 Syllogistic Validity 1.1.3.1 The Valid Syllogisms 1.1.1 Categorical Propositions and their Interpretation 1.2 Syllogisms and Relations 1.3 From the History of Relations 1.3.1 The Groundwork: DE MORGAN and PEIRCE 1.3.2 The Followers: SCHRÖDER and TARSKI Additional Reading References 2. Mathematical Prerequisites 2.1 Sets and their Operations 2.1.1 Some Properties of Set Difference 2.1.2 Cartesian Products, Relations, and Functions 2.1.2.1 Some Basic Function Properties 2.1.3 Closures and Interiors 2.2 Basics fromPredicate Logic 2.3 Algebraic Structures 2.3.1 A Simple Example: Semigroups 2.3.2 Algebras and Homomorphisms 2.3.3 Some more Examples of Algebraic Structures 2.3.4 Partial Orders and Lattices 2.3.5 Boolean Algebras 2.3.5.1 Boolean Rings 2.3.5.2 Atomic Boolean Algebras 2.3.6 Galois Connections and ResiduatedMappings 2.3.7 Partially Ordered Semigroups Additional Reading References PART 2 : Relations - Concrete, two-valued 3. Binary Relations: Basic Properties and Operations 3.1 Set Theoretical Properties 3.1.1 Images of Sets under a Relation 3.2 Basic Relation Operations 3.2.1 Representing Relations 3.3 Basic Relation Properties 3.3.1 Relations and Syllogisms Again 3.3.2 (A Lot of) Properties and some of their Interrelationships 3.4 Some Results fromthe Calculus of Relations 3.5 Dual Relations, Residuals and Symmetric Quotients 3.5.1 Dual Relations 3.5.2 Residuals 3.5.3 Symmetric Quotients and Bidirectional Residuals 3.6 Operations and Properties revisited 3.6.1 Point-free Representation of Relation Properties 3.6.2 Properties of Compound Relations 3.6.3 Powers and Closures of Relations 3.7 Homomorphisms and Isomorphisms 3.7.1 The Heterogeneous Case 3.7.2 The Homogeneous Case References 4. Some Basic Kinds of Binary Relations 4.1 Relations and Functions 4.2 Order Relations 4.3 Tolerance and Equivalence Relations 4.3.1 Equivalence Relations 4.3.2 Tolerance Relations 4.3.3 Partial Equivalence Relations References 5. Relations, Matrices, and Graphs 5.1 Recalling Basic Facts on Boolean Matrices 5.2 Graphs and Matrices 5.3 Relations and Matrices 5.4 Powers of Relations on a Finite Set 5.4.1 Indices of Semigroups 5.4.2 Inclines, Permanents and Adjoints 5.4.3 Properties of Incline Matrices and Relation Powers References 6. Some Special Topics around Relations 6.1 Bandler-Kohout Products and Images 6.1.1 The Basic Concepts 6.1.2 On Properties of BK images and products 6.1.2.1 Image Properties 6.1.2.2 Product Properties 6.1.2.3 Some More Properties of BK Products 6.2 Some Further Kinds of Relations 6.2.1 Subsets, Vectors, and Rectangles 6.2.1.1 Vectors and Points 6.2.1.2 Describing Sets with Relations 6.2.1.3 Rectangles and Fringes 6.2.2 Inverses and Regular Relations 6.2.2.1 Difunctional Relations 6.2.3 Commuting Relations 6.2.3.1 Commuting Equivalences 6.2.3.2 Regular Equivalences 6.2.3.3 Idempotent Relations References PART 3 : Relations - Concrete, many-valued 7. Many-valued Extensions: Preliminaries 7.1 Graded Truth Values and their Structures 7.2 Order and Lattice Theory: Supplements 7.2.1 More on Orders and Residuation 7.2.1.1 Duality 7.2.1.2 Residuated Mappings 7.2.2 More on Lattices References 8. Fuzzy Sets and Fuzzy Relations 8.1 Fuzzy Sets: Basic Definitions and Properties 8.2 Many-valued Connectives on Complete lattices 8.3 Fuzzy Relations: Basic Operations and Properties 8.3.1 Basic Operations on Fuzzy Relations 8.3.2 Basic Properties of Fuzzy Relations 8.4 Fuzzy Equivalence Relations 8.5 Fuzzy Relation Equations and Inequalities 8.5.1 Types of Fuzzy Relation Equations 8.5.2 The Lattice Based Approach 8.5.2.1 Starting with the Begin 8.5.2.2 Fuzzy Relation Inequalities 8.5.2.3 Minimal Solutions 8.6 Applications of Fuzzy Relations 8.6.1 Inference Rules 8.6.2 Fuzzy Rule Based Systems References PART 4 : Relations - Abstract 9. Semigroups and Binary Relations 9.1 Some Basic Concepts of Semigroup Theory 9.1.1 Various Kinds of Semigroups 9.1.2 Ideals and Green’s Relations 9.1.2.1 The Structure of D-Classes 9.1.3 Natural Partial Order 9.2 Algebraic Properties of Relations on Finite Sets 9.2.1 The Semigroup of Binary Relations BX 9.2.1.1 Subsemigroups of BX 9.2.2 The Green’s Relations on BX 9.2.2.1 The Green’s Relations on Subsemigroups of BX 9.2.3 The Natural Partial Order on BX 9.2.3.1 The Natural Partial Order on Subsemigroups of BX References 10. Relation Algebras 10.1 Algebras of relations 10.2 Some Basic Concepts from Universal Algebra 10.2.1 Subalgebras and Homomorphic Images 10.2.2 Congruences and Quotient Algebras 10.2.3 Direct Products and Factor Congruences 10.2.4 Varieties and Equational Definability 10.2.5 Boolean Algebras with Operators 10.3 Relation Algebras 10.3.1 Arithmetic in Relation Algebras 10.3.1.1 Arithmetic in NA 10.3.1.2 The Need for Associativity 10.3.2 Special Kinds of Elements 10.3.2.1 Symmetric Elements 10.3.2.2 Transitive Elements 10.3.2.3 Equivalence Elements 10.3.2.4 Ideal Elements and Ideals 10.3.3 Representability and other Algebraic Properties of RA 10.3.3.1 Representation of Relation Algebras 10.3.3.2 Simple and Integral Relation Algebras References 11. Relations and Categories 11.1 Categories: Basic Concepts 11.1.1 Special Arrows and Structures 11.1.1.1 Mono-, Epi-, and Isomorphisms 11.1.1.2 Equalizers and Coequalizers 11.1.1.3 Initial and Terminal Objects 11.1.1.4 Elements, Subobjects and Images 11.1.1.5 Products 11.1.1.6 Pullbacks 11.1.1.7 Limits 11.2 Relations and Regular Categories 11.2.1 Regular Categories and Factorizations 11.2.2 Relations in Regular Categories 11.3 Some Related Concepts 11.3.1 Using Elements in the Categorical Setting 11.3.2 2-categories 11.4 Relations and Allegories 11.4.1 Allegories: The Basics 11.4.2 Special Properties of Arrows 11.4.3 Regular Categories and Allegories 11.4.4 Special Types of Allegories 11.4.4.1 Distributive Allegories 11.4.4.2 Division Allegories References PART 5 : Relations - Applied 12. Semiotics and Semantics 12.1 The Meaning Triangle 12.2 Ambiguity, Vagueness, Uncertainty and the like 12.3 Some relational Clarifications References 13. Information Systems and Rough Sets 13.1 Information Systems 13.2 Rough Set Theory (RST) 13.2.1 Basic Ideas of Rough Set Theory 13.2.2 Generalized Relation Based Rough Sets 13.2.2.1 Using Arbitrary Relations 13.2.2.2 Using Special Relations References 14. Formal Concept Analysis 14.1 The Basic Notions and Algebra of FCA 14.2 Attribute Implications 14.3 FCA and Relations References 15. Mereology and Qualitative Spatial and Temporal Reasoning 15.1 Mereology 15.1.1 Basic Notions of Mereology 15.1.2 Ground Mereology 15.1.3 Minimal and Extensional Mereology, Atoms 15.1.4 Closure and General Mereologies 15.2 Introducing Qualitative Models and Inferences 15.2.1 Some Formal Background 15.3 Qualitative Temporal Calculi 15.3.1 Point Algebra 15.3.2 Interval Algebra 15.4 Qualitative Spatial Calculi: Mereotopology 15.4.1 Background and Ontological Aspects 15.4.2 GroundMereotopology 15.4.3 The Region-Connection Calculus 15.5 Some Logical and Algebraic Considerations 15.5.1 Composition Tables 15.5.2 Constraint-based Qualitative Reasoning Additional Reading References 16. Argumentation Frameworks 16.1 Introduction 16.2 Key Concepts of Argumentation Frameworks 16.3 DAFs from a Relational Viewpoint 16.4 Generalizations and Variants 16.4.1 Values and Preferences 16.4.2 Bipolar Frameworks 16.4.3 Abstract Dialectical Frameworks Additional Reading References 17. Describing Graphs and Transition Systems 17.1 Graphs and Relations 17.1.1 Basic Concepts 17.1.2 Describing a Graph by its Relations 17.1.2.1 Bipartite Graphs and Independence 17.1.3 Paths and Reachability 17.1.3.1 Rooted Graphs and Rooted Trees 17.1.4 Homomorphisms and Isomorphisms 17.2 Transition Systems and Behavioral Equivalence 17.2.1 Trace Equivalences 17.2.2 Simulation Equivalences References 18. Order Relations and PreferenceModelling 18.1 Ferrers Relations 18.2 More on Order Relations 18.3 Preferences and their Measurement 18.3.1 A Short Sketch of Measurement Theory 18.3.2 Semiorders and Interval Orders 18.4 Preference Structures References 19. Relations and Syllogisms Again 19.1 Relational Analysis of Syllogisms 19.2 Relations and the Square of Opposition 19.2.1 The Square of Opposition 19.2.2 Opposition Structures Induced by Sets and Relations References Index