The set of elements that are members of this set?

Question

Can a set refer to itself in its own definition / define itself in the above way? Is the above set a set?

variant: A word w is a member of a language L iff it is a member of language L, ie. the condition for w's membership to L is that it be a member of L.

Is there a proof for the fact that this language is undecidable due to this self-reference, due to the fact that this language might not be a set? Can you say a language is not decidable because it is not defined? Or is simply outside the bounds of computability theory? Or is this a property of every language and is totally fine?

Answer 1

Can a set refer to itself in its own definition / define itself in the above way?

No. This is what's known as an impredicative definition. This is, instead, a true statement about all sets, distinguishing none over any of the others.

In certain circumstances, we do define things implicitly, meaning we provide some conditions for an object to satisfy, argue that there is a unique object satisfying these criteria, and then proceed to use this unique object in our calculations. Probably the most elementary examples of this are recurrence relations, e.g. $$x_n = x_{n-1} + x_{n-2}, \quad x_1 = x_2 = 1.$$ Note that, as a definition, this would be impredicative. But, it can be proven (with induction) that there is one and only one sequence whose terms satisfy these conditions. This is how we typically define the Fibonacci sequence, not with a formula, but implicitly, with this relationship!

But, as I said, your example cannot function as a definition, simply because every set satisfies this condition; you don't get the uniqueness required for an implicit definition.

I wouldn't say this makes $L$ undecidable, so much as undefined.

Answer 2

No, this doesn't work.

The key point is that definitions are really statements. When we say "Let $X$ be the foo that blahs," we're implicitly claiming that there is exactly one foo that blahs - and then we're deciding to give it the name "$X$." That second part doesn't work without the first part.

The problem with the "definition" you give is that the property "Is the set of all things in this set" does not pin down a unique set, since every set satisfies it. (Similarly, "The set of all things which are elements of this set iff they are not elements of this set" doesn't work as a definition since no set has the relevant property.)

Computability does not come into this; it doesn't make sense to ask whether "this set" has any property at all, since it hasn't been specified. We can ask whether some sets satisfying the relevant property are decidable (or whatever), but it doesn't make sense to ask whether the set satisfying the relevant property is decidable (or whatever) until we've proved that there is in fact exactly one such set: is "The prime less than $10$" even or odd?

On the other hand, there are some apparently-self-referential "definitions" which are actually valid (ignoring predicativity issues - I'm talking purely classically here). For example,

The set of all objects which are in this set if and only if they are not in this set

can actually be construed as a meaningful definition: there is exactly one set $X$ with the property $$X=\{a: a\in X\leftrightarrow a\not\in X\},$$ namely the emptyset.