Документ взят из кэша поисковой машины. Адрес оригинального документа : http://chronos.msu.ru/old/EREPORTS/graev_geometric.pdf Дата изменения: Sat Dec 14 12:30:48 2013 Дата индексирования: Fri Feb 28 20:29:40 2014 Кодировка:

Geometric and Topological Structures Related to Universal Algebras
Research Institute for Systems Research, Russian Academy of Sciences, 109280 Moscow, Russia

M. I. Graev and A. V. Koganov
Received December 23, 2002

Abstract.

system is closed with respect to the operations and forms a semimodular lattice similar to the system of subspaces of a pro jective space. This structure enables one to extend the metric and topology from the system of generators of the A-system to the entire A-system in such a way that the Archimedean and Hausdor properties are preserved under the extension.

A-systems) that includes free algebras with an arbitrary set of operations, their commutative and idempotent modi cations, and some other ob jects. It turns out that there is a system of subsets (the so-called planar subsets) of the support of an arbitrary tame A-system, and this

In the paper, a special class of universal algebras is introduced (the so-called tame

INTRODUCTION 1. The paper is devoted to universal algebras. Recall that a universal algebra is de ned by a set U with an arbitrarily given collection F of mappings f : U n ! U , n = 0 1 2 : :: where the number n depends n f 2 F . The set U is referred to as the support of the universal algebra and on the mappings f : U ! U as n-ary operations on U , see 1, 2]. The universal algebra with support U and the set of operations F is denoted in the paper by (U F ), the subset of n-ary operations of U by Fn , and the image of a sequence (u1 ::: un ) 2 U n under an n-ary operation f by f (u1 ::: un ). It is assumed that F contains no 0-ary operations ? ! U (under a 0-ary operation, some element u 2 U becomes xed). For brevity, instead of the term \universal algebra" we always use the term \A-system." The theory of universal algebras has been developing extensively since the forties of the last century. Since the notion of universal algebra is sometimes too general, the investigations in this area are related to some restrictions concerning the operations in F . 2. In the paper, we consider A-systems (universal algebras) (U F ) satisfying the following two conditions. Condition 1 (uniqueness of decompositions). For any element u 2 U , there exists at most one representation (up to the order of elements u1 ::: un ) of the form u = f (u1 ::: un) f 2F (1) where ui 6= u for at least one index i. Condition 2. The support U is generated by the subset of elements in U which are not representable in the form (1). This means that every element u 2 U can be obtained from these elements by a composition of nitely many operations f 2 F . We refer to the universal algebras of this kind as tame A-systems. The class of tame A-systems includes all free, free commutative, and free idempotent A-systems. An A-system (U F )is saidto be free if (1) the relation f (u1 ::: um )= f 0 (u01 ::: u0n ) (2) holds if and only if f = f 0 (and hence m = n)and ui = u0i for each i (2) there are no relations of the form u = f (u : : : u), and (3) the support U is generated by the subset of elements in U not representable in the form u = f (u1 ::: un).
Supported by RFBR under grant no. 01-01-00754.

57


