PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 93 (107) (2013), 127–132 DOI: 10.2298/PIM1307127R

QUASI-REGULAR RELATIONS – A NEW CLASS OF RELATIONS ON SETS

Daniel A. Romano

Communicated by Siniša Crvenković

Abstract. Following Jiang Guanghao and Xu Luoshan’s concept of conjugative, dually conjugative, normal and dually normal relations on sets, the concept of quasi-regular relations is introduced. Characterizations of quasi-regular relations are obtained and it is shown when an anti-order relation is quasiregular. Some nontrivial examples of quasi-regular relations are given. At the end we introduce dually quasi-regular relations and give a connection between these two types of relations.

1. Introduction and Preliminaries

The regularity of binary relations was first characterized by Zareckiǐ [9]. Further criteria for regularity were given by Hardy and Petrich [3], Markowsky [7], Schein [8] and Xu Xiao-quan and Liu Yingming [11] (see also [1] and [2]). The concepts of conjugative relations, dually conjugative relations and dually normal relations were introduced by Guanghao Jiang and Luoshan Xu [4], [5], and a characterization of normal relations was introduced and analyzed by Jiang Guanghao, Xu Luoshan, Cai Jin and Han Guiwen [6]. In this paper, we introduce and analyze the so-called quasi-regular relations on sets.

Notions and notations which are not explicitly exposed but are used in this article, readers can find e.g., in [3] and [11].

For a set X, we call ρ a binary relation on X, if ρ ⊆ X × X. Let B(X) denote the set of all binary relations on X. For α, β ∈ B(X), define

β ∘ α = {(x, z) ∈ X × X : (∃y ∈ X)((x, y) ∈ α ∧ (y, z) ∈ β)}.

The relation β ∘ α is called the composition of α and β. It is well known that (B(X), ∘) is a semigroup. For a binary relation α on a set X, define α^{−1} = {(x, y) ∈ X × X : (y, x) ∈ α} and α^{C} = (X × X) ∖ α.

2010 Mathematics Subject Classification: Primary 06A11; 06B35.

Let A and B be subsets of X. For α ∈ B(X), set

Aα = {y ∈ X : (∃a ∈ A)((a, y) ∈ α)}, αB = {x ∈ X : (∃b ∈ B)((x, b) ∈ α)}.

Specially, we put aα instead of {a}α and αb instead of α{b}.

2. Quasi-regular relations

The following classes of elements in the semigroup B(X) are known.

Definition 2.1. For a relation α ∈ B(X) we say that it is:

(1) regular if and only if there exists a relation β ∈ B(X) such that

α = α ∘ β ∘ α.

(2) [6] normal if and only if there exists a relation β ∈ B(X) such that

α = α ∘ β ∘ (α^{C})^{−1} .

(3) [5] dually normal if and only if there exists a relation β ∈ B(X) such that

α = (α^{C})^{−1} ∘ β ∘ α.

(4) [4] conjugative if and only if there exists a relation β ∈ B(X) such that

α = α^{−1} ∘ β ∘ α.

(5) [4] dually conjugative if and only if there exists a relation β ∈ B(X) such that

α = α ∘ β ∘ α^{−1} .

Diverse descriptions of regular elements of B(X) can be found in [7], [8], [9], and [10]. For any α ∈ B(X), Zaretskiĭ [10, Section 3.2] (See also [3]) introduced the following relation in his study of regular elements of B(X),

α^{+} = {(x, y) ∈ X × X : α ∘ {(x, y)} ∘ α ⊆ α}.

Schein in [8, Theorem 1] proved that α^{+} = (α^{−1} ∘ α^{C} ∘ α^{−1} )^{C} is the maximal element in the family of all elements β ∈ B(X) such that α ∘ β ∘ α ⊆ α.

In the following definition we introduce a new class of elements in B(X).

Definition 2.2. For relation α ∈ B(X) we say that it is a quasi-regular relation on X if and only if there exists a relation β ∈ B(X) such that α = α^{C} ∘ β ∘ α.

