SKEDSOFT

Automata | Comp. Sc. Engg.

Binary Relation Basics: A binary relation R on S is a subset of S × S. It is a relation that can be expressed by a 2-place predicate. Examples: (i) x loves y, (ii) x > y. Set S is the domain of the relation. Theoretically, it is possible that the domain S is empty (in which case R will be empty). In all instances that we consider, the domain S will be non-empty. However, it is quite possible that S is non-empty and R is empty.
We now proceed to examine various types of binary relations. In all these definitions, we assume that the binary relation R in question is on S, i.e., a subset of S×S. For a relation R, two standard prefixes are employed: irr- and non-. Their usages will be clarified in the sequel.
Relations can be depicted as graphs. Here are conventions attributed to Andrew Hodges in [63]. The domain is represented by a closed curve (e.g., circle, square, etc) and the individuals in the domain by dots labeled, perhaps, a, b, c, and so on. The fact that a, b ∈ R will be depicted by drawing a single arrow (or equivalently one-way arrow) from dot a to dot b. We represent the fact that both a, b ∈ R and b, a ∈ R by drawing a double arrow between a and b. We represent the fact that a, a ∈ R by drawing a double arrow from a back to itself (this is called a loop). We shall present examples of these drawings in the sequel.

We shall use the following examples. Let S = {1, 2, 3}, R1 = {x, x | x ∈ S}, R2 = S × S, and R3 = {1, 1, 2, 2, 3, 3, 1, 2, 2, 1, 2, 3, 3, 2}. All these (and three more) relations are depicted in Figure 4.1.
Reflexive, and Related Notions: R is reflexive, if for all x ∈ S, x, x ∈ R. Equivalently, In R’s graph, there is no dot without a loop. Informally, “every element is related to itself.” A relation R is irreflexive if there are no reflexive elements; i.e., for no x ∈ S is it the case that x, x ∈ R. Equivalently, In R’s graph, no dot has a loop.

Note that irreflexive is not the negation (complement) of reflexive. This is because the logical negation of the definition of reflexive would be, “there exists x ∈ S such that x, x /∈ R. This is not the same as irreflexive because all such pairs must be absent in an irreflexive relation. A relation R is non-reflexive if it is neither reflexive nor irreflexive.
Equivalently,
In R’s graph, at least one dot has a loop and at least one dot does not.
Examples:

  • R1,R2,R3 are all reflexive.
  • R = ∅ is reflexive and irreflexive. It is not non-reflexive.
  • For x, y ∈ Nat, x = y2 is non-reflexive (true for x = y = 1, false for x = y = 2).

Symmetric, and Related Notions: R is symmetric if for all x, y ∈ S, x, y ∈ R ⇒ y, x ∈ R. Here, x and y need not be distinct. Equivalently, In R’s graph, there are no single arrows. If the relation holds one way, it also holds the other way.
Examples: R1,R2, and R3 are symmetric relations. Also note that ∅ is a symmetric relation. R is asymmetric if there exists no two distinct x, y ∈ S such that
x, y ∈ R ∧ y, x ∈ R. In other words, if x, y ∈ R, then y, x /∈ R.
Example: “elder brother” is an asymmetric relation, and so is < over Nat. Equivalently, There are no double arrows in its graph; if the relation holds one way, it does not hold the other. Again, note that asymmetric is not the same as the negation of (the definition of) symmetric. The negation of the definition of symmetric would be that there exists distinct x and y such that x, y ∈ R, but y, x /∈ R.
R is non-symmetric if it is neither symmetric nor asymmetric (there is at least one single arrow and at least one double arrow). Example: ∅ is symmetric and asymmetric, but not non-symmetric. R is antisymmetric if for all x, y ∈ S, x, y ∈ R ∧ y, x ∈ R ⇒ x = y (they are the same element). Equivalently, There is no double arrow unless it is a loop. Antisymmetry is a powerful notion that, unfortunately, is too strong for many purposes. Consider the elements of 2S, the powerset of S, as an example. If, for any two elements x and y in S, we have x ⊆ y and y ⊆ x, then we can conclude that x = y. Therefore, the set containment
relation ⊆ is antisymmetric; and hence, antisymmetry is appropriate for comparing two sets in the “less than or equals” sense. Consider, on the other hand, two basketball players, A and B.
Suppose the coach of their team defines the relation BB as follows: A ≤BB B if and only if B has more abilities or has the same abilities as A. Now, if we have two players x and y such that x ≤BB y and y ≤BB x, we can conclude that they have identical abilities - they don’t end up becoming the very same person, however! Hence, BB must not be antisymmetric. Therefore, depending on what we are comparing, antisymmetry may or may not be appropriate.