The simplest examples of free A-systems are as follows: 1) a sequence fx1 ::: xn ::: g with the only unary operation f (xn ) = xn+1 2) U is the set of \words" in the one-letter alphabet: a aa a(aa) (aa)a (aa)(aa) etc. the only binary operation given on U is the concatenation f (u v )= uv (juxtaposition of words). An A-system (U F ) is said to be free commutative if Condition 1 of the previous de nition is replaced by a weaker one, namely, relation (2) holds if and only if f = f 0 and the sequences (u1 ::: um ) and (u01 ::: u0n ) di er in their order only. An A-system (U F ) is said to be free idempotent if u = f (u ::: u) for all u 2 U and f 2 F and there are no other relations. 3. The tame A-systems (U F ) are endowed with several important structures. These are, rst, integral-valued characteristics of elements of the support, namely, the height of an element (the number of successive iterations of operations used to construct the given element from the indecomposable ones) and the length of an element u (the number of symbols of elements in a \word" expressing u in terms of indecomposable elements). We stress that, in a tame A-system, the length and the height of an element are de ned uniquely. Further, to any element u of a tame A-system one can assign a nite directed graph of tree type (decomposition scheme) whose vertices are operations used when constructing this element from indecomposable elements. The support U of anytame A-system is naturally endowed with a partial order relation. Finally,to any tame A-system, one can assign a directed graph whose vertices are elements of the support of this system. For any free A-system, this graph completely reconstructs the A-system up to isomorphism. These structures are studied in Section 2. 4. In Section 3 we assign to any tame A-system (U F ) an analog of pro jective space. We consider the family L of subsets V U that are closed with respect to the operations in F and have the nite base property. The number of base elements is called the rank of the set V and is denoted by r(V ). Note that an inclusion V1 V does not imply the inequality r(V1) 6 r(V ) because the set V can contain subsets of arbitrarily large rank. The set L is endowed with the structure of lattice with respect to the operation of intersection. However, this lattice is not semimodular, and therefore cannot be viewed as a geometric ob ject 4, 5]. In the lattice L,wechoose a family L0 L of elements V 2 L satisfying the following maximality condition : there exist no subsets V 0 2 L strictly containing V and such that r(V 0 ) 6 r(V ) these subsets are said to be planar. We prove that the family L0 of planar subsets is closed with respect to the operation of intersection, and therefore the sets L0 and L are simultaneously endowed with the structure of a lattice with respect to this operation. Note that the operations of union in L0 and L are di erent, and hence L0 is not a sublattice of L. It turns out that the lattice L0 is semimodular. Thus, one can naturally interpret the elements of V of rank r as planes of dimension r ; 1 in the \pro jective" (generally in nite-dimensional) space U because these ob jects satisfy the main axioms on the intersections and unions of planes. The speci c feature of the geometry thus de ned is that, on every plane of dimension n,wehave a uniquely chosen set of n + 1 points generating the plane (elements of the base). Here the base of the intersection of two planes is contained in the union of the bases of these planes. Starting from the notion of a planar subset, we then introduce the notion of plane in the support U of a tame A-system. An F -subset V U of a tame A-system A = (U F ) is called a plane if every planar subset in V is a planar subset in U . In particular, all planar subsets in U are planes. We prove that eachintersection of planes is also a plane. Thus, the set of planes is endowed with the structure of a lattice, and the family of planar subsets forms a sublattice of this lattice. It is shown that the lattice of planes is also semimodular. 5. Sections 4 and 5 are devoted to topological and metric universal A-systems. An A-system (U F ) is said to be topological (metric ) if the support U of this system is endowed with the structure of a topological (metric) space with respect to which all operations f 2 F are continuous.
RUSSIAN JOURNAL OF MATHEMATICAL PHYSICS Vol. 10 No. 1 2003


