# Branch of math studying relations

There are many branches of mathematics (analysis, algebra, group theory, logic, ...). Now, I'm interested in relations and their special kinds (like equivalence relation) and their properties. I'd like to find out more about them.

Where should I search to learn everything from the origin of the concept of relation to the knowledge about them of today? Which branch of math studies them carefully?

• This question strikes me as slightly misguided. It is analogous to asking "what branch of math studies functions carefully?" Every branch of mathematics makes use of the notion of function, just as every branch of mathematics makes use of the notion of relation (even just equivalence relations). Can you be more specific about what you're interested in? – Qiaochu Yuan Jan 18 '12 at 21:12
• There are lots of areas that would touch on this; you can represent relations with (directed) graphs, and you can address questions about relations in terms of questions about graphs, placing you in graph theory. For large sets, you will probably end up having to deal with Set Theory; there is also the study of Relational Algebras within Universal Algebra, but that will be more along the lines of understanding maps between sets-with-relations that respect the relations. The basics are covered in elementary set theory. The history of todays presentation can be found in the essays in Bourbaki. – Arturo Magidin Jan 18 '12 at 21:14
• Another way of expressing my concerns is that I would say that relations are not so much a thing you study as a language you use to study other things. But there is room for disagreement on this point, I suppose. – Qiaochu Yuan Jan 18 '12 at 22:09
• @QiaochuYuan analysis studies functions but in a little different way. I'm aware that function is a special kind of relation. But relations are really interesting, they create various patterns - you can draw them as hasse diagrams (relations that create orderings), graphs are relations between vertices. It's interesting to study the properties of these patterns and structures. Maybe relations are only formalism for other branches of math, but maybe more care was devoted to them and this is what interests me. – xralf Jan 19 '12 at 7:51
• I was talking about the historical essays; they can be found in "Elements of the History of Mathematics"; otherwise, they are covered in the "Set Theory" volumes. – Arturo Magidin Jan 19 '12 at 15:59

This is probably too advanced, but there is Roland Fraïssé's book (which I'm surprised no one has mentioned yet):

Roland Fraïssé, Theory of Relations, Studies in Logic and The Foundations of Mathematics #118 [Revised Edition is #145], North Holland, 1986, xii + 397 pages [Revised Edition is 2000, ?? + 451 pages].

Review of 1986 edition by Arnold William Miller, Bulletin of the American Mathematical Society (N.S.) 23 #1 (July 1990), pp. 206-209.

Review of 2000 edition by Peter van Emde Boas, Nieuw Archief voor Wiskunde (5) 5 #3 (September 2004), p. 251. [Boas's review is in English.]

More useful, I think, would be to gather up a lot of undergraduate level set theory texts (Enderton, Schaum's outline, Dalen/Doets/De Swart, Devlin, Hrbacek/Jech, Monk, Roitman, Vaught, etc.) and compile a list of basic results about relations from the text material and the exercises (most will probably be in the exercises). I've often used this method to learn something new. In the U.S. you can find many such books in most any college library under the Library of Congress headings QA 9 and QA 248. As you compile and orgainize the results, you'll become better acquainted with subject, and sometimes you'll even come up with some new results on your own by extending ideas in the results you have. (In my case, I almost always later come across my "original result" published somewhere, usually as an exercise in a book or as an aside in a research paper.)

• It seems to me that relations are branch of math for itself and because they are more general are used often as a formalism to describe other topics of math. – xralf Jan 19 '12 at 8:05
• Now, I see that this book is under mathematical logic – xralf Jan 19 '12 at 8:08

While it is not a systematic study of relations, there is a paper by Smullyan which may be of interest to you, "Equivalence Relations and Groups ". Abstract:

Our purpose is to show how the logic of relations can be uitilized in the study of group theory. There are some striking similarities in certain theorems in group theory and certain results about equivalence relations, and we show how the former can be derived as consequences of the latter. This transition is accomplished by means of certain ismorphism theorems, proved in considerable generality in section 2, and applied to groups in section 3. In section 1 we give several miscellaneous theorems on equivalence relations, which later turn out to have their analogues in the theory of groups.

The theory of binary relations over a set is in a sense the same as the theory of (non-weighted) directed graphs. The theory of symmetric relations is in a sense the same as the theory of (non-weighted) undirected graphs. Indeed, every graph can be seen as the set of vertices and the adjacency relation (which is symmetric in the case of undirected graphs).

Since relations can be composed, and the composition is associative, they are of interest in semigroup theory. If you google "semigroup of binary relations", you will find many hits. These semigroups were studied quite intensively in the 1960s.

There are connections between semigroup-theoretic properties of relations and standard notions such as transitivity or being an equivalence relation. One simple example is that every equivalence relation is idempotent with respect to composition. Indeed, every preorder is. A relation $R$ is transitive iff $R\circ R\subseteq R.$ A relation $R$ over a set $X$ is interpolative, that is $(\forall a,b\in x) ((a,b)\in R \Longrightarrow (\exists c\in X) ((a,c)\in R\wedge (c,b)\in R))$, iff $R\circ R\supseteq R.$

At least in the undergraduate curriculum, relations are usually studied on the way to something else. Many textbooks on combinatorics and on abstract algebra will devote a chapter to relations. Have you mastered all of the information on relations in those books?

• It depends which books do you have on mind. Please, post here some title. Thanks. – xralf Jan 19 '12 at 8:01
• Sorry, I'm out of my office the next few days and have no access to books. But really it shouldn't be that hard for you to find a few introductory textbooks with titles mentioning Abstract Algebra, or Combinatorics, or Discrete Mathematics, and have a look to see if there's a chapter on relations. – Gerry Myerson Jan 19 '12 at 9:06

A book on the transition to advanced mathematics will give you a thorough (50 page) introduction to relations (as opposed to a 5 page introduction as is done in Munkres' Topology).

I liked How to Prove It by Daniel Velleman. It covered equivalence relations, ordering relations, closures, etc.

• Thanks. Which transition to advanced mathematics do you have on mind? There are more such titles. – xralf Jan 19 '12 at 14:09
• How to prove it is the title that I wanted to read (it was in the library) but never found time, maybe I should find it. – xralf Jan 19 '12 at 14:10
• "How to Prove It" is the one I had in mind. I just wanted to point out that there are quite a few books in that category. You might find a different one that you like better, I don't know. – Matt Gregory Jan 19 '12 at 14:41

On the Calculus of Relations by Tarski

The paper contains a nice introduction to the elementary theory of binary relations (unfortunately restricted access).

Towards algebraic abstraction of relations, I also suggest Allegories and Relation Algebras..