Definability

Proposition: The definable languages are closed under complementation, union and intersection.

Proof: A language can simply be defined as the intersection of two given languages. The same argument applies to union and complementation.

Proposition: Recognizable languages (and thus also decidable languages) are definable.

Proof: An algorithm recognizing a language constitutes one of the ways in which that language can be defined.

Temporary assumption: Definability is well defined above.

I will show that this assumption is incorrect.

Take as alphabet all symbols used for communication, and consider the definitions of languages over that alphabet. Such a definition can be given as a string over that very alphabet, and such a string may or may not belong to the language defined by that very string. Thus one distinguishes those definitions (represented as strings) that define a language that contains that definition itself, from those that don't.

Definition: Let L be the set of those definitions - represented as strings - of languages that do not contain that definition.

Paradox: Let d be the definition of L displayed above. Suppose that L contains d. Then, by definition d, d does not belong to L, which is a contradiction. Now suppose that L does not contain d. Then, by definition d, d is in L, which is a contradiction as well.

As both possibilities concerning d being in L lead to a contradiction, L is not well-defined, and d cannot be a correct definition. The reason is that d says, in essence, that L contains d exactly when it does not contain d. Surely that's a bad way to define L.

It is of importance to rule out bad definitions, such as d above. Let us for the moment assume that we have done this, and that there is perfect clarity on what exactly counts as a valid definition, and consequently what is a definable language. Note that this is the temporary assumption mentioned above. Now the description d of the language L given above becomes totally unambiguous: surely for every correct definition c of a language it is determined whether that language contains c or not. Thus we find:

Theorem: There exists an undefinable language.

Proof: The language L is undefinable. Namely its definition d is flawed, as we established before, and if the language L would have any other definition that wasn't flawed, the same paradox would arise.

Still, L has an unambiguous description that determines exactly whether a given word belongs to that language or not. This description therefore satisfies our definition of a definition. Thus, with every formal concept of a definable language, we can find a language that does not satisfy that concept of definability, but still has what could be regarded as a valid definition. The conclusion is that the concept of definability is not well-defined.