Indescribability of certain infinite objects I was thinking about infinite sequences of integers and it occurred to me that we usually depend on some kind of formula for the elements of the sequence, e.g. $s_n = 2n$ would be the sequence of even natural numbers.
However, I was thinking about it and it seemed that it's difficult to exactly describe every single possible sequence of integers in $\mathbb{Z}^\mathbb{N}$. Indeed, it seems to me that without some kind of formula or pattern emerging, there is no way to describe the sequence in a finite amount of information (of course, we could always describe the sequence one-by-one, but this is not really satisfying). I've also heard of the Berry paradox, which I suppose is similar to the question at hand. 
Is there some branch of mathematics which deals with this formalization of the "indescribability" of objects? Is there some kind of axiom which governs this?
 A: In addition to the excellent subfields described by Noah, I'm reminded of Shannon Entropy of Information Content.

Shannon's entropy measures the information contained in a message as
opposed to the portion of the message that is determined (or
predictable).

A sequence with a simple formula like $x_n = 2n$ has low entropy. If you need a computer program or algorithm to calculate the sequence (say the digits of pi), the entropy is higher. The entropy is maximal when the only known way to express a sequence is the sequence content itself.
A: Yes - this is a focus of mathematical logic, especially the subfields of computability theory and set theory!
Some immediate responses:


*

*One reasonable notion of "describable" is "computable", that is, computable by a Turing machine. Since there are uncountably many sequences of natural numbers, and only countably many Turing machines, "most" sequences are indescribable in this sense.

*This also holds if we replace "computable" with any similar notion of definability - as long as the definitions form a countable set, "most" sequences will escape our net.

*Now, this isn't the end of the story: given a notion of describability (say, computability) and a pair of nondescribable sequences, we can ask whether one is "even less describable than" the other. This turns out to not be a silly question! See relative computability. Another (perhaps less silly-sounding) way to view this sort of question is to take a given sequence $A$, and ask: "What sort of language do I need to be able to describe $A$?"

*On the set-theoretic side, we can also ask versions of this question inside models of set theory. That is, if we have some notion of describability, and some model $V$ of set theory (that is, $V$ may not actually contain all sets, but $V$ contains enough that it satisfies the basic properties of set theory), we can ask if every sequence in $V$ is describable. It turns out that, surprisingly, this can happen, in apparent (but not actual) contradiction with the first bulletpoint; see https://arxiv.org/abs/1105.4597. 

*And of course other areas of logic also have things to say about this. Model theory looks at sets and sequences from the perspective of logical definability in a structure, and studies both the types of sequences definable in certain structures and the logics needed to define certain sequences over certain structures; and in proof theory we pay attention to what sort of axiom system can verify that a given description of a sequence "behaves nicely" (for instance, how hard is it to prove that two descriptions of the same sequence actually correspond to the same object?).
A: To answer the part of the question about Berry's paradox, it is indeed related but not as much as you might think, because it is more about the distinction between provability inside and outside a formal system. Specifically, to even show that a single positive integer $k$ is uniquely definable in some formal system $S$ you would need to prove that there is some $1$-parameter sentence $φ$ such that $S$ proves "$φ(n)$" iff "$n$" is the term for $k$, namely "$\underbrace{1+\cdots+1}_\text{$k$ times}$". But to do so includes proving that $S$ does not prove a whole lot of sentences, which implies that $S$ is not inconsistent. Thus the formal system you are working in to do all this cannot be $S$ itself unless it is incapable of some basic arithmetic (cannot prove what PA can) or it is impractical (undecidable proof validity), by Godel's incompleteness theorem.
It is instructive to see what happens if we attempt to define "definability in $S$" as merely that $S$ proves "$\forall n \in \mathbb{N}\ ( φ(n) \leftrightarrow n=k )$" for some $1$-parameter sentence $φ$. If we do so then the number of positive integers that are definable this way by some $φ$ with length shorter than $c$ may be more than the number of possible such $φ$ of length shorter than $c$, because $S$ might prove a contradiction and hence prove that every positive integer is definable by every such $φ$! Thus we still need to prove that $S$ is consistent after all, otherwise we cannot bound the number of positive integers definable by even a single such $φ$.
As you can see, Berry's paradox vanishes, but has very little to do with indescribability or infinity. What you might be looking for is Skolem's paradox. If ZFC is consistent then it has a countable model, but ZFC itself proves that there is an uncountable set, such as the one in your question. There is no contradiction, because ZFC cannot prove itself consistent, and also because the model simply cannot see (does not have) an object representing a bijection between its notion of $\mathbb{N}$ and $\mathbb{Z}^\mathbb{N}$. From the outside, however, there may in fact be a bijection between the two collections that represent those two in the model. In short, the meta-system knows more than the model, because it not only sees all the bijections that the model sees but also sees all the bijections that the model does not see.
It may help to realize that the sequences that you can construct in ZFC are those that all models of ZFC must have. There are only countably many of these, but that does not prevent some models from having uncountably many. Also, there's a slight catch to "description". In ZFC the axiom of choice allows you to construct a set that you cannot actually pin down, in that it is not given to be unique. This means that we need to be more careful when we say "countably many describable objects". Instead this is what we can do. Extend ZFC to a theory $T$ with an axiom $φ(c_φ)$ for every $1$-parameter sentence $φ$ over $T$ such that $T \vdash \exists x\ ( φ(x) )$, where $c_φ$ is a new constant symbol for each such $φ$. (This can be done by the limit of an inductive construction.) Then $T$ has countably many constants, and hence no model of ZFC with an uncountable set (such as one where $\mathbb{Z}^\mathbb{N}$ is interpreted as an uncountable set) can be extended to have a constant for each element in that set.
Of course, Noah's post answers the other part of your question about which branch of mathematics deals with all these. =)
