Expressing Properties of Binary Relations in RA
The following table shows how many of the usual properties of binary relations can be expressed as succinct RA equalities or inequalities. Below, an inequality of the form A≤B is shorthand for the Boolean equation A∨B = B.
The most complete set of results of this nature is chpt. C of Carnap (1958), where the notation is rather distant from that of this entry. Chpt. 3.2 of Suppes (1960) contains fewer results, presented as ZFC theorems and using a notation that more resembles that of this entry. Neither Carnap nor Suppes formulated their results using the RA of this entry, or in an equational manner.
| R is | If and only if: |
|---|---|
| Functional | R•R ≤ I |
| Total or Connected | I ≤ R•R (R is surjective) |
| Function | functional and total. |
| Injective |
R•R ≤ I (R is functional) |
| Surjective | I ≤ R•R (R is total) |
| Bijection | R•R = R•R = I (Injective surjective function) |
| Reflexive | I ≤ R |
| Coreflexive | R ≤ I |
| Irreflexive | R ∧ I = 0 |
| Transitive | R•R ≤ R |
| Preorder | R is reflexive and transitive. |
| Antisymmetric | R ∧ R ≤ I |
| Partial order | R is an antisymmetric preorder. |
| Total order | R is a total partial order. |
| Strict partial order | R is transitive and irreflexive. |
| Strict total order | R is a total strict partial order. |
| Symmetric | R = R |
| Equivalence | R•R = R. R is a symmetric preorder. |
| Asymmetric | R ≠ R |
| Dense | R ∧ I– ≤ (R ∧ I–)•(R ∧ I–). |
Read more about this topic: Relation Algebra
Famous quotes containing the words expressing, properties and/or relations:
“The woman may serve as a vehicle for the rapist expressing his rage against a world that gives him pain—because he is poor, or oppressed, or mad, or simply human. Then what of her? We have waded in the swamp of compassion for him long enough.”
—Robin Morgan (b. 1941)
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)
“Words are but symbols for the relations of things to one another and to us; nowhere do they touch upon absolute truth.”
—Friedrich Nietzsche (1844–1900)