Talk:Quasitransitive relation

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Low Priority
 Field:  Discrete mathematics
WikiProject Economics (Rated Start-class, Low-importance)
WikiProject icon This article is within the scope of WikiProject Economics, a collaborative effort to improve the coverage of Economics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Low  This article has been rated as Low-importance on the project's importance scale.

Is there a reference for this? I am not aware of it being standard mathematical terminology. A google search showed that it does seem to be used quite a bit in decision theory. Sam Staton 18:41, 8 January 2007 (UTC)

Hi, I'm the one who wrote the original article. I can look for references, but I haven't read a paper entirely devoted to it yet -- it's usually just used in passing. Though I have a math background, I've really only seen it in social choice theory (and at most once or twice outside of that field). Would you like an article or book that uses the term in passing, or should I dig harder for one that addresses it directly? Alternately, perhaps I should find a Sloane sequence that references it? CRGreathouse (t | c) 02:49, 9 January 2007 (UTC)

Hi - thanks for your reply. Maybe the article should begin 'In social choice theory...' or something like that. What do you think? My reason for asking was that I was thinking of using the term in an article, to refer to a very different transitivity-like condition on relations.

I'm not a 'social choice' theorist and it seems a bit absurd if I can't define the vague phrase 'quasi-transitive' just because some people in another, very different branch of maths have occasionally used the phrase in a different way.

I suppose that my complaint is that this wikipedia page takes a term that is used by a relative minority and presents it as if the term is general and mainstream. Sam Staton 13:41, 9 January 2007 (UTC)

First of all, there's no reason to avoid the term if you think it's the right one—plenty of math terms are overloaded. Out of curiosity, what is your version of 'quasitransitivity'?
Second, you may wish to avoid writing an article on a term of your own invention, because I think that's discouraged or disallowed in some Wikipedia guideline or other. If you think an article should be written about it, that it's not too niche of a term (I say this without knowing what you use the term for), then you should probably have someone else write it. Frankly, I'd be happy to do this if you'd like; having more math articles on research-level topics is great. You'd have to get me a preprint somehow, though.
Third, a very brief search of Sloane's database gave two mentions, (sequence A082677 in the OEIS) and (sequence A082678 in the OEIS).
Fourth, I don't think that the term is actually that specialized. It is a straightforward generalization of transitivity to partial orders. Unless there's a more common use of the term (and I've never heard any other use, even though social choice isn't my area of study), I see no reason to change the general presentation and/or move the page. Of course if you know better please inform me.
CRGreathouse (t | c) 00:19, 11 January 2007 (UTC)

Thanks for your reply.

Thank you for finding the Sloane sequences. They give substantially older references than google provided. But I notice that they both refer to social choice theory.

Would you mind if I include a reference to Social Choice Theory in the page? Firstly, it seems that the term is used primarily in social choice theory, so a link might be helpful to the reader. Secondly, I've never seen this definition defined next to reflexivity, transitivity etc in a general maths textbook. The point is, to a general mathematician, this is not what 'quasitransitive' means: to a general mathematician, 'quasitransitive' does not mean anything. To a social choice theorist, it seems to be an important notion, and so I propose we mention this on the page.

In fact, I might use a different term now, for various reasons. In response to your second point, I was certainly not intending to modify the page to refer to my term. (As you know, mathematicians invent phrases all the time, often only using terminology within an article, and I'm not sure that the role of wikipedia is to index this.) (Since you ask, the notion that I'm concerned with regards a transitivity-like condition on a relation between two different sets, so 'quasi-transitive', ie 'like transitive', seems a reasonable phrase.)

One last thing: when you say "It is a straightforward generalization of transitivity to partial orders", what do you mean? I don't understand. (Maybe it's not important.) Transitivity already makes sense for partial orders.

Best regards Sam Staton 21:56, 14 January 2007 (UTC)

I don't mind if you add information on social choice to the article. I did already have the social choice example, but explicit statements may be of use. In any case the article is quite brief now and could use more content regardless. I trust your additions will improve the page.
I should have said "on partial orders", rather than "to partial orders". With = quasitransitivity, = asymmetry, = antisymmetry, and = transitivity:
I'm not sure how to explain it; the second definition given (which is more common in social choice) is similar to transitive closure in reverse. I'll try to explain this better when I think of a way.
CRGreathouse (t | c) 22:11, 14 January 2007 (UTC)

I've made the change I proposed. I hope it's OK with you. If not, we can discuss more. I wonder about deleting 'In mathematics' since I'm not sure that social choice theory is mathematics, rather than economics. Would you be OK with that?

Thank you for explaining your comment. My point is that while this is a general notion, it is not general terminology. 'Quasitransitive' only means 'like-transitive', and other transitivity-like conditions are relevant in other branches of mathematics. As an example, see Filtration via Bisimulation, Valentin Shehtman, Adv. in Modal Logics, Vol 5 (2005), pp 289-308, Defn 9, where the term is used with a different meaning. Sam Staton 10:44, 15 January 2007 (UTC)

I don't think that mathematics should be removed. As a compromise, though, I've changed the order. How's that look? CRGreathouse (t | c) 16:21, 15 January 2007 (UTC)

Yes, that's fine. Thank you. Although, to be picky, the article still suggests that "the term 'quasitransitive' means the concept provided on this page in contexts broader than social choice theory". Yet we have no evidence for this statement. I would be happiest if either the reference to general maths was removed, or if some 'evidence' was found, ie a usage of the term in this way in work that is not related to social choice theory. (I think this is the appropriate interpretation of the verifiability guidelines.)

I'll try to get an example of usage, then. Don't hold your breath, though; I'm pretty busy now. I'll get it as I'm able. CRGreathouse (t | c) 00:58, 16 January 2007 (UTC)

Hi. Still waiting for an example, so I've taken out the broader reference in the meantime. Sam Staton 12:47, 20 May 2007 (UTC)

Hello. Why have you put the reference to broader mathematics back in? Do you now have evidence that the term is used more broadly than in social choice theory? If so please supply it. --Sam Staton 13:24, 4 June 2007 (UTC)

I have removed the reference to broader mathematics again, pending an example of general mathematical usage outside of social choice theory. This is in accordance with the verifiability guidelines. Sam Staton 16:49, 17 July 2007 (UTC)

iff or if[edit]

Hello again, I reverted the change of iff to if, because I think you were right with iff in the first place. Provided P is defined by


the conditions


are identical, right? Sam Staton (talk) 00:40, 29 December 2007 (UTC)

Sorry, you're right, I was reading it backward. CRGreathouse (t | c) 04:31, 29 December 2007 (UTC)


It might motivate the formal definition better to say that it is models a preference relation for which the strict (asymmetric) part is transitive: in other words, a strict order relation. Deltahedron (talk) 19:39, 16 May 2014 (UTC)

Relation to other properties[edit]

It is worth saying that every transitive relation is quasi-transitive, and that every quasi-transitive relation is acyclic; but that neither converse holds. Deltahedron (talk) 19:42, 16 May 2014 (UTC)