The technique that uses the Chinese Remainder theorem, to express 1st order arithmetical statements encoding statements about infinite sets of numbers I know this technique is heavily used in Number Theory, in Combinatorics (e.g. for phrasing Ramsey's theorems in a first order language of arithmetic), and in some related realms. However, unfortunately, I've never seen any information about this technique. Not in Wikipedia either! So I've got some fundamental questions about it:


*

*How does this technique look? I want to use it!

*Who invented it?

*I guess this thechnique can't be used for encoding - in a first order language of arithmetic - all statements about sets of natural numbers (because I know that not every second order arithmetical statement about natural numbers can be phrased in a first order language, even though it can be phrased as a statement about sets of natural numbers), so the capability of this technique is probably limited, but what are its limitations or constraints? in other words: are there any conditions, being necessary and sufficient, for a given statement about sets of natural numbers - to be able to be encoded in a first order language of arithmetic - using this technique?
 A: I believe you're thinking of Gödel's $\beta$ function which allows you to quantify over all finite sequences of natural numbers by just two quantified variables ranging over the naturals.
It only handles finite sequences, so you cannot represent statements about arbitrary sets of natural number. For reasons of cardinality there cannot be a representation of all infinite set/sequences by any fixed number of integer variables, so I think you must misremembering or misunderstanding when you're talking about a representation of infinite sets.
The $\beta$-function technique represents the $n$th element of a sequence as the remainder
$$ p \bmod q(n+1)+1 $$
for appropriate constants $p$ and $q$. If you don't know from context how long the sequence must be, just encode its length as the $0$th element of the sequence.
To see that every sequence can be represented as a $(p,q)$ combination, first choose $q$ such that it is larger than every element in the sequence and such that the moduli $q+1, 2q+1, 3q+1, \ldots$ up to the length of the sequence are all coprime. Then use the CRT to find a $p$ that gives you the remainders you want.

As the name says, this was introduced by Kurt Gödel in his 1931 paper that presented the Incompleteness Theorem. It is not the same as the more well-known Gödel numbering for sequences that the same paper also introduced (but the argument that operations on Gödel numbers can be expressed in the language of arithmetic uses the $\beta$ function to represent certain auxiliary sequences that appear in the construction).

If you do need infinite sets, you can represent a great many interesting sets -- namely the computable ones -- by quantifying over indices for Turing machines that recognize the elements of the set. (Or, for technical convenience, quantify over encodings of programs in a more manageable programming language). The claim that the number $x$ is in the set numbered $y$ can then be expressed as an arithmetical statement.
You don't need to stop at computable sets, though -- you can pick any finite level of the arithmetical hierarchy and write an arithmetic formula that allows you to encode all sets on that or lower levels.
But you can't find a uniform arithmetical representation of the entire arithmetical hierarchy -- no matter which formula you propose, an easy diagonalization argument can produce an arithmetical set that it cannot represent.