The family of quasi-regular relations is not empty. Let α ∈ B(X) be a relation such that α^{C} ∘ (α^{C})^{−1} = Id_{X}. Then, we have α = Id_{X} ∘α = α^{C} ∘ (α^{C})^{−1} ∘ α. So, such relation α is a quasi-regular relation on X. Analogously, for relation α ∈ B(X) such that α ∘ α^{−1} = Id_{X}, we have

α^{C} = Id_{X} ∘α^{C} = α ∘ α^{−1} ∘ α^{C} = (α^{C})^{C} ∘ α^{−1} ∘ α^{C}.

Therefore, the relation α^{C} is a quasi-regular relation.

Our first lemma is an adaptation of Schein’s concept exposed in [8, Theorem 1], (See also [2, Lemma 1]) for our needs.

Lemma 2.1. For a binary relation α ∈ B(X), relation

α^{∗} = ((α^{C})^{−1} ∘ α^{C} ∘ α^{−1} )^{C}

is the maximal element in the family of all relations β ∈ B(X) such that

α^{C} ∘ β ∘ α ⊆ α.

Proof. First, remember ourselves that

max{β ∈ B(X) : α^{C} ∘ β ∘ α ⊆ α} = ⋃ {β ∈ B(X) : α^{C} ∘ β ∘ α ⊆ α}.

Let β ∈ B(X) be an arbitrary relation such that α^{C} ∘ β ∘ α ⊆ α. We will prove that β ⊆ α^{∗}. If not, there is (x, y) ∈ β such that ¬((x, y) ∈ α^{∗}). The last gives:

(x, y) ∈ (α^{C})^{−1} ∘ α^{C} ∘ α^{−1}
⇔ (∃u, v ∈ X)((x, u) ∈ α^{−1} ∧ (u, v) ∈ α^{C} ∧ (v, y) ∈ (α^{C})^{−1} )
⇔ (∃u, v ∈ X)((u, x) ∈ α ∧ (u, v) ∈ α^{C} ∧ (y, v) ∈ α^{C})
⇒ (∃u, v ∈ X)((u, x) ∈ α ∧ (x, y) ∈ β ∧ (y, v) ∈ α^{C} ∧ (u, v) ∈ α^{C})
⇒ (∃u, v ∈ X)((u, v) ∈ α^{C} ∘ β ∘ α ⊆ α ∧ (u, v) ∈ α^{C})

We got a contradiction. So, must be β ⊆ α^{∗}.

On the other hand, we should prove that α^{C} ∘α^{∗}∘α ⊆ α. Let (x, y) ∈ α^{C} ∘α^{∗}∘α be an arbitrary element. Then, there are elements u, v ∈ X such that (x, u) ∈ α, (u, v) ∈ α^{∗} and (v, y) ∈ α^{C}. So, from (x, u) ∈ α, ¬((u, v) ∈ (α^{C})^{−1} ∘ α^{C} ∘ α^{−1} ), (v, y) ∈ α^{C}, we have ¬((x, y) ∈ α^{C}). Suppose that (x, y) ∈ α^{C}. Then, we have (u, v) ∈ (α^{C})^{−1} ∘ α^{C} ∘ α^{−1} , which is impossible. Hence, we have (x, y) ∈ α and, therefore, α^{C} ∘ α^{∗} ∘ α ⊆ α.

Finally, we conclude that α^{∗} is the maximal element of the family of all relations β ∈ B(X) such that α^{C} ∘ β ∘ α ⊆ α. □

It is easy to see that α^{∗} = {(x, y) ∈ X ×X : α^{C} ∘{(x, y)}∘α ⊆ α}. In addition,

we have the following property of α^{∗}:

α^{∗} = {(x, y) ∈ X × X : αx × yα^{C} ⊆ α}

The formula α^{C} ∘ {(x, y)} ∘ α = αx × yα^{C} follows directly from our adaptation of the concept exposed in [3, Lemma 3.1(ii)].

In the following proposition we give an essential characterization of quasiregular relations. It is our adaptation of concept exposed in [3, Theorem 7.2]. (Also, we can look at this theorem as our adaptation of concepts exposed in the following theorems: Theorem 2.3 in [6], Theorem 2.4 in [5] and Theorem 2.3 in [4]).

