Groups in Allegories

Yasuo KAWAHARA

                        kawahara@i.kyushu-u.ac.jp

Department of Informatics, Kyushu University 33, Fukuoka 812-8581, Japan.

Abstract Groups are one of the most fundamental notions in mathematics. This paper provides a foundation of group theory in allegories. Almost all results in the paper can be applied to theory of fuzzy groups.

1 Introduction

The motivation of the paper arose from the following three fundamental exercises in group theory:

(a) Let G = (G, ·) be a semigroup, that is, a binary operation · : G × G → G is associative. Show that if ∀x ∈ G : xe = x and ∀x ∈ G∃y ∈ G : xy = e for some element e ∈ G, then ∀x ∈ G : ex = x and ∀x ∈ G∃y ∈ G : yx = e.

(b) Let H be a subgroup of a group G = (G, ·, e, ·^{−1}). Prove that the (binary) relation x ≡ y on G, defined by x^{−1}y ∈ H, is an equivalence relation.

(c) Show that the set of all normal subgroups of a group G forms a modular lattice. In other words, the following modular law holds for three normal subgroups S, T and U of G:

S ⊆ U ⇒ ST ∩ U ⊆ S(T ∩ U).

To define group objects in categories [6] is not new, but it is difficult to directly treat algebraic relations, such as residual relations (b) induced by subgroups, in the ordinary category theory. Allegories [2], as a kind of relation categories, give a natural and suitable setting for manipulating algebraic binary relations in group theory, lattice theory [5] and so on. This paper provides a foundation of group theory in allegories, and solves the above three questions (a), (b) and (c).

2 Allegories

In this section we recall the fundamentals on relation categories, called allegories [2].

Throughout this paper, a morphism α from an object X into an object Y in an allegory (which will be defined below) will be denoted by a half arrow α : X ⇁ Y, and the composite of a morphism α : X ⇁ Y followed by a morphism β : Y ⇁ Z will be written as αβ : X ⇁ Z. Also we will denote the identity morphism on X as id_{X}.

Definition 2.1 An allegory A is a category satisfying the following: D1. [Meet Semi-Lattice] For all pairs of objects X and Y the hom-set A(X, Y) consisting of all morphisms of X into Y is a meet semi-lattice with the greatest morphism ∇_{XY}. Its semi-lattice structure will be denoted by

A(X, Y) = (A(X, Y), ⊑, ⊓, ∇_{XY}).

D2. [Converse] There is given a converse operation ^{♯} : A(X, Y) → A(Y, X). That is, for all morphisms α, α′ : X ⇁ Y, β : Y ⇁ Z, the following converse laws hold:

(a) (αβ)^{♯} = β^{♯}α^{♯}, (b) (α^{♯})^{♯} = α, (c) If α ⊑ α′, then α^{♯} ⊑ α′^{♯} for all morphisms α, α′ : X ⇁ Y and β : Y ⇁ Z. D3. [Dedekind Formula] For all morphisms α : X ⇁ Y, β : Y ⇁ Z and γ : X ⇁ Z the Dedekind formula αβ ⊓ γ ⊑ α(β ⊓ α^{♯}γ) holds. D4. [Sub-Distributivity] The composition preserves order: If α ⊑ α′ and β ⊑ β′, then αβ ⊑ α′β′.

The fundamental properties of relational categories is referred to [1, 2, 7, 4]. A morphism α : X ⇁ Y is total if id_{X} ⊑ αα^{♯} (or equivalently, α∇_{Y X} = ∇_{XX}). A morphism f : X ⇁ Y such that f^{♯}f ⊑ id_{Y} (univalent) is called a function and may be introduced as f : X → Y. In what follows the word relation is used as synonym for morphisms in allegories.

Definition 2.2 A pair (A, B) of objects in an allegory A has a relational product if there exists a pair (p : A × B → A, q : A × B → B) of total functions such that p^{♯}q = ∇_{AB} and pp^{♯} ⊓ qq^{♯} = id_{A×B}. The pair (p : A × B → A, q : A × B → B) is called a pair of projections for (A, B). An allegory A has a relational product if every pair of objects in A has a relational product.

An object I in an allegory A is called a strict unit if ∇_{II} = id_{I} and ∇_{XI}∇_{IX} = ∇_{XX} for all objects X in A.

Throughout the rest of the paper we assume that A is a fixed allegory with relational products and a strict unit I.

Let ξ : A ⇁ X and η : B ⇁ Y be a pair of relations. We define a relation ξ × η : A × B ⇁ X × Y by ξ × η = pξ⊤qη = pξp_{0}^{♯} ⊓ qηq_{0}^{♯}. If f : A → X and g : B → Y are total functions, then f × g is a unique function such that (f × g)p_{0} = pf and (f × g)q_{0} = qg.

