Complete Axiomatisations of Properties of Finite Sets
Bergen University College, Norway. E-mail: tag{at}hib.no
University of Bergen, Norway. E-mail: michal{at}ii.uib.no
We study a logic whose formulae are interpreted as properties of a finite set over some universe. The language is propositional, with two unary operators inclusion and extension, both taking a finite set as argument. We present a basic Hilbert-style axiomatisation, and study its completeness. The main results are syntactic and semantic characterisations of complete extensions of the logic.
Received for publication 18 August 2007.
Revision received 16 April 2008.
References
-
1 Ågotnes Thomas. A Logic of Finite Epistemic States (2004) PhD thesis, Department of Informatics, University of Bergen.
2 Ågotnes Thomas, Alechina Natasha. Knowing minimum/maximum n formulae. Brewka Gerhard, Coradeschi Silvia, Perini Anna, Traverso Paolo, eds. (2006) IOS Press. 317–321. Proceedings of the 17th European Conference on Artificial Intelligence (ECAI 2006).
3 Ågotnes Thomas, Alechina Natasha. The dynamics of syntactic knowledge. Journal of Logic and Computation (2007) 17(1).
4 Ågotnes Thomas, van der Hoek Wiebe, Wooldridge Michael. Quantified coalition logic. In. Veloso MM, ed. (2007) California: AAAI Press. 1181–1186. Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI 2007).
5 Ågotnes Thomas, Walicki Michal. Complete axiomatizations of finite syntactic epistemic states. In. In: volume 3904 of Lecture Notes in Computer Science (LNCS)—Baldoni Matteo, Endriss Ulle, Omicini Andrea, Torroni Paolo, eds. (2006) Springer Berlin / Heidelberg. 33–50. Declarative Agent Languages and Technologies III: Third International Workshop, DALT 2005, Utrecht, The Netherlands, July 25, 2005, Selected and Revised Papers.
6 Ågotnes Thomas, Walicki Michal. Strongly complete axiomatizations of "knowing at most" in syntactic structures. In. In: CLIMA VI volume 3900 of Lecture Notes in Computer Science (LNCS)—Toni Francesca, Torroni Paolo, eds. (2006) London, UK: Springer Berlin / Heidelberg. 57–76.
7 Brown KR, Wang H. Finite set theory, number theory and axioms of limitation. Math. Annalen (1966) 164:26–29.[CrossRef]
8 Buss SR. Bounded Arithmetic (1985) PhD thesis, Department of Mathematics, University of Princeton.
9 Clote Peter, Krajícek Jan, eds. Arithmetic, Proof Theory and Computational Complexity (1993) Oxford University Press.
10 Ebbinghaus Heinz-Dieter, Flum Jörg. Finite Model Theory (1999) Springer.
11 Fagin Ronald, Halpern Joseph Y, Moses Yoram, Vardi Moshe Y. Reasoning About Knowledge (1995) Cambridge, Massachusetts: The MIT Press.
12 Friedman Harvey. Some systems of second order arithmetic and their use. In. (1975) Proceedings of 1974 International Congress of Mathematicians.
13 Hintikka J. Impossible possible worlds vindicated. Journal of Philosophical Logic (1975) 4:475–484.[CrossRef][Web of Science]
14 Hintikka Jaakko. Knowledge and Belief (1962) Ithaca, New York: Cornell University Press.
15 Immerman Neil, Patnaik Sushant, Stemple David. The expressiveness of a family of finite set languages. Theoretical Computer Science (1996) 155(1):111–140.[CrossRef][Web of Science]
16 Levesque HJ. All I know: a study in autoepistemic logic. Artificial Intelligence (1990) 42:263–309.[CrossRef][Web of Science]
17 Lewine Shaughan. Understanding the Infinite (1994) Cambridge University Press.
18 Libkin Leonid. Locality of queries and transformations. In. Proceedings of WoLLIC'05—de Queiroz Ruy, Macintyree Angus, Bittencourt Guilherme, eds. (2005).
19 Meyer J-J. Ch, van der Hoek W. Epistemic Logic for AI and Computer Science (1995) CUP.
20 Montague Richard. Pragmatics. In. In: Contemporary Philosophy: A Survey. I—Klibansky R, ed. (1968) Florence: La Nuova Italia Editrice. 102–122.
21 Montague Richard. Universal grammar. Theoria (1970) 36:373–398.[Web of Science]
22 Moreno Antonio. Avoiding logical omniscience and perfect reasoning: a survey. AI Communications (1998) 11:101–122.[Web of Science]
23 Mycielski J. Locally finite theories. Journal of Symbolic Logic (1986) 51:59–62.[CrossRef][Web of Science]
24 Pauly M. A modal logic for coalitional power in games. Journal of Logic and Computation (2002) 12(1):149–166.
25 Rantala V. Impossible worlds semantics and logical omniscience. Acta Philosophica Fennica (1982) 35:106–115.
26 Rantala V. Quantified modal logic: non-normal worlds and propositional attitudes. Studia Logica (1982) 41:41–65.[CrossRef]
27 Sahlqvist H. Completeness and correspondence in the first and second order semantics for modal-logic. In. Kanger S, ed. (1975) Uppsala, North-Holland Publishing Company. 110–143. Proceedings of the Third Scandinavian Logic Symposium.
28 Scott Dana S. Advice on modal logic. In. In: Philosophical Problems in Logic—Lambert Karel, ed. (1970) Dordrecht: D. Reidel Publishing Co. 143–173.
29 Sim Kwang Mong. Epistemic logic and logical omniscience: A survey. International Journal of Intelligent Systems (1997) 12:57–81.[CrossRef][Web of Science]
30 Wansing H. A general possible worlds framework for reasoning about knowledge and belief. Studia Logica (1990) 49(4):523–539.[CrossRef]
CiteULike 
Connotea 
Del.icio.us What's this?
| ||||||||||||||||||||||||||||||||||||||||||||||||||