On Some Related Problems In Domain Theory And Rough Set Theory

With the rapid development of computer science, people are paying moreattention to the research about its mathematical foundations which have beenthe common field of mathematicians and computer scientists. Domain Theory(DT) and Rough Set Theory (RST), established in 1970's and 1980's, respec-tively, are just two very important cross-discipline fields. They developed in-dependently, but they are both based on order theory and are simultaneouslyrelated to topology, algebra, category, logic and so on.They both have stronger backgrounds of computer science, in fact, it isalso necessary for the development of mathematics. On the one hand, the orig-inal purpose of Domain Theory is to provide the mathematica foundation fordenotational semantics of programming languages, where the interaction be-tween topology and order is essential. So DT becomes the research field thatmathematicians and computer scientists are commonly interested in. Actually,besides the formal semantics of programming languages, knowledge represen-tation and reasoning (KRR), and data analysis in AI, domain is still a veryvital mathematical structure in topology, dynamical systems, fractal,, measure,integral and so on. For example, from the viewpoint of the interaction betweentopology and order, domain environment provides a computational model forsome important topological spaces. On the other hand, establishing Rough Set Theory is to process the vague concept or data. But its theoretical foundationis still based on the classical mathematical branches such as topology, ordertheory, set theory, algebra, logic and so on. In the past more than 20 years,rough approach has been broadly applied in AI and cognitive science, especially,data analysis, KRR, KDD, machine learning, decision analysis, expert systems,pattern recognition, etc.As two mathematical branches, DT and RST have different research objectsand characteristics, but their studies are both done within the framework oforder and are affected each other in some aspects. The main purpose of thepaper is to discuss some aspects about their common mathematical foundation,particularly order structure. In this paper, we will use the theories of topology,order, algebra, category and logic. On the DT side, we study the duals of twoimportant and classical topologies (Hausdorff topology, Scott toplogy), retractsof Cartesian product of finite posets, related categories and domain equations.On the RST side, we give a characterization of approximation operators andstudy the related category. At last, the deeply internal relationship betweenDT and RST is established.In detail, our work is as follows.First of all, we discuss three related problems in Domain Theory.The first one is about dual topology. That is a problem in "Open Problemsin Topology" raised by Mislove and Lawson as the following: Characterize thosetopologies that arise as dual topologies; if one continues the process of takingduals, does the process terminate after finitely many steps with topologies thatare duals of each other? For this problem, we discuss the related results abouttwo classical topologies, i.e., Hausdorff topology and Scott topology. Let (X,Ñ‚)be a Hausdorff topological space. We haveÑ‚^d=Ñ‚^ddd. Therefore, if one contin-ues taking duals forÑ‚, at most 3 topologies can arise:Ñ‚,Ñ‚^d andÑ‚^dd. Accordingto the number of topologies generated by taking duals, Hausdorff spaces can be classified to three increasing classes. Then we give a characterization of Haus-dorff spaces withÑ‚=Ñ‚^dd which are precisely Hausdorff k-spaces. In addition, westudy the properties of topologies that arise as dual topologies. On the otherhand, for Scott topology, let D be a dcpo, endowed with the Scott topologyσ(D). We show a characterization and a sufficient condition ofσ(D)^d=ω(D)and study the relationship betweenσ(D)^d=ω(D), Scott compact sets andstrongly compact sets. For a dcpo D,σ(D)^dd(?)σ(D)holds. Furthermore, wegive a characterization ofσ(D)^dd=σ(D) and a sufficient condition to decideσ(D)^dd=σ(D) easily. The above results give a partial answer to the proceedingopen problem.The second and third problems are about Cartesian products of finiteposets.The second one is the following conjecture by Plotkin in [90]: for the three-element truthvalue cpo T, ifκ＞ω, then the function space [T^κ→T^κ] is nota retract of T^κ. We constructively give a positive answer to this conjecture.This result not only shows a topological and order property of the basic gen-erating structure T^κ, but also expresses a following fact: forκ＞ω, T^κcannotprovide denotational semantics for any programming languages that incorpo-rateλ-calculus, which makes clear the theoretical limit of coherent domainsgenerated by T^κas the models of denotational semantics.Similarly, based on Scott's result that any continuous lattice is preciselysome product of 2, further, Mislove and Lawson in [55] raised the followingproblem i.e. the third one of the paper: Investigate those "varieties" of topolog-ical spaces that are generated by a certain class of spaces by taking the smallestclass closed under retracts and products. When do all members of the varietyarise as a retract of a product of generating spaces? What classes arise whenone starts with a set of finite T₀ spaces? In the latter case is the variety gen-erated Cartesian Closed? Is it finitely generated? In fact, finite T₀ spaces areexactly finite posets with Scott topology, so the finite T₀ spaces can be replaced by finite posets. For this open problem, we concretely discuss any family F offinite posets whose generated spaces include T. We show that the class gen-erated by F is not Cartesian Closed. Thus the result shows that the categoryCONT of continuous lattices and continuous functions is the least CartesianClosed full subcategory (closed under products and retracts) of the variety gen-erated by any family of nontrivial finite posets. If F consists of finite nontrivialL-domains, then CONT is the unique Cartesian Closed Category of the variety.The above results of three aspects make clear some douts about dual topol-ogy, retracts of Cartesian product of finite posets and related categories.The other work of this paper is to study three problems related to orderstructure in Rough Set Theory.As mentioned previously, like DT, RST has the functions of knowledgerepresentation and reasoning, data analysis, etc., where the used key conceptis approximation operator. Firstly, we characterize the approximation opera-tor. Secondly, further we consider all approximation spaces from the angle ofcategory.Let (U, R) be an approximation space. We focus on upper approximationoperators, because lower approximation operators and upper approximationoperators are dual in some sense. We give the characterizations of upper ap-proximation operators under possible cases, which shows the deep relationshipbetween Rough Set Theory and Order Theory. Moreover, some important andnovel properties of this operator are obtained. On the other hand, the rela-tionship between approximation spaces, complete atomic boolean lattices, andcomplete prime algebraic lattices are established. Then, to process differentknowledge bases, we define a category AS_E of approximation spaces. We canuse the category-theoretic language to interpret the different processing of in-formation systems. For example, pullback can express the merging of two (ormore) source approximation spaces and pushout can express the common back- ground knowledge of two (or more) source approximation spaces, where thepullback and the pushout lie in the same square. Introducing category theoryinto Rough Set Theory breaks up the original approach that knowledge basesare processed singly. From the categorical point of view, we can process therelated or unrelated knowledge. The above studies open a new way to researchRough Set Theory.At last, based on a common research object, we establish the deep andinternal relationship between Domain Theory and Rough Set Theory throughGalois connection (â—‡,â–¡) and introducing approximation structures. First ofall, through Galois connections(â—‡,â–¡), we discuss the structures of partial or-ders on two known rough concept lattices. They are extended to infinite case,thus a rough concept representation of complete lattices is obtained. Then wediscuss the relationship between rough concept lattice and information system(in the sense of Scott) and prove that for any formal context (U, V,(?)), if Vis finite, all object-oriented concepts are precisely states of derived informationsystem. Generally, in the infinite case, we introduce rough approximable con-cept, then rough approximable concepts coincide with states of correspondingderived information system for every formal context. Furthermore, we constructa domain from any formal context, i.e., rough approximable concept lattice andshow the important representation theorem—a rough approximable concept lat-tice representation of every complete algebraic lattice. The above results notonly establish the deep relationship between Domain Theory and Rough SetTheory, but also show that some class of domains implies non-classical logicalstructure.