Thursday 2 July 2009

lo.logic - Properties of collections (functions) that make them proper classes (uncomputable)

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 notin 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.)

No comments:

Post a Comment