Properties of collections (functions) that make them proper classes (uncomputable) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T14:35:00Z http://mathoverflow.net/feeds/question/17731 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/17731/properties-of-collections-functions-that-make-them-proper-classes-uncomputable Properties of collections (functions) that make them proper classes (uncomputable) Hans Stricker 2010-03-10T15:15:43Z 2010-03-10T18:13:17Z <p>There are collections too big to be a set, e.g. the collection of all sets (in ZFC), and there are collections that cannot be sets for "pure" logical reasons, e.g. the collection of sets that do not contain themselves.</p> <p>There are functions growing too fast to be computable, e.g. the busy beaver function, and there are functions that cannot be computed for "pure" logical reasons, e.g. the halting function.</p> <p>In the final end it is of course shown by logical means that being too big (growing too fast) prohibit a collection to be a set (a function to be computable), but those properties are not "purely" logical (they are about sizes and growth rates), opposed to the "pure" logical reasons mentioned above.</p> <blockquote> <p>Is there a simple lesson to be learned from these observations? Are there other not "purely" logical properties of collections (functions) that prohibit them to be sets (computable)?</p> </blockquote> <p><strong>Edit</strong>: It's from the very definition of a collection -- $\lbrace x | x = x \rbrace$ or $\lbrace x | x \not\in x \rbrace$ -- that it is shown by logical means, that it cannot be a set. And not, firstly, from a hard to define meta-property of "defining too big a collection" or "being intrinsically inconsistent".</p> <p>Then it's at least somehow astonishing, that some of those definitions cohere with the meta-property of "defining too big a collection". </p> <blockquote> <p>Cannot - after all - the meta-property of "defining too big a collection" be rigorously defined such that it can be shown that no definition of a collection with this meta-property defines a set?</p> </blockquote> <p>(The same should go - mutatis mutandis - for functions and computability.)</p> http://mathoverflow.net/questions/17731/properties-of-collections-functions-that-make-them-proper-classes-uncomputable/17746#17746 Answer by wmitt for Properties of collections (functions) that make them proper classes (uncomputable) wmitt 2010-03-10T18:13:17Z 2010-03-10T18:13:17Z <p>One plausible necessary condition for a collection c to satisfy the meta-property in question is tthe following: the existence of c must not be a logical consequence of either ZFC or any large cardinal axioms expressible in the language of ZF. However, it is unclear what to say about collections that follow from large cardinal axioms expressible only in some larger language that includes the language of ZF (e.g., a language obtained by adding a truth-predicate to the language of ZF). It's not obvious a priori whether to call such collections "sets" or not; it would seem to depend on the specific nature of the relevant large cardinal axiom(s). It is tempting to say that the collections in question should be regarded as sets if they exist within a cumulative hierarchy satisfying the axioms of ZFC. Such a position is not clearly correct, however; for it is possible, using a certain language containing a truth-predicate, to distinguish "sets" from "proper classes" within this hierarchy itself, using omega-inconsistency as a criterion: see "Omega-inconsistency and the universe of sets," in IeCCS 2007 (International e-Conference on Computer Science), ed. T.E. Simos and G. Psihoyios. Thus, the attempt to rigorously define your meta-property raises some difficult questions and issues that make me skeptical about the possibility of such a definition.</p>