Theorem 2.1. For a binary relation α on a set X, the following conditions are equivalent:

(1) α is a quasi-regular relation.

(2) For all x, z ∈ X, if (x, y) ∈ α, there exists u, v ∈ X such that:

(a) (u, x) ∈ α^{−1} ∧ (v, y) ∈ α^{C}

(b) (∀s, t ∈ X)((u, s) ∈ α^{−1} ∧ (v, t) ∈ α^{C} ⇒ (s, t) ∈ α).

(3) α ⊆ α^{C} ∘ α^{∗} ∘ α.

Proof. (1) ⇒ (2). Let α be a quasi-regular relation, i.e., let there exists a relation β such that α = α^{C} ∘ β ∘ α. Let (x, y) ∈ α. Then there exist elements u, v ∈ X such that (x, u) ∈ α, (u, v) ∈ β, (v, y) ∈ α^{C}. It follows that there exist elements u, v ∈ X such that (u, x) ∈ α^{−1} and (v, y) ∈ α^{C}. This proves condition (a).

Now, we check condition (b). Let s, t ∈ X be arbitrary elements such that (u, s) ∈ α^{−1} and (v, t) ∈ α^{C}. Now, from (s, u) ∈ α, (u, v) ∈ β and (v, t) ∈ α^{C} it follows (s, t) ∈ α^{C} ∘ β ∘ α = α.

(2) ⇒ (1). Define a binary relation

