Swipe to navigate through the chapters of this book
Relations play an important role in computer science, both as tools of analysis and for representing computational structures such as databases. In this chapter, we introduce the basic concepts you need to master in order to work with them.
We begin with the notions of an ordered pair (and more generally, ordered n-tuple) and the Cartesian product of two or more sets. We then consider operations on relations, notably those of forming the converse, join and composition of relations, as well as some other operations that make relations interact with sets, notably the image and the closure of a set under a relation.
We also explore two of the main jobs that relations are asked to carry out: to classify and to order. For the former, we explain the notion of an equivalence relation (reflexive, transitive, symmetric) over a set and how it corresponds to the notion of a partition of the set. For the latter, we look first of all at several kinds of reflexive order, and then at their strict parts.
Please log in to get access to this content
The three books listed at the end of Chap. 1 for sets also have good chapters on relations. In detail:
Bloch ED (2011) Proofs and fundamentals: a first course in abstract mathematics, 2nd edn. Springer, New York, chapter 5
Halmos PR (2001) Naive set theory, new edn. Springer, New York, chapters 6 – 7
Lipschutz S (1998) Set theory and related topics, Schaum’s outline series. McGraw Hill, New York, chapter 3
A gentle introductory account which, like that of Bloch, pays careful attention to underlying logical and heuristic matters, is:
Velleman DJ (2006) How to prove it: a structured approach, 2nd edn. Cambridge University Press, Cambridge, chapter 4
Finally, we mention a chapter from the following text on discrete mathematics written specifically for computer science students:
Hein JL (2002) Discrete structures, logic and computability, 2nd edn. Jones and Bartlett, Sudbury, chapter 4
- Comparing Things: Relations
- Springer London
- Sequence number
- Chapter number