MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

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.

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.

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)?

Edit: 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".

Then it's at least somehow astonishing, that some of those definitions cohere with the meta-property of "defining too big a collection".

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?

(The same should go - mutatis mutandis - for functions and computability.)

share|cite|improve this question

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.