Assuming only computable functions, and in line with set theory, defining a "proper class" as a collection that is itself not allowed to be a member of a set. A "collection" is then defined as either a set or else a proper class, in cases where we do not wish to distinguish.

If a set is defined by its membership function, then we can see that there exist membership functions that will not define a set but a proper class.

If we try to define the collection of set membership functions, we would need to exclude proper class membership functions.

This means that this collection needs a membership function that can determine if other membership functions are set membership functions or else proper class membership functions.

We can turn computable functions into programs that accept input and return output.

Is it valid to say that because of Turing's Halting problem, since it is impossible to design a program that will even determine if these other programs will even halt, it will be impossible for any program to distinguish between set membership functions versus class membership functions?

In that case, is it correct to say that it will never be possible to mechanically distinguish between set membership functions and proper class membership functions?

In other words, is it permissible to liberally use/abuse Turing's halting problem to decide that kind of questions? So, is this a proper use or merely an abuse of Turing's work on the halting problem?

  • 1
    $\begingroup$ You can probably define a class which is the empty set if some Turing machine halts or doesn't halt, and a proper class otherwise. This should fulfill your requirements. $\endgroup$ – Yuval Filmus Sep 25 '18 at 5:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.