An Algebraic Approach To Incompleteness In Modal Logic [phd Thesis]

An Algebraic Approach to Incompleteness in Modal Logic by Tadeusz Litak submitted to Japan Advanced Institute of Science and Technology in partial fulfillment of the requirements for the degree of Doctor of Philosophy Supervisor: Professor Hiroakira Ono School of Information Science Japan Advanced Institute of Science and Technology September 22, 2005 1 Acknowledgments I would like to thank heartily: • Professor Hiroakira Ono, the principal advisor of this thesis. His decision to accept an almost completely unknown foreigner as a PhD student was risky and brave. I can only hope he did not regret it at times. It would be impossible to write this thesis, live and study in Japan without his support. Special thanks for allowing and encouraging me to pursue problems I was really interested in, even when it was not easy to fit them into present research activity of Ono Laboratory. • My former teacher and supervisor, professor Andrzej Wro´ nski. It was and it is a rare privilege to have a master like him. I would have never become a scientist (although I could have easily become a parody of a scientist) if I had not met him at the Institute of Philosophy UJ. • Tomasz Kowalski. Together with professors Ono, Wro´ nski and Perzanowski, he worked to establish the JAIST-UJ connection, which made my studies at JAIST possible. Thanks for everything, Tomek. Hardly any foreigner in Japan has such a soft landing as the one you provided me. • Japanese Ministry of Education, Sports, Culture, Science and Technology who financed my PhD studies. I wish the Polish government was a fraction as generous to Polish researchers as the Japanese government is. • Frank Wolter, the only non-Japanese member of the committee for his invitation to visit Liverpool in September 2004 and his comments to my papers. But most of all, for the result we obtained together. I would never think of attacking this problem without him. • Other members of the committee: Tatsuya Shimura, Mizuhito Ogawa and Satoshi Tojo, my subtheme research supervisor. I hope I will have more opportunities in future to study and collaborate with them. i • Balder ten Cate, another person co-responsible for some results in this thesis. It is a pity his wedding takes place at the same time as my final defense. But I believe we will have soon an opportunity to celebrate both events together. Congratulations, Balder. • Many other members of ILLC, in particular Johan van Benthem and Yde Venema. Johan generously financed my first scientific journeys (to Georgia and Amsterdam in 2001) from his Spinoza grant. I could always rely on his feedback, inspiration and lightning speed e-mail answers. Yde was the person who together with Tomasz convinced me that the present subject is worth writing a thesis on. Thanks are also due for an early draft of one of his papers. • Valentin Shehtman, another author who has provided me with feedback, inspiration and comments since a very early stage of work. • All the guests of the Ono laboratory at the time I have been here. They added much variety to the scientific and social life at JAIST. In particular, I would like to mention Ian Hodkinson, Vladimir Sotirov, Guillaume Malod, Josep Maria Font, Misha Zakharyaschev, Agi Kurucz, Clint van Alten and Norbert Preining. Special thanks are due to long-term visitors: Nick Galatos and Felix Bou. • The students of our laboratory. I would like to single out Tadamune, Hiroki and Kouji. Guys, meeting friends like you is worth traveling nine thousand kilometers. Thanks are also due to Hitoshi Kihara for his assistance and Toshimasa Matsumoto for being a computer expert and an old-school Japanese gentleman. • My mother, my sister