predicates {relations}R Documentation

Relation Predicates

Description

Predicate functions for testing for binary relations and endorelations, and special kinds thereof.

Usage

relation_is_Ferrers(x)
relation_is_antisymmetric(x)
relation_is_asymmetric(x)
relation_is_bijective(x)
relation_is_binary(x)
relation_is_complete(x)
relation_is_coreflexive(x)
relation_is_crisp(x)
relation_is_endorelation(x)
relation_is_equivalence(x)
relation_is_functional(x)
relation_is_injective(x)
relation_is_interval_order(x)
relation_is_irreflexive(x)
relation_is_left_total(x)
relation_is_linear_order(x)
relation_is_match
relation_is_negatively_transitive
relation_is_partial_order(x)
relation_is_reflexive(x)
relation_is_right_total(x)
relation_is_semiorder(x)
relation_is_semitransitive(x)
relation_is_strict_linear_order(x)
relation_is_strict_partial_order(x)
relation_is_strongly_complete(x)
relation_is_surjective(x)
relation_is_symmetric(x)
relation_is_tournament(x)
relation_is_transitive(x)
relation_is_weak_order(x)
relation_is_preference(x)
relation_is_preorder(x)
relation_is_quasiorder(x)

Arguments

x an object inheriting from class relation.

Details

A binary relation is a relation with arity 2.

An endorelation R on a set X is a relation with domain D(R) = (X, X), i.e., a binary relation on X.

For a crisp binary relation, let us write x R y iff (x, y) is contained in R.

A crisp binary relation R is called

left-total:
for all x there is at least one y such that x R y.
right-total:
for all y there is at least one x such that x R y.
functional:
for all x there is at most one y such that x R y.
surjective:
the same as right-total.
injective:
for all y there is at most one x such that x R y.
bijective:
left-total, right-total, functional and injective.

A crisp endorelation R is called

reflexive:
x R x for all x.
irreflexive:
there is no x such that x R x.
coreflexive:
x R y implies x = y.
symmetric:
x R y implies y R x.
asymmetric:
x R y implies that not y R x.
antisymmetric:
x R y and y R x imply that x = y.
transitive:
x R y and y R z imply that x R z.
complete:
for all distinct x and y, x R y or y R x.
strongly complete
for all x and y, x R y or y R x (i.e., complete and reflexive).
negatively transitive
not x R y and not y R z imply that not x R z.
Ferrers
x R y and z R w imply x R w or y R z.
semitransitive
x R y and y R z imply x R w or w R z.

Some combinations of these basic properties have special names because of their widespread use:

preorder:
reflexive and transitive.
quasiorder:
the same as preorder.
equivalence:
a symmetric preorder (reflexive, symmetric and transitive).
weak order:
complete and transitive.
preference:
the same as weak order.
partial order:
antisymmetric and transitive.
strict partial order:
an irreflexive partial order (i.e., irreflexive, antisymmetric and transitive, or equivalently: asymmetric and transitive).
linear order:
a complete partial order.
match:
strongly complete.
strict linear order:
an irreflexive linear order, or equivalently: a complete strict partial order.
tournament:
complete and asymmetric.
interval order:
complete and Ferrers.
semiorder:
a semitransitive interval order.

If R is a weak order (“weak preference relation”), I = I(R) defined by x I y iff x R y and y R x is an equivalence, the indifference relation corresponding to R.

There seem to be no commonly agreed definitions for order relations: e.g., Fishburn (1972) requires these to be irreflexive.

For a fuzzy binary relation R, let R(x, y) denote the membership of (x, y) in the relation. Write T and S for the fuzzy t-norm (intersection) and t-conorm (disjunction), respectively (min and max for the “standard” Zadeh family). Then generalizations of the above basic endorelation predicates are as follows.

reflexive:
R(x, x) = 1 for all x.
irreflexive:
R(x, x) = 0 for all x.
coreflexive:
R(x, y) > 0 implies x = y.
symmetric:
R(x, y) = R(y, x) for all x, y.
asymmetric:
T(R(x, y), R(y, x)) = 0 for all x, y.
antisymmetric:
T(R(x, y), R(y, x)) = 0 for all x ne y.
transitive:
T(R(x, y), R(y, z)) <= R(x, z) for all x, y, z.
complete:
S(R(x, y), R(y, x)) = 1 for all x ne y.
strongly complete:
S(R(x, y), R(y, x)) = 1 for all x, y.
negatively transitive:
R(x, z) <= S(R(x, y), R(y, z)) for all x, y, z.
Ferrers:
T(R(x, y), R(z, w)) <= S(R(x, w), R(z, y)) for all x, y, z, w.
semitransitive:
T(R(x, w), R(w, y)) <= S(R(x, z), R(z, y)) for all x, y, z, w.

The combined predicates are obtained by combining the basic predicates as for crisp endorelations (see above).

References

P. C. Fishburn (1972), Mathematics of decision theory. Methods and Models in the Social Sciences 3. Mouton: The Hague.

H. R. Varian (2002), Intermediate Microeconomics: A Modern Approach. 6th Edition. W. W. Norton & Company.


[Package relations version 0.3-2 Index]