predicates: Relation Predicates

In relations: Data Structures and Algorithms for Relations

Relation Predicates

Description

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

Usage

relation_is(x, predicate, ...)
relation_is_Euclidean(x, na.rm = FALSE)
relation_is_Ferrers(x, na.rm = FALSE)
relation_is_acyclic(x)
relation_is_antisymmetric(x, na.rm = FALSE)
relation_is_asymmetric(x, na.rm = FALSE)
relation_is_bijective(x)
relation_is_binary(x)
relation_is_complete(x, na.rm = FALSE)
relation_is_coreflexive(x, na.rm = FALSE)
relation_is_crisp(x, na.rm = FALSE)
relation_is_cyclic(x)
relation_is_endorelation(x)
relation_is_equivalence(x, na.rm = FALSE)
relation_is_functional(x)
relation_is_homogeneous(x)
relation_is_injective(x)
relation_is_interval_order(x, na.rm = FALSE)
relation_is_irreflexive(x, na.rm = FALSE)
relation_is_left_total(x)
relation_is_linear_order(x, na.rm = FALSE)
relation_is_match(x, na.rm = FALSE)
relation_is_negatively_transitive(x, na.rm = FALSE)
relation_is_partial_order(x, na.rm = FALSE)
relation_is_preference(x, na.rm = FALSE)
relation_is_preorder(x, na.rm = FALSE)
relation_is_quasiorder(x, na.rm = FALSE)
relation_is_quasitransitive(x, na.rm = FALSE)
relation_is_quaternary(x)
relation_is_reflexive(x, na.rm = FALSE)
relation_is_right_total(x)
relation_is_semiorder(x, na.rm = FALSE)
relation_is_semitransitive(x, na.rm = FALSE)
relation_is_strict_linear_order(x, na.rm = FALSE)
relation_is_strict_partial_order(x, na.rm = FALSE)
relation_is_strongly_complete(x, na.rm = FALSE)
relation_is_surjective(x)
relation_is_symmetric(x, na.rm = FALSE)
relation_is_ternary(x)
relation_is_tournament(x, na.rm = FALSE)
relation_is_transitive(x, na.rm = FALSE)
relation_is_trichotomous(x, na.rm = FALSE)
relation_is_weak_order(x, na.rm = FALSE)
relation_has_missings(x)

Arguments

x	an object inheriting from class relation.
na.rm	a logical indicating whether tuples with missing memberships are excluded in the predicate computations.
predicate	character vector matching one of the following (see details): "binary", "ternary", "quaternary", "left_total", "right_total", "surjective", "functional", "injective", "bijective", "endorelation", "homogeneous", "crisp", "complete", "match", "strongly_complete", "reflexive", "irreflexive", "coreflexive", "symmetric", "asymmetric", "antisymmetric", "transitive", "negatively_transitive", "quasitransitive", "Ferrers", "semitransitive", "trichotomous", "Euclidean", "equivalence", "weak_order", "preference", "preorder", "quasiorder", "partial_order", "linear_order", "strict_partial_order", "strict_linear_order", "tournament", "interval_order", "semiorder", "acyclic" "cyclic"
...	Additional arguments passed to the predicate functions (currently, only na.rm for most predicates).

Details

This help page documents the predicates currently available. Note that the preferred way is to use the meta-predicate function relation_is(x, "FOO") instead of the individual predicates relation_is_FOO(x) since the latter will become deprecated in future releases.

A binary relation is a relation with arity 2.

A relation R on a set X is called homogeneous iff D(R) = (X, \dots, X).

An endorelation is a binary homogeneous relation.

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.

quasitransitive:

x R y and not y R x and y R z and not z R y imply x R z and not z R x (i.e., the asymmetric part of R is transitive).

trichotomous:

exactly one of x R y, y R x, or x = y holds.

Euclidean:

x R y and x R z imply y R z.

acyclic:

the transitive closure of R is antisymmetric.

cyclic:

R is not acyclic.

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:

a complete preorder (complete, reflexive, and transitive).

preference:

the same as weak order.

partial order:

an antisymmetric preorder (reflexive, antisymmetric, and transitive).

strict partial order:

irreflexive, antisymmetric, and transitive, or equivalently: asymmetric and transitive).

linear order:

a complete partial order.

strict linear order:

a complete strict partial order.

match:

strongly complete.

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 \ne 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)) \le 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) \le S(R(x, y), R(y, z)) for all x, y, z.

Ferrers:

T(R(x, y), R(z, w)) \le S(R(x, w), R(z, y)) for all x, y, z, w.

semitransitive:

T(R(x, w), R(w, y)) \le 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).

A relation has missings iff at least one cell in the incidence matrix is NA. In addition to relation_has_missings(), an is.na method for relations is available, returning a matrix of logicals corresponding to the incidences tested for missingness.

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.

Examples

require("sets")
R <- relation(domain = c(1, 2, 3), graph = set(c(1, 2), c(2, 3)))
summary(R)

## Note the possible effects of NA-handling:
relation_incidence(R)
relation_is(R, "transitive") ## clearly FALSE

relation_incidence(R)[1, 2] <- NA
relation_incidence(R)
relation_is(R, "transitive") ## clearly NA

## The following gives TRUE, since NA gets replaced with 0:
relation_is(R, "transitive", na.rm = TRUE)

relations documentation built on April 3, 2025, 5:59 p.m.