Pair Algebras and Galois Connections

摘要

Most studies of Galois connections begin with a function and ask the question:211u001ewhen is there a second function that is connected to the first. In possibly the 211u001every first application of Galois connections directly related to the modern 211u001edigital computer, Hartmanis and Stearns posed a subtly different question, 211u001enamely: when does a relation define two functions that are Galois connected. Such 211u001ea relation they called a 'pair algebra'. In this paper we derive a general, 211u001enecessary and sufficient condition for a relation between complete lattices to 211u001edefine a Galois connection between the lattices. We also give several examples of 211u001epair algebras illustrating why this seemingly forgotten notion is relevant to the 211u001escience of computing.