The Theory of Finitely Supported Structures and Choice Forms

Published in Volume XXVIII, Issue 1, 2018, pages 1–38, doi: 10.7561/SACS.2018.1.1

Authors: A. Alexandru

Abstract

The theory of finitely supported algebraic structures provides a first step in computing infinite algebraic structures that are finitely supported modulo certain atomic permutation actions. The motivation for developing such a theory comes from both mathematics (by modelling infinite algebraic structures, hierarchically defined by involving some basic elements called atoms, in a finitary manner, by analyzing their finite supports) and computer science (where finitely supported sets are used in various areas such as semantics foundation, automata theory, domain theory, proof theory and software verification). The results presented in this paper include the meta-theoretical presentation of finitely supported structures, the study of the consistency of choice principles (and of results requiring choice principles) within this framework, and the presentation of several connections with other topics.

Full Text (PDF)

References

[1] A. Alexandru, G. Ciobanu. Finitely Supported Mathematics: An Introduction. Springer, 2016. doi:10.1007/978-3-319-42282-4_1.

[2] A. Alexandru, G. Ciobanu. Abstract Interpretations in the Framework of Invariant Sets. Fundamenta Informaticae 144(1), 1–22, 2016. doi:10.3233/fi-2016-1321.

[3] A. Alexandru, G. Ciobanu. On Logical Notions in the Fraenkel-Mostowski Cumulative Universe. Bulletin Mathématique de la Société des Sciences Mathématiques de Roumanie 60/108(2), 113–125, 2017.

[4] A. Alexandru, G. Ciobanu. Fuzzy Sets within Finitely Supported Mathematics. Fuzzy Sets and Systems 339, 119–133, 2018. doi:10.1016/j.fss.2017.08.011.

[5] J. Barwise. Admissible Sets and Structures: An Approach to Definability Theory. Perspectives in Mathematical Logic 7, Springer, 1975.

[6] M. Bojańczyk, B. Klin, S. Lasota. Automata with Group Actions. In: 26th Symposium on Logic in Computer Science, pages 355–364, IEEE Computer Society Press, 2011. doi:10.1109/lics.2011.48.

[7] N. Brunner. Amorphe Potenzen Kompacter Räume. Archiv für mathematische Logik und Grundlagenforschung 24, 119–135, 1984. doi:10.1007/bf02007144.

[8] A. Fraenkel. Zu den Grundlagen der Cantor-Zermeloschen Mengenlehre. Mathematische Annalen 86, 230–237, 1922. doi:10.1007/bf01457986.

[9] M.J. Gabbay, A.M. Pitts. A New Approach to Abstract Syntax with Variable Binding. Formal Aspects of Computing 13, 341–363, 2001. doi:10.1007/s001650200016.

[10] R. Gandy. Church’s Thesis and Principles for Mechanisms. In: J. Barwise, H.J. Keisler, K. Kunen, editors, The Kleene Symposium, pages 123-148, North Holland, 1980. doi:10.1016/s0049-237x(08)71257-6.

[11] L. Halbeisen. Combinatorial Set Theory, with a Gentle Introduction to Forcing. Springer, 2011.

[12] H. Herrlich. Axiom of Choice. Lecture Notes in Mathematics, Springer, 2006. doi:10.1007/11601562.

[13] P. Howard, J.E. Rubin. Consequences of the Axiom of Choice. Mathematical Surveys and Monographs, vol.59, American Mathematical Society, 1998. doi:10.1090/surv/059.

[14] T.J. Jech. The Axiom of Choice. Studies in Logic and the Foundations of Mathematics, North-Holland, 1973.

[15] F. Klein. Vergleichende Betrachtungen Über Neuere Geometrische Forschungen (A Comparative Review of Recent Researches in Geometry). Mathematische Annalen 43(1), 63-100, 1893. doi:10.1007/ bf01446615.

[16] A. Levy. The Independence of Various Definitions of Finite. Fundamenta Mathematicae 46(1), 1-13, 1958. doi:10.4064/fm-46-1-1-13.

[17] A. Lindenbaum, A. Mostowski. Über die Unabhangigkeit des Auswahlsaxioms und Einiger Seiner Folgerungen. Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie 31, 27-32, 1938.

[18] D. Petrișan. Investigations Into Algebra and Topology Over Nominal Sets. Ph.D. Thesis, University of Leicester, 2011.

[19] A.M. Pitts. Nominal Sets Names and Symmetry in Computer Science. Cambridge University Press, 2013.

[20] M.R. Shinwell. The Fresh Approach: Functional Programming with Names and Binders. Ph.D. Thesis, University of Cambridge, 2005.

[21] A. Tarski. What are Logical Notions?. History and Philosophy of Logic 7(2), 143-154, 1986. doi:10.1080/01445348608837096.

Bibtex

@article{sacscuza:alexandru2018ttofssacf,
  title={The Theory of Finitely Supported Structures and Choice Forms},
  author={A. Alexandru},
  journal={Scientific Annals of Computer Science},
  volume={28},
  number={1},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2018},
  pages={1–38},
  doi={10.7561/SACS.2018.1.1},
  publisher={``A.I. Cuza'' University Press}
}