Binary relations

For a well-founded choice of the best solution, it is necessary to have information about the preferences of the DM. Preferences, in the simplest sense, are the DM's ability to compare pairs of objects with each other and to choose, of two objects, the one that is more preferable to him. If a comparison operation is introduced for pairs of elements, then these two elements are said to be in a binary relation.

Definition

Binary relation Q on a set X is called a subset of the Cartesian product: Q ⊆ X × X.

It is said that elements x, y ∈ X are in relation Q, if (x, y) ∈ Q, in which case one writes xQy.

Please note!

Relations are introduced on some predefined set X, which is called the domain set of the relation.

Example of defining a binary relation. Let the domain set of the relation be the set of real numbers, X = ℝ. Let us define the binary relation Q as follows: the numbers x, y ∈ ℝ are in relation Q (xQy), if the following equality holds for them: x2 + y2 = 1. Then it can be asserted that two arbitrary numbers x, y ∈ ℝ are in relation Q, if the point with coordinates (x,y) lies on a circle of radius 1 centered at the origin.

Example of constructing a binary relation (*): consider a study group of fourth-year students. On the set H of quantities equal to the students' heights, one can introduce, for example, the following relations: Q1 = «greater than», Q2 = «equal», Q3 = «not greater than». Then for two students, Petrov, whose height is h1 = 180 cm, and Semenov, whose height is h2= 178 cm, one can write: h1Q1h2 (Petrov is taller than Semenov) and h2Qh1 (Semenov is not taller than Petrov). Here, the elements h1 and h2 are not in relation Q2.

On the set B of quantities equal to the students' average grade, one can likewise introduce relations: Q1 = «greater than», Q2 = «equal», Q3 = «not greater than». Then, if the average grades of Petrov and Semenov are b1 = 4.55 and b2 = 4.55 respectively, one can write: b1Q2b2 and b^b2.

Note that the statement «Petrov's height is greater than Semenov's average grade» makes no sense. Furthermore, denoting by G — the set of students in the group, one can introduce the relations Q = «relatives» or Q5 = «average grade greater». Then the students Petrov and Semenov will be in relation Q, if they are relatives. If Petrov's average grade is 4.55, and Ivanov's is 4.3, then Petrov and Ivanov are in the relation Petrov Q5 Ivanov.

Let us consider some basic properties of relations.

• 1. Completeness. A relation Q, defined on a set X, is said to be complete if for any pair of elements x, y ∈ X, either xQy, or yQx.
• 2. Symmetry. A relation Q, defined on the set X, is said to be symmetric if for a pair of elements x,y∈X from xQy it follows that yQx (from the fact that x is in relation Q to y, it follows that y is in relation Q to x).
• 3. Antisymmetry. A relation Q, defined on the set Xy is said to be antisymmetric if, from the fact that xQy and yQx it follows that x = y y i.e. x and y — are one and the same element of the set X.
• 4. Reflexivity. A relation Q, defined on a set X, is said to be reflexive if xQx for every x ∈ X.
• 5. Irreflexivity (antireflexivity). A relation Q, defined on a set X, is said to be irreflexive if for every x ∈ X it is not the case that xQx.
• 6. Transitivity. A relation Q, defined on a set X, is said to be transitive if, from the fact that xQy and yQzy it follows that xQz.
• 7. Acyclicity. A relation Q, defined on a set X,

is said to be acyclic if for any elements x, y, z2,..., zn ∈ X, where n —

is an arbitrary natural number, for which xQz2, z2Qz3, ..., znQy it follows that x = y.

In example (*), the relation Q1 has the properties of transitivity and acyclicity, the relation Q2 has the properties of symmetry, reflexivity and transitivity, Q3 — the properties of completeness, antisymmetry, reflexivity and transitivity.

Note that the relations Q1 and Q2, defined on the set of students' average grades in example (*), differ fundamentally in that the first relation allows students to be ordered by average grade, while the second divides students into certain performance classes. Thus, we have two types of relations: equivalence and order. Let us look at each of them in more detail.

Definition

A reflexive, symmetric and transitive relation Q on a set X is called an equivalence relation (indifference relation). For such a relation, a special notation is introduced: x ~ y, x, y ∈ X.

Examples of equivalence relations are the relations of equality or non-strict inequality, defined on the set of real numbers ℝ.

An equivalence relation divides the domain set of the relation into non-intersecting classes, called equivalence classes (sets). Then the equivalence class for an element x ∈ X will be the set

