PAIR ALGEBRAS AND GALOIS CONNECTIONS

Most studies of Galois connections begin with a function and ask the q uestion: when is there a second function that is connected to the firs t? In possibly the first application of Galois connections directly re lated to the digital computer, Hartmanis and Steams posed a subtly dif ferent question: when does a relation define two functions that are Ga lois connected? Such a relation they called a ''pair algebra''. We der ive a general, necessary and sufficient condition for a relation betwe en complete posers to define a Galois connection. We give examples of pair algebras illustrating why this notion is relevant to the science of computing. (C) 1998 Elsevier Science B.V. All rights reserved.