Strongly Extensional vs Complementable Collections

Marco Forti

We consider the problem of axiomatizing the primitive notion of collection, intended in the most general sense as “any aggregate of distinct objects conceived as a single object”. In our view, this notion originates from the fusion of two different naive concepts: the “extension of a property” and the “content of a list”. The first notion, which can be attributed to Frege, makes implicit reference to a (unique) universal collection V: a collection C is obtained by separating from V the objects which belong to C (possibly by means of some definite property). This concepition yields naturally to postulate Weak Extensionality up to urelements, and leaves open the difficult problem of isolating consistent Comprehension Principles (Russel’s property appears prima facie well-defined!). The second notion, more in line with the modern developements of Computer Science, has to define when two lists have the same content. A natural choice could be to assume Strong Extensionality up to bisimulation (possibly admitting atoms). (This choice is warmly recommended in [1].) Again one has to state suitable Comprehension Principles, and now one has to choose between Singleton and Complement, since V is bisimilar to V \ {V }.

In both cases arbitrary collections cannot be flexible enough to admit the uses of modern Mathematics. Cantor’s set theory, later axiomatized by Zermelo, bans large (absolutely infinite) collections as inconsistent, and so do the usual axiomatizations à la Zermelo. Von Neumann’s axiomatization of sets and classes identifies “sethood” with “elementhood”, Limitation of Size being the basic criterion for both. Hence large collections cannot be collected, and so are intended merely as a “façon de parler”. In the spirit of the Foundational Programme of E. De Giorgi, we consider all collections, large and small, as first class objects. It seems therefore appropriate to isolate sets as “not too large collections”, which can be freely manipulated, and introduce the collections Coll (of all collections) and Ins (of all sets). The idea that sets are small is embodied in the Axiom of Replacement, while their simple and controlled internal structure is rendered by stating that the graph of membership between sets and objects is a collection. Strong Comprehension Principles are obtained by means of suitable “Gödel Operations” acting on Coll: pairing, union, intersection, cartesian product, domain, etc.

Adopting the “Fregean” attitude, we should clearly include complement, and then we could not assume that the graph of general membership is in Coll. Hence unions, intersections, and cartesian products of collections of collections may not exist as collections. This fact would prevent a substantial use of collections in almost all areas of Mathematics, Logic and Semantics. We conjecture that arbitrary unions and intersections are consistent (at least), but in [3] we have only proved the consistency of the weaker axiom: Unions and intersections of sets of collections and of collections of sets are collections, and so is the cartesian product of a set of collections.

On the other hand, adopting the “Barwisean” attitude, one can assume that the graph of general membership is in Coll, thus obtaining the fullGeneralized Positive Comprehension GP K of [2], and in fact a good approximation of the “most wanted” theory SEC asked for in [1]. New problems obviously arise: we cannot enter in details here, and we refer to [2] for a discussion of related topics.

[1] J.BARWISE, L.MOSS - Vicious Circles. CSLI L. N. 60, Stanford 1996.

[2] M.FORTI, F.HONSELL - Choice principles in hyperuniverses. Ann. Pure Appl. Logic 77 (1996), 35-52. Addendum and Corrigendum, ibid. 92 (1998), 211-214.

[3] M.FORTI, F.HONSELL, M.LENISA - Operations, Collections and Sets within a General Axiomatic Framework, in Logic and Foundations of Mathematics (A. Cantini et al., eds.), Synthese Library 280, Kluwer, Dordrecht 1999, 1-24.

Address: Dip. Matematica Applicata ”U.Dini”, Universita’ di Pisa, V. Bonanno 25B - 56100 PISA (Italy)

E-mail: forti@dma.unipi.it