# Should we have a canonical question on transitive / symmetric / reflexive relations?

It seems that we fairly regularly get elementary questions of the form:

"Does a relation that is [A] and [B] have to be [C]?"

where [A], [B] and [C] are some permutation of "transitive", "symmetric" and "reflexive" or their negations.

For example, here's a recent one that made it onto the Hot Network Questions list.

Of course, the answer to all these questions is "no, here's a basic counterexample." In fact, a couple of years ago I posted an answer that provides counterexamples to all these questions. For convenience, let me briefly quote that answer here:

"On the three-element set $$\{a, b, c\}$$, the following relations are:

• Transitive, symmetric: $$R_0 = \emptyset$$
• Transitive, not symmetric: $$R_1 = \{(a,b)\}$$
• Not transitive, not symmetric: $$R_2 = \{(a,b), (b,c)\}$$
• Not transitive, symmetric: $$R_3 = \{(a,b), (b,a), (b,c), (c,b)\}$$

None of the relations above are reflexive, but they can all be turned into reflexive relations, without affecting their transitivity or symmetry, by adding $$R^* = \{(a,a), (b,b), (c,c)\}$$ to them."

I'm not saying that it's a perfect answer — one could surely do much more to try and build the reader's intuition for why these properties are independent — but it does show that a single answer (even a fairly short one) is sufficient to cover all these questions.

Unfortunately, the question that I originally posted that answer under is rather more narrowly scoped than the answer itself. Prompted by the recent Hot Network Question, I was think that I might want to post a more broader "canonical" question that did cover all these variations, and repost the answer (somewhat expanded, perhaps with some pictures to illustrate it, and probably as Community Wiki to invite improvements from others) under it.

That canonical question might, tentatively, look something like this:

"In school, we learned about symmetric, transitive and reflexive relations. Do any two of these properties (or their negations) imply the third (or its negation), or are they all independent?"

(There would, of course, also be a link to this meta question.)

That said, before going ahead with this, I figured I'd ask whether anyone else thinks this is a good idea. Would a single canonical question like this be a useful resource, or should we just maintain separate questions with separate answers for each of the (3 × 2³ = 24 or so) specific permutations of this question?

• Also, I just created the canonical tag, since we didn't seem to have one here yet. It already exists on meta.SE and meta.SO, so I figured that was probably appropriate. – Ilmari Karonen Sep 5 '18 at 20:42
• It also exists on ask ubuntu ;) – Daniel Fischer Sep 5 '18 at 20:49
• I lean towards "this is probably a good idea". – Daniel Fischer Sep 5 '18 at 21:18
• In some time we would just open a canonical "should we have a canonical question on X". – Asaf Karagila Sep 5 '18 at 23:08
• I think the idea is a good one, but canonical answers should probably be CW, because, it is likely that no one user can make the best of "canonical answers". – amWhy Sep 6 '18 at 22:59
• And you haven't touched on all the "Give a real life example of a relation that has properties A and B, but not property C..." and permutations thereof, questions. – amWhy Sep 6 '18 at 23:47
• I suppose the ideal answer would simply contain a list of concrete real-life relations demonstrating all 8 cases ($\pm$transitive, $\pm$symmetric, $\pm$reflexive), thus showing that the three properties are all independent of each other. – user856 Sep 7 '18 at 10:28
• @DanielFischer The question posed and proposal "is probably a good idea". Or, the creation of the canonical tag "is probably a good idea"? I mean, I'm not clear what you are referring to as "this" when you say "this is probably a good idea." [bold-face, italics mine]. Of course, perhaps both ideas are good, in which case you might have meant to say "these are probably good ideas" – amWhy Sep 7 '18 at 23:40
• @DanielFischer But... that's a company name (from tag info page). Not related to "canonical question and answer" anyway. – user202729 Sep 8 '18 at 12:55
• By the way [canonical] would be considered a meta tag. – user202729 Sep 8 '18 at 12:56
• @user202729 Yes. That's why I expected to find that tag on ask ubuntu (and put a wink at the end of the comment). – Daniel Fischer Sep 8 '18 at 14:35
• @amWhy The creation of a master relations-question is probably a good idea. – Daniel Fischer Sep 8 '18 at 14:38
• For anyone feeling confused, let me clarify that my first comment above is referring to this [canonical] tag here on meta, which the (meta)question above is tagged with. AFAIK, nobody has even proposed creating such a tag on the main site, where it would indeed clearly be inappropriate. I apologise for any confusion. – Ilmari Karonen Sep 11 '18 at 14:19
• Using the empty set as a counterexample is a Good Idea because the askers of these questions often fail to consider it. But it probably should not be the only counterexample, because some people might think that it is somehow a special or exceptional case, when in fact there are many non-reflexive, transitive, symmetric relations on that set (e.g. $\{(a, b), (b, a), (a, a), (b, b)\}$). – Kevin Sep 14 '18 at 17:20
• Should the 24 permutations be considered distinct? "R and S implies T" is logically equivalent to "R and not T implies not S". Should we list only one, on the basis that the other follows, or list both, on the basis that the whole point is to spell things out? – Acccumulation Sep 17 '18 at 14:50

Given the +17/-0 margin of on the original question, I have taken the liberty of writing a Question & Answer which are intended to serve as the canonical version of these questions:

Examples and Counterexamples of Relations which Satisfy Certain Properties

(There are, by the way, 27 permutations by my count. And that is only after eliminating things like relations which are both transitive and intransitive, or symmetric and antisymmetric).

• Thanks. This had completely slipped out of my mind. I made a small edit to your answer regarding the "reflexive and irreflexive" case, I hope you don't mind. (Also, I'd kind of prefer using "antitransitive" for the property you describe, since I very commonly see "intransitive" used for the weaker property $\exists x, y, z \in X: (x,y) \in R \land (y,z) \in R \land (x,z) \notin R$. And I also can't resist noting that parenthood is not necessarily antitransitive, for reasons that can be both legal (adoption) and illegal (incest). Biological motherhood (or fatherhood) would work, though.) – Ilmari Karonen Aug 27 at 8:42
• "Biological motherhood (or fatherhood) would work, though.)" There are some genetic engineers which may soon have something to say about that... :P – Xander Henderson Aug 27 at 12:37

I am concerned that the existence of a tag would lead to people fighting over which posts were, or were not, tagged . If it did, the benefit of the tag might be heavily outweighed by the strife it would cause.

• Just to clarify, my comment above was about this [canonical] tag here on meta, which I've tagged the question above with. I don't think anybody has proposed creating such a tag on the main site, where it would be an inappropriate meta tag. – Ilmari Karonen Sep 11 '18 at 14:14
• I understand now, thanks! – MJD Sep 11 '18 at 15:29
• On the main site, we already have faq, which seems intended for exactly such questions. – Misha Lavrov Sep 14 '18 at 22:38