Intransitivity

In mathematics, intransitivity (sometimes called nontransitivity) is a property of binary relations that are not transitive relations. This may include any relation that is not transitive, or the stronger property of antitransitivity, which describes a relation that is never transitive. A relation is transitive if, whenever it relates some A to some B, and that B to some C, it also relates that A to that C. Some authors call a relation if it is not transitive, that is, (if the relation in question is named ) This statement is equivalent to For example, consider the relation R on the integers such that a R b if and only if a is a multiple of b or a divisor of b. This relation is intransitive since, for example, 2 R 6 (2 is a divisor of 6) and 6 R 3 (6 is a multiple of 3), but 2 is neither a multiple nor a divisor of 3. This does not imply that the relation is (see below); for example, 2 R 6, 6 R 12, and 2 R 12 as well. As another example, in the food chain, wolves feed on deer, and deer feed on grass, but wolves do not feed on grass. Thus, the relation among life forms is intransitive, in this sense. Another example that does not involve preference loops arises in freemasonry: in some instances lodge A recognizes lodge B, and lodge B recognizes lodge C, but lodge A does not recognize lodge C. Thus the recognition relation among Masonic lodges is intransitive. Often the term is used to refer to the stronger property of antitransitivity. In the example above, the relation is not transitive, but it still contains some transitivity: for instance, humans feed on rabbits, rabbits feed on carrots, and humans also feed on carrots. A relation is if this never occurs at all, i.e. Many authors use the term to mean . For example, the relation R on the integers, such that a R b if and only if a + b is odd, is intransitive. If a R b and b R c, then either a and c are both odd and b is even, or vice-versa. In either case, a + c is even. A second example of an antitransitive relation: the defeated relation in knockout tournaments.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (3)

Related concepts (6)

Related courses (1)

Related lectures (7)

Upstream Erosion and Sediment Passage at Piano Key Weirs

Anton Schleiss, Michael Pfister, Ivan Stojnic

Piano key weirs (PKWs) are a weir type characterized by an effective rating curve. Accordingly, this control structure is primarily applied at dams to increase the spillway capacity. In recent years, PKWs also have been implemented in rivers combined with ...

2019

Monotone and Cash-Invariant Convex Functions and Hulls

Damir Filipovic

This paper provides some useful results for convex risk measures. In fact, we consider convex functions on a locally convex vector space E which are monotone with respect to the preference relation implied by some convex cone and invariant with respect to ...

2007

Fully dynamic cycle-equivalence in graphs

Monika Henzinger

Two edges e_1 and e_2 of an undirected graph are cycle-equivalent iff all cycles that contain e_1 also contain e_2, i.e., iff e_1 and e_2 are a cut-edge pair. The cycle-equivalence classes of the control-flow graph are used in optimizing compilers to speed ...

1994

Binary Relations and Cartesian Products MATH-110(a): Advanced linear algebra I

Explores binary relations, Cartesian products, and applications between sets, emphasizing their properties and significance.

Sets and Functions CS-101: Advanced information, computation, communication I

Introduces binary relations, functions, and various types of relations in sets.

Relations: Reflexive, Symmetric, Antisymmetric, Transitive CS-101: Advanced information, computation, communication I

Explains binary relations on a set and their properties with illustrative examples.

Asymmetric relation

In mathematics, an asymmetric relation is a binary relation on a set where for all if is related to then is not related to A binary relation on is any subset of Given write if and only if which means that is shorthand for The expression is read as " is related to by " The binary relation is called if for all if is true then is false; that is, if then This can be written in the notation of first-order logic as A logically equivalent definition is: for all at least one of and is , which in first-order logic c

Homogeneous relation

In mathematics, a homogeneous relation (also called endorelation) on a set X is a binary relation between X and itself, i.e. it is a subset of the Cartesian product X × X. This is commonly phrased as "a relation on X" or "a (binary) relation over X". An example of a homogeneous relation is the relation of kinship, where the relation is between people. Common types of endorelations include orders, graphs, and equivalences. Specialized studies of order theory and graph theory have developed understanding of endorelations.

Transitive relation

In mathematics, a relation R on a set X is transitive if, for all elements a, b, c in X, whenever R relates a to b and b to c, then R also relates a to c. Each partial order as well as each equivalence relation needs to be transitive. A homogeneous relation R on the set X is a transitive relation if, for all a, b, c ∈ X, if a R b and b R c, then a R c. Or in terms of first-order logic: where a R b is the infix notation for (a, b) ∈ R. As a non-mathematical example, the relation "is an ancestor of" is transitive.

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a