From Wikipedia, the free encyclopedia
Jump to navigation Jump to 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:  Foundations, logic, and set theory

On having 3 definitions[edit]

The present stage of the article betrays some confusion on my part. In the article as I found it, the term was used purely to refer to the presence of 'preference ordering loops'. I was quite surprised to see this, since it adds a third distinct meaning to the term, besides the two I was already familiar with (nontransitivity and antitransitivity).

Now Google provides confirmations for all three uses of the term. Therefore I strongly feel we have to recognize all three of them and explain their differences, rather than picking one of them, as a textbook would do.

But I didn't have too much time so I only added a "formal definition" section in which the three concepts are defined and exemplified. The article needs restructuring. Please help ...

Rp 15:39, 21 July 2006 (UTC)

PS: I have incorporated the distinctions into the main text, so there is no longer a separate "formal" sectio. Rp (talk) 20:53, 3 January 2008 (UTC)


Nontransitivity: (x)(y)(z)((RxyRyz )(x)(z)~Rxz)
Intransitivity: (x)(y)(z)((RxyRyz )~Rxz)

In reviewing these the following seems clear to me. A relation is transitive if A has the relationship to B and B has the relationship to C then A has the relationship to C.

The least thing we need in order for a relation to be NOT-transitive there has to be at least one example where A doesn't have the relation to C. Well that is exactly what this stated formulation says.

When there is not just one, but all As do not have the relation to all Cs, that is something different. That is intransitive. Well that is exactly what the formula stated for intransitivity says.

The article should reflect this.

Gregbard 05:26, 29 August 2007 (UTC)

As the definition of a transitive relation is purely universal, its negation should be purely existential. The formula above for "nontransitivity" is not purely existential.
But there is a more serious error. According to the definition of "nontransitive" the four-element Boolean algebra {0,1,a,b} is nontransitive. Since there exists x and z that aren't related (elements a and b), the right hand side of the implication is always satisfied, and thus the formula is always true. But the four element Boolean algebra is a lattice - in particular it's transitive.
To understand what's wrong with the formula, it may help to push the universal quantifiers inside the implication. First rename the variables:
(u)(v)(w)((RuvRvw )(x)(z)~Rxz)
then use one of the rules at prenex normal form:
That clearly isn't a definition of nontransitive. It says that if there is a chain of length 3 then there is also a (possibly unrelated) antichain of size 2. — Carl (CBM · talk) 13:40, 29 August 2007 (UTC)
I understand what you are saying here. You have put a sign in front of transitivity and put the expression back into proper form. You get three existential quantifiers. That is what might be called "strongly nontransitive" or "very nontransitive" or something else. However, all you have to do to screw up transitivity and make it nontransitive is have ONE case that screws it up (that only requires that two of the variable participate in screwing it up). It isn't as simple (and I am not saying what you have shown here is simple) as just negating the whole thing. Anyway, I find you quite credible, however, I still trust my well researched notes on this issue. At the very least, there are flavors of nontransitivity, which tells me that theres a separate article in there somewhere someday. Be well, Gregbard 22:26, 29 August 2007 (UTC)
I have put the definition you proposed into a different form to illustrate that transitive partial orders satisfy it and thus it cannot be a correct definition of any kind of nontransitivity. To say that there is at least one example to transitivity, that is when you put a negation sign in front of the definition of transitivity. — Carl (CBM · talk) 23:08, 29 August 2007 (UTC)
I have merged the "informal" and "formal" sections and also changed the formal definitions. Please review them again ... Rp (talk) 20:55, 3 January 2008 (UTC)

Wolves and grass[edit]

Small problem with the first example: both wolves and dogs do eat grass. One reference on this: —Preceding unsigned comment added by (talk) 09:44, 5 June 2009 (UTC)

Nice catch. I've fixed the example. Rp (talk) 19:33, 15 March 2010 (UTC)

A cycle in a binary relation[edit]

The last line of this section was unclear, so I've elaborated upon it with examples. Undsoweiter (talk) 06:46, 6 March 2010 (UTC)