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 class of set membership functions, we would need to exclude proper class membership functions.

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

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

Is it valid to say that because of Turing's Halting problem, it is impossible to design a program that will determine if these other programs will even halt, let alone determine if they represent valid set 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?


Your question has a ton of faulty background assumptions. Most importantly, it is completely and utterly false that "We can turn functions into programs that accept input and return output." Certain very special functions can be computed by programs. Normally we only even talk about such a thing for functions $\mathbb{N}\to\mathbb{N}$ (or functions between sets that have a canonical bijection to $\mathbb{N}$), and even most functions $\mathbb{N}\to\mathbb{N}$ cannot be computed by any program. We certainly can't talk about "programs" for the membership functions of sets or classes, whose domains would be the entire universe of all sets.

So, your question doesn't really make any sense. Membership functions of sets or classes are not even the sort of object which we can think about using programs in the first place. There is no way you could ever "input" the membership function of an arbitrary set or class into a program, in any reasonable sense.

(Also, there are issues even talking about things like the "membership function" of a set or class. Such a "membership function" would itself be a proper class, since its domain would have to be all sets. So, these functions cannot themselves be elements of a class.)

  • $\begingroup$ I think I must have been totally misled by the following sentence: "Because [function] g is partial computable, there must be a program e that computes g, by the assumption that the model of computation is Turing-complete." in the section "Sketch of proof" for the Halting problem in the page en.wikipedia.org/wiki/Halting_problem. It really sounds like computable functions can automatically be turned into programs? $\endgroup$ – erik Sep 24 '18 at 3:00
  • $\begingroup$ Yes, computable functions can be computed by programs. Most functions are not computable (and the word "computable" normally only even applies to functions $\mathbb{N}\to\mathbb{N}$, not to other kinds of functions). $\endgroup$ – Eric Wofsey Sep 24 '18 at 3:06
  • $\begingroup$ Ok. I agree that I made quite a mistake by omitting the qualifier "computable". Imagine we limit membership functions to computable ones, would my question make sense? Or is it still completely off? $\endgroup$ – erik Sep 24 '18 at 3:08
  • $\begingroup$ The question does not make sense. Membership functions are not functions $\mathbb{N}\to\mathbb{N}$ (unless you are just talking about subclasses of $\mathbb{N}$, which are always sets), so it does not make sense to ask whether they are computable. $\endgroup$ – Eric Wofsey Sep 24 '18 at 3:17
  • $\begingroup$ Why would a function need to map N on N ? I was rather thinking of functions as defined in the untyped lambda calculus that accept any input of any arbitrary type and which return true/false concerning membership. What would be wrong with supporting arbitrary input types? en.wikipedia.org/wiki/Lambda_calculus $\endgroup$ – erik Sep 24 '18 at 10:35

Your Answer

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

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