How to build a knowledge space by querying an expert (Q2277404)

The authors are concerned with the problem of building knowledge structures - KS - for particular domains (a KS is defined as the collection of all possible knowledge states, while the knowledge state of an individual is formalized as the subset of notions he has mastered; finally, a notion is identified with an equivalence class of questions/problems, testing just that notion). The algebraic foundation of this approach was investigated by \textit{J.-P. Doignon} and \textit{J.-C. Falmagne} [Int. J. Man-Mach. Stud. 23, 175-196 (1985; Zbl 0581.68066)]. If the KS is closed under union and intersection, then it can be equivalently specified by a quasi-order on the set of problems. When the - less realistic - assumption of closure under intersection is dropped, a representation of KSs by surmise systems - a variant of AND/OR graphs - is possible. The KSs which are closed under union are called knowledge spaces (KSP). The point of the current paper is to derive an alternative representation for KSP. Here, quasi-orders are used as relations on the power set of the set of problems; this representation is at the basis of a procedure that translates the responses of an expert to a set of queries of a specific form into a corresponding KSP. Birkhoff's theorem [\textit{G. Birkhoff}, Duke Math. J. 3, 443-454 (1937; Zbl 0017.19403)], which plays a central role in the quasi-order representation, can be derived from a Galois connection between the collection of KSs and the collection of binary relations on the set of problems. The main result of the paper under review is an extension of Birkhoff's theorem by establishing a more general Galois connection between KSs and relations on the power set of the set of problems.