\xymatrix{A \ar[d]_{ξ} & A × B \ar[l]_{p} \ar[r]^{q} \ar[d]^{ξ×η} & B \ar[d]^{η} \\ X & X × Y \ar[l]^{p_{0}} \ar[r]_{q_{0}} & Y}

3 Binary Operations

Throughout of the rest of the paper we assume that G is an object in an allegory A and (p : G × G → G, q : G × G → G) is a pair of projections for (G, G).

Definition 3.1 A binary operation on G is a relation μ : G × G ⇁ G in A.

Let μ : G × G ⇁ G be a binary operation. Then we define α ⊙ β = (αp^{♯} ⊓ βq^{♯})μ for a pair of relations α, β : X ⇁ G. Remark that p ⊙ q = μ.

Theorem 3.2 A binary operation μ : G × G ⇁ G satisfies the associative law (μ × id_{G})μ = a(id_{G} × μ)μ if and only if (α ⊙ β) ⊙ γ = α ⊙ (β ⊙ γ) for all relations α, β, γ : X ⇁ G. (Where a stands for the associative isomorphism.)

[figure: (G × G) × G; μ×id_{G}; a; G × G; μ; G × (G × G); id_{G}×μ; G × G; μ; G]

The first qeustion (a) reflects the following theorem on our framework:

Theorem 3.3 Let ε : I ⇁ G and ι : G ⇁ G be relations satisfying id_{G}⊙∇_{GI}ε = id_{G} and id_{G}⊙ι = ∇_{GI}ε. Then the following four conditions are equivalent:

(a) ι is a total function,

(b) ι ⊙ ι^{2} = ∇_{GI}ε,

(c) ∇_{GI}ε ⊙ ι^{2} = id_{G} and ∇_{GI}ε ⊙ id_{G} = id_{G},

(d) ι^{2} = id_{G}.

4 Groups

In this section we define the notion of groups, subgroups and normal subgroups in allegories, and state the main theorems. However we limit all the operations of group structures to be total functions for the sake of simplicity. Definition 4.1 A group G = (G, m, e, i) in an allegory A is a quartet of an object G and three total functions m : G × G → G, e : I → G and i : G → G satisfying the following conditions:

(Associative Law) (m × id_{G})m = a(id_{G} × m)m,
(Right Unitary)  id_{G} ⊙ ∇_{GI}e = id_{G},
(Right Inverse)  id_{G} ⊙ i = ∇_{GI}e.

Remark in the above definition that α ⊙ β = (αp^{♯} ⊓ βq^{♯})m for a pair of relations α, β : X ⇁ G. Definition 4.2 A nonempty relation ρ : I ⇁ G is a subgroup of G if ρi ⊑ ρ and ρ ⊙ ρ ⊑ ρ.

The following theorem is a generalization of the second question (b). Theorem 4.3 If ρ : I ⇁ G is a subgroup, then θ = id_{G} ⊙ ∇_{GI}ρ is an equivalence relation on G.

Normal subgroups in allegories will be simply defined as follows: Definition 4.4 A subgroup ρ : I ⇁ G of G is called normal if id_{G} ⊙ ∇_{GI}ρ = ∇_{GI}ρ ⊙ id_{G}.

It is trivial that a subgroup ρ : I ⇁ G is normal iff α ⊙ ∇_{XI}ρ = ∇_{XI}ρ ⊙ α for all relations α : X ⇁ G. Finally we can answer to the third question (c) that the set of all normal subgroups in allegories forms a modular lattice, as in the classical case: Theorem 4.5 Let ρ, σ, τ : I ⇁ G be normal subgroups of a group G. If ρ ⊑ τ, then (ρ⊙σ)⊓τ ⊑ ρ⊙(σ⊓τ).

References

[1] C. Brink, W. Kahl and G. Schmidt (eds.), Relational methods in computer science. Advances in Computing Science, (Springer, Wien, New York, 1997).

[2] P. Freyd and A. Scedrov, Categories, allegories (North-Holland, Amsterdam, 1990).

[3] J. Desharnais, Monomorphic characterization of n-ary direct products, Information Sciences 119(1999), 275–288.

[4] Y. Kawahara, Relational set theory, Lecture Notes in Computer Science, 953(1995), 44–58.

[5] Y. Kawahara, Lattices in Dedekind categories, In: Orlowska, E. and Szalas, A. (Eds), Relational Methods for Computer Science Applications, Physica-Verlag, 2001.

[6] S. Mac Lane, Categories for the working mathematician, (Springer-Verlag, 1972).

[7] G. Schmidt and T. Ströhlein, Relations and graphs – Discrete Mathematics for Computer Science – (Springer-Verlag, 1993).

[8] A. Rosenfeld, Fuzzy groups, J. Math. Anal. Appl. 35(1971), 512–517.

[9] A. Tarski, On the calculus of relations, J. Symbolic Logic 6 (1941) 73–89.