I'm trying to figure out where I'm going wrong with the following diagonal argument. This post is one to replace a vague general one I posted earlier
Let $S$ be the collection of all subsets of $\mathbb{N}$ which have a finite description (I realize this characterization might be imprecise thus causing all the problems but I envision $S$ to contain at least all sets in the arithmetic hierarchy)
Let $A_n$ refer to the set in $S$ having a description with code $n$ over some suitable encoding scheme with a defined syntax. If $n$ does not fit the acceptable syntax, define $A_n= \emptyset$.
Now define the set $D \subset \mathbb{N}$ as follows: $$D=\{n|n\notin A_n\}$$
By the standard diagonal argument, $D\notin S$, but as I just wrote above, it does have a finite description. I realize that if $S$ were different this wouldn't be an issue. For example, If $S$ were the collection of all r.e. sets then although $D$ has a finite description it cannot be defined through the domain of a partial recursive function so it would not be r.e. and thus not in $S$. Also if $S$ were larger, like the power set of $\mathbb{N}$, there would also not be an issue since not all subsets of $\mathbb{N}$ can have a finite description so $D$ would not be well-defined.
However, in this case, $S$ just involves sets which have a finite description and so I don't see why $D$ would not fall into that category. Any suggestions?
First of all, if we take "has a finite description" as "can be described in natural language", then this is too vague, and inevitably will lead to all sorts of self-referential paradoxes (consider "the smallest number that cannot be described in less than 15 words").
But let's say we can make "has a finite description" concrete in a more formal and consistent way.
Then what you have proved above, is that the set $D$ cannot have a finite description, regardless of what this finite description is, since it would lead to a contradiction ($D\in S\leftrightarrow D\notin S$).
As a concrete example, if you take "finite description" as being definable by a first-order formula without parameters, then the property of being definable by a first-order formula itself is not definable by a first-order formula (you cannot quantify over formulas). This property lives in a meta world where we talk about finite descriptions of the internal world. The kind of finite descriptions we use to describe this property are only finite descriptions in the meta world, and not finite descriptions of the internal world.
In particular the encoding scheme will be described in the meta world, so although each $A_n$ has a finite description, we cannot build the sequence $\langle A_n\rangle$ using a finite description. Thus $D$ itself depends on something not finitely described.