α′ = {(u, v) ∈ X × X : (∀s, t ∈ X)((u, s) ∈ α^{−1} ∧ ((v, t) ∈ α^{C} ⇒ (s, t) ∈ α)}

and show that α^{C} ∘ α′∘ α = α is valid. Let (x, y) ∈ α. Then there exist elements u, v ∈ X such that conditions (a) and (b) hold. We have (u, v) ∈ α′ by definition of the relation α′.

Further, from (x, u) ∈ α, (u, v) ∈ α′and (v, y) ∈ α^{C} it follows (x, y) ∈ α^{C}∘α′∘α. Hence, we have α ⊆ α^{C} ∘α′∘. Contrary, let (x, y) ∈ α^{C} ∘α′∘α be an arbitrary pair. There exist elements u, v ∈ X such that (x, u) ∈ α, (u, v) ∈ α′ and (v, y) ∈ α^{C}, i.e., such that (u, x) ∈ α^{−1} and (v, y) ∈ α^{C}. Hence, by definition of the relation α′, it follows (x, y) ∈ α′ since (u, v) ∈ α′. Therefore, α^{C} ∘ α′ ∘ α ⊆ α. So, the relation α is a quasi-regular relation on X since there exists a relation α′ such that α^{C} ∘ α′∘ α = α.

(1) ⇔ (3). Let α be a quasi-regular relation. Then there exists a relation β such that α = α^{C} ∘ β ∘ α. Since α^{∗} = max{β ∈ B(X) : α^{C} ∘ β ∘ α ⊆ α}, we have β ⊆ α^{∗} and α = α^{C} ∘ β ∘ α ⊆ α^{C} ∘ α^{∗} ∘ α. Contrary, let hold α ⊆ α^{C} ∘ α^{∗} ∘ α, for a relation α. Then, we have α ⊆ α^{C} ∘α^{∗} ∘α ⊆ α. So, the relation α is a quasi-regular relation on set X. □

Corollary 2.1. Let (X, ⩽) be a poset. The relation ⩽^{C} is a quasi-regular relation on X if and only if for all x, y ∈ X such that x ⩽^{C} y there exist u, v ∈ X such that: (a′) x ⩽^{C} u ∧ v ⩽ y, and (b′) (∀z ∈ X)(z ⩽ u ∨ v ⩽^{C} z).

Proof. Let ⩽^{C} be a quasi-regular relation on set X, and let x, y ∈ X be elements such that x ⩽^{C} y. Then, by the previous theorem, there exist u, v ∈ X such that: (a) x ⩽^{C} u ∧ v ⩽ y; (b) (∀s, t ∈ X)((s ⩽^{C} u ∧ v ⩽ t) ⇒ s ⩽^{C} t). Let z be an arbitrary element and if we put z = s = t in formula (b), then we have

(z ⩽^{C} u ∧ v ⩽ z) ⇒ z ⩽^{C} z.

This is a contradiction. Hence, ¬(z ⩽^{C} u ∧ v ⩽ z). It follows z ⩽ u ∨ v ⩽^{C} z.

Contrary, let x, y ∈ X be arbitrary elements such that x ⩽^{C} y. There exist elements u, v ∈ X such that (a′) x ⩽^{C} u∧v ⩽ y and (b′) (∀z ∈ X)(z ⩽ u∨v ⩽^{C} z). Let s, t ∈ X be arbitrary elements such that s ⩽^{C} u and v ⩽ t. From s ⩽^{C} u it follows s ⩽^{C} t or t ⩽^{C} u. For z = t, we have t ⩽^{C} u ∧ (t ⩽ ∨v ⩽^{C} t) by condition (b′). Hence (t ⩽^{C} u ∧ t ⩽ u) or (t ⩽^{C} u ∧ v ⩽^{C} t). The first case is a contradiction, and the second case is impossible because v ⩽ t. Therefore, there is only possibility s ⩽^{C} t. This means that u and v satisfy condition (b) of Theorem 2.1. So, the relation ⩽^{C} is a quasi-regular relation on X. □

3. Examples

Example 3.1. Let α be a quasi-regular relation on set X. Then there exists a relation β on X such that α = α^{C} ∘ β ∘ α. If θ is an equivalence relation on X, we define relation α/θ by α/θ = {(aθ, bθ) ∈ X/θ × X/θ : (a, b) ∈ α} and β/θ by analogy. We have α/θ = (α/θ)^{C} ∘ β/θ ∘ α/θ. Indeed:

(aθ, bθ)∈ α/θ ⇔ (a, b) ∈ α = α^{C} ∘ β ∘ α
⇔ (∃ u, v ∈ X)((a, u) ∈ α ∧ (u, v) ∈ β ∧ (v, b) ∈ α^{C})
⇔ (∃ u, v ∈ X)((a, u) ∈ α ∧ (u, v) ∈ β ∧ ¬((v, b) ∈ α))
⇔ (∃ uθ, vθ ∈ X/θ)((aθ, uθ) ∈ α/θ ∧ (uθ, vθ) ∈ β/θ ∧ ¬((vθ, bθ) ∈ α/θ))
⇔ (∃ uθ, vθ ∈ X/θ)((aθ, uθ) ∈ α/θ ∧ (uθ, vθ) ∈ β/θ ∧ (vθ, bθ) ∈ (α/θ)^{C})
⇔ (aθ, bθ) ∈ (α/θ)^{C} ∘ β/θ ∘ α/θ.

So, the relation α/θ is a quasi-regular relation on X/θ.

Example 3.2. Let α be a quasi-regular element in B(X′). Then there exists a relation β ∈ B(X′) such that α = α^{C} ∘ β ∘ α. For a mapping f : X → X′ and a relation γ ∈ B(X′) we define f^{−1} (γ) by (x, y) ∈ f^{−1} (γ) ⇔ (f(x), f(y)) ∈ γ. If f is a surjective mapping, we have:

(x, y) ∈ f^{−1} (α) ⇔ (f(x), f(y)) ∈ α = α^{C} ∘ β ∘ α
⇔ (∃u′, v′ ∈ X′)((f(x), u′) ∈ α ∧ (u′, v′) ∈ β ∧ (v′, f(y)) ∈ α^{C})
⇔ (∃u, v ∈ X)((f(x), f(u)) ∈ α ∧ (f(u), f(v)) ∈ β ∧ ¬((f(v), f(y)) ∈ α))
⇔ (∃u, v ∈ X)((x, u) ∈ f^{−1} (α) ∧ (u, v) ∈ f^{−1} (β) ∧ ¬((v, y) ∈ f^{−1} (α)))
⇔ (x, y) ∈ (f^{−1} (α))^{C} ∘ f^{−1} (β) ∘ f^{−1} (α).

So, the relation f^{−1} (α) is a quasi-regular relation in X.

Example 3.3. The relation ▽_{X} on X, defined by (x, y) ∈ ▽_{X} ⇔ x ≠ y, satisfies ▽_{X} = Id_{X} ∘ Id_{X} ∘▽_{X} = ▽_{X}^{C} ∘ Id_{X} ∘▽_{X} since ▽_{X}^{C} = Id_{X}. So, ▽_{X} is a quasi-regular relation on X.

Besides, let θ be an equivalence relation on X. There is natural surjective mapping π : X −→ X/θ. Then, ▽_{X} /θ, by Example 2.1, is a quasi-regular relation on X/θ. Thus, by Example 2.2, π^{−1} (▽_{X} /θ) is a quasi-regular relation on X.

4. Dually quasi-regular relations

There is a possibility to introduce the notion of dually quasi-regular relation on sets, for example, in the following way: For a relation α ∈ B(X) we say that it is a dually quasi-regular relation on X if and only if there exists a relation β ∈ B(X) such that α = α ∘ β ∘ α^{C}. For these relations we can state dual statements of Lemma 2.1, Theorem 2.1 and Corollary 2.1.

It is easy to see that the family of these relations is not empty. Relation α ∈ B(X) satisfying (α^{C})^{−1} ∘ α^{C} = Id_{X}, is a dually quasi-regular relation. Indeed, we have α = α ∘ Id_{X} = α ∘ (α^{C})^{−1} ∘ α^{C}.

In the end we give a connection between the quasi-regular and dually quasiregular elements of B(X).

Theorem 4.1. Relation α is a quasi-regular relation on X if and only if the relation α^{−1} is a dually quasi-regular relation on X.

Proof. Indeed, if α is a quasi-regular relation, then there exists a relation β such that α = α^{C} ∘ β ∘ α. Hence

α^{−1} = (α^{C} ∘ β ∘ α)^{−1} = α^{−1} ∘ β^{−1} ∘ (α^{C})^{−1} = α^{−1} ∘ β^{−1} ∘ (α^{−1} )^{C}.

So, the relation α^{−1} is a dually quasi-regular relation on X. □

References

1. H. J. Bandelt, Regularity and complete distributivity, Semigroup Forum 19 (1980), 123–126

2. H. J. Bandelt, On regularity classes of binary relations. In: Universal Algebra and Applications. Banach Center Publications, vol. 9, PWN-Pol. Sci. Publ., Warsaw 1982, 329–333

3. D. Hardy, M. Petrich, Binary relations as lattice isomorphisms, Ann. Mat. Pura Appl. 177(1) (1999), 195–224

4. J. Guanghao, X. Luoshan, Conjugative relations and applications, Semigroup Forum 80(1) (2010), 85–91.

5. J. Guanghao, X. Luoshan, Dually normal relations on sets, Semigroup Forum 85(1) (2012), 75–80

6. J. Guanghao, X. Luoshan, C. Jin, H. Guiwen, Normal relations on sets and applications, Int. J. Contemp. Math. Sci. 6(15) (2011), 721–726.

7. G. Markowsky, Idempotents and product representations with applications to the semigroup of binary relations, Semigroup Forum 5 (1972), 95–119

8. B. M. Schein, Regular elements of the semigroup of all binary relations, Semigroup Forum 13 (1976), 95–102

9. K. A. Zaretskiĭ, Regular elements of the semigroup of binary relations, Uspehi Mat. Nauk 3(105) (1962), 177–179 (in Russian).

10. K. A. Zareckiĭ, The semigroup of binary relations, Mat. Sb. 61(3) (1963), 291–305 (In Russian)

11. X. Xiao-quan, L. Yingming, Relational representations of hypercontinuous lattices, in: Domain Theory, Logic, and Computation, Kluwer, 2003, 65–74.

Faculty of Education (Received 31 03 2012) East Sarajevo University 76300 Bijeljina Bosnia and Herzegovina

   bato49@hotmail.com