If (U F ) is a tame A-system, then, starting from a topology (metric) on U , one can de ne the topology (metric) on the set L of all subsets V U of nite rank that are closed with respect to the operations in F . Here we restrict ourselves to free, free commutative, and free idempotent A-systems only. We construct an extension of the Hausdor topology and metric, Archimedean and non-Archimedean, which are initially given on the base X U only, to the Hausdor topology (Archimedean and non-Archimedean metric, respectively) on the entire support U . In the case of free idempotent A-system, we construct an extension of the topology to X to another topology on U , whichis weaker than the previous one. In this new (\secondary") topology, bases of neighborhoods are subsets of U closed with respect to the operations in F and generated by sets open in the original topology. Similarly, a non-Archimedean metric on X can be extended to a new non-Archimedean metric on U . In this new metric, every ball is a subset of U generated by a ball in the original metric and closed with respect to the operations in F . On the base of the topology and metric constructed on U , we then construct a topology and metric on the family L of all nite-rank subsets V U closed with respect to the operations in F . It is proved that, with respect to the topology thus constructed, the family L0 of planar subsets paying the role of planes in our geometry forms an open dense set. 1. A-SYSTEMS 1:1: De nition of A-System By an A-system we mean a pair A = (U F ) consisting of a set U of elements (the support of the A-system) and a set F of operations f : U n ! U (the fundamental set). For any operation f , the parameter n = n(f ) can be an arbitrary nonnegativeinteger, which is called the arity of the operation f , and f itself is called an n-ary operation. The subset of all n-ary operations is denoted by Fn . By de nition, each 0-ary operation xes some element of the set U . The image of an arbitrary sequence (u1 ::: un ) 2 U n under an n-ary operation f is denoted by f (u1 ::: un ). Example. 1) A set U with a chosen set of mappings f : U ! U . 2) A set U with a single binary operation (multiplication) f : U U ! U (a groupoid) 3]. A homomorphism of one A-system into another and an isomorphism of two A-systems are de ned in the usual way. The de nition of A-system coincides with the traditional de nition of a universal algebra 1, 2], and, if additional relations are de ned on the elements of the support, with the de nition of an algebraic system. However, the last term was recently overloaded by other interpretations in various areas of mathematics. Since, in the present paper, we foresee introducing some additional relations, we use a special term \A-system" to avoid varying readings. In this paper, we assume that all A-systems under consideration contain no 0-ary operations. 1:2:F -Subsets and A-Subsystems Let A = (U F ) be an arbitrary A-system. Any subset U 0 U closed with respect to the operations f 2 F is said to be F -closed or, brie y, an F -subset. By de nition, an empty set is assumed to be F -closed. The A-systems of the form A0 = (U 0 F ), where U 0 U is an arbitrary F -subset, are said to be A-subsystems (or simply subsystems ) of the original A-system A =(U F ). Wesay that a subsystem (U 0 F )is embedded in a subsystem (U 00 F )if U 0 U 00 . If all subsets U U are F -subsets, then their intersection \U is also an F -subset, and the subsystem (\U F ) is called the intersection of the subsystems (U F ). Hence, the family of all F -subsets U 0 U and the set of subsystems A0 =(U 0 F )ofevery A-system A =(U F ) are endowed with the structures of lattices with respect to embedding. In these lattices, the products (the compositions) U1 ^ U2 and A1 ^ A2 of F -sets U1 and U2 and subsystems A1 =(U1 F )and A2 =(U2 F ) are the set U1 \ U2 and the subsystem (U1 \ U2 F ), respectively, and the sums (disjunctions) U1 _ U2 and A1 _ A2 are the intersection U 0 of all F -subsets containing U1 and U2 and the subsystem A0 =(U 0 F ), respectively.
RUSSIAN JOURNAL OF MATHEMATICAL PHYSICS Vol. 10 No. 1 2003


1:3: Generating and Basis Subsets For any A-system A =(U F ), denote by f (U 0 ), where U 0 U and f 2 F , the image of the set U n , n = n(f ), under the mapping U n ! U . Toany subset X U we assign the sequence of subsets X1 ::: Xn ::: (3) where X1 = X , and the sets Xn are de ned by induction on n,

Xn =
Obviously, their union

f 2F

f ((X

1

Xn;1 )
1
n
=1

n(f

)

):

U0 =

X

n

is an F -subset, and therefore the pair A0 =(U 0 F )isan A-subsystem of A. This subsystem is said to be generated by the subset X U .We then write U 0 = U (X ) A0 = A(X ): The set X is said to be a generating subset of the F -subset U 0 and of the subsystem A0 . A subsystem is said to be nitely generated if it admits a nite generating subset. We say that X U is a base subset (in other words, is a base or a base ) of an A-system A =(U f )if A is a generated set X and any proper subset X 0 X is not a generating set for A. If X is a base subset of an A-system A =(U F ), then we write U X ] and A X ] instead of U (X ) and A(X ), respectively. Note that every nitely generated A-system has a nite base. 1:4: Height and Length of Elements Let A(X ) = (U F ) be an A-system generated by a set X U . By the height of an element u 2 U with respect to X we mean the number hX (u) that is the least of the positive integers n for which u 2 Xn , where fXn g is the sequence (3) de ned in Subsection 1.3. It follows from the de nition that 1) hX (u) = 1 if and only if u 2 X 2) if hX (u)= n> 1, then the element u can be represented in the form u = f (u1 ::: uk ), where max(hX (u1 ) ::: hX (uk )) = n ; 1. Let us de ne the length lX (u)ofanelement u 2 U by induction on hX (u). If hX (u) = 1, then we assume that lX (u) = 1. If hX (u) > 1, then we consider all representations of u in the form u = f (u1 ::: un(f )) f 2F where hX (ui ) 1 1

RUSSIAN JOURNAL OF MATHEMATICAL PHYSICS

Vol. 10

No. 1

2003


1:5: Indecomposability Condition for Elements An element u 2 U of an A-system A = (U F ) is said to be indecomposable if it cannot be represented in the form u = f (u1 ::: un(f ) ), where ui 6= u for at least one index i. By de nition, if an element u admits a representation of the form u = f (u : : : u), this is not a decomposition. Note that there are A-systems whichhave no indecomposable elements. For example, consider a set U of three elements x1 x2 x3 with a single binary operation (multiplication):

xi xi = x

i

i =1 2 3

xi xj = xk

for any pairwise distinct indices i j k. The following assertion results from the de nition of indecomposability.
able elements of this A-system.

Proposition 1.2. Each subset U

0

U generating an A-system (U F ) contains al l indecompos-

Corollary. If a subset X U of indecomposable elements generates the A-system (U F ), then X is a base, and this base of the A-system is unique.
1:6:N -Systems An A-system A =(U F ) is referred to as an N -system if it is generated by a subset X U of indecomposable elements. In this case, X is a base, and this base of the A-system A is unique in particular, A = A X ]. The cardinality of the set X is called the rank of the N -system A X ] and is denoted by

r(A X ]) = r(A)

r(A X ]) = #X:

Denote by h(u)and l(u) the height and thelengthofanelement u of an N -system with respect to its base.

a sequence of subsets Yn U by induction on n. Set Y1 = X10 \ U .Let Y1 ::: Yn;1 be already de ned. Let us de ne Y0n as the subset of elements in Xn \ U that do not belong to the subset U (Y1 Yn;1 )S U generated by Y1 Yn;1 . It follows from the de nition that the elements of the subset Y = 1 Yn are indecomposable in A0 =(U 0 F ) and generate A0 . n=1 In what follows, we consider only N -systems unless otherwise stated explicitly. 1:7: Commutative and Idempotent A-Systems An A-system A = (U F ) is said to be commutative if, for any operation f 2 F and any u1 ::: un(f ), the element u = f (u1 ::: un(f ) ) is preserved under all permutations of the elements u1 ::: un(f ) . An A-system A = (U F ) is said to be idempotent if f (u : : : u) = u for any u 2 U and any operation f 2 F . Note that if A =(U F ) is an idempotent A-system, then (fug F ) is a subsystem of A for any u 2 U.
RUSSIAN JOURNAL OF MATHEMATICAL PHYSICS Vol. 10 No. 1 2003

Proposition 1.3. Each subsystem A0 =(U 0 F ) of an N -system A X ]= (U F ) is an N -system. Proof. Let fXng be the sequence of subsets Xn U introduced0 in Subsection 1.3. We de ne 0


2. TAME A-SYSTEMS 2:1: Free A-Systems An A-system A(X )= (U F ) generated by a subset X U is said to be free if 1) the relation f (u1 ::: un(f ) ) = f 0 (u01 ::: u0n(f 0) ) holds if and only if f = f 0 (and hence n(f )= n(f 0 )= n) and ui = u0i, i =1 ::: n 2) no element u 2 X can be represented in the form u = f (u1 ::: un(f )). In particular, A is an N -system and X is its unique base consisting of indecomposable elements. The simplest example of a free A-system is given by a sequence fx1 ::: xn ::: g with the single unary operation f (xn )= xn+1 . The base of this A-system is X = fx1 g. The following proposition results from the de nition and Proposition 1.3. Proposition 2.1. Each subsystem of a free A-system is a free A-system. Let us note the following obvious fact. Proposition 2.2. In any free A-system A =(U F ), to each element x 2 U of height n, there corresponds an injective mapping x : F ! X (n+1) , where X (n+1) U is a subset of elements of height n +1 de ned by the formula x f = f (x : : : x):
and only if r(A) = r(A ) (i.e., #X = #X ) and #Fn = #Fn , n = 1 2 ::: , where Fn 0 Fn F 0 are the subsets of n-ary operations.

Proposition 2.3. Two free A-systems A X ]= (U F ) and 0A0 X 0]= (U 0 F 0 ) are isomorphic if 0 0

F and

Proof. In one direction, the assertion is obvious: if A-systems A and A0 are isomorphic, then the 0 condition of the proposition is satis ed. Conversely,let #X =#X 0 and #Fn =#Fn , n =1 2 :: : 0 and : Fn ! Fn , n =1 2 :: : Let us extend the bijection 0 then there exist bijections : X ! X to a bijection : U ! U 0 by induction on h(u). Let be already de ned for elements of heightless than n, and let h(u)= n, where n> 1. By de nition, the element u can be represented in the form u = f (u1 ::: uk(f )) f 2 F where h(ui ) 2:2: Embedding in a FreeGroupoid Consider a special case of a free A-system given by a free groupoid, i.e., a set with one binary operation whichwe call multiplication. According to the general de nition, a groupoid G generated by a subset X G is said to be free if 1) the relation x1 y1 = x2 y2 holds if and only if x1 = x2 and y1 = y2 2) no element x 2 X is representable in the form of a product x = x1 y1 .
RUSSIAN JOURNAL OF MATHEMATICAL PHYSICS Vol. 10 No. 1 2003


Let A X ]= (U F ) be a free A-system with base X U . Let us construct an embedding by induction on h(u), where G X then weset (u)= u.Let (u) be Let us rst de ne a mapping k of height less than n,by induction
1

(u)= (u)

U ! G X F] F ] is a free groupoid with base X F .If h(u)=1,i.e., u 2 X , already de ned for all elements of height less than n. :(Un ) k ! G X F ], where Un U is the subset of elements on k =1 2 ::: Namely,weset k (u1 ::: uk )= k;1 (u1 ::: uk;1 ) (uk ):

Note that the mappings k :(Un ) k ! G X F ] agree with the mappings k :(Um ) k ! G X F ] for m< n. Let h(u)= n. The element u has a representation in the form u = f (u1 ::: uk(f )), where f 2 F , h(ui ) RUSSIAN JOURNAL OF MATHEMATICAL PHYSICS Vol. 10 No. 1 2003


2) the following uniqueness condition holds for the decompositions: for any decomposable element u 2 U , there is a unique representation (up to the order elements ui ) of the form u = f (u1 ::: un(f )) where ui 6= u for at least one index i. In a tame A-system anytwo representations u = f (u1 ::: un(f )) and u = f (u01 ::: u0n(f )), (u1 ::: un(f ) ) and (u01 ::: u0n(f ) ) di er on the order only, are regarded as the same decompo It follows from the uniqueness condition for the decompositions that the following property Proposition 2.4. In a tame A-system, it follows from a decomposition

of the where sition. holds.

u = f (u1 ::: un)
that

where h(ui )
i =1 ::: n

h(u) = max(h(u1) ::: h(un)) + 1 l(u)= l(u1 )+ + l(un ): If an idempotent A-system is free, free commutative, or free idempotent, then it is a tame A-system. In general, in an arbitrary tame A-system, the permutation condition and the idempotent condition hold only for some subsets of operations and elements. Namely, let A X ] = (U F ) be an arbitrary tame A-system. For any f 2 F and u1 ::: un(f ) 2 U , write U (f )= fu 2 U j u = f (u : : : u)g
and denote by M (f u1 ::: un(f ) ) the subset of permutations (arrangements) u01 ::: u0n(f ) of the elements of u1 ::: un(f ) for which

f (u1 ::: u

n(f

)

)= f (u01 ::: u0n(f )):

The following assertion immediately results from the de nition of tame A-system. Proposition 2.5. Each tame A-system A X ]= (U F ) is uniquely de ned up to isomorphism by the sets U (f ) and M (f u1 ::: un(f ) ). Note that, for any tame A-system A = (U F ), one can de ne a natural surjection U 0 ! F , where U 0 U is the subset of all decomposable elements. Namely,to any element u 2 U 0 , there corresponds an element f 2 F de ning the decomposition of u, u = f (u1 ::: un ). Proposition 2.6. Every subsystem of a tame A-system is a tame A-system. As in the case of a free A-system, the assertion immediately follows from Proposition 1.3 and from the de nition of tame A-system. 2:5: Subordination Relation Let us introduce a subordination relation on elements of the support U of an arbitrary tame A-system A =(U F ). De nition. We say that an element u0 2 U is immediately subordinated to a decomposable element u, u 6= u0 , if one can nd a sequence fu1 ::: un g U containing u0 and an n-ary operation f 2 F such that u = f (u1 ::: un): It follows from the uniqueness of the decomposition that, for any decomposable element u 2 U , the set of elements immediately subordinated to u is nite and nonempty.
RUSSIAN JOURNAL OF MATHEMATICAL PHYSICS Vol. 10 No. 1 2003


or u is decomposable and there exists a nite sequence u = u1 u2 ::: un = u of decomposable elements in which each element except for the rst one is immediately subordinated to the preceding element. According to this de nition, if (U 0 F ) is a subsystem of (U F ), u0 u00 2 U 0 , and u00 is subordinated to u0 in the subsystem (U 0 F ), then u00 is subordinated to u0 in the A-system (U F ) as well. The following assertion also results from the de nitions. Proposition 2.7. If an element u0 is subordinated to an element u, u 6= u0 , then h(u0 ) 1, then l(u0) RUSSIAN JOURNAL OF MATHEMATICAL PHYSICS Vol. 10 No. 1 2003

De nition. Wesay that an element u0 2 U is subordinated to an element u 2 U if either u0 = u 0


Let us nowchoose an arbitrary element x 2 X and consider, for any n, the mapping Fn ! U taking every operation f 2 Fn to the element f (x : : : x) 2 U . This mapping is bijective. On the other hand, the elements f (x ::: x) are those and only those graph vertices from which exactly n edges issue, and all these edges end at the point x.Thus, for any n, the cardinality of the set Fn is also uniquely de ned by the graph G. 2:8: Subsets Xu Let X be the base of a tame A-system A =(U F ). Toanyelement u 2 U we assign the subset

Xu = fx 2 X j x 6 ug:
In particular, if u 2 X , then Xu = fug. The de nition implies the following assertion. Proposition 2.9. An element u belongs to the support U 0 U of a subsystem A X 0] with base 0 X if and only if Xu X 0 . X Proposition 2.7 implies the following assertion. Proposition 2.10. If u = f (u1 ::: un(f )), then

Xu = X X U be the base of U . Then
for any u 2 U 0 and Corollary. Let and x00 2 X 00 \ U 0 ,

u1

X

un(f

)

:
0

(4)

Proposition 2.11. Let A = (U F ) be a tame A-system, let U 0 0
h(u) >h(x)

U be an F -subset, and let

x 2 Xu , x 6= u, where l stands for the length of elements in U . U00 and00U 00 be F -subsets with 00ases X 0 U 0 0and X 00 U 00 . Then, if x0 2 X 0 \ U 00 b 0 0 x 6= x , then the relations x 2 Xx00 and x 2 Xx00 cannot hold simultaneously. Indeed, otherwise the relations h(x0 ) >h(x00 )and h(x00 ) >h(x0 )would hold simultaneously. Proposition 2.12. In the notation of the previous proposition, for any u 2 U 0 , we have l(u) >
X
x2Xu

l(x):

(5)

Moreover, if u = f (u1 ::: un(f ) ), where ui 2 U 0 , and if at least two sets Xui have nonempty intersection, then inequality (5) is strict.

Proof. (We proceed by induction on hX (u).) The assertion is obvious if hX (u)) = 1. Assume that hX (u)) = n > 1 then u = f (u1 ::: un(f ) ), where ui 2 U 0 , and hX (ui ) < hX (u) for any i. By the induction assumption, X l(ui) > l(x):
Therefore, the assertion for u immediately follows from (4) and from the relation
x2Xui

l(u)= l(u1 )+

+ l(un(f ) ):

Corollary 2.1. l(u) > #Xu. Corollary 2.2. If #Xu > 1, then l(u) >l(x) for any x 2 Xu.
RUSSIAN JOURNAL OF MATHEMATICAL PHYSICS Vol. 10 No. 1 2003


2:9: Completeness Condition Let U Y ] and U Z ]be F -subsets of a tame A-system, and let U Y ] U Z ]. Wesay that U Y ]is complete in U Z ]if U Y ] 6 U Z 0 ]for any proper subset Z 0 Z . The following assertion results from the de nition of the sets Xu . Proposition 2.13. U Y ] is complete in U Z ] if and only if Z = Zy :
y2Y

Proposition 2.14. If U Y ] U Z ], then U Y ] is a complete subset of U Z 0 ] U Z ], where
Z0 =
Moreover, if these subsets U Y ] and U Z ] are of nite rank, if r(U Y ]) > r(U Z ]), and if U Y ] is strictly containedin U Z ], then the set U Y ] is also strictly contained in U Z 0 ].
y2Y

Zy :

Proof. The rst asse