D:\User\sbornik_38_pdf\34.DVI


Mathematical Problems of Computer Science 38, 80{81, 2012.

A Fixed P oint T heor em for q-Lattices

Y u .M.Mo vs is ya n , D .S .D a vid o va

Department of mathematics and mechanics
Yerevan State University, Yerevan, Armenia

E-mail: yurimovsisyan@yahoo.com

I ntr oduction and pr eliminar ies
B . K n a s t e r 's a n d A . Ta r s ki's s e t -t h e o r e t ic a l ¯ xe d p o in t t h e o r e m is we ll kn o wn [1 ]. A g e n -
e r a liz a t io n o f t h is r e s u lt is t h e la t t ic e -t h e o r e t ic a l ¯ xe d p o in t t h e o r e m ( n a m e d Ta r s ki's ¯ xe d
p o in t t h e o r e m ) [2 ]. In [3 ] Ta r s ki's t h e o r e m is g e n e r a liz e d fo r s e m ila t t ic e s . In t h e p r e s e n t wo r k
a ¯ xe d p o in t -like t h e o r e m is p r o ve d fo r q-la t t ic e s . Th e c o n c e p t o f a q-la t t ic e wa s in t r o d u c e d
in [4 ].

Th e a lg e b r a ( L; \; [) is c a lle d q-s e m ila t t ic e , if it s a t is ¯ e s t h e fo llo win g id e n t it ie s : 1 .a\b =
b \ a( c o m m u t a t ivit y) ; 2 . a \ ( b \ c) = ( a \ b ) \ c ( a s s o c ia t ivit y) ; 3 . a \ ( b \ b) = a \ b ( we a k
id e m p o t e n c e ) .

Th e a lg e b r a ( L; \; [ ) wit h t wo b in a r y o p e r a t io n s is c a lle d q-la t t ic e , if t h e r e d u c t s ( L; \)
a n d ( L; [) a r e q-s e m ila t t ic e s a n d t h e fo llo win g id e n t it ie s , a\ ( b[a) = a\a, a[ ( b\a ) = a[a
( we a k a b s o r p t io n ) , a \ a = a [ a ( e qu a liz a t io n ) a r e va lid .

Fo r e xa m p le , ( Z n f0 g; \; [) , wh e r e x \ y = j ( x; y ) j a n d x [ y = j[x; y]j, fo r wh ic h ( x; y )
a n d [x; y] a r e t h e g r e a t e s t c o m m o n d ivis io n ( g c d ) a n d t h e le a s t c o m m o n m u lt ip le ( lc m ) o f x
a n d y , is a q-la t t ic e , wh ic h is n o t a la t t ic e , s in c e x \ x 6= x a n d x [ x 6= x.

Th e r e la t io n Q µ L £ L is c a lle d a qu a s io r d e r if it is r e ° e xive a n d t r a n s it ive . L e t
Q b e a qu a s io r d e r o n t h e s e t L 6= ;; t h e n EQ = Q \ Q¡1 µ L £ L is a n e qu iva le n c e .
Th e r e la t io n Q=EQ wh ic h is in d u c e d fr o m Q o n t h e s e t L=EQ in t h e fo llo win g m a n n e r :
( A; B ) 2 Q=EQ $ aQb; 8a 2 A,8b 2 B , wh e r e A; B 2 L=EQ, is a n o r d e r . Fu r t h e r , t h e
o r d e r Q=EQ is d e n o t e d b y ·Q a n d t h e c la s s o f e qu iva le n c e wh ic h in c lu d e s t h e e le m e n t x is
d e n o t e d b y [x] 2 L=EQ. Th e fu n c t io n K : L=EQ ! L is c a lle d c h o ic e fu n c t io n , if K ( [a]) 2 [a]
fo r e a c h [a] 2 L=EQ. Th e p a ir ( L; Q) is c a lle d inf sup-qu a s io r d e r e d s e t , if fo r e a c h t wo c la s s e s
o f e qu iva le n c e s [a]; [b] 2 L=EQ t h e r e e xis t inf ( [a]; [b]) = [a] \ [b] a n d sup ( [a]; [b]) = [a] [ [b],
i.e . if ( L=EQ; ·Q ) is a la t t ic e .

A n inf sup-qu a s io r d e r e d s e t ( L; Q ) is c a lle d c o m p le t e , if fo r e a c h ; 6= Y 2 L=EQ t h e r e
e xis t inf ( Y ) 2 L=EQ a n d sup( Y ) 2 L=EQ , i.e . if ( L=EQ; ·Q ) is a c o m p le t e la t t ic e .

L e t ( L; Q ) b e a n infsup-qu a s io r d e r e d s e t , K : L=EQ ! L is a n a r b it r a r y c h o ic e fu n c t io n
a n d fo r a n y t wo e le m e n t s x; y 2 L we h a ve :x \ y = K ( sup( [x]; [y]) ) ; x [ y = K ( inf ( [x]; [y]) ) ;
t h e n t h e a lg e b r a ( L; \; [) is a q-la t t ic e .

L e t ( L; \; [) b e a q-la t t ic e , t h e n t h e r e la t io n aQb $ a \ b = a \ a is a qu a s io r d e r o n t h e
s e t L, t h e fu n c t io n K : L=EQ ! L , wh ic h is d e ¯ n e d in t h e fo llo win g m a n n e r K ( [a]) = a \ a
is a c h o ic e fu n c t io n a n d t h e p a ir ( L; Q) is a n infsup-qu a s io r d e r e d s e t , wh e r e inf ( [a]; [b])
a n d sup ( [a]; [b]) a r e d e ¯ n e d b y t h e fo llo win g r u le s : inf ( [a]; [b]) = [a \ b]; sup( [a]; [b]) =

8 0



Yu. Movsisyan, D. Davidova 8 1

[a [ b]: Mo r e o ve r , fo r t h e o p e r a t io n s \ a n d [ we h a ve : x \ y = K ( inf ( [x]; [y]) ) ; x [ y =
K ( sup( [x]; [y]) ) :

Th e fu n c t io n ' : L ! L o f a c o m p le t e infsup-qu a s io r d e r e d s e t ( L; Q) is c a lle d m o n o t o n e
if it fo llo ws fr o m xQy t h a t '( x) Q'( y ) .

Th e fu n c t io n ' : L ! L o f a c o m p le t e inf sup-qu a s io r d e r e d s e t ( L; Q ) is c a lle d h o m o -
m o r p h is m , if ' is a h o m o m o r p h is m o f t h e c o r r e s p o n d in g q-la t t ic e ( L; \; [ ) in t o it s e lf.

Th e p o in t x o f a n inf sup-qu a s io r d e r e d s e t ( L; Q) is c a lle d a ¯ xe d p o in t o f t h e fu n c t io n
' : L ! L, if '( x) = x.

Th e fu n c t io n ' : L ! L o f a c o m p le t e infsup-qu a s io r d e r e d s e t ( L; Q) is c a lle d a n t im o n o -
t o n e , if it fo llo ws fr o m xQy t h a t '( y ) Q'( x) .

Th e fu n c t io n ' : L ! L o f a c o m p le t e infsup-qu a s io r d e r e d s e t ( L; Q) is c a lle d a n t ih o -
m o m o r p h is m , if t h e fu n c t io n ' is a h o m o m o r p h is m fo r t h e c o r r e s p o n d in g q-la t t ic e ( L; \; [)
in t o it s e lf.

N o t e , t h a t if ' : L ! L is a h o m o m o r p h is m ( a n a n t ih o m o m o r p h is m ) o f a n infsup-
qu a s io r d e r e d s e t ( L ;Q) in t o it s e lf, t h e n t h e in d u c e d fu n c t io n ~' : L=EQ ! L=EQ , wh ic h is
d e ¯ n e d in t h e fo llo win g m a n n e r ~'( [x]) = ['( x ) ] is a h o m o m o r p h is m ( a n a n t ih o m o m o r p h is m ) .

Th e p o in t s x; y o f a n infsup-qu a s io r d e r e d s e t ( L; Q) wit h t h e p r o p e r t y xQy a r e c a lle d
a lt e r n a t ive ¯ xe d p o in t s o f t h e fu n c t io n ' : L ! L, if '( x ) = y a n d '( y ) = x.

Th e a lt e r n a t ive ¯ xe d p o in t s x; y o f t h e fu n c t io n ' : L ! L o f a n infsup-qu a s io r d e r e d s e t
( L; Q ) in t o it s e lf a r e c a lle d e xt r e m e , if fo r e a c h a lt e r n a t ive ¯ xe d p o in t s a; b o f t h e fu n c t io n '
we h a ve xQaQbQy.

M ain r esult
T heor em 1 ) E a c h h o m o m o r p h is m ' : L ! L o f t h e c o m p le t e inf sup-qu a s io r d e r e d s e t ( L; Q )
h a s a lt e r n a t ive ¯ xe d p o in t s . Mo r e o ve r , if [®] = supf[x] 2 L=EQj[x] ·Q ~'( [x]) g 2 L=EQ is
t h e g r e a t e s t ¯ xe d p o in t o f t h e fu n c t io n ~', t h e n fo r e a c h ¯ xe d p o in t a o f t h e fu n c t io n ' we h a ve
aQ( ®\® ) . S im ila r ly, if [¯] = inff[x] 2 L=EQj[x] ·Q ~'( [x]) g 2 L=EQ is t h e lo we r ¯ xe d p o in t
o f t h e fu n c t io n ~', t h e n fo r a n y ¯ xe d p o in t a o f t h e fu n c t io n ' we h a ve ( ¯ \ ¯ ) Qa. Mo r e o ve r ,
t h e infsup-qu a s io r d e r e d s e t F ix ( ') = fx 2 Lj'( x) = xg is a c o m p le t e inf sup-qu a s io r d e r e d
s e t .

2 ) E a c h a n t ih o m o m o r p h is m ' : L ! L o f t h e c o m p le t e infsup-qu a s io r d e r e d s e t ( L; Q )
h a s e xt r e m e a lt e r n a t ive ¯ xe d p o in t s .

A n a p p lic a t io n o f t h is t h e o r e m in s e m a n t ic o f lo g ic p r o g r a m m in g is c o n s id e r e d .

R e fe r e n c e s

[1 ] B . K n a s t e r , A . Ta r s ki, U ¶n t h e o r e m e s u r le s fo n c t io n s d 'e n s e m b le s , A n n . S o c . P o lo n .
Ma t h ., 1 9 2 8 , v. 6 , p . 1 3 3 -1 3 4 .

[2 ] A . Ta r s ki, A la t t ic e -t h e o r e t ic a l ¯ xe d p o in t t h e o r e m a n d it s a p p lic a t io n s , P a c ī c Jo u r n a l
o f Ma t h e m a t ic s , 1 9 5 5 , v. 5 , p . 2 8 5 -3 0 9 .

[3 ] J. B e r m a n a n d W . J. B lo k, Ge n e r a liz a t io n s o f Ta r s ki's ¯ xe d p o in t t h e o r e m fo r o r d e r
va r ie t ie s o f c o m p le t e m e e t s e m ila t t ic e s , Or d e r , 1 9 8 9 , v. 5 , p . 3 8 1 -3 9 2 .

[4 ] I. Ch a jd a , L a t t ic e s in qu a s io r d e r e d s e t s , A c t a P o la c ky U n ive r s it y, Olo m o u c , 1 9 9 2 , v. 3 ,
p . 6 -1 2 .

8 1