Relations in a cross-compiler

Let A and B be the two sets; then the relationship R between A and B is nothing more than a set of ordered pairs (a, b) such that a is in A and b is in B, and a is related to b by relation R. That is:

R = { (a, b) | a is in A and b is in B, and a is related to b by R }

For example, if A = { 0, 1 } and B = { 1, 2 }, then we can define a relation of ‘less than,’ denoted by < as follows:

A pair (1, 1) will not belong to the < relation, because one is not less than one. Therefore, we conclude that a relation R between sets A and B is the subset of A � B.

If a pair (a, b) is in R, then aRb is true; otherwise, aRb is false.

A is called a "domain" of the relation, and B is called a "range" of the relation. If the domain of a relation R is a set A, and the range is also a set A, then R is called as a relation on set A rather than calling a relation between sets A and B. For example, if A = { 0, 1, 2 }, then a < relation defined on A will result in: < = { (0, 1), (0, 2), (1, 2) }.

Properties of the Relation

Let R be some relation defined on a set A. Therefore:

1. R is said to be reflexive if aRa is true for every a in A; that is, if every element of A is related with itself by relation R, then R is called as a reflexive relation.

2. If every aRb implies bRa (i.e., when a is related to b by R, and if b is also related to a by the same relation R), then a relation R will be a symmetric relation.

3. If every aRb and bRc implies aRc, then the relation R is said to be transitive; that is, when a is related to b by R, and b is related to c by R, and if a is also related to c by relation R, then R is a transitive relation.

   If R is reflexive and transitive, as well as symmetric, then R is an equivalence relation.

Property Closure of a Relation

Let R be a relation defined on a set A, and if P is a set of properties, then the property closure of a relation R, denoted as P-closure, is the smallest relation, R′, which has the properties mentioned in P. It is obtained by adding every pair (a, b) in R to R′, and then adding those pairs of the members of A that will make relation R have the properties in P. If P contains only transitivity properties, then the P-closure will be called as a transitive closure of the relation, and we denote the transitive closure of relation R by R⁺; whereas when P contains transitive as well as reflexive properties, then the P-closure is called as a reflexive-transitive closure of relation R, and we denote it by R*. R⁺ can be obtained from R as follows:

For example, if: