Hostname: page-component-745bb68f8f-l4dxg Total loading time: 0 Render date: 2025-01-11T23:31:05.179Z Has data issue: false hasContentIssue false
  • English
  • Français

COMPLETE LOGICS FOR ELEMENTARY TEAM PROPERTIES

Part of: General logic

Published online by Cambridge University Press:  01 December 2022

JUHA KONTINEN Open the ORCID record for JUHA KONTINEN [Opens in a new window]  and
FAN YANG Open the ORCID record for FAN YANG [Opens in a new window]
JUHA KONTINEN
Affiliation:
DEPARTMENT OF MATHEMATICS AND STATISTICS UNIVERSITY OF HELSINKI PL 68 (PIETARI KALMIN KATU 5) 00014, HELSINKI FINLAND E-mail: [email protected]
FAN YANG*
Affiliation:
DEPARTMENT OF MATHEMATICS AND STATISTICS UNIVERSITY OF HELSINKI PL 68 (PIETARI KALMIN KATU 5) 00014, HELSINKI FINLAND E-mail: [email protected]
*
E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, we introduce a logic based on team semantics, called $\mathbf {FOT} $ , whose expressive power is elementary, i.e., coincides with first-order logic both on the level of sentences and (possibly open) formulas, and we also show that a sublogic of $\mathbf {FOT} $ , called $\mathbf {FOT}^{\downarrow } $ , captures exactly downward closed elementary (or first-order) team properties. We axiomatize completely the logic $\mathbf {FOT} $ , and also extend the known partial axiomatization of dependence logic to dependence logic enriched with the logical constants in $\mathbf {FOT}^{\downarrow } $ .

Keywords

dependence logicteam semanticsfirst-order logicaxiomatization

MSC classification

Primary: 03B60: Other nonclassical logic
Type
Article
Information
The Journal of Symbolic Logic , Volume 88 , Issue 2 , June 2023 , pp. 579 - 619
Check for updates
Copyright
© The Author(s), 2022. Published by Cambridge University Press on behalf of The Association for Symbolic Logic

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abramsky, S. and Väänänen, J., From IF to BI . Synthese , vol. 167 (2009), no. 2, pp. 207–230.10.1007/s11229-008-9415-6CrossRefGoogle Scholar
Armstrong, W. W., Dependency structures of data base relationships , IFIP Congress , North-Holland, Amsterdam, 1974, pp. 580–583.Google Scholar
Arrow, K., A difficulty in the concept of social welfare . Journal of Political Economy , vol. 58 (1950), no. 4, pp. 328–346.10.1086/256963CrossRefGoogle Scholar
Baltag, A. and van Benthem, J., A simple logic of functional dependence . Journal of Philosophical Logic , vol. 50 (2021), no. 5, pp. 939–1005.10.1007/s10992-020-09588-zCrossRefGoogle Scholar
Barwise, J. and Schlipf, J., An introduction to recursively saturated and resplendent models, this Journal, vol. 41 (1976), no. 2, pp. 531–536.Google Scholar
Casanova, M. A., Fagin, R., and Papadimitriou, C. H., Inclusion dependencies and their interaction with functional dependencies , Proceedings of the 1st ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (PODS ‘82) , Association for Computing Machinery, New York, 1982, pp. 171–176.Google Scholar
Ciardelli, I., Dependency as question entailment , Dependence Logic: Theory and Application (Abramsky, S., Kontinen, J., Väänänen, J., and Vollmer, H., editors), Progress in Computer Science and Applied Logic, Birkhäuser Basel, 2016, pp. 129–182.10.1007/978-3-319-31803-5_8CrossRefGoogle Scholar
Ciardelli, I., Questions in logic , Ph.D. thesis, University of Amsterdam, 2016.Google Scholar
Ciardelli, I., Iemhoff, R., and Yang, F., Questions and dependency in intuitionistic logic . Notre Dame Journal of Formal Logic , vol. 61 (2020), no. 1, pp. 75–115.10.1215/00294527-2019-0033CrossRefGoogle Scholar
Corander, J., Hyttinen, A., Kontinen, J., Pensar, J., and Väänänen, J., A logical approach to context-specific independence . Annals of Pure and Applied Logic , vol. 170 (2019), no. 9, pp. 975–992.10.1016/j.apal.2019.04.004CrossRefGoogle Scholar
Enderton, H. B., Finite partially-ordered quantifiers . Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik , vol. 16 (1970), pp. 393–397.10.1002/malq.19700160802CrossRefGoogle Scholar
Engström, F., Kontinen, J., and Väänänen, J., Dependence logic with generalized quantifiers: Axiomatizations . Journal of Computer and System Sciences , vol. 88 (2017), pp. 90–102.10.1016/j.jcss.2017.03.010CrossRefGoogle Scholar
Fagin, R., Functional dependencies in a relational database and propositional logic . IBM Journal of Research and Development , vol. 21 (1977), no. 6, pp. 534–544.10.1147/rd.216.0534CrossRefGoogle Scholar
Galliani, P., The dynamics of imperfect information , Ph.D. thesis, University of Amsterdam, 2012.Google Scholar
Galliani, P., Inclusion and exclusion in team semantics: On some logics of imperfect information . Annals of Pure and Applied Logic , vol. 163 (2012), no. 1, pp. 68–84.10.1016/j.apal.2011.08.005CrossRefGoogle Scholar
Galliani, P., Epistemic operators in dependence logic . Studia Logica , vol. 101 (2013), no. 2, pp. 367–397.10.1007/s11225-013-9478-3CrossRefGoogle Scholar
Galliani, P., On strongly first-order dependencies , Dependence Logic (Abramsky, S., Kontinen, J., Väänänen, J., and Vollmer, H., editors), Springer, Cham, 2016, pp. 53–71.10.1007/978-3-319-31803-5_4CrossRefGoogle Scholar
Galliani, P., Hannula, M., and Kontinen, J., Hierarchies in independence logic , Proceedings of Computer Science Logic 2013 (S. Rocca, editor), Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl Publishing, Saarbrücken, vol. 23, 2013, pp. 263–280.Google Scholar
Galliani, P. and Hella, L., Inclusion logic and fixed point logic , Computer Science Logic 2013 (S. Rocca, editor), Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl Publishing, Saarbrücken, vol. 23, Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik, 2013, pp. 281–295.Google Scholar
Geiger, D., Paz, A., and Pearl, J., Axioms and algorithms for inferences involving probabilistic independence . Information and Computation, vol. 91 (1991), no. 1, pp. 128–141.10.1016/0890-5401(91)90077-FCrossRefGoogle Scholar
Grädel, E. and Väänänen, J., Dependence and independence . Studia Logica , vol. 101 (2013), no. 2, pp. 399–410.10.1007/s11225-013-9479-2CrossRefGoogle Scholar
Grilletti, G., Completeness for the classical antecedent fragment of inquisitive first-order logic . Journal of Logic, Language and Information , vol. 30 (2021), pp. 725–751.10.1007/s10849-021-09341-yCrossRefGoogle Scholar
Hannula, M., Axiomatizing first-order consequences in independence logic . Annals of Pure and Applied Logic , vol. 166 (2015), no. 1, pp. 61–91.10.1016/j.apal.2014.09.002CrossRefGoogle Scholar
Hannula, M., Hirvonen, Å., Kontinen, J., Kulikov, V., and Virtema, J., Facets of distribution identities in probabilistic team semantics . Logics in Artificial Intelligence, JELIA 2019 (Calimeri, F., Leone, N., and Manna, M., editors), Lecture Notes in Computer Science, vol. 11468, Springer Cham, 2019.Google Scholar
Hannula, M. and Kontinen, J., A finite axiomatization of conditional independence and inclusion dependencies . Information and Computation , vol. 249 (2016), pp. 121–137.10.1016/j.ic.2016.04.001CrossRefGoogle Scholar
Henkin, L., Some remarks on infinitely long formulas , Infinitistic Methods (Warsaw) , Proceedings Symposium Foundations of Mathematics, Państwowe Wydawnictwo Naukowe, Warsaw, and Pergamon Press, Oxford-London-New York-Paris, 1961, pp. 167–183.Google Scholar
Hodges, W., Compositional semantics for a language of imperfect information . Logic Journal of the IGPL , vol. 5 (1997), pp. 539–563.10.1093/jigpal/5.4.539CrossRefGoogle Scholar
Hodges, W., Some strange quantifiers , Structures in Logic and Computer Science: A Selection of Essays in Honor of A. Ehrenfeucht (Mycielski, J., Rozenberg, G., and Salomaa, A., editors), Lecture Notes in Computer Science, vol. 1261, Springer, London, 1997, pp. 51–65.10.1007/3-540-63246-8_4CrossRefGoogle Scholar
Hyttinen, T., Paolini, G., and Väänänen, J., Quantum team logic and bell’s inequalities . Review of Symbolic Logic , vol. 8 (2015), no. 4, pp. 722–742.10.1017/S1755020315000192CrossRefGoogle Scholar
Kontinen, J., Coherence and complexity of quantifier-free dependence logic formulas . Studia Logica , vol. 101 (2013), no. 2, pp. 267–291.10.1007/s11225-013-9481-8CrossRefGoogle Scholar
Kontinen, J., On natural deduction in dependence logic , Logic Without Borders: Essays on Set Theory, Model Theory, Philosophical Logic and Philosophy of Mathematics (Villaveces, A., Kossak, J. K. R., and Hirvonen, Å., editors), De Gruyter, Berlin/Boston/Munich, 2015, pp. 297–304.CrossRefGoogle Scholar
Kontinen, J. and Nurmi, V., Team logic and second-order logic . Fundamenta Informaticae , vol. 106 (2011), pp. 259–272.CrossRefGoogle Scholar
Kontinen, J. and Väänänen, J., On definability in dependence logic . Journal of Logic, Language and Information , vol. 18 (2009), no. 3, pp. 317–332 (Erratum: the same journal, vol. 20 (2011), no. 1, pp. 133–134).CrossRefGoogle Scholar
Kontinen, J. and Väänänen, J., Axiomatizing first-order consequences in dependence logic. Annals of Pure and Applied Logic , vol. 164 (2013), no. 11, pp. 1101–1117.10.1016/j.apal.2013.05.006CrossRefGoogle Scholar
Kontinen, J. and Yang, F., Logics for first-order team properties . Proceedings of the 26th Workshop on Logic, Language, Information and Computation (WoLLIC 2019) , Lecture Notes in Computer Science, vol. 11541, Springer, Berlin, 2019, pp. 392–414.CrossRefGoogle Scholar
Lück, M., Axiomatizations of team logics . Annals of Pure and Applied Logic , vol. 169 (2018), no. 9, pp. 928–969.CrossRefGoogle Scholar
Lyndon, R. C., An interpolation theorem in the predicate calculus . Pacific Journal of Mathematics , vol. 9 (1959), no. 1, pp. 129–142.CrossRefGoogle Scholar
Pacuit, E. and Yang, F., Dependence and independence in social choice: Arrow’s theorem , Dependence Logic: Theory and Application (Vollmer, H., Abramsky, S., Kontinen, J., and Väänänen, J., editors), Progress in Computer Science and Applied Logic, Birkhäuser Basel, 2016, pp. 235–260.10.1007/978-3-319-31803-5_11CrossRefGoogle Scholar
Väänänen, J., Dependence Logic: A New Approach to Independence Friendly Logic , Cambridge University Press, Cambridge, 2007.10.1017/CBO9780511611193CrossRefGoogle Scholar
Walkoe, W. J., Finite partially-ordered quantification, this Journal, vol. 35 (1970), pp. 535–555.Google Scholar
Yang, F., Negation and partial axiomatizations of dependence and independence logic revisited . Annals of Pure and Applied Logic , vol. 170 (2019), no. 9, pp. 1128–1149.CrossRefGoogle Scholar
Yang, F., Axiomatizing first-order consequences in inclusion logic . Mathematical Logic Quarterly , vol. 66 (2020), no. 2, pp. 195–216.CrossRefGoogle Scholar
Yang, F. and Väänänen, J., Propositional logics of dependence . Annals of Pure and Applied Logic , vol. 167 (2016), no. 7, pp. 557–589.CrossRefGoogle Scholar