Example of an equivalence relation. Let an equality-modulo-2 relation be defined on the set of integers X : numbers x, y ∈ X are said to be comparable modulo 2, and one writes x = y (mod 2), if their difference (x - y) is evenly divisible by 2, i.e., (x - y) 2 ∈ X. This relation is reflexive, symmetric, and transitive, and hence is an equivalence relation. Moreover, it splits the set of integers X into two equivalence classes — the set of even and the set of odd integers.

Example of equivalence classes. For the group of students described in example (*), let us introduce the relation = «same average grade», which is an equivalence relation. Then student Semenov belongs to the equivalence set of student Petrov and vice versa. At the same time, students Petrov and Ivanov are not in the relation 06. In this case, the students of the group will be split into equivalence classes, each of which will contain students having the same average grade.

Definition

A complete, reflexive, antisymmetric, and transitive relation <2 on the set X is called a relation (of weak) preference, denoted x > y, x} y ∈ X. Here it is said that x is no worse than (no less preferable than) y.

An example of a weak preference relation is the partial order relation > (or <) defined on the set of real numbers.

Definition

An irreflexive and transitive relation () on the set X is called a strict preference relation or an order relation, denoted x> yy x, y € X. Here it is said that x is better (more preferable) than y.

A strict preference relation can be defined in terms of a weak preference relation as follows:

Attention!

A strict preference relation is also not complete.

An example of a strict preference relation is the order relation > (or <) defined on the set of real numbers.

Example of the «less than» and «greater than» relations. A store sells three sets of candy: «Sweet Nights» for 200 rubles, «Golden Teeth» for 450 rubles, and «Chocolate Dreams» for 600 rubles. The pensioner Maria Petrovna wants to choose the cheapest candy for herself, while the private entrepreneur Oksana Nikolaevna wants the most expensive one. Then for Maria Petrovna the preference relations will look as follows: 200 > 450, 450 > 600. For Oksana Nikolaevna the preference relations will be as follows: 600 > 450, 450 > 200. Thus, for the pensioner the preference relation is the order relation «less than» (<), while for the second buyer it is «greater than» (>).

A weak preference relation defined on the set X generates an equivalence relation on X as follows:

Using the preference and indifference relations defined on one and the same set X, one can construct the preferred and non-preferred sets of an element x ∈ X.

Definition

Suppose that on some set X a relation > or relations > and ~ are defined. The preferred set of an element x ∈ X is the set consisting of tuples of elements that are more preferred than or indifferent to the given element x:

where the symbol V denotes the logical OR.

Non-preferred set of an element € X is the set consisting of tuples of elements that are less preferred than or indifferent to the given element x.

Example of a graphical representation of a relation on a set. Suppose that the set on which the relation is defined is a square with side equal to 1: X= [0,1] x [0,1 ]. The preference and equivalence relations on X are defined as follows: for x = (x{, x2), y = (g/p y2) ∈ X

it is true that x>y if and only if x + x2 > y] + y, and x~y if and only if Then for the element the preferred set Γ* will be the shaded region shown in Fig. 7.1, including the part of the circle with radius 1 /√2 on which the point x, lies, and the non-preferred set Γt will be the remaining unshaded region, including the part of the circle containing the point x.

The use of binary relations is a convenient way of eliciting the DM's preferences in the DMP being solved, since it allows the use of such notions as «worse», «better», «no worse», «the same», etc. to compare the available alternatives. Here, the elicitation of prefer-

Fig. 7.1. The preferred and non-preferred sets of preferences of the DM by means of binary relations has the following characteristics:

• • each alternative is considered in pairs with others, rather than on its own;
• • the result of comparing each pair of alternatives does not depend on whether any other alternatives exist;
• • each pair of alternatives can be compared according to some relation, or declared incomparable.

The drawbacks of the binary relations method include its labor-intensiveness: pairwise comparison of n alternatives requires n(n - 1)/2 operations, as well as the impossibility of analyzing a single alternative in isolation without comparing it to others. Moreover, not every preference relation exhibits the property of acyclicity. Thus, in the children's game «rock, scissors, paper», it is known that rock beats scissors, scissors beat paper, and paper beats rock, and it becomes impossible to choose the best of the three alternatives.

Another important aspect is that the notions of indifference for the DM and of indifference (equivalence) from the standpoint of binary relations may not be the same. In many practical situations, indifference from the DM's standpoint does not possess the property of transitivity. For example, for someone the choice between mineral water and tea, as well as between tea and coffee, may turn out to be indifferent, but the choice between coffee and mineral water will always be made in favor of one particular beverage (say, coffee).